Эффективное проектирование списка списков в F #

Question

Я должен сделать проекцию списка списков, который возвращает все комбинации с каждым элементом из каждого списка. Например:

projection([[1]; [2; 3]]) = [[1; 2]; [1; 3]].
projection([[1]; [2; 3]; [4; 5]]) = [[1; 2; 4]; [1; 2; 5]; [1; 3; 4]; [1; 3; 5]].

Я придумала функцию:

let projection lss0 =
    let rec projectionUtil lss accs =
        match lss with
        | []        ->  accs
        | ls::lss'  ->  projectionUtil lss' (List.fold (fun accs' l -> 
                                                        accs' @ List.map (fun acc -> acc @ [l]) accs) 
                                                        [] ls)
match lss0 with
| [] -> []
| ls::lss' ->         
    projectionUtil lss' (List.map (fun l -> [l]) ls)

и контрольный пример:

#time "on";;
let N = 10
let fss0 = List.init N (fun i -> List.init (i+1) (fun j -> j+i*i+i));;
let fss1 = projection fss0;;

Функция теперь довольно медленная, с N = 10 ее выполнение занимает более 10 секунд. Более того, я думаю, что решение неестественно, потому что мне приходится разбивать один и тот же список двумя разными способами. Любое предложение, как я могу улучшить производительность и удобочитаемость функции?

Answer 1

Прежде всего, старайтесь по возможности избегать конкатенации списков (@), так как это O (N) вместо O (1).

Я бы начал с (относительно) простого для понимания плана вычисления декартового внешнего произведения списков.

• Добавить каждый элемент первого списка к каждому подсписку в декартовом произведении остальных списков.
• Позаботьтесь о базовом случае.

Первая версия:

let rec cartesian = function
  | [] -> [[]]
  | L::Ls -> [for C in cartesian Ls do yield! [for x in L do yield x::C]]

Это прямой перевод приведенных выше предложений в код.

Теперь ускорите это: вместо списков используйте списки и карты:

let rec cartesian2 = function
  | [] -> [[]]
  | L::Ls -> cartesian2 Ls |> List.collect (fun C -> L |> List.map (fun x->x::C))

Это можно сделать еще быстрее, вычисляя списки по запросу с помощью последовательности:

let rec cartesian3 = function
  | [] -> Seq.singleton []
  | L::Ls -> cartesian3 Ls |> Seq.collect (fun C -> L |> Seq.map (fun x->x::C))

Эта последняя форма - то, что я использую сам, так как мне чаще всего нужно просто перебирать результаты, а не иметь их все сразу.

Некоторые тесты на моей машине: Тестовый код:

let test f N = 
  let fss0 = List.init N (fun i -> List.init (i+1) (fun j -> j+i*i+i))
  f fss0 |> Seq.length

Результаты в FSI:

> test projection 10;;
Real: 00:00:18.066, CPU: 00:00:18.062, GC gen0: 168, gen1: 157, gen2: 7
val it : int = 3628800
> test cartesian 10;;
Real: 00:00:19.822, CPU: 00:00:19.828, GC gen0: 244, gen1: 121, gen2: 3
val it : int = 3628800
> test cartesian2 10;;
Real: 00:00:09.247, CPU: 00:00:09.250, GC gen0: 94, gen1: 52, gen2: 2
val it : int = 3628800
> test cartesian3 10;;
Real: 00:00:04.254, CPU: 00:00:04.250, GC gen0: 359, gen1: 1, gen2: 0
val it : int = 3628800

Answer 2

Эта функция является последовательностью в Haskell (хотя sequence является более общей). Перевод на F #:

let sequence lss =
    let k l ls = [ for x in l do for xs in ls -> x::xs ]
    List.foldBack k lss [[]]

в интерактивном режиме:

> test projection 10;;
Real: 00:00:12.240, CPU: 00:00:12.807, GC gen0: 163, gen1: 155, gen2: 4
val it : int = 3628800
> test sequence 10;;
Real: 00:00:06.038, CPU: 00:00:06.021, GC gen0: 75, gen1: 74, gen2: 0
val it : int = 3628800

Общая идея: избегать явной рекурсии в пользу стандартных комбинаторов (сгиб, карта и т. Д.)

Answer 3

Вот хвосто-рекурсивная версия. Это не так быстро, как некоторые другие решения (только на 25% быстрее, чем ваша исходная функция), но использование памяти постоянно, поэтому оно работает для очень больших наборов результатов.

let cartesian l = 
  let rec aux f = function
    | [] -> f (Seq.singleton [])
    | h::t -> aux (fun acc -> f (Seq.collect (fun x -> (Seq.map (fun y -> y::x) h)) acc)) t
  aux id l

Answer 4

Ваша реализация медленная из-за операции @ (т.е. списка конкататов), которая является медленной операцией и выполняется много раз рекурсивным способом. Причина, по которой @ медленен, заключается в том, что список - это связанный список в функциональном программировании, и для того, чтобы составить список 2, сначала нужно пройти до конца списка (один за другим, проходя по элементам), а затем добавить другой список.

Пожалуйста, посмотрите на предлагаемые ссылки в комментариях. Я надеюсь, что они помогут вам.

Answer 5

let crossProduct listA listB listC listD listE = 
  listA |> Seq.collect (fun a -> 
  listB |> Seq.collect (fun b -> 
  listC |> Seq.collect (fun c -> 
  listD |> Seq.collect (fun d -> 
  listE |> Seq.map (fun e -> a,b,c,d,e))