삽입시간이 매우 빠른 구조

StackOverflow https://stackoverflow.com/questions/8409269

문제

나는 매우 빠른 삽입이 가능한 정렬된 데이터 구조를 찾고 있습니다.이것이 필요한 유일한 속성입니다.데이터는 최상위 요소에서만 액세스 및 삭제됩니다.

더 정확하게 말하면 두 가지 구조가 필요합니다.

1) 첫 번째 구조에서는 int 값을 사용하여 순서대로 삽입할 수 있어야 합니다.삽입이 완료되면 다음과 같습니다. 삽입된 요소의 순위를 보고합니다..

2) 두 번째 구조는 지정된 랭크에 삽입이 가능해야 합니다.

저장될 요소의 수는 수천 또는 수만 개가 될 가능성이 높습니다.

[편집] 볼륨 가설을 수정해야 합니다.어떤 순간에 정렬된 구조의 크기가 수만 범위에 있을 가능성이 높더라도 총 삽입 횟수는 실행당 수천만에 이를 가능성이 높습니다.

O(1)의 삽입 시간은 좋지만 O(log(log(n)))도 매우 수용 가능합니다.현재 나는 첫 번째 구조에만 흥미로운 후보를 가지고 있지만 log(n)에 있거나 삽입 순위를 보고하는 기능(필수)이 없습니다.

도움이 되었습니까?

해결책

형태는 어떻습니까? 건너뛰기 목록, 특히 링크된 기사의 '색인이 생성된 건너뛰기 목록'입니다.그러면 두 사용 사례 모두에 대해 O(lg N) 삽입 및 조회와 첫 번째 노드에 대한 O(1) 액세스가 제공되어야 합니다.

--편집하다--

O(1) 알고리즘을 생각하면 기수 기반 방법이 떠오릅니다.다음은 순위가 반환된 O(1) 삽입입니다.아이디어는 키를 니블로 나누고 해당 접두사가 있는 삽입된 모든 항목의 수를 유지하는 것입니다.불행하게도 상수는 높고(<=64 역참조 및 추가) 저장 공간은 O(2 x 2^INT_BITS)로 끔찍합니다.이는 16비트 정수용 버전이므로 32비트로 확장하는 것은 간단합니다.

int *p1;int *p2;int *p3;int *p4;
void **records;
unsigned int min = 0xFFFF;

int init(void)     {
   p1 = (int*)calloc(16,sizeof(int));
   p2 = (int*)calloc(256, sizeof(int));
   p3 = (int*)calloc(4096, sizeof(int));
   p4 = (int*)calloc(65536,sizeof(int));
   records = (void**)calloc(65536,sizeof(void*));
   return 0;
}

//records that we are storing one more item, 
//counts the number of smaller existing items
int Add1ReturnRank(int* p, int offset, int a) {
   int i, sum=0;
   p+=offset;
   for (i=0;i<a;i++)
      sum += p[i];
   p[i]++;
   return sum;
}

int insert(int key, void* data) {
   unsigned int i4 = (unsigned int)key;
   unsigned int i3= (i4>> 4);
   unsigned int i2= (i3>> 4);
   unsigned int i1= (i2>> 4);
   int rank = Add1ReturnRank(p1,0, i1&0xF);
   rank += Add1ReturnRank(p2,i2&0xF0,i2&0xF);
   rank += Add1ReturnRank(p3,i3&0xFF0,i3&0xF);
   rank += Add1ReturnRank(p4,i4&0xFFF0,i4&0xF);
   if (min>key) {min = key;}
   store(&records[i4],data);
   return rank;
}

이 구조는 O(1) GetMin 및 RemoveMin도 지원합니다.(GetMin은 즉각적이며 Remove는 Insert와 유사한 상수를 갖습니다.)

void* getMin(int* key) {
    return data[*key=min];
}

void* removeMin(int* key)  {
   int next = 0;
   void* data = records[min];
   unsigned int i4 = min;
   unsigned int i3= (i4>> 4);
   unsigned int i2= (i3>> 4);
   unsigned int i1= (i2>> 4);

   p4[i4]--;
   p3[i3]--;
   p2[i2]--;
   p1[i1]--;
   *key = min;
   while (!p1[i1]) {
      if (i1==15) { min = 0xFFFF; return NULL;}
      i2 = (++i1)<<4;
   }
   while (!p2[i2])
      i3 = (++i2)<<4;
   while (!p3[i3])
      i4 = (++i3)<<4;
   while (!p4[i4])
      ++i4;
   min = i4;
   return data;
}

데이터가 드물고 잘 분산되어 있는 경우 p4 카운터 대신 P3 레벨에 삽입 정렬을 수행합니다.유사한 값이 많을 때 최악의 경우를 더 많이 삽입하는 대신 저장 비용을 16만큼 줄일 수 있습니다.

저장 공간을 개선하는 또 다른 아이디어는 이 아이디어를 다음과 같은 것과 결합하는 것입니다. 확장 가능한 해시.정수 키를 해시 값으로 사용하고 디렉터리에 삽입된 노드 수를 유지합니다.삽입 시 관련 사전 항목에 대한 합계를 수행하는 경우(위와 같이) 여전히 큰 상수를 사용하여 O(1)이어야 하지만 저장 공간은 O(N)으로 줄어듭니다.

다른 팁

주문 통계 트리 O(LogN) 시간에 귀하의 요구에 맞는 것 같습니다. 링크

주문 통계 트리는 다음의 증강된(AugmentedDataStructures 참조) 버전입니다.
추가 연산을 지원하는 BinarySearchTree 순위를 반환하는 Rank(x) x(즉, 키가 x보다 작거나 같은 요소의 수) 및 FindByRank(k), 트리의 k 번째로 작은 요소를 반환합니다.

요소가 수만 개만 있는 경우 O(LogN) 시간과 O(1) 시간 점근적 시간 복잡도의 성능 차이는 생각만큼 크지 않습니다.예를 들어 100,000개의 요소를 고려하면 logN 방법은 16배만 느립니다.

로그(100 000) / 로그(2) = 16.6096405

이 경우 계수(구현, 오버헤드)의 차이가 실제 최적화 목표가 될 수 있습니다.멋진 데이터 구조는 일반적으로 상속 복잡성으로 인해 훨씬 ​​더 높은 오버헤드를 갖습니다(때로는 수천 배 느림).덜 사용되기 때문에 덜 세련된 구현에서 나올 가능성이 더 높습니다.

가장 좋은 것을 찾으려면 다양한 힙 구현을 벤치마킹(실제로 테스트)해야 합니다. 실제 성능.

주문한 데이터 구조가 필요합니다. 나에게는 O (n) 시간에 포함 된 모든 요소를 생성 할 수있는 것처럼 보이는 것처럼 들리 었습니다.

그러나 당신은 당신이 꼭대기 (최소한) 요소에만 액세스 할 것이라고합니다.

그것은 무엇입니까?

질문을 올바르게 이해했다면 키가 순위이고 값이 연결 목록 인 사전을 사용하는 것이 좋습니다.

키를 사용하면 순위를 가질 수 있고 연결 목록을 값으로 사용하면 O (1) 삽입 시간을 가질 수 있습니다.또한 제거로 O (1)을 가질 수 있습니다.원하는 연결 목록을 사용하여 스택 또는 대기열을 구현할 수 있습니다.

또는 O (1) 삽입 및 제거가 보장되는 이중 연결 목록을 사용할 수도 있습니다.순위를 매기려면 해당 정보를 노드 내에 포함 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top