LINUX.ORG.RU

Ответ на: комментарий от r2d2

я имею в виду специфику F#, работу его библиотечных ф-ций, во что они раскрываются. Возможно на разных объёмах входных списков. Вопрос к тем, кто хорошо знает как работает под капотом F#. К примеру, в моём коде, судя по всему, используется append для склейки списков и, скорее всего, это не очень хорошо

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от r2d2

вот пример, 

let a = [1..10000]
let b = [1..10000]

let intersectionCollect f l1 l2 =
    l1 |> List.collect (fun el1 ->
                            l2 |> List.collect (fun el2 ->
                                                    match f el1 el2 with
                                                    | Some(res) -> [res]
                                                    | None -> []))

intersectionCollect (fun a b -> if (a = b) then Some(a,b) else None) a b
(*Real: 00:00:10.020, CPU: 00:00:09.562, GC gen0: 3, gen1: 1, gen2: 0*)

let intersectionCollect2 f l1 l2 =
    l1 |> List.fold 
            (fun acc el1 ->
                (l2 |> List.fold 
                        (fun acc el2 ->
                            match f el1 el2 with
                            | Some(res) -> res :: acc
                            | None -> acc) 
                        []) :: acc) 
            [] 

intersectionCollect2 (fun a b -> if (a = b) then Some(a,b) else None) a b
(*Real: 00:00:04.783, CPU: 00:00:04.718, GC gen0: 2, gen1: 0, gen2: 0*)
pseudo-cat ★★★
() автор топика

Что именно собираетесь оптимизировать? Потребление памяти? Скорость исполнения? Количество строк кода? Количество непечатных символов?

trex6 ★★★★★
()
Ответ на: комментарий от pseudo-cat

вместо cons надо append во внешнем fold: 

let a = [1..10000]
let b = [1..10000]

let intersectionCollect f l1 l2 =
    l1 |> List.collect (fun el1 ->
                            l2 |> List.collect (fun el2 ->
                                                    match f el1 el2 with
                                                    | Some(res) -> [res]
                                                    | None -> []))

intersectionCollect (fun a b -> if (a = b) then Some(a,b) else None) a b
(*Real: 00:00:09.516, CPU: 00:00:09.390, GC gen0: 4, gen1: 1, gen2: 0*)

let intersectionCollect2 f l1 l2 =
    l1 |> List.fold 
            (fun acc el1 ->
                (l2 |> List.fold 
                        (fun acc el2 ->
                            match f el1 el2 with
                            | Some(res) -> res :: acc
                            | None -> acc) 
                        []) @ acc) 
            [] 

intersectionCollect2 (fun a b -> if (a = b) then Some(a,b) else None) a b
(*Real: 00:00:04.918, CPU: 00:00:04.859, GC gen0: 3, gen1: 0, gen2: 0*)

pseudo-cat ★★★
() автор топика

Можно переписать как

let rec intersectionCollect2 f l1 l2 = [
    for el1 in l1 do
        for el2 in l2 do
            match f el1 el2 with
            | Some(res) -> yield res
            | None -> ()
]

А дальше оптимизировать, прибегнув к локальным побочных эффектам, если очень того хочется:

let rec intersectionCollect3 f l1 l2 = 
    let els = new List<_>()
    for el1 in l1 do
        for el2 in l2 do
            match f el1 el2 with
            | Some(res) -> els.Add(res)
            | None -> ()
    els |> Seq.toList
dave ★★★★★
()

Товарищи любезно напоминают о premature optimization как о зле?

vladimir-vg ★★
()
Ответ на: комментарий от dave

первый вариант работает: 

(*Real: 00:00:20.524, CPU: 00:00:20.515, GC gen0: 10, gen1: 1, gen2: 0*)
второй: 
(*Real: 00:00:06.143, CPU: 00:00:06.078, GC gen0: 3, gen1: 1, gen2: 0*)

pseudo-cat ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development