Получение постоянной длины для получения постоянной времени с неизменяемыми списками в контексте функционального программирования

Question

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

Каковы предлагаемые подходы к проблеме?

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

Как вы, ребята, справляетесь с этимв вашей повседневной жизни?

Я сейчас использую F #.Я знаю, что могу использовать изменяемые списки .NET, которые решат проблему.Однако меня больше интересует чисто неизменный функциональный подход.

Answer 1

Встроенный тип списка F # не имеет никакого кэширования длины, и нет способа добавить это каким-то умным способом, поэтому вам нужно определить свой собственный тип.Я думаю, что написание оболочки для существующего типа F # list, вероятно, является лучшим вариантом.

Таким образом, вы можете избежать явных преобразований - когда вы переносите список, он фактически не копирует его (как в реализации svick), но оболочка может легко кэшировать свойство Length:

open System.Collections

type LengthList<'T>(list:list<'T>) =
  let length = lazy list.Length
  member x.Length = length.Value
  member x.List = list
  interface IEnumerable with
    member x.GetEnumerator() = (list :> IEnumerable).GetEnumerator()
  interface seq<'T> with  //'
    member x.GetEnumerator() = (list :> seq<_>).GetEnumerator()

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module LengthList =
  let ofList l = LengthList<_>(l)
  let ofSeq s = LengthList<_>(List.ofSeq s)
  let toList (l:LengthList<_>) = l.List
  let length (l:LengthList<_>) = l.Length

Лучший способ работы с оберткой - использовать LengthList.ofList для создания LengthList из стандартного списка F # и использовать свойство LengthList.toList (или только List) перед использованием любых функций изстандартный List модуль.

Однако это зависит от сложности вашего кода - если вам нужна длина только в нескольких местах, тогда может быть проще хранить ее отдельно и использовать кортеж list<'T> * int.

Answer 2

Как вы, ребята, справляетесь с этим в своей повседневной жизни?

Мы не знаем, потому что это не проблема в повседневной жизни. Это звучит как проблема, возможно, в ограниченных доменах.

Если вы недавно создали списки, значит, вы, вероятно, уже проделали O (N) работу, поэтому просмотр списка для получения его длины, вероятно, не имеет большого значения.

Если вы создаете несколько очень больших списков, которые не сильно «меняются» (очевидно, никогда не меняются, но я имею в виду изменение набора ссылок на заголовки списков, которые используются в вашем домене / алгоритме), то это может имеет смысл просто располагать словарь рядом с кортежами reference-to-list-head * length и обращаться к словарю при запросе длин (выполнение реальной работы по их обходу при необходимости, но кеширование результатов для будущего спрашивает о тот же список).

Наконец, если вы действительно имеете дело с каким-то алгоритмом, который должен постоянно обновлять списки в игре и постоянно сверяться с длинами, то создайте свой собственный тип данных, подобный списку (да, вам также нужно написать карту / фильтр и любые другие).

(В целом, я думаю, что лучше всего использовать встроенные структуры данных в 99,99% времени. В 0,01% времени, когда вы разрабатываете алгоритм или часть кода, которая должна быть очень высокой оптимизированный, то почти всегда вам нужно отказаться от встроенных структур данных (которые в большинстве случаев достаточно хороши) и использовать пользовательскую структуру данных, предназначенную для решения именно той проблемы, над которой вы работаете. Структуры "для идей и воплощения в этом случае. Но редко переходят к этому случаю.)

Answer 3

Я не понимаю, почему изменение длины вокруг является хрупким подходом.Попробуйте что-то вроде этого (Haskell):

data NList a = NList Int [a]

nNil :: NList [a]
nNil = NList 0 []

nCons :: a -> NList a -> NList a
nCons x (NList n xs) = NList (n+1) (x:xs)

nHead :: NList a -> a
nHead (NList _ (x:_)) = x

nTail :: NList a -> NList a
nTail (NList n (_:xs)) = NList (n-1) xs

convert :: [a] -> NList a
convert xs = NList (length xs) xs

и так далее.Если это в библиотеке или модуле, вы можете сделать это безопасно (я думаю), не экспортируя конструктор NList.

. Возможно также, что GHC можно будет принудительно заставить запоминать length, но я 'Я не уверен, как и когда.

Answer 4

В F # большинство List функций имеют эквивалентные Seq функции. Это означает, что вы можете просто реализовать свой собственный неизменный связанный список, который имеет длину для каждого узла. Примерно так:

type MyList<'T>(item : Option<'T * MyList<'T>>) =

    let length =
        match item with
        | None -> 0
        | Some (_, tail) -> tail.Length + 1

    member this.Length = length

    member private this.sequence =
        match item with
        | None -> Seq.empty
        | Some (x, tail) ->
            seq {
                yield x
                yield! tail.sequence
            }

    interface seq<'T> with
        member this.GetEnumerator() =
            (this.sequence).GetEnumerator()
        member this.GetEnumerator() =
            (this.sequence :> System.Collections.IEnumerable).GetEnumerator()

module MyList =
    let rec ofList list =
        match list with
        | [] -> MyList None
        | head::tail -> MyList(Some (head, ofList tail))