지도로 작업 할 때 요소를 삽입 할 때와 동일한 순서로 반복 할 수있는 요소를 선호하는 경향이 있습니다. 그것은 그들이 결정 론적이고 쉽게 테스트 할 수있게합니다. 이러한 이유와 다른 이유로 저는 항상 Java에서 LinkedHashMap을 망각했습니다.빠른 검색 및 삽입 순서를 지원하는 영구 데이터 구조 (스칼라에서)?
FP 세계에서 조회를 위해지도 위에 나무를 선호합니다. 사실, 스칼라에는 ListMap이라는 LinkedHashMap의 불변 버전이 있지만 해시를 사용하지 않으며 실제로 사용하기에는 너무 느립니다.
불변의 장점을 얻고 싶다면 삽입 순서를 기억하고 빠른 조회를하는 데이터 구조에 대해 어떻게 갈증을 뺄 수 있습니까? 누군가 도서관에서 뭔가를 어딘가에 썼습니까?
Finit 맵 (해시 테이블, 사전)은 일반적으로 올바른 순서 반복을 보장하지 않습니다. 그것은 도서관과 언어의 대부분을위한 공통점입니다. 따라서 반복 할 때 삽입 순서 반복을 지원하는 추가 데이터 구조에 키 (포인터)를 저장하도록 권장합니다. 따라서 헬퍼 배열을 반복하고 finit 맵을 검색하여 항목에 대한 세부 정보를 얻을 수 있습니다.
finit 맵에 관해서. 스칼라 (Closure와 마찬가지로)는 해시 테이블 구현을 위해 HAMT (Hash Array Mapped Tree) 데이터 구조를 사용합니다. 그리고 그것은 정말로 빠릅니다. 또한 finite map으로 사용할 수있는 Fast Mergeble Integer Maps (C. Okasaki)가 있습니다. 그리고, 당신은 나무에 대해 옳았습니다. Haskell은 Red-Black tree를 finit map implementation으로 사용합니다. 그것도 빠르며 거의 O(1)입니다. 예를 들어, JVM 플랫폼에서 그러한 맵에 가능한 모든 키를 저장하려면 2147483647 노드를 할당해야합니다. 따라서 전체 트리를 살펴 보시려면 log_2(2147483647)=31 걸음 만 있으면됩니다. 그렇게 천천히, 응?
이것이 내가 얻을 수있는 가장 가까운 것 같습니다. 어쩌면 하나의 데이터 구조에 대해 너무 많이 묻고있었습니다. 방금 Java에서 LinkedHashMap에 버릇이 있습니다. 결국, 내 특정 문제에 대해 나는 필자가 룩업 (lookup) 할 필요가 없다는 것을 깨달았고 구조를 쌍 목록 (List of pairs)으로 단순화했다. –