Должен ли я хранить промежуточную стоимость при создании ее?

StackOverflow https://stackoverflow.com/questions/2036073

Вопрос

Я пытаюсь выучить F#, поэтому зашёл в гости Проект Эйлера и я сейчас работаю над Проблема 3.

Простые множители числа 13195: 5, 7, 13 и 29.

Какое самое большое простое число множитель числа 600851475143?

Некоторые вещи, которые следует учитывать:

  1. Мой главный приоритет — выработать хорошие функциональные привычки.
  2. Мой второй приоритет — я хочу, чтобы это было быстро и эффективно.

В следующем коде я отметил раздел, к которому относится этот вопрос.

let isPrime(n:int64) = 
    let rec check(i:int64) = 
        i > n / 2L or (n % i <> 0L && check(i + 1L))
    check(2L) 

let greatestPrimeFactor(n:int64) =
    let nextPrime(prime:int64):int64 = 
        seq { for i = prime + 1L to System.Int64.MaxValue do if isPrime(i) then yield i }  
        |> Seq.skipWhile(fun v -> n % v <> 0L) 
        |> Seq.hd
    let rec findNextPrimeFactor(number:int64, prime:int64):int64 =
        if number = 1L then prime else 
            //************* No variable
            (fun p -> findNextPrimeFactor(number / p, p))(nextPrime(prime))    
            //*************               
            //************* Variable
            let p = nextPrime(prime)
            findNextPrimeFactor(number / p, p) 
            //*************
    findNextPrimeFactor(n, 2L)

Обновлять

Основываясь на некоторых отзывах, я переработал код, чтобы он стал в 10 раз быстрее.

module Problem3

module private Internal =
    let execute(number:int64):int64 = 
        let rec isPrime(value:int64, current:int64) = 
            current > value / 2L or (value % current <> 0L && isPrime(value, current + 1L))   
        let rec nextPrime(prime:int64):int64 = 
            if number % prime = 0L && isPrime(prime, 2L) then prime else nextPrime(prime + 1L)       
        let rec greatestPrimeFactor(current:int64, prime:int64):int64 =
            if current = 1L then prime else nextPrime(prime + 1L) |> fun p -> greatestPrimeFactor(current / p, p)
        greatestPrimeFactor(number, 2L)


let execute() = Internal.execute(600851475143L)

Обновлять

Я хотел бы поблагодарить всех за советы.Эта последняя версия представляет собой сборник всех полученных мной советов.

module Problem3

module private Internal =
    let largestPrimeFactor number = 
        let rec isPrime value current = 
            current > value / 2L || (value % current <> 0L && isPrime value (current + 1L))   
        let rec nextPrime value =
            if number % value = 0L && isPrime value 2L then value else nextPrime (value + 1L) 
        let rec find current prime =
            match current / prime with
            | 1L -> prime
            | current -> nextPrime (prime + 1L) |> find current
        find number (nextPrime 2L)            

let execute() = Internal.largestPrimeFactor 600851475143L
Это было полезно?

Решение

По мере практики функциональное программирование становится проще и автоматическим, поэтому не переживайте, если с первой попытки у вас не получится абсолютно правильно.

Имея это в виду, давайте возьмем пример кода:

let rec findNextPrimeFactor(number:int64, prime:int64):int64 =
        if number = 1L then prime else 
            //************* No variable
            (fun p -> findNextPrimeFactor(number / p, p))(nextPrime(prime))    
            //*************               
            //************* Variable
            let p = nextPrime(prime)
            findNextPrimeFactor(number / p, p) 
            //*************

Твой no variable версия просто странная, не используйте ее.Мне нравится ваша версия с явной привязкой let.

Другой способ написать это:

nextPrime(prime) |> fun p -> findNextPrimeFactor(number / p, p)

Его хорошо и иногда полезно написать это вот так, но все равно выглядит немного странно.Большую часть времени мы используем |> каррировать значения без необходимость называть наши переменные (в стиле «без точек»).Постарайтесь предугадать, как будет использоваться ваша функция, и, если возможно, перепишите ее, чтобы можно было использовать ее с оператором канала без явного объявления переменных.Например:

let rec findNextPrimeFactor number prime =
    match number / prime with
    | 1L -> prime
    | number' -> nextPrime(prime) |> findNextPrimeFactor number'

Больше никаких именованных аргументов :)

Хорошо, теперь, когда мы разобрались с этим, давайте посмотрим на ваш isPrime функция:

let isPrime(n:int64) = 
    let rec check(i:int64) = 
        i > n / 2L or (n % i <> 0L && check(i + 1L))
    check(2L)

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

  1. это немного более читабельно, и

  2. неправильно написанная рекурсия приведет к переполнению стека.Например, ваша функция не является хвостовой рекурсивной, поэтому она не будет работать при больших значениях n.

я бы переписал isPrime так:

let isPrime n = seq { 2L .. n / 2L } |> Seq.exists (fun i -> n % i = 0L) |> not

В большинстве случаев, если вы можете абстрагироваться от явного цикла, вы просто применяете преобразования к входной последовательности, пока не получите результаты:

let maxFactor n =
    seq { 2L .. n - 1L }                        // test inputs
    |> Seq.filter isPrime                       // primes
    |> Seq.filter (fun x -> n % x = 0L)         // factors
    |> Seq.max                                  // result

В этой версии у нас даже нет промежуточных переменных.Прохлада!

Мой второй приоритет – мне бы этого хотелось быть быстрым и эффективным.

В большинстве случаев F# будет сопоставим с C# по скорости или будет «достаточно быстрым».Если вы обнаружите, что выполнение вашего кода занимает много времени, это, вероятно, означает, что вы используете неправильную структуру данных или плохой алгоритм.Конкретный пример читайте в комментариях. по этому вопросу.

Итак, код, который я написал, «элегантен» в том смысле, что он краток, дает правильные результаты и не требует каких-либо ухищрений.К сожалению, это не очень быстро.Для начала:

  • он использует пробное деление для создания последовательности простых чисел, тогда как Решето Эратосфена будет работать намного быстрее.[Редактировать:Я написал несколько наивную версию этого сита, которая не работала для чисел больше, чем Int32.MaxValue, поэтому я удалил код.]

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

[Редактировать:Я включил некоторый код с несколько наивной реализацией решета Эратосфена.Он работает только для входных данных меньше, чем int32.MaxValue, поэтому, вероятно, не подходит для эйлера проекта.]

Другие советы

Что касается «хорошей функциональной привычки» или, скорее, хорошей практики, я вижу три незначительных вещи.Использование доходности в вашей последовательности немного сложнее читать, чем просто фильтровать.Ненужные аннотации типов в языке с выводимым типом приводят к сложному рефакторингу и усложняют чтение кода.Не переусердствуйте и не пытайтесь удалить все аннотации типов, если вам это сложно.Наконец, создание лямбда-функции, которая принимает только значение для использования в качестве временной переменной, снижает читаемость.

Что касается личного стиля, я предпочитаю больше пробелов и использую кортежи аргументов только тогда, когда данные имеют смысл группировать вместе.

Я бы написал ваш исходный код следующим образом.

let isPrime n = 
    let rec check i = 
        i > n / 2L || (n % i <> 0L && check (i + 1L))
    check 2L

let greatestPrimeFactor n =
    let nextPrime prime = 
        seq {prime + 1L .. System.Int64.MaxValue}
        |> Seq.filter isPrime
        |> Seq.skipWhile (fun v -> n % v <> 0L) 
        |> Seq.head

    let rec findNextPrimeFactor number prime =
        if number = 1L then 
            prime 
        else 
            let p = nextPrime(prime)
            findNextPrimeFactor (number / p) p

    findNextPrimeFactor n 2L

Ваш обновленный код оптимален для вашего подхода.Чтобы работать быстрее, вам придется использовать другой алгоритм, например ответ Инь Чжу.Я написал тест, чтобы проверить, делает ли F # хвостовую рекурсивную функцию «проверки», и это так.

тот переменная p на самом деле является привязкой имени, а не переменной.Использование привязки имени — неплохой стиль.И это более читабельно.Ленивый стиль nextPrime это хорошо, и на самом деле оно проверяет каждое число только один раз за всю программу.

Мое решение

let problem3 = 
    let num = 600851475143L
    let rec findMax (n:int64) (i:int64) =
        if n=i || n<i then
            n
        elif n%i=0L then
            findMax (n/i) i
        else
            findMax n (i+1L)
    findMax num 2L

Я в основном делю число на 2, 3, 4..и не рассматривайте простые числа.Потому что если мы разделим все 2 из num, то мы не сможем разделить его на 4,8 и т. д.

по этому номеру мое решение быстрее:

> greatestPrimeFactor 600851475143L;;
Real: 00:00:01.110, CPU: 00:00:00.702, GC gen0: 1, gen1: 1, gen2: 0
val it : int64 = 6857L
> 
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

val problem3 : int64 = 6857L

Я думаю, что код с временной привязкой читается значительно легче.Довольно необычно создавать анонимную функцию, а затем сразу же применять ее к значению, как вы делаете в другом случае.Если вы действительно хотите избежать использования временного значения, я думаю, что наиболее идиоматическим способом сделать это в F# было бы использование (|>) оператор для передачи значения в анонимную функцию, но я все еще думаю, что это не так читабельно.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top