Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Вариант перебора по простым делителям с
To Igor Korolyov То, что надо ограничивать перебор по корню проверяемого числа, а не вычислять корень из порядкового номера последнего простого числа, это понятно. Но эти величины на самом деле растут практически одинаково (доказательства привести не могу, т.к. просто "нутром чую" ). Конечно, строгой линейности там нет, но с некоторым допуском это работает - при округлении в бОльшую сторону простые числа находятся правильно (во всяком случае, до 50000-го простого числа, дальше не проверял). Т.е. и ограничение по aDigits[i] < Sqrt(m.iDigit), и ограничение по i < Ceiling(Sqrt(m.iCount)), выдают один результат, Попробовал также реализовать вероятностный метод проверки простоты числа (Миллера-Рабина), но при малом количестве итераций он ошибается, а с увеличением числа итераций время выполнения растет очень сильно. [i]Исправлено 1 раз(а). Последнее : ry, 16.04.10 16:47 |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Чисто теоретически. Можно попробовать найти искомое число,воспользовавшись решетом Эратосфена. По моим прикидкам выигрыш должен быть, т.к. данный алгос позволяет обойтись практически без деления, одними умножениями.
Алгос для решета Эратосфена подразумевает хотя бы грубую оценку верхней границы искомого числа. Для этого можно воспользоваться формулой: количество простых чисел, не превосходящих n стремится к n/ln n при n, стремящемся к бесконечности. Тут возникает проблема - уравнения типа x/ln x = a не решаются аналитически, надо юзать приближенные методы. Не сожрет ли приближенное вычисление корней этого уравнения весь выигрыш от алгоса, если он конечно вообще есть (выигрыш то бишь). |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
-
Исправлено 1 раз(а). Последнее : medstrax, 16.04.10 16:33 |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
sphinx Сообщений: 31166 Откуда: Каменск-Уральски Дата регистрации: 22.11.2006 |
Цитата: Во, точно! А я никак не мог вспомнить как такой алгоритм называется. ------------------ "Veni, vidi, vici!"(с) |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Решето Эратосфена работает на заранее определенной области натуральных чисел и для задачи нахождения N-го простого числа не совсем подходит, т.к. заранее неизвестно количество простых числе в области.
|
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Советую внимательней перечитать мой пост
|
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Да, не внимателен... Все о том же |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Да, некрасиво редименшн на кажом шаге делать, но что ещё более интересно, на производительности для данного случая это практически не сказывается - по крайней мере в VFP9 SP2... 2 leonid Я предполагаю какой ты использовал способ (очевидно это "модерновое" развитие моего "древнего" и простейшего v1), мне просто лениво было его кодировать Подождём что другие придумают. P.S. Информации в сети более чем достаточно P.P.S. Совершенно естественно, что на какой-нить 10-летней давности машинке с 128Мб памяти некоторые варианты запросто могут оказаться проигрышными по причине сваливания в своп - всё-же фокс не может так-же экономно память использовать как Си - там, скажем, массив байт имеет размер разный числу элементов - в фоксе же масив его "элементов произвольных типов" будет заметно больше... Как я понимаю, каждый элемент массива занимает как минимум 16 байт (если это строка, то конечно же может быть и намного больше). Впрочем, в указанных пределах поиска 10000-го, я как-то о-о-чень сомневаюсь что не хватит памяти - каких-то жалких 1.5-2 Мб на "самый большой" массив ------------------ WBR, Igor |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Чисто практически, это и есть мой v1 Во древние греки жгут то! Я думал его слегка оптимизировать убрав все чётные элементы, но боюсь что тут как раз может сказаться негативно необходимость пересчёта числа в индекс массива, плюс пропуск чётных потом... Ну теперь наверное и до варианта Леонида остался 1 шаг ------------------ WBR, Igor |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
P.S. Приближение по указанной оценке (x/ln(x)=N) делается для сравнительно небольших чисел (до 1e10) всего за 10 шагов итеративного алгоритма. Ессно что памяти под такие числа фоксу уже гарантировано не хватит... Для поиска миллионного простого числа этим способом уже потребуется порядка 280Мб памяти (именно фоксу).
------------------ WBR, Igor |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
2Igor Korolyov.
Если не лениво, попробуй сравнить исходный вариант на 100 попугаев и твой v1, переписав оба варианта на ассемблере. Разница должна быть много больше, чем в 6 раз. К тому же можно будет вычислять простые числа с многократно бОльшим порядковым номером. На асме можно заюзать битовые строки, таким образом на каждый байт можно хранить 8 чисел. Для вычисления миллионного простого число достаточно битовой строки, представляющей решето Эратосфена, которая будет занимать примерно 2,5 Мбайт |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
На асме не програмлю, на c# можно будет попробовать - тем паче что челу дал "задание" Он правда все алгоритмы с моего второго пинка уже нашёл - до этого додумался токмо до v2 (массив с уже найденными простыми и там конечно же проверять только < SQRT(проверяемого)).
------------------ WBR, Igor |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Zakharov_slava Сообщений: 2022 Откуда: Алматы Дата регистрации: 14.10.2005 |
На этот счет довольно интересно:
habrahabr.ru |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Да, действительно, на коленке собранное решето Эратосфена с оценкой размера решета по методу Ньютона дает эффект в 13-14 попугаев:
[i]Исправлено 1 раз(а). Последнее : ry, 19.04.10 11:20 |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005 |
13 попугаев - это сколько? У меня выигрыш по скорости в 65 раз.
------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить. |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Если исходный вариант, предложенный Игорем во втором посте темы, принять за 100 попугаев (у меня он отрабатывает за 1,75 сек), то "решето" вычисляется за 0,23 сек, т.е. примерно 13 попугаев или в 7,6 раза быстрее.
|
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Форум урезал в исходнике первый индекс по i т.к. это код для курсива Нать было другие буковки для переменной выбрать, или хотя-бы круглые скобки вместо квадратных
Кроме того сам индекс искомого стоило параметром сделать, а не хардкодингом (кстати не понимаю отчего "задающим" числом ты поставил не 10тыс. а 100тыс. - оно не влияет на результат, просто странно это). Да, у меня совмещённый цикл отсеивания и поиска (а он, естственно, идёт до конца, а не до "половины", как твой), да и я забыл как-то что отсеивать можно сразу с квадрата очередного простого, потому мой вариант был медленнее... Однако мой способ оценки размера всё-же чуть быстрее, хотя и требует на 1-2 шага больше (его я приведу, остальную часть не имеет смысла). Копеечная экономия, но всё-же
реализация Аткина один-в-один взятая из википедии - ну с небольшой правкой синтаксиса, и заменой (хотя это и не очень существенно по скорости, зато очень хорошо влияет на размер отъедаемой памяти) bool[] на BitArray - даёт 1.5 фоксовых попугая (при происке 100000-го числа и вовсе 0.25 попугая. А милионное на фоксе - я задолбался ждать эталона, там даже самый быстрый эратосфен занимает порядка 21 секунды, тогда как на C# находит за чуть более 1 секунды)... 2 Влад В начале темы я привёл тупой алгоритм перебора, который предложил как эталон измерения производительности (а то компы то разные, на чистое время нельзя полагаться, а так - сравнивать есть с чем)... И кстати было бы очень неплохо понять по сравнению с чем у тебя выигрыш в 65 раз Т.к. это получается 1.5 попугая, что ОЧЕНЬ быстро (именно для поиска 10000-го, т.к. для других индексов пропорции будут совсем другие). Может всё-же в 6.5 раза - тогда это 15 попугаев что неплохо, но чуть ниже текущего "рекорда". ------------------ WBR, Igor |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Точно, а я и не обратил внимания, в коде должно быть IF !aDigits(i) Исходное число по методу великого научного тыка взял в 10 раз бОльшим Хотя оказалось достаточно близко к искомой точке. Вообще быстрый алгоритм оценки размера "решета" не искал, взял наугад метод Ньютона. Хотелось просто убедиться, что "решето" работает быстро даже с учетом поиска его размера. Убедился. Молодцы греки, особенно древние! |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Ребята, для n>50 для оценки размера решета вполне годится формула 1.2*n*log(n). А мой последний алгоритм вот
Он вроде как меньше восьми попугаев дает. |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005 |
А, ну значит вариант с решетом по сравнению с исходным у меня дает 3 при первом запуске и 0.8 при втором. А вариант Леонида - 7-8.
------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить. |
© 2000-2024 Fox Club  |