Объясните этот фрагмент кода хекелла, который выводит поток простых чисел

18

Мне трудно понять этот кусок кода:

let
  sieve (p:xs) = p : sieve (filter (\ x -> x 'mod' p /= 0) xs)
in sieve [2 .. ]

Может кто-то сломает меня? Я понимаю, что в нем есть рекурсия, но я не понимаю, как работает рекурсия в этом примере.

    
задан nubela 19.11.2009 в 16:38
источник
  • @ Everybody: такой элегантный, как этот алгоритм, его фактически не очень эффективный вообще (значительно менее результативный, чем пробное деление), и его определенно не реализация Сита Эратосфена. См. Следующее: cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf –  Juliet 19.11.2009 в 17:06
  • @Juliet: Умм ... это пробное подразделение. –  newacct 19.11.2009 в 19:32
  • @newacct: да и нет. С одной стороны, это пробное деление, а с другой - плохая реализация (автор в приведенной выше статье называет это «неверным ситом»). Правильные реализации просто проверяют число, чтобы увидеть, делит ли он все ранее вычисленное просто до sqrt (независимо от того, что вы проверяете) для сложности вокруг theta (n * sqrt (n) / (log n) ^ 2). Приведенный выше код фактически проверяет ввод по всем ранее вычисленным простым числам, что приводит к сложности вокруг theta (n ^ 2 / (log n) ^ 2). –  Juliet 19.11.2009 в 22:52
  • @MihaiMaruseac Как этот вопрос может быть возможным дубликатом другого, который не существовал в то время? –  Patrick Bard 27.02.2015 в 00:03

5 ответов

12

На самом деле это довольно элегантно.

Сначала мы определяем функцию sieve , которая принимает список элементов:

sieve (p:xs)

В теле sieve мы берем главу списка (потому что мы передаем бесконечный список [2..] , а 2 определяется как простой) и добавим его к результату применения sieve к остальной части списка:

p : sieve (filter (\ x -> x 'mod' p /= 0) xs)

Итак, давайте посмотрим на код, который выполняет работу над остальной частью списка:

sieve (filter (\ x -> x 'mod' p /= 0) xs)

Мы применяем sieve к отфильтрованному списку. Давайте разберем, что делает часть фильтра:

filter (\ x -> x 'mod' p /= 0) xs

filter принимает функцию и список, на которые мы применяем эту функцию, и сохраняем элементы, соответствующие критериям, заданным функцией. В этом случае filter принимает анонимную функцию:

\ x -> x 'mod' p /= 0

Эта анонимная функция принимает один аргумент, x . Он проверяет модуль x против p (глава списка, каждый раз, когда вызывается sieve ):

 x 'mod' p

Если модуль не равен 0:

 'mod' p /= 0

Затем элемент x сохраняется в списке. Если он равен 0, он отфильтровывается. Это имеет смысл: если x делится на p , то x делится более чем на 1 и на себя и, следовательно, не является простым.

    
ответ дан mipadi 19.11.2009 в 16:49
источник
  • Очень ясное объяснение, спасибо! –  nubela 19.11.2009 в 18:02
  • -1 для «мы берем главу списка ... и добавляем его к результату ...». Новички легко путаются такими неточными формулировками. –  Will Ness 27.01.2012 в 19:29
  • @WillNess: Не могли бы вы уточнить? Я не понимаю, что случилось. –  mipadi 27.01.2012 в 19:32
  • Это касается лени и времени. Мы не используем результаты в охраняемой рекурсии (использовать результат рекурсивного вызова - рекурсия). «Результат» будет рассчитан позже и поставлен на его место. Кроме того, «результат» никогда не присутствует одновременно. Это процесс вычисления взаимозачетов результатов, один за другим, которые действительно определены здесь. Просто мое личное занятие. –  Will Ness 27.01.2012 в 19:51
19

Вопреки тому, что здесь указывали другие, эта функция не не реализует true сито Эратосфена . Он действительно возвращает начальную последовательность простых чисел, хотя и аналогичным образом, так что нормально думать о ней как о сите Эратосфена.

Я проделал разъяснение кода, когда mipadi опубликовал свой ответ; Я мог бы удалить его, но поскольку я потратил на это некоторое время, и потому что наши ответы не полностью идентичны, я оставлю его здесь.

Прежде всего, обратите внимание, что в коде, который вы отправили, есть некоторые синтаксические ошибки. Правильный код:

let sieve (p:xs) = p : sieve (filter (\x -> x 'mod' p /= 0) xs) in sieve [2..]
  1. let x in y определяет x и позволяет использовать его определение в y . Результатом этого выражения является результат y . Таким образом, в этом случае мы определяем функцию sieve и возвращаем результат применения [2..] к sieve .

  2. Теперь давайте более подробно рассмотрим часть let этого выражения:

    sieve (p:xs) = p : sieve (filter (\x -> x 'mod' p /= 0) xs)
    
    1. Определяет функцию sieve , которая принимает список в качестве первого аргумента.
    2. (p:xs) - это шаблон , который соответствует p с заголовком указанного списка и xs с хвостом (все, кроме головы).
    3. В общем случае p : xs - это список, первым элементом которого является p . xs - это список, содержащий остальные элементы. Таким образом, sieve возвращает первый элемент списка, который он получает.
    4. Не смотрите на оставшуюся часть списка:

      sieve (filter (\x -> x 'mod' p /= 0) xs)
      
      1. Мы видим, что sieve вызывается рекурсивно. Таким образом, выражение filter вернет список.
      2. filter использует функцию фильтра и список. Он возвращает только те элементы в списке, для которых функция фильтра возвращает true.
      3. В этом случае xs - это список, который фильтруется и

        (\x -> x 'mod' p /= 0)
        

        - функция фильтра.

      4. Функция фильтра принимает единственный аргумент, x и возвращает true, если он не кратен p .
  3. Теперь, когда sieve определено, мы передаем ему [2 .. ] , список всех натуральных чисел, начинающихся с 2. Таким образом,

    1. Будет возвращено число 2. Все остальные натуральные числа, кратные двум, будут отброшены.
    2. Второе число равно 3. Оно будет возвращено. Все остальные кратные 3 будут отброшены.
    3. Таким образом, следующее число будет равно 5. Etc.
ответ дан Stephan202 19.11.2009 в 16:50
источник
  • Спасибо, Мипади выложил сначала, поэтому я дал ему правильные ответы, но ваш ответ тоже хорош, спасибо! –  nubela 19.11.2009 в 18:03
  • в первом вызове сите, haskell не создает бесконечный список (он не может быть выполнен ...) чисел и перенаправляет их на следующий вызов сита, который сам должен составить список бесконечного списка и т. д. и т. д. так как работает здесь механизм? и если haskell не делает бесконечных списков, во втором вызове сите (p = 3), как он знает, что он должен отбросить 4 и перейти к 5? второе сито не «знает» о первом вызове решета, в котором, конечно, будет устранено (но опять же, если haskell действительно не делает бесконечный список, как он знает, что число 4 или 60002 должно быть удалено из списка? ) –  Elimelech 12.11.2017 в 10:55
8

Он определяет генератор - трансформатор потока, называемый «сито» ,

Sieve s = 
  while( True ):
      p := s.head
      s := s.tail
      yield p                             -- produce this
      s := Filter (notAMultipleOf p) s    -- go next

primes := Sieve (Nums 2)

, который использует карриную форму анонимной функции, эквивалентную

notAMultipleOf p x = (mod x p) /= 0

Оба Sieve и Filter являются операциями построения данных с внутренней семантикой передачи состояния и переменной значения.

Здесь мы видим, что самая вопиющая проблема этого кода не , повторите не , что она использует пробный раздел , чтобы отфильтровать кратность из рабочей последовательности, тогда как он может найти их напрямую, подсчет с шагом p . Если бы мы заменили первый на последний, то полученный код по-прежнему имел бы ужасную сложность во время выполнения.

Нет, его наиболее вопиющая проблема заключается в том, что она добавляет Filter поверх своей рабочей последовательности слишком скоро , когда она действительно должна сделать это на вкладке отображается квадрат праймера . В результате цепочка Filter s, которую она создает, является слишком длинной , и большинство из них даже не нужны вообще.

Исправленная версия с созданием фильтра отложено до нужного момента

Sieve ps s = 
  while( True ):
      x := s.head
      s := s.tail
      yield x                             -- produce this
      p := ps.head
      q := p*p
      while( (s.head) < q ):
          yield (s.head)                  --    and these
          s := s.tail
      ps := ps.tail                       -- go next
      s  := Filter (notAMultipleOf p) s

primes := Sieve primes (Nums 2) 

или в Haskell ,

primes = sieve primes [2..] 
sieve ps (x:xs) = x : h ++ sieve pt [x | x <- t, rem x p /= 0]
     where (p:pt) = ps
           (h,t)  = span (< p*p) xs 

rem используется здесь вместо mod , поскольку в некоторых интерпретаторах это может быть намного быстрее, и все равно все цифры положительны.

Измерение локальных заказов роста алгоритма путем выполнения его времени выполнения t1,t2 при размере проблемы очков n1,n2 , logBase (n2/n1) (t2/t1) , мы получаем O(n^2) для первого и чуть выше O(n^1.4) для второго (в n простых чисел).

Чтобы уточнить это, недостающие части могут быть определены на этом (мнимом) языке просто как

Nums x =            -- numbers from x
  while( True ):
      yield x
      x := x+1

Filter pred s =     -- filter a stream by a predicate
  while( True ):
      if pred (s.head) then yield (s.head)
      s := s.tail

см. также .

    
ответ дан Will Ness 15.01.2012 в 18:51
источник
  • +1. Вы уверены, что сложность для второго равна O (n ^ 1.4)? Как вы пришли к такому результату? –  is7s 16.01.2012 в 07:13
  • log (t2 / t1) / log (n2 / n1). Эмпирическая локальная временная сложность. На самом деле это чуть выше, 1.40..1.42, в измеренном низком диапазоне n значений. Я запустил интерпретируемый код в GHCi, взяв статистику времени для простых чисел !! 1000, а затем простые! 2000, и вычисляет logBase 2 (1 + t2 / t1) (так как расчет в этом случае является накапливающим). Смотрите сагу на странице haskellwiki. –  Will Ness 16.01.2012 в 10:05
  • @ is7s, когда GHC-O2 скомпилирован и работает автономно, это было n ^ 1,36,1,46 для 50-100-200 тысяч простых чисел. Вызов диапазона нелокален и вызывает утечку пространства. С развернутым диапазоном он работает при n ^ 1,36,1,43,1,43 для 50-100-200-400 000 простых чисел. –  Will Ness 16.01.2012 в 11:50
  • На самом деле я предполагаю, что он все еще O (n ^ 2). Насколько я понимаю, он все еще является алгоритмом пробного деления и должен каждый раз проверять делимость на все предыдущие простые числа. Настоящая изменчивая версия, в которой используется STUArrays, вычисляет миллионное число мгновенно, пока эта реализация занимает минуту. Мне нужно сделать больше анализа, чтобы быть точным. –  is7s 16.01.2012 в 19:57
  • не со всеми предыдущими штрихами, а со всеми штрихами, предшествующими квадратному корню. Теоретическая сложность O (n ^ 1,5 / (log n) ^ 0,5) в n простых числах (в отличие от выражения в m верхнего предела O (m ^ 1,5 / (log m) ^ 2) IIRC) , Посмотрите на эту страницу haskellwiki, чтобы проверить настоящую версию. Это первый шаг в длительной последовательности улучшений. –  Will Ness 17.01.2012 в 08:53
Показать остальные комментарии
1

Он реализует Сито Эратосфена

В принципе, начните с простого (2) и отфильтруйте из остальных целых чисел, все кратные два. Следующее число в этом отфильтрованном списке также должно быть простым и, следовательно, фильтровать все его кратные от остальных и т. Д.

    
ответ дан sykora 19.11.2009 в 16:42
источник
1

В нем говорится: «Сито некоторого списка - это первый элемент списка (который мы будем называть p) и сито остальной части списка, отфильтрованный таким образом, что только« элементы, не делящиеся на p »разрешены через«. Затем он начинает работать, возвращая сито всех целых чисел от 2 до бесконечности (что равно 2, за которым следует сито всех целых чисел, не делящихся на 2 и т. Д.).

Я рекомендую The Little Schemer перед атакой Haskell.

    
ответ дан Jonathan Feinberg 19.11.2009 в 16:47
источник