Должен ли я хранить промежуточную стоимость при создании ее?
-
19-09-2019 - |
Вопрос
Я пытаюсь выучить F#, поэтому зашёл в гости Проект Эйлера и я сейчас работаю над Проблема 3.
Простые множители числа 13195: 5, 7, 13 и 29.
Какое самое большое простое число множитель числа 600851475143?
Некоторые вещи, которые следует учитывать:
- Мой главный приоритет — выработать хорошие функциональные привычки.
- Мой второй приоритет — я хочу, чтобы это было быстро и эффективно.
В следующем коде я отметил раздел, к которому относится этот вопрос.
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)
Вы, наверное, слышали об использовании рекурсии вместо циклов, и это правильно.Но везде, где это возможно, вам следует абстрагироваться от рекурсии с помощью складок, карт или функций более высокого порядка.Две причины для этого:
это немного более читабельно, и
неправильно написанная рекурсия приведет к переполнению стека.Например, ваша функция не является хвостовой рекурсивной, поэтому она не будет работать при больших значениях
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# было бы использование (|>)
оператор для передачи значения в анонимную функцию, но я все еще думаю, что это не так читабельно.