Я не думаю, что этот вопрос является полным, рассматривая только чисто функциональные алгоритмы, которые скрывают состояние либо в карте, либо в приоритетной очереди в случае нескольких ответов или в виде сложенного дерева слияния в случае одного из моих других ответов вчто любой из них весьма ограничен в отношении удобства использования для больших диапазонов простых чисел из-за их приблизительной производительности O (n ^ 1.2) («^» означает возведение в степень, где n - верхнее число в последовательности), а также ихвычислительные затраты на операцию выбраковки.Это означает, что даже для диапазона 32-битных чисел эти алгоритмы будут занимать что-то в диапазоне, по крайней мере, многих минут, чтобы генерировать простые числа до четырех миллиардов плюс, что не очень удобно.
* 1002Было несколько ответов, представляющих решения, использующие различные степени изменчивости, но они либо не в полной мере использовали свою изменчивость и были неэффективными, либо были просто очень упрощенными переводами императивного кода и уродливыми функционально.Мне кажется, что изменяемый массив F # - это просто еще одна форма сокрытия изменяемого состояния внутри структуры данных, и что может быть разработан эффективный алгоритм, в котором
не используется никакая другая изменчивость , кромемассив изменяемых буферов, используемый для эффективной выборки составных чисел по сегментам выгружаемого буфера, а остальная часть кода написана в чистом функциональном стиле.
Следующий код был разработан после просмотра кода Джоном Харропом , и улучшает эти идеи следующим образом:
Код Джона терпит неудачу с точки зрения высокого использования памяти (сохраняет все сгенерированные простые числа вместо простых простых чисел в квадратный корень самого высокого кандидата)простое и непрерывно восстанавливает буферные массивы постоянно увеличивающегося огромного размера (равного размеру последнего найденного простого) независимо от размеров кэша ЦП.
Кроме того, его код в представленном виде делаетне включая генерирующую последовательность.
Далее, код как presented не имеет оптимизаций, чтобы по крайней мере иметь дело только с нечетными числами, не говоря уже о том, чтобы не учитывать использование факторизации колес.
Если код Джона использовался для генерации диапазона простых чисел дляДиапазон 32-разрядных чисел, равный четырем миллиардам, потребует памяти в гигабайтах для сохраненных простых чисел в структуре списка и еще нескольких гигабайт для ситового буфера, хотя нет реальной причины, по которой последний не может быть фиксированнымМеньший размер.Как только ситовый буфер превысит размер кеша ЦП, производительность будет быстро ухудшаться при «перегрузке кеша», с увеличением потери производительности, когда сначала превышаются размеры L1, затем L2 и, наконец, L3 (если есть).
Вот почему код Джона будет вычислять простые числа примерно до 25 миллионов или около того даже на моей 64-битной машине с восемью гигабайтами памяти до генерации исключения нехватки памяти, а также объясняет, почему существует большийи большее падение относительной производительности по мере того, как диапазоны становятся выше примерно с производительностью O (n ^ 1.4) при увеличении диапазона и лишь немного сохраняются, поскольку с самого начала имеют столь низкую вычислительную сложность.
Следующий код обращается ко всем этим ограничениям, поскольку он запоминает только базовые простые числа до квадратного корня от максимального числа в диапазоне, которые рассчитываются по мере необходимости (всего несколько килобайт в случае 32-разрядного диапазон номеров) и использует только очень маленькие буферы размером около шестнадцати килобайт для каждого из генератора базовых простых чисел и ситового фильтра главной страницы (меньше, чем размер кэша L1 большинства современных ЦП), а также включает код генерирующей последовательности и ( в настоящее время) в некоторой степени оптимизирован только для просеивания нечетных чисел, что означает, что память используется более эффективно. Кроме того, упакованный битовый массив используется для дальнейшего повышения эффективности памяти; его стоимость вычислений в основном компенсируется меньшим количеством вычислений, необходимых для сканирования буфера.
let primesAPF32() =
let rec oddprimes() =
let BUFSZ = 1<<<17 in let buf = Array.zeroCreate (BUFSZ>>>5) in let BUFRNG = uint32 BUFSZ<<<1
let inline testbit i = (buf.[i >>> 5] &&& (1u <<< (i &&& 0x1F))) = 0u
let inline cullbit i = let w = i >>> 5 in buf.[w] <- buf.[w] ||| (1u <<< (i &&& 0x1F))
let inline cullp p s low = let rec cull' i = if i < BUFSZ then cullbit i; cull' (i + int p)
cull' (if s >= low then int((s - low) >>> 1)
else let r = ((low - s) >>> 1) % p in if r = 0u then 0 else int(p - r))
let inline cullpg low = //cull composites from whole buffer page for efficiency
let max = low + BUFRNG - 1u in let max = if max < low then uint32(-1) else max
let sqrtlm = uint32(sqrt(float max)) in let sqrtlmndx = int((sqrtlm - 3u) >>> 1)
if low <= 3u then for i = 0 to sqrtlmndx do if testbit i then let p = uint32(i + i + 3) in cullp p (p * p) 3u
else baseprimes |> Seq.skipWhile (fun p -> //force side effect of culling to limit of buffer
let s = p * p in if p > 0xFFFFu || s > max then false else cullp p s low; true) |> Seq.nth 0 |> ignore
let rec mkpi i low =
if i >= BUFSZ then let nlow = low + BUFRNG in Array.fill buf 0 buf.Length 0u; cullpg nlow; mkpi 0 nlow
else (if testbit i then i,low else mkpi (i + 1) low)
cullpg 3u; Seq.unfold (fun (i,lw) -> //force cull the first buffer page then doit
let ni,nlw = mkpi i lw in let p = nlw + (uint32 ni <<< 1)
if p < lw then None else Some(p,(ni+1,nlw))) (0,3u)
and baseprimes = oddprimes() |> Seq.cache
seq { yield 2u; yield! oddprimes() }
primesAPF32() |> Seq.nth 203280220 |> printfn "%A"
Этот новый код вычисляет 203 280 221 простых чисел в диапазоне 32-разрядных чисел приблизительно в ДОБАВЛЕНО / ИСПРАВЛЕНО: 25,4 секунды с продолжительностью работы для первых 100000, одного миллиона, 10 миллионов и 100 миллион тестируется как 0,01, 0,088, 0,94 и 11,25 секунд соответственно на быстром настольном компьютере (i7-2700K @ 3,5 ГГц) и может работать на tryfsharp.org и ideone. com , хотя в меньшем диапазоне для последнего из-за ограничений по времени выполнения. Он имеет худшую производительность, чем код Джона Харропа, для небольших диапазонов в несколько тысяч простых чисел из-за повышенной вычислительной сложности, но очень быстро передает его для больших диапазонов благодаря более эффективному алгоритму производительности, который компенсирует эту сложность так, что он примерно в пять раз быстрее для 10-миллионного простого числа и примерно в семь раз быстрее, перед тем как код Джона взорвется до 25-миллионного простого числа.
Из общего времени выполнения более половины тратится на перечисление базовой последовательности и, таким образом, в значительной степени не помогло бы, если бы операции составного отбраковки чисел выполнялись в качестве фоновых операций, хотя в этом случае поможет оптимизация факторизации колеса в комбинации ( хотя эта сложность требует больших вычислительных ресурсов, эта сложность будет выполняться в фоновом режиме, поскольку они уменьшают количество операций проверки буфера, требуемых при перечислении. Дальнейшая оптимизация может быть сделана, если не нужно сохранять порядок последовательностей (например, просто считать число простых чисел или суммировать простые числа), так как последовательности могут быть написаны для поддержки параллельных интерфейсов перечисления или код может быть записывается как класс, чтобы методы-члены могли выполнять вычисления без перечисления. Этот код может быть легко настроен для обеспечения производительности, близкой к коду C #, но более кратко выраженной, хотя он никогда не достигнет производительности оптимизированного нативного кода C ++, такого как PrimeSieve , который был оптимизирован главным образом для задача простого подсчета числа простых чисел в диапазоне и вычисления числа простых чисел в 32-разрядном числовом диапазоне занимает небольшую долю секунды (0,25 секунды на i7-2700K).
Таким образом, дальнейшая оптимизация будет сконцентрирована вокруг дальнейшей упаковки битов ситовой решеткой с использованием факторизации колес, чтобы минимизировать работу, выполняемую при отборе составных чисел, пытаясь повысить эффективность перечисления полученных простых чисел и отводя всю составную отбраковку на задний план. потоки, в которых четырех-восьмиядерный процессор может скрыть необходимую дополнительную вычислительную сложность.
И это в основном чистый функциональный код, просто он использует изменяемый массив для объединения составной выборки ...