F # списки с операторами последовательности

Question

После просмотра этих двух потоков: Имеет ли F # эквивалент взятию Хаскелла? , Взять N элементов из последовательности с N различными индексами в F # , я былинтересно, как лучше использовать операторы последовательности в списках или даже использовать их.

Сейчас я новичок в F #, и я пишу программу, которая должна иметь дело с большим количеством последовательностей, которые я получаю.из HtmlAgilityPack.В модуле Seq есть несколько интересных операторов, но, как указано в этих потоках, он может быть плохим в отношении производительности, и если мы вынуждены постоянно конвертировать между seq -> list, он также загромождает код вещами, которые не решают проблемы.Именно поэтому я начал изучать F # в первую очередь.

Простой пример - когда мне нужно взять 'N' элементов списка:

               listOfRows
               |> Seq.take 2
               // Now I don't have a list anymore, it returns a sequence
               |> List.ofSeq

Итак, кто-нибудь может потерятькакой-нибудь свет о лучшем способе справиться с этими сценариями?Я могу работать над решениями, используя Seq.take и Seq.skip, но это, как известно, очень неэффективно.С другой стороны, стыдно, что функциональность встроена в стандартную библиотеку и что она должна быть переопределена для использования одной и той же концепции в другой коллекции, или сделать код более грязным с явными преобразованиями.

Как я могу увидетьвлияние на производительность каждого преобразования между «list -> seq» и ​​«seq -> list»?

Большое спасибо.

Answer 1

Это довольно тривиально для реализации.

module List =

  let take n items =
    let rec take' acc = function
      | 0, _ -> List.rev acc
      | _, [] -> invalidOp "count exceeds number of elements"
      | n, h::t -> take' (h::acc) (n-1, t)
    take' [] (n, items)

  let rec skip n items =
    match n, items with
    | 0, _ -> items
    | _, [] -> invalidOp "count exceeds number of elements"
    | n, _::t -> skip (n-1) t

А вот как они работают против своих Seq аналогов.

let n = 10000000
let l = List.init n id
let test f = f (n-1) l

test List.take               //Real: 00:00:03.724, CPU: 00:00:03.822, GC gen0: 57, gen1: 34, gen2: 1
test Seq.take |> Seq.toList  //Real: 00:00:04.953, CPU: 00:00:04.898, GC gen0: 57, gen1: 33, gen2: 0
test List.skip               //Real: 00:00:00.044, CPU: 00:00:00.046, GC gen0: 0, gen1: 0, gen2: 0
test Seq.skip |> Seq.toList  //Real: 00:00:01.147, CPU: 00:00:01.154, GC gen0: 0, gen1: 0, gen2: 0

Если для вашего приложения считаются миллисекунды, возможно, стоит создать «отсутствующие» List функции В противном случае, я бы сказал, что использование версий Seq прекрасно.

Answer 2

Отчасти это может зависеть от того, как именно вы хотите использовать все это сквозное.

Во многих случаях будет хорошо преобразовать в список один раз, а затем использовать только операторы List для отображения / перемещения / и т.д. Может не быть List.take, но это потому, что со списками, если вы знаете, что будет по крайней мере два элемента, и вы хотите получить эти два элемента, вы можете сделать это с помощью сопоставления с образцом, например,

let (item1::item2::rest) = someList

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

(Если лень / потоковая передача необходимы, то Seq становится намного более полезным.)

Вкратце, наиболее распространенные операторы (например, map) есть во всех типах коллекций (Seq, List, Array, ...), тогда как не столь распространенные (например, take) доступны на Seq, часто потому что есть лучшие способы сделать что-то, когда у вас есть конкретный тип (например, сопоставление с шаблоном списка, чтобы взять первые элементы).

Answer 3

Вы можете полностью понять влияние преобразований Seq -> List и List -> Seq, просмотрев соответствующие реализации преобразований:

// List.ofSeq
let ofSeq source = Seq.toList source
// List.toSeq
let toSeq list = Seq.ofList list
// Seq.ofList
let ofList (source : 'T list) = 
        (source :> seq<'T>)
// Seq.toList
let toList (source : seq<'T>) = 
        checkNonNull "source" source
        match source with 
        | :? ('T list) as res -> res
        | :? ('T[]) as res -> List.ofArray res
        | _ -> 
            use e = source.GetEnumerator()
            let mutable res = [] 
            while e.MoveNext() do
                res <- e.Current :: res
            List.rev res

Сами преобразования относительно мало влияют на производительность по сравнению с фактическими операциями с коллекциями.Запуск следующего фрагмента, который преобразует Список из 1 миллиона участников в seq, а затем возвращает его в другой Список на моем старом ноутбуке Core 2 Duo 2,4 ГГц

open System.Diagnostics

let tls = Stopwatch()
let l = [1..1000000]
tls.Start()
let s = List.toSeq l
//Seq.length s |> ignore
//Seq.length s |> ignore
tls.Stop()
printfn "List<int> of 1000000 -> Seq: %d ticks" tls.ElapsedTicks 

let tsl = Stopwatch()
tsl.Start()
let l' = Seq.toList s
//l'.Length |> ignore
//l'.Length |> ignore
tsl.Stop()
printfn "Seq<int> of 1000000 -> List: %d ticks" tsl.ElapsedTicks

, показывает взрывные 42 и 8 тиков соответственно.Если раскомментировать первые соответствующие строки со счетчиками длины, выполнение займет 18695 и 12952 тика.После раскомментирования вторых соответствующих строк счетчиками длины продолжительность выполнения показывает 38377 и 25404 тика, что указывает на то, что лень не связана с наблюдаемыми явлениями.

Кажется, что издержки преобразований между типами Seq и List могут быть незначительными по сравнению с коллекциямисамо выполнение операций.

Answer 4

Чтобы добавить комментарий

В чисто функциональном смысле take не может работать со списком на месте - рассмотрим

a::b::c::d::[]

, если нам нужны только первые 2 элемента, нам нужнопо крайней мере изменить b так, чтобы мы получили

a::b::[]

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

Если вы действительно беспокоитесь о производительности, сначала выполните профиль, а затемрассмотрите возможность переключения на другой тип данных.Возможно, вам лучше использовать .Net System.Collections.Generic.List<_>, который использует многие из тех же методов, что и List и Array - http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/fsharp.powerpack/microsoft.fsharp.collections.resizearray.html

Answer 5

List to Seq - это не что иное, как создание итератора (в мире .net Enumerable) в List, поэтому, по сути, это не операция, которая вызовет большую часть проблем с производительностью (она просто создает конечный автомат, содержащий состояниео котором является текущий элемент в списке, который должен быть «yield», и увеличивать его, когда запрашивается больше элементов).С другой стороны, преобразование Seq (который будет иметь некоторую базовую коллекцию, из которой он генерирует значения) в List - это то же самое, что итерация списка и создание из него нового списка, так что это может занять много времени и памяти в случае, еслисписок достаточно длинный.

Что касается использования этих операторов, то одним из возможных подходов было бы объединить все ваши операторы последовательности (аналогично запросам linq, когда ваш вид создает конвейер, через который обрабатываются элементы коллекции).один за другим), а затем, в конце концов, если вам нужно, вы можете создать список из результирующего Seq, так как список создается в конце всех операций фильтрации, отображения, выполнения и т. д. в seq, и когда окончательные данные готовы, вы преобразуете егок списку.Создание промежуточных списков не будет работать хорошо и приведет к проблемам с производительностью.