Есть сайт с подробным объяснением работы чисел с плавающей запятой (как на русском, так и на английском). Хорошие пример, объясняются тонкости и неожиданные для математика свойства. Вот здесь. Сайт сырой, а вот именно этот материал в основе изложен полностью.
Затем, что мне он не нужен. «Учёным», на которых я работал, как выяснилось, тоже, а хранить хлам не люблю. Если вернусь к этим задачам, то в любом случае буду все переписывать начисто, уже с иных позиций и имея больше опыта. Вообще, в моей концепции научной работы программы переписываются с нуля десятки раз, я против классической схемы, когда код пишется один раз и потом только исправляется и дорабатывается, эта позиция не работает в сфере сложных расчётов. Шаг за шагом, удаляя старую программу и создавая новую, мысль совершенствуется. Старая программа даёт некий набор тестовых данных для новой. Новая даёт набор ещё больше — и так далее десятки раз. На третьем четвёртом шаге обычно получается новые научные результаты, но для того, чтобы найти свой предел, итераций требуется гораздо больше. Зачем удалять старую программу? Чтобы не было соблазна забрать оттуда кусок (скопировать или просто подсмотреть, когда забыл), перетащив в новую программу какие-то недостатки.
Это невозможно по целому ряду причин. Одна из них (не самая важная) — весь свой научный код я удалил, когда ушёл из академической науки, осознав за несколько лет трудов, что там ловить нечего. Но есть и другие причины, по которым я всё равно бы его не показал. Самая важная причина — в научных расчётах, особенно новых, не решённых ранее задач, важно, чтобы кто-либо повторил результат независимо. Ответы должны сойтись. Когда даёшь свой код кому-то, гарантия независимости обнуляется, а это недопустимо. Возможно, я ещё вернусь к этим задачам, но без какой-либо связи с государственной наукой.
Знаете, самые разные из класса так называемых «труднорешаемых» задач. Которые в принципе не имеют эффективного алгоритма решения. Классический пример: число незамкнутых маршрутов шахматного коня на доске 8x8. На данный момент считается нерешённой проблемой комбинаторики, однако в моей собственной классификации она находится где-то посередине по сложности. В принципе, решается она не очень сложно, но ни один функциональный язык её не потянет. Можно даже не пытаться. Решать её нужно на кластерах только на Си или Фортране. Конечно, я не говорю о том, что сам программист при этом должен быть очень сильным.
Не буду объяснять то, зачем решать такие задачи, но если кратко, то их решение открывает в науке новые методы, с помощью которых решаются аналогичные задачи, скажем, из статистической физики (например, расчёт термодинамических свойств макромолекул, этим я занимался в своей диссертации).
Я думаю, что нет смысла доказывать мою точку зрения, просто выскажу общую мысль всех тех учёных, которые трудились над подобными задачами: функциональщина там не пройдёт ни под каким видом. А нравится это кому-то или нет — нам без разницы: ) Не пройдёт и всё. Никто пока не смог доказать обратного на реальных практических примерах.
Есть ещё одна причина непопулярности функциональных языков, по крайней мере, в сфере сложных научных расчётов. На функциональном языке нельзя написать ни одной эффективной (и одновременно полезной) программы, которая выжимала бы из процессора максимум. Это можно легко сделать на Си, на Паскале (и Delphi) в связке с ассемблером… на Java и C#, к сожалению, нельзя, ещё можно на Фортране. Да, можете со мной спорить, если есть опыт и аргументы, но факт таков: ни одна из сложных задач, по крайней мере, из моего списка задач, не будет решена на функциональном языке. Они все будут решены на простых императивных языках с помощью кластеров и видеокарт.
Да, я знаю, что тут не нужно путать язык и компилятор, ведь эффективность кода зависит от компилятора. Однако я пока не видел компиляторов функциональных языков, которые давали бы не тормознутый код.
Есть хорошая статья Kai Hormann, Alexander Agathos "The Point in Polygon Problem for Arbitrary Polygons", в которой показано, что по сути метод трассировки луча и метод, основанный на индексе точки — это практически одно и то же. Там же в статье описано то, как коротко и ясно разбираются абсолютно все крайние случаи для совершенно любых вариантов многоугольников (не помню только, что там насчёт вырожденных).
Вынужден Вас поправить, это не всегда так. Иногда добавление лишних команд не только не приводит к замедлению, но даже может сделать программу быстрее. Есть минимум две причины, почему так может произойти: добавление лишней команды меняет состояние кэша, за счёт чего другие команды (дальше по коду), исполняются быстрее; «разбавление» кода командами может улучшить работу конвейера и сделать всё выполнение более быстрым. К сожалению, примеров я Вам не дам сходу, но лично наблюдал оба варианта. Не буду спорить, что второй случай специфический, но первый мне попадается часто. А что касается числа тактов, то это число не имеет никакого смысла на практике, так как есть конвейер (имхо). Число тактов не отражает скорость выполнения достаточно точно.
Ну, смотря как «прикинуть». Если совсем не точно, то достаточно просто запустить и время от времени смотреть на часы. Если прикидка должна быть довольно точной, а программа работает долго, то можно параллельно работать на компьютере с другими вычислениями, которые могут занимать массу времени. В этом случае процессорное время необходимо, иначе получите, что программа работает час, а астрономическое время будет 2-3 часа. Так что при параллельной работе всё равно это важно.
Есть несколько причин. Самая важная: при длительном тестировании у вас нет никаких гарантий, что в середине пути ОС вдруг не захочет что-нибудь сделать, что повлияет на результат (гарантировать на 100%, что этого не произойдёт, нельзя). При этом программа может работать весьма долго и перетестировать её (минимум трижды) довольно трудно. Далее, например, на олимпиаде по программированию один компьютер может запускать сразу несколько программ единовременно, нужно точно учитывать, сколько отработала каждая, с учётом разделения времени с конкурентами. Даже при отключённых лишних программах разница на несложных тестах может оказаться равной секунде или двум (в виндоусе). Так что как ни крути, процессорное время чище.
Не-не-не, Евгений. Вы уж простите, если я как-то не так слова подобрал, но я имел в виду, что У МЕНЯ ЛИЧНО runexe уже хорошо работает, и поэтому мне не сложнее делать так, как уже делается. Кому-то другому, наверное, удобнее взять готовое. И потом я пока ещё не убедился, что предложенный Вами метод действительно будет работать — это нужно проверять. В данном случае практика — критерий истинности.
А в целом по статье всё нормально, я Вам очень благодарен за проделанную работу (перевод и популяризация). Одно замечание: название неверное. «Как измерять процессорное время» — это намёк на методологию самого процесса измерения, Вы же даёте готовое решение, написанное каким-то мужиком. То есть предлагаете инструмент, а не методологию. Но это имхо.
Мне кажется, Вы напрасно уводите разговор в сторону. То, как я работаю дома, это вряд ли кому-то интересно, но раз я сказал, что у меня нет проблем с автоматизацией, значит их нет. Да, там есть скрипты, да, там есть разные параметры перекомпиляции, это всё, что я могу сообщить.
Чужой код, конечно, нужно читать, когда это возможно. Например, в Вашем случае это невозможно. Потому что этот код вызывает функции системы. Если ту часть кода линукса, которая отвечает за таймер, писал какой-нибудь школьник в рамках своей курсовой работы, то эту функцию тоже нужно детально изучать — это тянет за собой ещё кучу ненужной работы. Так ведь? И потом только мы получим гарантию, функция из Вашей статьи работает правильно. Так или нет?
Вопрос риторический, конечно. Что касается вопроса корректности тестирования с помощью runexe, то здесь всё просто — меня устраивает время, которое она выдаёт при тестировании. Есть ряд традиционных методов, изучаемых на курсах истории и методологии науки, по которым можно считать некое знание достоверным или недостоверным. Все эти методы мне известны и они работают. Абсолютной уверенности в том, что runexe работает лучше или хуже системных функций нет никаких. То же самое можно сказать о системных функциях — они тоже работают «как-то» и нам остаётся верить, что работают правильно. Это философский вопрос… если тянуть его дальше, то возникнет другой вопрос: правильно ли мы вообще живём и какова (и откуда) степень нашей уверенности в этом?
Я уже говорил, что предложенный здесь Вами подход нужно детально изучать на практике. А я по природе своей (и тому есть объяснение) всегда НЕ доверяю ЛЮБЫМ чужим программам, пока не проверю их на практике — отсюда и мой кажущийся скептицизм. Не знаю, что Вы ещё от меня хотите :) Я уже сказал, что попытаюсь всё это проверить массово и сделать выводы. Хотя это могли бы сделать и Вы сами.
Так а Вы думаете, что у меня подход чем-то отличается от «запустил и пошёл спать»?: )
Код включает в себя вызов исключительно системных функций. При этом от криворукости создателя runexe вас никто не спасает, кроме вашей веры в него.
С этим кодом я и не спорю (пока), я выразил мнение о том, чем закачивается 99% попыток внедрить в свой код что-то другое. По поводу runexe — у меня пока не было нареканий к нему, так что это дело не веры, а проверки на сотнях тысячах запусках. А предложенные Вами код я пока не проверял. Когда проверю, тогда будет видно.
Если вы хотите сравнить две версии алгоритма, то в лоб еще скриптом не автоматизируешь. Или держать два проекта, или собирать вручную, или использовать аргументы при запуске.
Эта проблема уже давно решена. Поэтому я и говорю, что лично мне не легче. Легче будет, возможно, сделать универсальный код для других пользователей, но это, повторюсь, нужно проверять на практике. Как я уже сказал, что если сработает, буду рад. Но почему-то я сомневаюсь пока.
Вы ответили лишь на половину моих замечаний, при этом недооцениваете мой способ работы дома и то, что лично мне удобнее. Я лишь ответил на ваш тезис "Ведь автоматизировать замеры с функцией обычно гораздо легче, чем с утилитой", ответив, что лично мне не легче. Я с подозрением отношусь к внедрению стороннего кода в свой, в 99% случаев это приводит к пустой потере времени (в силу доминирующей криворукости создателей подобного опенсорса). Это лишь моё мнение. Вопрос практической полезности подобного кода решается ТОЛЬКО через практику.
Что касается моих проблем, которые я мог бы попытаться решить этим готовым кодом — а именно, подготовка для других людей готового к запуску проекта — это нужно пробовать решать в ходе исследования. На Вашем месте я бы так и сделал: состряпал бы программу с тестированием некоторых интересных функций, и попросил бы пользователей БЕЗ КАКИХ ЛИБО ЛИШНИХ УСИЛИЙ скомпилировать из запустиь её, затем показать вывод на консоль. Если это сработает, я буду рад таком подходу… однако это не изменит моих личных привычек и избавить от необходимости измерять иногда память.
Что касается автоматизации, то со сторонними утилитами она решается, но иным способом, например, через cmd-файл.
Если за мои эксперименты проголосует больше 80% участников, я могу попробовать данный подход в тестировании. Только тогда станет ясно, стоит игра свеч или нет. Я НЕ спорю, что это может работать, я лишь ответил, почему не считаю это решение более лёгким. Ответ мой можно опровергнуть только на практике. Тут как бы спорить не имеет смысла даже.
Совершенно не легче. Во-первых, подобные утилиты обычно работают везде, где их можно скомпилировать, по идее их должны поддерживать их разработчики (runexe, в принципе, не требует поддержки сейчас — она работает). Что касается таких вот жутких функций, то встраивание их в мой код делает программу сложнее и не даёт гарантий, что она запустится у кого-то другого. Это против моих правил — давать код, который тяжело скомпилировать (одна из причин, по которой я плохо отношусь к опенсорсу — это трудности с компиляцией, возникающие по причине доступа к коду тех людей, которых это мало заботит). Во-вторых, указанная мною утилита может также правильно замерять использованную единовременно память, что тоже важно. В-третьих, включать таймер до цикла тестирования и выключать после — это ничем по сути не отличается от тестирования внешней утилитой. В-четвертых, я не знаю, какие побочные эффекты порождают вот такие отдельные функции и как они влияют на измерение. Короче, я считаю, что в любом эксперименте измерительный прибор должен быть как можно дальше от опытного образца, не только в программировании. Ну и в-пятых, дело привычки.
Поэтому когда я пишу код для других людей, то, к сожалению, приходится замеры делать через chono, в надежде, что когда-нибудь оно начнёт работать везде. Дома использую только runexe.
Отвечаю на Ваш первый вопрос. На самом деле он следует из комментария grechnik, который написан здесь. В случае последовательной версии цикл полностью сворачивается в константу, поэтому время работы пустого цикла равно нулю (ну, или эпсилон), значит я вычитаю ноль на самом деле. В случае хаотичной версии пустой цикл в константу не сворачивается (хотя сумма чисел та же), поэтому там я вычитаю не ноль. Значит получается, что после вычитания в хаотичной версии числа будут заметно меньше, чем в последовательной, где ничего не вычитается. А это значит, что нужно более аккуратно следить за ходом эксперимента. Это одна из тех мыслей, которую выразил halyavin в первом комментарии к этой статье — нужно смотреть, что с вашим кодом сделал компилятор. Мой эксперимент это тоже показывает, и это как раз очень удачно укладывается в его цели (эксперимент же пробный). Спасибо за вопрос.
Первый вопрос у меня пока в очереди на обработку, сейчас я не знаю на него ответа.
Второй вопрос: случайные числа использовать не получится, потому что я не знаю ни одного генератора случайных чисел. Псевдослучайные же числа можно генерировать по-разному и мой вариант — это как раз и есть так называемый линейный конгруэнтный генератор псевдослучайных чисел. Он даёт не очень хорошую последовательноть с точки зрения случайности, но она ганрантированно весьма хаотичная и переберёт все числа из диапазона при наличии трёх условий (ответ на третий Ваш вопрос), перечисленных по указанной ссылке. Например, если взять множитель 11, то данный генератор НЕ перебирает все числа — этот факт, о котором многие не знают, можно довольно забавно использовать чтобы запутать человека, с которым споришь: ) Он начнёт искать ошибку в другом месте и обязательно скажет глупость.
Что касается оптимизации метода получения последовательности, то у меня нет целей его оптимизировать. Но, отвечаю, да, это можно сделать массой способов, вплоть до выбора другого генератора.
Не буду объяснять то, зачем решать такие задачи, но если кратко, то их решение открывает в науке новые методы, с помощью которых решаются аналогичные задачи, скажем, из статистической физики (например, расчёт термодинамических свойств макромолекул, этим я занимался в своей диссертации).
Я думаю, что нет смысла доказывать мою точку зрения, просто выскажу общую мысль всех тех учёных, которые трудились над подобными задачами: функциональщина там не пройдёт ни под каким видом. А нравится это кому-то или нет — нам без разницы: ) Не пройдёт и всё. Никто пока не смог доказать обратного на реальных практических примерах.
Да, я знаю, что тут не нужно путать язык и компилятор, ведь эффективность кода зависит от компилятора. Однако я пока не видел компиляторов функциональных языков, которые давали бы не тормознутый код.
А в целом по статье всё нормально, я Вам очень благодарен за проделанную работу (перевод и популяризация). Одно замечание: название неверное. «Как измерять процессорное время» — это намёк на методологию самого процесса измерения, Вы же даёте готовое решение, написанное каким-то мужиком. То есть предлагаете инструмент, а не методологию. Но это имхо.
Чужой код, конечно, нужно читать, когда это возможно. Например, в Вашем случае это невозможно. Потому что этот код вызывает функции системы. Если ту часть кода линукса, которая отвечает за таймер, писал какой-нибудь школьник в рамках своей курсовой работы, то эту функцию тоже нужно детально изучать — это тянет за собой ещё кучу ненужной работы. Так ведь? И потом только мы получим гарантию, функция из Вашей статьи работает правильно. Так или нет?
Вопрос риторический, конечно. Что касается вопроса корректности тестирования с помощью runexe, то здесь всё просто — меня устраивает время, которое она выдаёт при тестировании. Есть ряд традиционных методов, изучаемых на курсах истории и методологии науки, по которым можно считать некое знание достоверным или недостоверным. Все эти методы мне известны и они работают. Абсолютной уверенности в том, что runexe работает лучше или хуже системных функций нет никаких. То же самое можно сказать о системных функциях — они тоже работают «как-то» и нам остаётся верить, что работают правильно. Это философский вопрос… если тянуть его дальше, то возникнет другой вопрос: правильно ли мы вообще живём и какова (и откуда) степень нашей уверенности в этом?
Я уже говорил, что предложенный здесь Вами подход нужно детально изучать на практике. А я по природе своей (и тому есть объяснение) всегда НЕ доверяю ЛЮБЫМ чужим программам, пока не проверю их на практике — отсюда и мой кажущийся скептицизм. Не знаю, что Вы ещё от меня хотите :) Я уже сказал, что попытаюсь всё это проверить массово и сделать выводы. Хотя это могли бы сделать и Вы сами.
С этим кодом я и не спорю (пока), я выразил мнение о том, чем закачивается 99% попыток внедрить в свой код что-то другое. По поводу runexe — у меня пока не было нареканий к нему, так что это дело не веры, а проверки на сотнях тысячах запусках. А предложенные Вами код я пока не проверял. Когда проверю, тогда будет видно.
Эта проблема уже давно решена. Поэтому я и говорю, что лично мне не легче. Легче будет, возможно, сделать универсальный код для других пользователей, но это, повторюсь, нужно проверять на практике. Как я уже сказал, что если сработает, буду рад. Но почему-то я сомневаюсь пока.
Что касается моих проблем, которые я мог бы попытаться решить этим готовым кодом — а именно, подготовка для других людей готового к запуску проекта — это нужно пробовать решать в ходе исследования. На Вашем месте я бы так и сделал: состряпал бы программу с тестированием некоторых интересных функций, и попросил бы пользователей БЕЗ КАКИХ ЛИБО ЛИШНИХ УСИЛИЙ скомпилировать из запустиь её, затем показать вывод на консоль. Если это сработает, я буду рад таком подходу… однако это не изменит моих личных привычек и избавить от необходимости измерять иногда память.
Что касается автоматизации, то со сторонними утилитами она решается, но иным способом, например, через cmd-файл.
Если за мои эксперименты проголосует больше 80% участников, я могу попробовать данный подход в тестировании. Только тогда станет ясно, стоит игра свеч или нет. Я НЕ спорю, что это может работать, я лишь ответил, почему не считаю это решение более лёгким. Ответ мой можно опровергнуть только на практике. Тут как бы спорить не имеет смысла даже.
Поэтому когда я пишу код для других людей, то, к сожалению, приходится замеры делать через chono, в надежде, что когда-нибудь оно начнёт работать везде. Дома использую только runexe.
Первый вопрос у меня пока в очереди на обработку, сейчас я не знаю на него ответа.
Второй вопрос: случайные числа использовать не получится, потому что я не знаю ни одного генератора случайных чисел. Псевдослучайные же числа можно генерировать по-разному и мой вариант — это как раз и есть так называемый линейный конгруэнтный генератор псевдослучайных чисел. Он даёт не очень хорошую последовательноть с точки зрения случайности, но она ганрантированно весьма хаотичная и переберёт все числа из диапазона при наличии трёх условий (ответ на третий Ваш вопрос), перечисленных по указанной ссылке. Например, если взять множитель 11, то данный генератор НЕ перебирает все числа — этот факт, о котором многие не знают, можно довольно забавно использовать чтобы запутать человека, с которым споришь: ) Он начнёт искать ошибку в другом месте и обязательно скажет глупость.
Что касается оптимизации метода получения последовательности, то у меня нет целей его оптимизировать. Но, отвечаю, да, это можно сделать массой способов, вплоть до выбора другого генератора.