매우 큰 LinkedList에 삽입해야합니다. 요소는 고속 액세스 HashMap에 보관됩니다.
목록을 순서대로 유지하는 것이 중요합니다 (키의 자연 순서가 아닙니다).엘리먼트가 주어 졌을 때 O (1)에 추가 된 자바 컬렉션의 링크드 목록은 무엇입니까?
링크 된 목록 노드를 해시 한 다음 노드에 직접 삽입 할 수 있다고 생각했습니다.지도에서 노드를 가져오고 연결된 목록 == 상수 시간에 삽입하십시오.
그러나 내가 할 수있는 Java 컬렉션을 찾지 못했습니다.
현재 위의 요구 사항을 충족하지 않는 LinkedHashMap을 사용하고 있습니다. LinkedList의 각 삽입 후 정렬해야하는 경우
:-)
감사 asaf, 나는 당신이 시간 복잡도를 가진 정렬 알고리즘을 얻을 것이라는 점을 의미 당신이 이러한 데이터 구조를 찾을 수있을 것입니다 의심 O (n)은 불가능한 것으로 입증되었습니다. (정렬에서 가장 낮은 경계는 O (n log n)입니다.) 삽입시 얻을 수있는 최상의 결과는 O (log n)입니다.
그런 다음 TreeMap 데이터 구조를 사용할 수 있습니다.
"목록을 순서대로 유지하는 것이 중요합니다"라고 말하면 효과적으로 O (n)의 최상의 성능을 가진 insertion sort을 수행합니다. 또한 해시의 순서가 기본 해시 테이블의 크기에 따라 달라 지므로 해싱과 정렬을 혼동하지 않아야합니다. (해시를 삽입하려면 삽입하려는 노드의 전신 또는 후속 노드를 알고있는 경우에만 유용합니다)
'O (n)의 최상의 케이스 - 퍼포먼스를 가진 삽입 정렬을 효과적으로합니다. -리스트가 저장되어 있다면, 이진 검색은 삽입을 찾는 데 사용될 수 있습니다 인덱스 및 삽입 복잡성은 O (log n)입니다. –
복잡성이 O (log n) 인 이진 검색은 인덱싱 된 요소에 대한 임의 액세스의 복잡성이 O (1) 인 경우에만 가능합니다. 이는 링크 된 목록의 경우가 아닙니다. – jarnbjo
저자는 무작위 요소 액세스에 O (1) 복잡성을 허용하는 목록 요소에 대한 색인 된 액세스를 위해 전용 HashMap을 사용한다는 정보를 제공했습니다. –
TreeSet 또는 TreeMap을 사용하십시오. 삽입물은 O (log (n))이지만 LOG를 의미한다는 것을 기억하십시오. 따라서 40 억 개의 항목이있는 경우 런타임은 O (32)입니다. 2 항목이있는 경우 삽입하려면 O (64)가 필요하므로 큰 문제는 아닙니다.
귀하의 목록을 순서대로 보관해야한다고 말했지만 키의 자연스러운 순서가 아니라고 말하면 삽입 주문을 보존해야한다는 말을 듣고 있습니다.
하지만 LinkedHashMap이 사용자의 요구 사항을 충족시키지 않는 이유를 알 수 없습니다.
LinkedHashMap이 실패한 것을 설명 할 수 있습니까?
재생 해 주셔서 감사합니다. 물론 나는 일반적으로 n 개의 원소를 o (n)로 정렬하지 않는다. ... 나는 서버로부터 순서가 정해진리스트를 얻는다. 그때 나는 각 항목에 필요한 정보를 얻기 위해 해시를 사용하여 목록의 하위 집합을 표시하고, 때로는 목록을 거치고 원래 순서대로 표시를 재설정합니다. 그런 다음 'y 다음에 항목 추가'와 같은 업데이트가 표시됩니다. 저는 주문을 보존하기를 원하지만 (현재는 게재 신청서가 아닙니다), 전체 목록을 스캔하는 데 비용을 지불하고 싶지는 않습니다. 내 자신의 DS를 올바르게 작성했다면 x를 얻고, 이중 연결 목록을 사용하여 y를 추가합니다. – Asaf
흠, 어떻게 코멘트에 개행합니까? 그 죄송합니다. – Asaf
어쩌면 데이터 구조와 함께 질문에 예제를 추가해야 할 것입니다. 추가 입력이 필요한 경우 어디에서 언제 어떻게 변경해야하는지 알 수 있습니다. (적어도 나를 위해서) 따라하기가 어렵습니다 ... – MicSim