Ленивый декартово произведение множественных последовательностей (последовательность последовательностей) - PullRequest
Новая
       30

Ленивый декартово произведение множественных последовательностей (последовательность последовательностей)

8 голосов
/ 27 июня 2011

Можете ли вы предложить более простой и понятный способ написания этой функции? 

let cartesian_product sequences = 
    let step acc sequence = seq { 
        for x in acc do 
        for y in sequence do 
        yield Seq.append x [y] }
    Seq.fold step (Seq.singleton Seq.empty) sequences

Ответы [ 2 ]

2 голосов
/ 28 июня 2011

Менее элегантное, но (кажется, более быстрое) решение: 

let cartesian_product2 sequences = 
    let step acc sequence = seq { 
        for x in acc do 
        for y in sequence do 
        yield seq { yield! x ; yield y } }
    Seq.fold step (Seq.singleton Seq.empty) sequences

; 

> cartesian items |> Seq.length;;
Real: 00:00:00.405, CPU: 00:00:00.405, GC gen0: 37, gen1: 1, gen2: 0
val it : int = 1000000
> cartesian_product2 items |> Seq.length;;
Real: 00:00:00.228, CPU: 00:00:00.234, GC gen0: 18, gen1: 0, gen2: 0
val it : int = 1000000
2 голосов
/ 28 июня 2011

Я протестировал функцию, с которой связана Джульетта: 

let items = List.init 6 (fun _ -> [0..9])
cart1 items |> Seq.length |> ignore

Реальный: 00: 00: 03.324, CPU: 00: 00: 03.322, GC gen0: 80, gen1: 0, gen2: 0

и немного модифицированная (чтобы сравнить яблоки с яблоками) ваша версия: 

let cartesian items =
  items |> Seq.fold (fun acc s ->
    seq { for x in acc do for y in s do yield x @ [y] }) (Seq.singleton [])

cartesian items |> Seq.length |> ignore

Реальный: 00: 00: 00.763, CPU: 00: 00: 00.780, GC gen0: 37, gen1: 2, gen2: 1

Ваш значительно быстрее (и вызывает меньше GC). Смотрит мне, что то, что у тебя есть, хорошо.

...