함수 프로그래밍 컨텍스트에서 불변 목록으로 일정한 길이의 시간 상수 가져 오기

Question

현재 주어진 목록의 길이를 기반으로 계산해야하는 문제에 직면하고 있습니다. 목록의 모든 요소를 ​​반복하여 크기를 알면 오히려 큰 목록을 사용함에 따라 성능이 크게 저하 될 수 있습니다.

문제에 대한 제안 된 접근 방법은 무엇입니까?

전화 사이트에서 계산할 필요없이 크기를 미리 알 수 있으므로 목록과 함께 항상 크기 값을 전달할 수 있다고 생각합니다. 그러나 그 방법은 약한 것처럼 보입니다. 나는 또한 각 노드가 목록의 크기를 속성으로 갖는 목록 유형을 정의 할 수 있지만 표준 목록에 대한 프로그래밍 언어의 라이브러리가 제공하는 영향력을 잃어 버리게됩니다.

당신은 어떻게 일상 업무에서 이것을 처리합니까?

현재 F #을 사용 중입니다. 나는 .NET의 변경 가능한 (배열)리스트를 사용할 수 있다는 것을 알고 있는데, 이는 문제를 해결할 것이다. 그러나 나는 순수하게 불변의 기능적 접근법에 관심이 있습니다.

Answer 1

내장 된 F #의 목록 유형 길이의 캐싱을 가지고이 일부 영리한 방법으로 그를 추가 할 수있는 방법이 없기 때문에 자신의 유형을 정의해야하지 않습니다 . 필자는 기존 F # list 유형의 래퍼를 작성하는 것이 가장 좋은 방법이라고 생각합니다.

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 

: 당신은 목록을 포장 할 때 실제로 (svick의 구현으로) 복사하지 않습니다,하지만 래퍼 쉽게 Length 속성을 캐시 할 수 있습니다 -

이 방법을 사용하면 명시 적 변환을 방지 할 수 있습니다 래퍼를 사용하는 가장 좋은 방법은 표준 List 모듈의 함수를 사용하기 전에 표준 F # 목록에서 LengthList을 만들고 LengthList.toList (또는 단지 List) 속성을 사용하여 LengthList.ofList을 사용하는 것입니다.

그러나 코드의 복잡성에 따라 다릅니다. 몇 군데에만 길이가 필요한 경우 별도로 유지하고 튜플 list<'T> * int을 사용하는 것이 더 쉽습니다.

Answer 2

왜 길이를 줄이는 것이 약한 접근인지는 알 수 없습니다. 다음과 같이 해보십시오 (하스켈) :

등등. 이것이 라이브러리 나 모듈에 있다면, 생성자 NList을 내보내지 않아도 안전하다고 생각할 수 있습니다.

GHC를 암기 용 length으로 강제 할 수도 있지만, 방법이나시기는 확실하지 않습니다.

Answer 3

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)) 

Answer 4

어떻게 일상 업무에서이 문제를 처리합니까?

일상적인 문제가 아니기 때문에 우리는 그렇지 않습니다. 그것은 아마 제한된 영역에서 문제처럼 들린다.

최근에 목록을 작성한 경우 이미 O (N) 작업을 완료했을 가능성이 있으므로 목록을 길게 가져 오는 것이 중요하지 않습니다.

매우 큰 목록을 많이 만들고 (분명히 변경하지는 않지만 도메인/알고리즘에 사용되는 목록의 머리글을 변경한다는 의미입니다), 레퍼런스 헤드 * 길이 튜플의 측면에 사전을 준비하고 길이를 물어볼 때 사전을 참조하는 것이 좋습니다. 필요할 때 실제 작업을 수행하지만 나중에 캐싱 결과에 대해서는 묻습니다. 같은 목록).

마지막으로, 지속적으로 목록을 업데이트하고 끊임없이 길이를 컨설팅해야하는 알고리즘을 실제로 다루는 경우 자신의 목록과 같은 데이터 형식을 만듭니다 (예,지도를 작성해야합니다./필터 및 기타).

(매우 일반적으로, 일반적으로 내장 데이터 구조를 99.99 %의 시간 내에 사용하는 것이 가장 좋습니다.) 알고리즘을 개발할 때 또는 0.01 % 고도로 최적화되면, 거의 항상 당신은 당신이 작업하고있는 정확한 문제를 해결하기 위해 고안된 커스텀 데이터 구조를 사용하고 내장 데이터 구조를 포기할 필요가 있습니다. 위키 백과 또는 오카사키 (Okasaki)의 "Purely Functional 그럴 경우 아이디어와 아이디어를 얻으려는 데이터 구조 "라고 말합니다.하지만이 경우는 거의하지 않습니다.)