C++ набор медленнее?

Question

Мне пришлось использовать структуру данных, которая сохраняет элементы в некотором порядке, такие как Я могу запросить наименьший элемент, а также вставить новые элементы эффективно. Поэтому я выбрал set (C++ stl). Требуется log(n) раз вставка и log(n) для удаление наименьший элемент.

Так я написал следующую программу:

#include<iostream> 
#include<set> 
#include<stdio.h> 
using namespace std; 
int main() 
{ 
    set<int>s1,s2; 
    set<int>::iterator it; 
    int tmp,i; 
    for(i=1;i<=1000000;i++)s1.insert(i); 
    for(i=1;i<=1000000;i++) 
    { 
     it=s1.begin(); 
     s2.insert(*it); 
     s1.erase(s1.begin()); 
    } 
return 0; 
} 

но это занимает 1.67 секунд на моей машине (я сердечник 3) я ожидал гораздо меньше O(log(1000000)*1000000) т.е. 2*10^7 я пытался очереди приоритетов также он дал мне такая же производительность. Так что я должен реализовать свою собственную кучу, чтобы сделать ее быстрее или есть какой-то другой способ?

Answer 1

Что вы делаете, это одна из самых сложных вещей, которую может пострадать сбалансированное двоичное дерево поиска. Вы сохраняете вставные элементы в правой части дерева и продолжаете удалять элементы из большей части левой стороны, заставляя дерево всегда перебалансироваться.

Answer 2

Существует шаблон под названием priority_queue, который обрабатывает рабочую нагрузку, которую вы описали намного лучше. Это максимальная куча, а не мини-куча, но она позволяет передавать пользовательский компаратор в качестве аргумента шаблона. Он реализуется путем сохранения порядка кучи на базовом контейнере, который обычно равен vector.

set реализован как сбалансированное двоичное дерево. Это означает, что каждая вставка и запрос имеют отношение к log2 (n) с очень нелокальным доступом к памяти; подумайте об этом как о провале кеша log2 (n). Кучи делают намного лучше. Это особенно грубо для современных процессоров, и это не редкость, если вы приручите свои шаблоны доступа к памяти.

Answer 3

class heap 
{ 
    int heap[1000001],siz; 
    public: 
    int ini() 
    { 
     siz=0; 
    } 
    int size() 
    { 
     return siz; 
    } 
    int top() 
    { 
    return heap[1]; 
    } 
    void insert(int num) 
    { 
    siz++; 
    heap[siz]=num; 
    int pos=siz,tmp; 
    while(pos>1) 
    { 
    if(heap[pos]<heap[pos/2]) 
    { 
     tmp=heap[pos]; 
     heap[pos]=heap[pos/2]; 
     heap[pos/2]=tmp; 
    } 
    else break; 
    } 
    } 
    void del() 
    { 
    if(siz==1) 
    { 
    siz=0; 
    return; 
    } 
    heap[1]=heap[siz]; 
    siz--; 
    int pos=1,tmp; 
    while(2*pos<=siz) 
    { 
    if(2*pos+1<=siz) 
    { 
     if(heap[2*pos]<=heap[2*pos+1]) 
     { 
      if(heap[pos]>heap[2*pos]) 
      { 
     tmp=heap[pos]; 
     heap[pos]=heap[2*pos]; 
     heap[2*pos]=tmp; 
     pos=2*pos; 
      } 
      else break; 
     } 
     else if(heap[2*pos+1]<=heap[2*pos]) 
     { 
      if(heap[pos]>heap[2*pos+1]) 
      { 
     tmp=heap[pos]; 
     heap[pos]=heap[2*pos+1]; 
     heap[2*pos+1]=tmp; 
     pos=2*pos+1; 
      } 
      else break; 
     } 
    } 
    else 
    { 

     if(heap[pos]>heap[2*pos]) 
     { 
      tmp=heap[pos]; 
      heap[pos]=heap[2*pos]; 
      heap[2*pos]=tmp; 
      pos=2*pos; 
     } 

     else break; 

    } 
    } 
    } 

}; 
int main() 
{ 
    int i,tmp; 
    heap a1,a2; 
    a1.ini();a2.ini(); 
    for(i=1;i<=1000000;i++)a1.insert(i); 
    for(i=1;i<=1000000;i++) 
    { 
     tmp=a1.top(); 
     a2.insert(tmp); 
     a1.del(); 
    } 
} 

я реализовал свою собственную кучу и сделал то же самое, он работает в настоящее 0.25 seconds.I предполагаю, что это на самом деле выделение и освобождение памяти, которая делает набор медленнее.