동일한 인덱스 및 값을 사용하여 정렬 된 정수 목록, 중복 없음을 유지할 수있는 데이터 구조 (또는 구조)를 찾고 있습니다. 범위.빠른 랜덤 액세스, 검색, 삽입 및 삭제를위한 효율적인 데이터 구조
나는 중요성을 거친 위해, 효율적으로 네 가지 주요 작업이 필요 O (1)에 I가 1 어레이를 사용하여 지정된 인덱스
에서의 값을 삭제하는 인덱스
링크 된 목록에는 O (삽입) 및 삭제 (일단 노드가 있음)가 있지만 1과 2는 O (N)이므로 이득이 무효화됩니다.
1과 2를 O (1)로 바꾸지 만 3와 4를 훨씬 더 비싼 연산으로 바꾸는 두 개의 배열 [index] = value와 b [value] = index를 유지하려고했습니다.
더 적합한 데이터 구조가 있습니까?
키를 값에 매핑하는 데 red-black tree을 사용합니다. 이것은 1, 3, 4에 대한 O (log (n))를 제공합니다. 또한 정렬 된 순서로 키를 유지합니다.
2의 경우 해시 테이블을 사용하여 값을 키에 매핑하면 O (1) 성능을 얻을 수 있습니다. 또한 red-black 트리에서 키를 추가 및 삭제할 때 해시 테이블을 업데이트하기 위해 O (1) 오버 헤드를 추가합니다.
나는 그것을 어딘가에서 읽었다는 것을 알고 있었다 : http://www.cs.tau.ac.il/~wein/publications/pdfs/rb_tree.pdf – Javier
좋은 소리. 나는 그것을 시도해 보겠습니다. – Leonel
@Javier : Red-black trees는 절대로 O (1) 액세스를 상각하지 않았습니다. 붉은 검정 나무는 나무의 원소를 읽을 때 실제로 아무 것도하지 않으므로 상환하지 않습니다. 이진 트리가 동적이거나 아니어도 트리의 임의의 요소에 액세스하기 위해 o (n log n)을 얻을 수 있습니다. –
이진 검색에서 정렬 된 배열을 사용하는 방법은 어떻습니까?
삽입 및 삭제 속도가 느립니다. 그러나 C 나 C++를 사용하고 있다면 memcpy()를 호출하여 데이터가 일반 정수가되도록 최적화 할 수 있습니다. 배열의 최대 크기를 알고있는 경우 최대 크기로 미리 할당 할 수 있으므로 배열 사용 중 메모리 할당을 피할 수도 있습니다.
"최상의"접근법은 저장해야하는 항목 수와 찾는/삭제할 빈도에 따라 다릅니다. O (1) 값으로 액세스 할 수있는 정렬 된 배열을 거의 삽입하거나 삭제하지 않는 것이 좋습니다. 그러나 일을 자주 삽입하고 삭제하면 이진 트리가 배열보다 더 좋을 수 있습니다. 작은 n만큼 배열은 어쨌든 나무를 능가합니다.
저장소 크기가 문제가되면 배열이 나무보다 좋습니다. 나무는 또한 저장하는 모든 항목에 메모리를 할당해야하며 작은 값 (정수) 만 저장하면 메모리 할당의 오버 헤드가 커질 수 있습니다.
정렬 된 배열이나 트리를 메모리 (de) 할당과 함께 삽입/삭제하면 더 빠르게 정수를 복사 할 수 있습니다.
트리 맵은 어떻습니까? 설명 된 작업에 대한 log (n).
나는 균형 잡힌 이진 트리를 많이 좋아한다. 해시 테이블이나 다른 구조보다 느린 경우도 있지만 훨씬 더 예측 가능합니다. 일반적으로 모든 작업에 대해 O(log n)입니다. Red-black tree 또는 AVL tree을 사용하시기 바랍니다.
해시 테이블에서 데이터 정렬을 유지하지 않음을 의미합니다. –
죄송합니다. 주문한 부품을 보지 못했습니다 ... 문제를 해결했습니다. – Zifre
사용하는 언어를 모르지만 Java 인 경우 LinkedHashMap 또는 유사한 컬렉션을 활용할 수 있습니다. 그것은 List와 Map의 장점을 모두 가지고 있으며, 대부분의 작업에 일정한 시간을 제공하고, 코끼리의 메모리 사용량을 가지고 있습니다. :)
Java를 사용하지 않는 경우 LinkedHashMap이라는 아이디어는 문제의 사용 가능한 데이터 구조에 여전히 적합 할 수 있습니다.
LinkedHashMap을 사용하여 어떻게 임의의 요소를 가져 오시겠습니까? – Hengameh
당신은 http://msdn.microsoft.com/en-us/library/f7fta44c.aspx이
메모리 사용량과 삽입/제거 속도가 서로 다릅니다. SortedList는 SortedDictionary보다 적은 메모리를 사용합니다. SortedList가 정렬 된 데이터에서 한꺼번에 채워지면 SortedDictionary보다 빠릅니다. 따라서 상황에 따라 어떤 것이 가장 적합한 지에 따라 다릅니다.
또한 링크 된 목록에 대한 인수는 삽입에 대한 O (1) 일 수 있으므로 실제로 유효하지 않지만 삽입 지점을 찾기 위해 목록을 탐색해야하므로 실제로 그렇지 않습니다.
RB-trees를 사용하여 2를 달성하는 방법은 무엇입니까? 모든 삽입/삭제 작업을 통해 자녀를 셀 수 있습니다. 이것은 이러한 작동이 더 오래 지속되는 것을 의미하지는 않습니다. 그런 다음 트리를 내려 와서 i 번째 요소를 찾으려면 log n 시간이 가능합니다. 그러나 자바 나 stl에서는이 메소드를 구현하지 않았다.
배열 액세스에 벡터를 사용하십시오.
지도를 벡터의 첨자에 대한 검색 색인으로 사용하십시오.
어떤 언어를 사용하고 있습니까? –
정말로 중요하지는 않지만, C++입니다. – Leonel
그것은 중요합니다. 모든 언어가 동일한 데이터 구조를 제공하는 것은 아닙니다. 예를 들어,이 특별한 문제는 C Judy 배열이나 C# CPTrie로 매우 효율적으로 해결할 수 있습니다. (또는 물론, Ayman이 제안한 것과 같은 일종의 균형 이진 트리입니다.) – Qwertie