У вас там на каждый чих аллокация, что весьма плохо для производительности. Особенно в fft. Не надо выделять каждый раз массивы под четные/нечетные элементы. Можно передавать индекс первого элемента и шаг, например. А можно вообще на месте делать преобразование, без выделения двух массивов для входа и выхода, да еще и весь доступ к памяти будет последовательный. Этот алгоритм даже на вики описан.
Умножение/деление на короткое должно быть отдельной функцией, особенно *=. У вас там вообще даже += все число переаллоцирует, хотя это совсем не обязательно.
Gcd гораздо быстрее работает не через длинное деление, а с помощью деления на 2 и вычитания - тоже на википедии есть описание алгоритма. При чем и деление и вычитание можно делать на месте, вообще без аллокаций.
Базу стоит брать не 256, а 2^32 хотя бы. Все будет почти в 4 раза быстрее и переполнений в long long вызывать не должно, если аккуратно писать.
Как упраждение - неплохо. Но, вообще, на практике гораздо лучше использовать GMP. Оно сильно лучше вылизано. Там и оптимизации под конкретную архитектуру, и SIMD, и лучшие алгоритмы. Можно быстренько сделать c++ обертку с перегруженными арифметическими операторами, или взять любую из кучи готовых.
По поводу аллокаций - нормальные списки делаются поверх массива (вместо указателей используются индексы в массиве). Тогда все элементы списка, хоть и идут не по-порядку, но лежат кучно. Независимо от того, как и что вы там аллоцируете параллельно. Если вы еще и часто по списку проходитесь, то можно его периодически "сортировать" - во время прохода перепешите его в новый массив по порядку и все следующие проходы будут удобны для кэша и сильно быстрее. Эти оптимизации делают список гораздо выгоднее и лучше массива для меньших n и с большим соотношением поиска/вставки.
O(1) — это только момент перецепления указателей. До нужного места ещё надо дойти:
Как обычно, грубейшая ошибка в сравнении. Вы сравниваете O(n) в массиве и O(n) в списке и удивляетесь, что список медленный. Поиск в массиве сильно быстрее поиска в списке. Поэтому поиск+вставка в массиве часто выигрывают поиску+вставке в списке.
Бесполезно применять список вот так. Он выигрывает, когда вы уже знаете место, куда вставляете. Это значит, что вставка тут не отдельная абстрактная операция, а часть алгоритма.
Один такой пример - структура данных skip list. Попробуйте реализовать ее поверх массива, она для весьма маленьких n станет медленнее списоков. Даже при учете хорошего для кэшей обращения к памяти.
Другой пример: обратная операция - не вставка, а удаление из середины списка. Тут ассимптотика у списка тоже O(1) против O(n) в массиве. Примером тут будет LRU кэш.
Да недружественность к памяти дает весьма большую константу в этом O(1) и для выигрыша перед массивами нужно n заметно больше, чем люди себе представляют. Но если у вас миллион объектов, то список будет выгоднее.
n сложений и дают этот самый медленный O(n^2). Ведь для сложения чисел из n цифр надо O(n) операций. Ваши кеширования особо не помогают в этом наивном умножении столбиком.
Там фактически O(n log n log log n). Ибо при сильно больших n числа не помещаются в машинное слово и там уже длинная арифметика внутри длинной арифметики вылезает.
Есть относительно простой и быстрый алгоритм за O(n log n log log n) (но это не точно). И работает он быстрее карацубы даже на совсем небольших числах. Так что это не галактический алгоритм.
Работает это через быстрое преобразование Фурье. Есть варианты и на целочисленном аналоге. Пребразуйте каждое число по отдельности, перемножте значения покомпонентно, преобразуйте назад, сделайте переносы.
И идея простая: представим каждое число в виде полинома - цифры будут коэффициентами.
Вот было у нас , заменим 10 на x, получим
Потом можно перемножить 2 полинома и подставить x=10. Подстановка очень проста - просто берем коэффициенты и записываем их в виде цифр. Только некоторые могут быть больше 10, и надо сделать переносы с меньших разрядов.
А произведение полиномов это известная задача, решающаяся FFT. Потому что прямое преобразование - это вычисление значений полинома в точках-корнях-из-единицы. Обратное преобразование по значениям в точках восстанавливает полином. Так что произведение полиномов просто делается в пространстве спектра - ведь значения в точках тупо перемножаются покомпонентно.
На практике, пока количество цифр поменьше чем 2^64/81 можно игнорировать log log n в оценке сложности, потому что числа в вычислениях помещаются в процессорное слово.
Все-равно прямой метод оказывается проще. Если в вашем тоже надо докывать минимум по множеству пар, то почему-бы не взять минимум не по уменьшению длины, а по самой длине. А потом вместо процесса и рассуждений о его сходимости гораздо проще сразу взять минимум и от противного сказать, что там нет пересечений.
А как доказать, что оно уменьшается на какую-то ограниченную снизу длину? Ясно, что на положительную, но надо доказать, что процесс остановится. Абстрактно рассуждая, может быть ситуация бесконечного уменьшения длины на все меньшие числа. Гораздо проще просто сказать, что множество возможных суммарных длинн конечно, ведь конечно количество всевозможных паросочетаний (n!). А значит процесс уменьшения всегда сойдется куда-то. И там не будет пересечений, потому что пересечение позволило бы уменьшить длину еще дальше.
Исходное решение с поиском минимальной длины сразу мне кажется короче и концептуально проще. Возьмем вот эту конфигурацию. Там нет пересечений. Ведь если бы они были, то можно было бы расрезать крест и получить меньшую суммарную длину. Противоречие.
Не очень активно прислушивайтесь к этому комментатору, он весьма своеобразный. Писать свои аллокаторы - это терминальная стадия синдрома "это плохо, потому что сделано не тут". В вашей демке вообще аллокаций во время работы не должно происходить. Перед симуляцией выделили массивы и все. Выбором алгоритмов и структур данных вы гораздо больше пользы получите.
За ее доказательство дают миллион долларов. Причем, возможно несколько организаций сразу. Вы там так преисполнились, что вам лень ее решить ради 1-5 миллионов баксов и всемирного престижа? Или лошары тут, все-таки не все математики мира, а кое-кто другой?
Да не, в этой задаче все просто. Если уж тут все взаимодействия происходят парочками, то можно и все импульсы считать независимо. И потом их все применить к скоростям. Надо только их аккуратно аггрегировать. Тут достаточно atomic<double> v_x; v_x += imp_x; использовать.
Спасибо, очень классное объяснение. Вот только в глаза бросилось - вы несколько раз в произведениях пишите множители через запятую. Это что за нотация такая?
Тогда вам стоит отредактировать статью. Пока выглядит, как будто вы код в 1000 раз соптимизировали, а по факту всего в 2-3 раза (ускорив в 1000 только 2 из 3 правил).
Так нельзя же тупо смотреть только на соседние ячейки. Гравитация так не работает. Так можно делать только для локальных взаимодейсвий вроде столкновений.
Есть честные O(n log n) методы для просчета гравитации. Например Barnes-Hut. Там, конечно, тоже есть неточности, но не настолько ужасные. Там тоже использутеся сетка, но все далекие объекты в далеких ячейках групперуются и заменяются точечной массой и все-таки учитываются хотя бы аггрегированно.
Если же к этой идее приложить еще и жесткую математику, то получается O(n) метод для просчета гравитации глобально (fast multipole method). В отличии от вашего хака, там есть далекое взаимодействие и точность можно приближать сколь угодно близко к идеальной.
То, что по идее ваше, накопленное, должно лежать на счету и работать в фондах, расти потихоньку - тупо выплачено другим пенсионерам. Этих денег больше нет.
Да, это предыдущие настройки, но они отвратительные, как раз потому, что без постоянного роста населения это не работает.
Вспоминается история с чумой в европе. Тогда выкосило двузначное число в процентах от населения. Случилась ужасная трагедия: работников стало не хватать, и им пришлось платить больше, появился средний класс.
Проблема есть только в пенсионных системах, где текущие работники платят пенисию. Кстати, такие системы не везде. Даже в России вводили накопительную часть, пока не прихватизировали ее всю на нужды государства. Во многих государствах пенсионные накопления индивидуальны в основном.
Если популисты геронтофилы все не испортят, эта проблема тоже не велика. В россии пенсии сейчас уже нищенские, ну будут еще меньше, разницы принципиальной нет. Западные пенсионеры не смогут путешествовать, будут вынуждены продать свое жилье в центре города и переехать на окраину в дешевое, но с голоду не умрут.
Вымрут целые отрасли бессмысленной работы (те самые bullshit jobs).
Жилье станет снова доступным, зарплаты вырастут, места в детских садиках перестанут быть адским дефицитом. И люди станут охотнее заводить семьи и детей. Проблема рассосется сама через поколение, если ей не мешать.
Но ей мешают. Пока завозят мигрантов, например, что наоборот только снижает зарплаты и удорожает жилье. Всеми силами сохранят статус кво, который должен поменятся, но от этого будет только режче и больнее переход.
У вас "быстрота" за а счет двух простых оптимизаций:
1) Cокращать делители по мере их нахождения.
Идея хорошая, но очевидная и давно всем известная.
Вот, посмотрите например на код тут, в функцию findDivisors.
Это очень простая идея, она уже была изобретена тысячи раз и даже какого-то названия не имеет. Помнится, я ее применял еще лет 20 назад будучи школьником на какой-то олимпиаде.
2) Перебирать отдельно 2, 3 и потом все числа заведомо не делящиеся на 2 и 3, потому что только такие могут быть простыми. Это тоже очевидная и давно известная оптимизация, называющаяся "методом колеса" или "колесной оптимизацией". Можно взять любой набор простых чисел, перемножить их и потом надо рассматривать в качестве кандидатов на простые числа только те, которые заведомо взаимно просты с этим произведением.
Чаще всего эту идею применяют в решете эратосфена.
В наивном разложении на делители ее используют редко, потому что там алгоритм итак относительно быстрый в своей области применения - до корня. Несколько процентов вы этим колесом еще выдавите, но на маленьких числах (как у вас, влезающих в обычные типы) это смысла это несет мало, а код усложняет заметно. А если уж раскладывать длинные (десятки десятичных цифр) числа, то надо расчехлять тяжелую математику и применять что-то поумнее наивного перебора. Например, какие-нибудь эллиптические кривые.
В целом, алгоритм чуть-чуть быстрее стандартной реализации, но для "огромных" составных чисел не применим и ничего нового не привнес.
Edit: Более того, даже та статья на хабре на которую вы в конце ссылаетесь, сначала находит простые делители применяя первую оптимизацию, а потом строит все делители. Это функция prchoosediv там.
Какие проблемы? Когда ввели комплексные числа, уже получается sin(π/2+ln(67 + 8√70)i) = 67
Есть пара тривиальных вопросов в том, что возможных значений у arcsin много, ну так и на вещественных числах там такая же проблема. Только надо ввести дополнительные правила на комплексную часть ответа. Ну и область определения arcsin похоже будет не вся комплексная плоскость, но все вещественные положительные числа там точно есть.
Раз уж вы ссылку запостили, оставлю отзыв.
У вас там на каждый чих аллокация, что весьма плохо для производительности. Особенно в fft. Не надо выделять каждый раз массивы под четные/нечетные элементы. Можно передавать индекс первого элемента и шаг, например. А можно вообще на месте делать преобразование, без выделения двух массивов для входа и выхода, да еще и весь доступ к памяти будет последовательный. Этот алгоритм даже на вики описан.
Умножение/деление на короткое должно быть отдельной функцией, особенно *=. У вас там вообще даже += все число переаллоцирует, хотя это совсем не обязательно.
Gcd гораздо быстрее работает не через длинное деление, а с помощью деления на 2 и вычитания - тоже на википедии есть описание алгоритма. При чем и деление и вычитание можно делать на месте, вообще без аллокаций.
Базу стоит брать не 256, а 2^32 хотя бы. Все будет почти в 4 раза быстрее и переполнений в long long вызывать не должно, если аккуратно писать.
Как упраждение - неплохо. Но, вообще, на практике гораздо лучше использовать GMP. Оно сильно лучше вылизано. Там и оптимизации под конкретную архитектуру, и SIMD, и лучшие алгоритмы. Можно быстренько сделать c++ обертку с перегруженными арифметическими операторами, или взять любую из кучи готовых.
По поводу аллокаций - нормальные списки делаются поверх массива (вместо указателей используются индексы в массиве). Тогда все элементы списка, хоть и идут не по-порядку, но лежат кучно. Независимо от того, как и что вы там аллоцируете параллельно. Если вы еще и часто по списку проходитесь, то можно его периодически "сортировать" - во время прохода перепешите его в новый массив по порядку и все следующие проходы будут удобны для кэша и сильно быстрее. Эти оптимизации делают список гораздо выгоднее и лучше массива для меньших n и с большим соотношением поиска/вставки.
Как обычно, грубейшая ошибка в сравнении. Вы сравниваете O(n) в массиве и O(n) в списке и удивляетесь, что список медленный. Поиск в массиве сильно быстрее поиска в списке. Поэтому поиск+вставка в массиве часто выигрывают поиску+вставке в списке.
Бесполезно применять список вот так. Он выигрывает, когда вы уже знаете место, куда вставляете. Это значит, что вставка тут не отдельная абстрактная операция, а часть алгоритма.
Один такой пример - структура данных skip list. Попробуйте реализовать ее поверх массива, она для весьма маленьких n станет медленнее списоков. Даже при учете хорошего для кэшей обращения к памяти.
Другой пример: обратная операция - не вставка, а удаление из середины списка. Тут ассимптотика у списка тоже O(1) против O(n) в массиве. Примером тут будет LRU кэш.
Да недружественность к памяти дает весьма большую константу в этом O(1) и для выигрыша перед массивами нужно n заметно больше, чем люди себе представляют. Но если у вас миллион объектов, то список будет выгоднее.
n сложений и дают этот самый медленный O(n^2). Ведь для сложения чисел из n цифр надо O(n) операций. Ваши кеширования особо не помогают в этом наивном умножении столбиком.
Там фактически O(n log n log log n). Ибо при сильно больших n числа не помещаются в машинное слово и там уже длинная арифметика внутри длинной арифметики вылезает.
Есть относительно простой и быстрый алгоритм за O(n log n log log n) (но это не точно). И работает он быстрее карацубы даже на совсем небольших числах. Так что это не галактический алгоритм.
Работает это через быстрое преобразование Фурье. Есть варианты и на целочисленном аналоге. Пребразуйте каждое число по отдельности, перемножте значения покомпонентно, преобразуйте назад, сделайте переносы.
И идея простая: представим каждое число в виде полинома - цифры будут коэффициентами.
Вот было у нас
, заменим 10 на x, получим
Потом можно перемножить 2 полинома и подставить x=10. Подстановка очень проста - просто берем коэффициенты и записываем их в виде цифр. Только некоторые могут быть больше 10, и надо сделать переносы с меньших разрядов.
А произведение полиномов это известная задача, решающаяся FFT. Потому что прямое преобразование - это вычисление значений полинома в точках-корнях-из-единицы. Обратное преобразование по значениям в точках восстанавливает полином. Так что произведение полиномов просто делается в пространстве спектра - ведь значения в точках тупо перемножаются покомпонентно.
На практике, пока количество цифр поменьше чем 2^64/81 можно игнорировать log log n в оценке сложности, потому что числа в вычислениях помещаются в процессорное слово.
Все-равно прямой метод оказывается проще. Если в вашем тоже надо докывать минимум по множеству пар, то почему-бы не взять минимум не по уменьшению длины, а по самой длине. А потом вместо процесса и рассуждений о его сходимости гораздо проще сразу взять минимум и от противного сказать, что там нет пересечений.
А как доказать, что оно уменьшается на какую-то ограниченную снизу длину? Ясно, что на положительную, но надо доказать, что процесс остановится. Абстрактно рассуждая, может быть ситуация бесконечного уменьшения длины на все меньшие числа. Гораздо проще просто сказать, что множество возможных суммарных длинн конечно, ведь конечно количество всевозможных паросочетаний (n!). А значит процесс уменьшения всегда сойдется куда-то. И там не будет пересечений, потому что пересечение позволило бы уменьшить длину еще дальше.
Исходное решение с поиском минимальной длины сразу мне кажется короче и концептуально проще. Возьмем вот эту конфигурацию. Там нет пересечений. Ведь если бы они были, то можно было бы расрезать крест и получить меньшую суммарную длину. Противоречие.
Не очень активно прислушивайтесь к этому комментатору, он весьма своеобразный. Писать свои аллокаторы - это терминальная стадия синдрома "это плохо, потому что сделано не тут". В вашей демке вообще аллокаций во время работы не должно происходить. Перед симуляцией выделили массивы и все. Выбором алгоритмов и структур данных вы гораздо больше пользы получите.
За ее доказательство дают миллион долларов. Причем, возможно несколько организаций сразу. Вы там так преисполнились, что вам лень ее решить ради 1-5 миллионов баксов и всемирного престижа? Или лошары тут, все-таки не все математики мира, а кое-кто другой?
Да не, в этой задаче все просто. Если уж тут все взаимодействия происходят парочками, то можно и все импульсы считать независимо. И потом их все применить к скоростям. Надо только их аккуратно аггрегировать. Тут достаточно
atomic<double> v_x; v_x += imp_x;использовать.Спасибо, очень классное объяснение. Вот только в глаза бросилось - вы несколько раз в произведениях пишите множители через запятую. Это что за нотация такая?
Тогда вам стоит отредактировать статью. Пока выглядит, как будто вы код в 1000 раз соптимизировали, а по факту всего в 2-3 раза (ускорив в 1000 только 2 из 3 правил).
Так нельзя же тупо смотреть только на соседние ячейки. Гравитация так не работает. Так можно делать только для локальных взаимодейсвий вроде столкновений.
Есть честные O(n log n) методы для просчета гравитации. Например Barnes-Hut. Там, конечно, тоже есть неточности, но не настолько ужасные. Там тоже использутеся сетка, но все далекие объекты в далеких ячейках групперуются и заменяются точечной массой и все-таки учитываются хотя бы аггрегированно.
Если же к этой идее приложить еще и жесткую математику, то получается O(n) метод для просчета гравитации глобально (fast multipole method). В отличии от вашего хака, там есть далекое взаимодействие и точность можно приближать сколь угодно близко к идеальной.
https://www.kommersant.ru/doc/5706513
То, что по идее ваше, накопленное, должно лежать на счету и работать в фондах, расти потихоньку - тупо выплачено другим пенсионерам. Этих денег больше нет.
Да, это предыдущие настройки, но они отвратительные, как раз потому, что без постоянного роста населения это не работает.
Вспоминается история с чумой в европе. Тогда выкосило двузначное число в процентах от населения. Случилась ужасная трагедия: работников стало не хватать, и им пришлось платить больше, появился средний класс.
Проблема есть только в пенсионных системах, где текущие работники платят пенисию. Кстати, такие системы не везде. Даже в России вводили накопительную часть, пока не прихватизировали ее всю на нужды государства. Во многих государствах пенсионные накопления индивидуальны в основном.
Если популисты геронтофилы все не испортят, эта проблема тоже не велика. В россии пенсии сейчас уже нищенские, ну будут еще меньше, разницы принципиальной нет. Западные пенсионеры не смогут путешествовать, будут вынуждены продать свое жилье в центре города и переехать на окраину в дешевое, но с голоду не умрут.
Вымрут целые отрасли бессмысленной работы (те самые bullshit jobs).
Жилье станет снова доступным, зарплаты вырастут, места в детских садиках перестанут быть адским дефицитом. И люди станут охотнее заводить семьи и детей. Проблема рассосется сама через поколение, если ей не мешать.
Но ей мешают. Пока завозят мигрантов, например, что наоборот только снижает зарплаты и удорожает жилье. Всеми силами сохранят статус кво, который должен поменятся, но от этого будет только режче и больнее переход.
Хороший термин.
У вас "быстрота" за а счет двух простых оптимизаций:
1) Cокращать делители по мере их нахождения.
Идея хорошая, но очевидная и давно всем известная.
Вот, посмотрите например на код тут, в функцию findDivisors.
Это очень простая идея, она уже была изобретена тысячи раз и даже какого-то названия не имеет. Помнится, я ее применял еще лет 20 назад будучи школьником на какой-то олимпиаде.
2) Перебирать отдельно 2, 3 и потом все числа заведомо не делящиеся на 2 и 3, потому что только такие могут быть простыми. Это тоже очевидная и давно известная оптимизация, называющаяся "методом колеса" или "колесной оптимизацией". Можно взять любой набор простых чисел, перемножить их и потом надо рассматривать в качестве кандидатов на простые числа только те, которые заведомо взаимно просты с этим произведением.
Чаще всего эту идею применяют в решете эратосфена.
В наивном разложении на делители ее используют редко, потому что там алгоритм итак относительно быстрый в своей области применения - до корня. Несколько процентов вы этим колесом еще выдавите, но на маленьких числах (как у вас, влезающих в обычные типы) это смысла это несет мало, а код усложняет заметно. А если уж раскладывать длинные (десятки десятичных цифр) числа, то надо расчехлять тяжелую математику и применять что-то поумнее наивного перебора. Например, какие-нибудь эллиптические кривые.
В целом, алгоритм чуть-чуть быстрее стандартной реализации, но для "огромных" составных чисел не применим и ничего нового не привнес.
Edit: Более того, даже та статья на хабре на которую вы в конце ссылаетесь, сначала находит простые делители применяя первую оптимизацию, а потом строит все делители. Это функция
prchoosedivтам.Это вы про тот текст от DeepSeak выложенный юзером x2v0? Перелогиниться забыли?
Какие проблемы? Когда ввели комплексные числа, уже получается sin(π/2+ln(67 + 8√70)i) = 67
Есть пара тривиальных вопросов в том, что возможных значений у arcsin много, ну так и на вещественных числах там такая же проблема. Только надо ввести дополнительные правила на комплексную часть ответа. Ну и область определения arcsin похоже будет не вся комплексная плоскость, но все вещественные положительные числа там точно есть.