Почему этот код F # медленнее, чем эквивалент С#?

Я снова сталкиваюсь с проблемами Project Euler (делали первые 23 перед тем, как учил С#), и я совершенно сбив с толку на подпункт производительности моего решения проблемы 5.

Он читается следующим образом:

2520 - наименьшее число, которое можно разделить на каждый из чисел от 1 до 10 без остатка.

Какое наименьшее положительное число, которое равномерно делится на все чисел от 1 до 20?

Теперь мое невероятно примитивное грубое решение С# перехватывает эту проблему примерно через 25 секунд.

var numbers = Enumerable.Range(1, 20);
int start = 1;
int result;
while (true)
{
   if (numbers.All(n => start % n == 0))
   {
       result = start;
       break;
   }
   start++;
}

Теперь мое решение F # также использует грубое форсирование, но, по крайней мере, оно делает немного больше дискриминации и поэтому так, что оно "должно" в моем сознании работать быстрее, но оно срабатывает через ~ 45 секунд, поэтому оно почти в два раза медленнее, чем С# 1.

let p5BruteForce =
    let divisors = List.toSeq ([3..20] |> List.rev)
    let isDivOneToTwenty n =
        let dividesBy = 
            divisors |> Seq.takeWhile(fun x -> n % x = 0)                
        Seq.length dividesBy = Seq.length divisors

    let findNum n =
        let rec loop n = 
            match isDivOneToTwenty n with
            | true -> n
            | false -> loop (n + 2)
        loop n
    findNum 2520

P.S - Я знаю, что мое решение может быть лучше, в этом случае мне просто интересно, как могло бы быть, что лучшее решение грубой силы может быть настолько медленнее, чем примитивное.

Ответы

Ответ 1

Вы можете использовать List.forall вместо преобразования в seq, а затем выполнить Seq.length:

let divisors = [3..20] |> List.rev
let isDivOneToTwenty n = divisors |> List.forall (fun d -> n % d = 0)

Seq.length необходимо пройти всю последовательность, чтобы определить количество элементов, а forall может вернуться, как только элемент завершит сбой предиката.

вы также можете написать findNum как:

let rec findNum n = if isDivOneToTwenty n then n else findNum (n + 2)

Ответ 2

Даже более прямой перевод, такой как

let numbers = { 1..20 }
let rec loop start =
    if numbers |> Seq.forall (fun n -> start % n = 0) 
    then start
    else loop (start + 1)
loop 1

занимает минуту и ​​половину (ваша версия С# занимает 25 секунд на моей машине). Числовая последовательность, по-видимому, является виновником изменения ее в массив ([| 1..20 |]), а с помощью Array.forall - до 8 секунд. Версия С# с использованием массива занимает 20 секунд (используя мой собственный специализированный метод ForAll, а не Enumerable.All занимает 17 секунд).

EDIT: после просмотра ответа Ли я попробовал List.forall, и он даже быстрее, чем массив (~ 5 секунд).

Ответ 3

ну, это должен быть этот бит

            divisors |> Seq.takeWhile(fun x -> n % x = 0)                
    Seq.length dividesBy = Seq.length divisors

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