안정적인 구현을 위해 FingerTree를 충분히 사용하지 않는 이유는 무엇입니까?

Question

얼마 전에 an article on FingerTrees (an accompanying Stack Overflow Question 참조)을 가로 질러 아이디어를 제기했습니다. 나는 마침내 그 (것)들을 이용하는 이유를 찾아 냈다.

제 문제는 Data.FingerTree package에 가장자리가 약간 부식 된 것 같습니다. 또한 데이터 구조 re-implements을 사용하는 컨테이너 패키지의 Data.Sequence은 (더 나은) 버전 일 수는 있지만 내보낼 수는 없습니다.

이 구조가 이론적으로 유용하기 때문에 실제 사용이나 관심을 많이 얻지는 못하는 것 같습니다. FingerTree가 실제적인 문제로 유용하지 않다는 사실을 사람들에게 알았습니까?

---

자세한 설명 :

내가 좋은 연결의 속성을 가진 데이터 구조를 유지 텍스트를 작성에 관심이 있어요. 분류 된 단편에서 HTML 문서를 작성하는 방법을 생각해보십시오. 대부분 미리 빌드 된 솔루션은 바이트 테스트를 사용하지만 실제로 유니 코드 텍스트를 제대로 처리하는 것이 필요합니다. 내 계획은 DataText 조각을 FingerTree에 쌓는 것입니다.

또한 Data.Vector에서 (오프셋, 길이) 조작을 사용하여 복사하지 않고 슬라이스를 가져 오는 트릭을 빌리고 싶습니다. Data.Text.Text는 데이터 유형에 내장되어 있지만 효율적인 uncons 및 unsnoc 처리에만 사용됩니다. FingerTree에서이 정보는 매우 쉽게 v 또는 주석이 될 수 있습니다.

Answer 1

특히 손가락 나무에 대한 질문에 대답하기 위해 어레이에 비해 상대적으로 높은 고정 비용을 가지며 효율적인 연결을 달성하는 다른 방법보다 복잡하다는 것이 문제라고 생각합니다. 빌더는 청크를 추가하기위한보다 효율적인 인터페이스를 가지고 있으며 일반적으로 쉽게 사용할 수 있습니다 (@ informatikr의 답변에있는 링크 참조). Data.Text.Lazy이 청크의 링크 된 목록으로 구현되고 빌더에서 Data.Text.Lazy을 작성한다고 가정 해보십시오. 청크가 많거나 (아마 50 개 이상) 목록의 끝 부분에있는 데이터에 반복적으로 액세스하지 않는 한 핑거 트리의 높은 일정한 비용은 아마도 가치가 없습니다.

Data.Sequence 구현은 성능상의 이유로 전문화되었으며 fingertree 패키지에서 제공하는 전체 인터페이스만큼 일반적이지 않습니다. 그것이 수출되지 않는 이유입니다. Sequence 이외의 다른 용도로는 사용할 수 없습니다.

상당히 많은 추상화 장벽이 있기 때문에 monoidal 주석을 실제로 사용하는 방법에 관해서는 많은 프로그래머가 상실한 것으로 생각됩니다. 많은 사람들이 다른 데이터 유형에 비해 유용 할 수있는 방법을 모르기 때문에 사용하지 않을 것입니다.

내가 word numbers (part2, part3, part4)에 정 치에 산의 블로그 시리즈를 읽을 때까지 나는 정말 그것을 얻을하지 않았다. 아이디어가 실용적인 코드에서 확실히 사용될 수 있다는 증거입니다.

부분 결과를 검사하고 효율적인 추가가 필요한 경우 핑거 트리를 사용하는 것이 빌더보다 낫을 수 있습니다. 빌더의 구현에 따라, Text으로 변환하고, 빌더에 더 많은 항목을 추가하고, Text으로 다시 변환하는 등 많은 반복 작업을 마칠 수 있습니다. 그러나 이는 사용 패턴에 따라 달라집니다.

내 splaytree 패키지는 모노 모양의 주석이 포함 된 스플레이 트리를 제공하며 여러 가지 구조가이 패키지를 기반으로합니다. 스 플레 그 자체 이외에, Set과 RangeSet 모듈은 더 많거나 적은 완벽한 API를 가지고 있습니다. Sequence 모듈은 주로 테스트 용 스켈레톤입니다. 당신이 찾고있는 것에 대한 "배터리 포함"해결책은 아니지만 (다시, @ informatikr의 답은 그것들을 제공합니다), 단선 주석을 실험하고 싶다면 Data.FingerTree보다 유용 할 수 있습니다. 모든 요소를 ​​순차적으로 (또는 계속해서 끝까지 또는 유사한 방향으로) 순회하는 경우 분출 트리가 불균형해질 수 있지만 추가 및 조회가 인터리브 된 경우 성능이 우수 할 수 있습니다.

Answer 2

귀하의 손가락 트리 질문을 무시하고 귀하의 추가 설명에만 응답 : Data.Text.Lazy.Builder 또는 특히 HTML을 구축하기 위해 blaze-html을 조사 했습니까?

둘 모두 빠른 연결을 허용합니다. 슬라이싱의 경우 문제를 해결하는 것이 중요하다면 이상적인 성능이 아닐 수도 있습니다.

Answer 3

존 라토 (John Lato)의 대답 외에도 손가락 나무의 성능에 대한 몇 가지 구체적인 내용을 추가 할 것입니다.

광범위한 개요는 다음

• Data.Sequence 큰 정수 인자와 근성을 갖는다 (모두 데이터 구조는 O (1) 점근가)리스트의 정면에 접근 할 때 거의 빨리 []로는 (Data.Sequence의 로그 점근선이 []의 선형 점근선을 휩쓸고있는) 다른 곳에서는 훨씬 빠릅니다.

• Data.FingerTree은 Data.Sequence과 동일한 점성 계수를 갖지만, 약 1 배 정도 느리다.

목록과 마찬가지로 손가락 트리는 요소 당 메모리 오버 헤드가 높기 때문에 더 나은 메모리와 캐시 사용을 위해 청킹과 결합해야합니다. 실제로 몇 가지 패키지가 이것을 수행합니다 (yi, trifecta, rope). Data.FingerTree이 성능면에서 Data.Sequence에 가까워 질 수 있다면 유형이 표시되어 손가락 모양의 트리가 Data.Text 값으로 구현되기를 바랍니다. 이러한 형식은 Data.Text.Lazy의 스트리밍 동작을 잃지 만 향상된 임의 액세스 및 연결 성능의 이점을 얻을 수 있습니다. (마찬가지로, 나는 Data.ByteString.Sequence 및 Data.Vector.Sequence을보고 싶은 것입니다.)

장애물을 지금이 구현하려면 손가락 나무의 더 효율적 및 일반적인 구현 (I이 더 토론하는 곳 바로 아래 참조)이 존재한다는 것입니다. Data.Text.Sequence의 효율적인 구현을 위해서는 Text에 특화된 손가락 트리를 완전히 다시 구현해야합니다. 이 완전히 다시 구현 된 목록 인 Text을 전문으로합니다. 안타깝게도 핑거 트리는 목록 (특히 concatenation!)보다 훨씬 복잡하므로이 작업은 상당한 양입니다.

• 전문 손가락 나무가 큰, 그러나 많은 작업 (예 : Data.Text.Sequence) 큰 수 있지만에서 것이다
• 손가락 나무를 청크 구현 : 나는 대답은 그것을보고 그래서

  Data.FingerTree의 성능이 좋지 않다는 것을 의미합니다. 일반적인 경우에 청크리스트에 대한 실행 가능한 대안이되지 못합니다.

• 빌더 및 청크 목록은 청크 핑거 트리의 많은 이점을 얻을 수 있으므로 일반적인 경우에 충분합니다.
• 흔하지 않은 경우 빌더와 청크 목록으로 충분하지 않은 경우 우리는 우리의이를 닦고 청크 핑거 나무의 가난한 상수 요소 (예. yi와 trifecta에서). ,

  • 척도 유형 Int으로 전문화되어 효율적이고 일반적인 손가락 트리 Data.Sequence 및 Data.FingerTree 간의 성능 차이의 대부분

    -

  장애물 Data.Sequence 인해 두 최적화이고 따라서 계수 조작은 효율적인 정수 연산으로 컴파일됩니다.

• The measure type is unpacked into the Deep constructor은 트리 작업의 내부 루프에서 포인터 역 참조를 저장합니다.

이 data families for generic unpacking를 사용하고 GHC의 inliner 및 specialiser를 이용하여 Data.FingerTree의 일반적인 경우 이러한 최적화를 적용하는 것이 가능하다 - 거의 Data.Sequence의 최대 일반적인 손가락 트리의 성능을 제공합니다 내 fingertree-unboxed package를 참조하십시오. 그들이 인스턴스를 많이 정의해야하기 때문에,

• data families for generic unpacking is unpleasant for the user : 불행하게도, 이러한 기술은 몇 가지 중요한 문제가있다. 이 문제에 대한 명확한 해결책은 없습니다.

• 핑거 나무는 GHC의 전문가가 잘 처리하지 않는 다형성 재귀를 사용합니다 (1, 2). 즉, 측정 유형에 대해 충분한 전문화를 얻으려면 많은 수의 INLINE pragma가 필요하므로 엄청난 양의 코드가 GHC에서 생성됩니다.

이러한 문제로 인해 나는 Hackage 패키지를 출시하지 못했습니다.