Какой стиль для неизменяемого набора и карты в F #

Question

Я только что решил задачу 23 в Project Euler, в которой мне нужно установить для хранения всех чисел. У F # есть неизменный набор, я могу использовать Set.empty.Add(i), чтобы создать новый набор, содержащий число i. Но я не знаю, как использовать неизменяемый набор, чтобы делать более сложные вещи.

Например, в следующем коде мне нужно посмотреть, можно ли записать число 'x' как сумму двух чисел в наборе. Я прибегаю к сортированному массиву и алгоритму двоичного поиска массива, чтобы выполнить работу.

Пожалуйста, прокомментируйте мой стиль следующей программы. Спасибо!

let problem23 = 
    let factorSum x =
        let mutable sum = 0
        for i=1 to x/2 do
            if x%i=0 then
                sum <- sum + i
        sum
    let isAbundant x = x < (factorSum x)
    let abuns = {1..28123} |> Seq.filter isAbundant |> Seq.toArray
    let inAbuns x = Array.BinarySearch(abuns, x) >= 0
    let sumable x = 
        abuns |> Seq.exists (fun a -> inAbuns (x-a))
    {1..28123} |> Seq.filter (fun x -> not (sumable x)) |> Seq.sum

обновленная версия:

let problem23b =
    let factorSum x =
        {1..x/2} |> Seq.filter (fun i->x%i=0) |> Seq.sum
    let isAbundant x = x < (factorSum x)
    let abuns = Set( {1..28123} |> Seq.filter isAbundant )
    let inAbuns x = Set.contains x abuns  
    let sumable x = 
        abuns |> Seq.exists (fun a -> inAbuns (x-a))
    {1..28123} |> Seq.filter (fun x -> not (sumable x)) |> Seq.sum

Эта версия запускается примерно за 27 секунд, в то время как первые 23 секунды (я запускал несколько раз). Таким образом, неизменное красно-черное дерево на самом деле не имеет большой скорости по сравнению с отсортированным массивом с двоичным поиском. Общее количество элементов в наборе / массиве составляет 6965.

Answer 1

Ваш стиль выглядит хорошо для меня. Различные шаги в алгоритме понятны, что является наиболее важной частью заставить что-то работать. Это также тактика, которую я использую для решения задач Project Euler. Сначала заставьте это работать, а затем сделайте это быстро.

Как уже отмечалось, замена Array.BinarySearch на Set.contains делает код еще более читабельным. Я обнаружил, что почти во всех PE-решениях, которые я написал, я использую массивы только для поиска. Я обнаружил, что использование последовательностей и списков в качестве структур данных более естественно в F #. Как только вы к ним привыкнете, то есть.

Я не думаю, что использование изменчивости внутри функции обязательно плохо. Я оптимизировал задачу 155 с почти 3 минут до 7 секунд с некоторыми агрессивными оптимизациями изменчивости. В целом, хотя, я бы сохранил это как шаг оптимизации и начал бы писать его, используя сгибы / фильтры и т. Д. В примере с проблемой 155 я начал использовать композицию неизменяемых функций, потому что она выполняла тестирование и, самое главное, понимание Мой подход легкий.

Выбор неправильного алгоритма гораздо более пагубен для решения, чем сначала использование более медленного неизменяемого подхода. Хороший алгоритм все еще быстр, даже если он медленнее, чем изменяемая версия ( диван привет капитан очевиден! кашель ).

Редактировать: давайте посмотрим на вашу версию

Ваша проблема 23b () заняла 31 секунду на моем ПК.

Оптимизация 1: использовать новый алгоритм.

//useful optimization: if m divides n, (n/m) divides n also
//you now only have to check m up to sqrt(n)
let factorSum2 n = 
    let rec aux acc m =
        match m with
        | m when m*m = n -> acc + m
        | m when m*m > n -> acc
        | m -> aux (acc + (if n%m=0 then m + n/m else 0)) (m+1)
    aux 1 2

Это все еще очень функциональный стиль, но с использованием этого обновленного фактора суммы в вашем коде время выполнения увеличилось с 31 до 8 секунд.

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

Оптимизация 2: использовать массив для поиска:

let absums() = 
    //create abundant numbers as an array for (very) fast lookup
    let abnums = [|1..28128|] |> Array.filter (fun n -> factorSum2 n > n)
    //create a second lookup: 
    //a boolean array where arr.[x] = true means x is a sum of two abundant numbers
    let arr = Array.zeroCreate 28124
    for x in abnums do 
        for y in abnums do
            if x+y<=28123 then arr.[x+y] <- true
    arr

let euler023() = 
    absums() //the array lookup
    |> Seq.mapi (fun i isAbsum -> if isAbsum then 0 else i) //mapi: i is the position in the sequence
    |> Seq.sum

//I always write a test once I've solved a problem.
//In this way, I can easily see if changes to the code breaks stuff.
let test() = euler023() = 4179871 

Время выполнения: 0,22 секунды (!).

Это то, что мне так нравится в F #, оно все еще позволяет вам использовать изменяемые конструкции, чтобы возиться под капотом вашего алгоритма. Но я все еще делаю это после Сначала я сделал что-то более элегантное.

Answer 2

Вы можете легко создать Set из заданной последовательности значений.

let abuns = Set (seq {1..28123} |> Seq.filter isAbundant)

inAbuns поэтому будет переписано в

let inAbuns x = abuns |> Set.mem x

Seq.exists будет изменено на Set.exists

Но реализация массива тоже подойдет ...

Обратите внимание, что нет необходимости использовать изменяемые значения в factorSum, за исключением того, что это неверно, поскольку вы вычисляете число делителей вместо их суммы:

let factorSum x = seq { 1..x/2 } |> Seq.filter (fun i -> x % i = 0) |> Seq.sum

Answer 3

Вот простое функциональное решение, которое короче вашего оригинала и более чем в 100 раз быстрее:

let problem23 =
  let rec isAbundant i t x =
    if i > x/2 then x < t else
      if x % i = 0 then isAbundant (i+1) (t+i) x else
        isAbundant (i+1) t x
  let xs = Array.Parallel.init 28124 (isAbundant 1 0)
  let ys = Array.mapi (fun i b -> if b then Some i else None) xs |> Array.choose id
  let f x a = x-a < 0 || not xs.[x-a]
  Array.init 28124 (fun x -> if Array.forall (f x) ys then x else 0)
  |> Seq.sum

Первый трюк - записать, какие числа встречаются в массиве, проиндексированном самим числом, а не использовать структуру поиска. Второй трюк состоит в том, чтобы заметить, что все время тратится на создание этого массива, и, следовательно, делать это параллельно.