Бесконечное решето Эратосфена

Во время выполнения одного из упражнений учебника по языку Haskell Р. Душкина, меня посетила мысль, что упражнение можно выполнить и на языке C# в духе Haskell.

Упражнение заключалось в реализации функции для получения бесконечного списка простых чисел с помощью алгоритма ”решето Эратосфена”. Надеюсь на то, что автор учебника не обидится на меня за то, что я привел тут решение задачи. Оно же почти в том же виде описано на wikipedia (ссылка выше на решето). Мое же решение отличается от опубликованного лишь тем, что четные числа я вычернкул загодя:

primes :: [Integer]
primes = 2 : sieve [3, 5..]
       where
         sieve (p:ps) = p : sieve [x | x <- ps, x `mod` p > 0]

Нет, я не подглядывал и решение на Haskell в википедии обнаружил уже после того, как решил поделиться мыслями на эту тему. Мысли были примерно следующего характера:

Круто, ведь несколько раз мне приходилось реализовывать решето Эратосфена, и ни разу не пришло в голову реализовать его для бесконечного списка! Всегда требовалось задавать порог-размер решета. Беда даже не в том, что нужен порог, а в том, что нужно его тщательно подбирать для каждой задачи. Слишком малый порог грозит тем, что размера решета не хватит, а слишком большой опасен тем, что приложение будет слишком много времени тратить на ненужный счет.

Впрочем, в C# есть механизмы для работы с бесконечными последовательностями. Ну или почти бесконечными.

Подумал я так, и решил повторить решение на C#:

public static IEnumerable<int> GetPrimes()
{
  yield return 2;
  var sieve = Generate(3, 2);

  while(true)
  {
      var p = sieve.First();
      yield return p;

      sieve = sieve.Where(x => x % p > 0);
  }
}
static IEnumerable<int> Generate(int start, int step)
{
  for (int i = start; ; i += step)
      yield return i;
}

По ходу написания ощутил, что в C# таки нет некоторых инструментов, но в остальном реализация на C# почти полностью соответсвует представленному выше решению на Haskell, потому я решение на Haskell не буду комментировать.

Код на C# вполне рабочий. Первым делом он возвращает 2, затем берет последовательность нечетных чисел больше 2 и на каждой итерации делает следующее: берет первое число p из последовательности и навешивает на последовательность фильтр, выкидывающий все что делится нацело на p.

Итак, отличия этого кода от решения на Haskell.

1. В C# нет типа BigInt (неограниченного целого). Потому решение на C# ограничено типом Int32.
2. В C# нет встроенного генератора бесконечного списка. Enumerable.Range требует ограничителя диапазона и не воспринимает шаг. Впрочем, легко написать свой генератор, что я и сделал.
3. В C# недоступен механизм рекурсии для работы с бесконечными списками. Ну т.е. рекурсия сама по себе есть, но воспользовавшись ей мы получим переполнение стека не дойдя до второго члена последовательности. Потому рекурсивное определение списка пришлось заменить на цикл с изменяемым состоянием. Да, решение на C# императивно. Ну да ладно, хоть состояние изменяемое, но оно невидимое клиенту изменяемое состояние.

Вот, пожалуй, и все отличия, подмеченные мной с первого раза. Все да не все. Что-то заставляет скомпилированный код на C# доставать 1000-е простое число в 5 раз дольше, чем выполняется код на интерпретаторе Haskell!!! Нет, это не шутка. А если попросить Haskell обойтись ограниченным целым (Int32), то он работает в 20 раз быстрее C#-а!!!

Все дело в том, что Haskell на каждой итерации выполняет фильтрацию над хвостом бесконечного списка, а C# выполняет фильтрацию над всей бесконечной последовательностью. Т.е. при поручении очередного элемента каждый раз требуется пройти часть бесконечной последовательности с самого начала, но уже с новыми условиями для фильтрации, которые добавляются на каждой итерации. Далее представлен слегка оптимизированный вариант на C#:

public static IEnumerable<int> GetPrimes1()
{
  yield return 2;
  var sieve = Generate(3, 2);

  Func<int, bool> predicate = x => true;

  while (true)
  {
      var p = sieve.First();
      yield return p;
      predicate = predicate.And(x => x % p > 0);

      sieve = Generate(p, 2)
          .Where(predicate);
  }
}

static Func<T, bool> And<T>(this Func<T, bool> p1, Func<T, bool> p2)
{
  return t => p1(t) && p2(t);
}

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

public static IEnumerable<int> GetPrimes2()
{
  yield return 2;
  var primes = new List<int> {2};
  var sieve = Generate(3, 2);

  Func<int, bool> predicate = x => primes.All(p => x % p > 0);

  while (true)
  {
      var p = sieve.First();
      yield return p;
      primes.Add(p);

      sieve = Generate(p, 2)
          .Where(predicate);
  }
}

Впрочем, последние две версии решета на C# уже уверенно обгоняют интерпретатор Haskell-а. Вот только оригинальное решето Эратосфена они напоминают лишь отдаленно. И сильно смахивают на проверку делением на предварительно найденные простые числа. Следующее решение на языке F#:

let primes =
  let gen n = seq { n..2..System.Int32.MaxValue }
  let f (sieve, filter) =
      let p = sieve |> Seq.filter filter |> Seq.hd
      Some(p, (gen p, (fun x -> filter x && x % p > 0)))
  Seq.unfold f (gen 3, (fun _ -> true))
  |> Seq.append [2]

Оно больше всего соответствует варианту GetPrimes1() на C#, хотя написано без явно изменяемого состояния. В библиотеке F# имеется тип для представления больших целых, но я им здесь не воспользовался.

Выводы

Хоть .NET и имеет средства для работы с бесконечными последовательностями, но к сожалению, пользоваться ими далеко не так удобно, как могло бы быть. Но основная мысль не об этом. Мое знакомство с Haskell-ем, пока еще поверхностное, позволило по новому взглянуть на известные ранее алгоритмы и инструменты.