tại sao việc chèn này vào heap nhanh hơn chèn vào danh sách chưa được sắp xếp?

Question

Sau khi chèn 100000000 phần tử vào heap của tôi và danh sách chưa được phân loại, có vẻ như việc chèn vùng heap thực sự nhanh hơn (12 giây so với 20 giây). Tại sao điều này? Tôi tin rằng chèn đống là O(logn) trong khi chèn danh sách chưa được phân loại là O(1). Tôi cũng nhận thấy rằng việc triển khai chèn heap của tôi không thực sự mở rộng với số lượng đầu vào. Điều này cũng làm tôi bối rối.

Dưới đây là đoạn code mà tôi chạy:

int main() 
{ 
    clock_t unsortedStart; 
    clock_t heapStart; 

    double unsortedDuration; 
    double heapDuration; 

    int num_pushes = 100000000; 
    int interval = 10000; 

    ofstream unsorted ("unsorted.txt"); 
    ofstream heap ("heap.txt"); 

    UnsortedPQ<int> unsortedPQ; 
    HeapPQ<int> heapPQ; 

    unsortedStart = clock(); 

    for (int i = 0; i < num_pushes; ++i) 
    { 
     if (i % interval == 0) { 
      unsortedDuration = (clock() - unsortedStart)/(double) CLOCKS_PER_SEC; 
      unsorted << unsortedDuration << " " << i << endl; 
     } 

     unsortedPQ.insertItem(rand() % 100); 
    } 

    heapStart = clock(); 
    for (int i = 0; i < num_pushes; ++i) 
    { 
     if (i % interval == 0) { 
      heapDuration = (clock() - heapStart)/(double) CLOCKS_PER_SEC; 
      heap << heapDuration << " " << i << endl; 
     } 
     heapPQ.insertItem(rand() % 100); 
    } 
    return 0; 
} 

này là việc thực hiện đống chèn (sử dụng std::vector):

template <class T> 
void HeapPQ<T>::insertItem(T data) { 
    //insert into back of heap (std::vector) 
    dataArray.push_back(data); 
    int i = dataArray.size() - 1; 

    //sifts the inserted element up 
    while (i != 0 && dataArray[(i - 1)/2] > dataArray[i]) { 
     swap(dataArray[i], dataArray[(i - 1)/2]); 
     i = (i - 1)/2; 
    } 
} 

Đây là danh sách thực hiện không được phân loại của chèn (sử dụng std::list) :

//pushes element to the back of a std::list 
template <class T> 
void UnsortedPQ<T>::insertItem(T data) { dataList.push_back(data); } 

Answer 1

Việc chèn vào đống là O(logn), điều đó có nghĩa là mọi lần chèn có thể mất tối đa O(logn) bước. Nó không có nghĩa là nó phải.

Trong ví dụ chi phí trung bình của bạn khi chèn phần tử là O(1). Lý do tại sao mà?

Để đơn giản, chúng ta hãy giả sử bạn chèn chỉ 0 a và 1 s theo một thứ tự ngẫu nhiên (trong phiên bản hiện tại của bạn chỉ số 0..99 (rand() % 100) được chèn - tính toán phức tạp hơn, nhưng hành vi này vẫn như cũ). Sau 2*n yếu tố được chèn vào, sẽ có khoảng n0 s và n1 s trong heap, và heap sẽ trông như sau:

        0 
           0 0 
           00 00 
          ............... 
         0 0 0 0 0 0 0 
         11 11 11 11 11 11 11 

Vì vậy, về cơ bản, 1 s đều ở mức cuối cùng k và 0 s ở cấp độ 0..k-1.

1. nếu 1 được chèn vào, không có gì để làm (không có số 2 ở trên).
2. nếu 0 được chèn vào, có tối đa một lần hoán đổi (1 s có thể ở cấp cao hơn cấp cuối cùng, nhưng 2 cấp ở trên).

Đó là trung bình chúng tôi chỉ cần 0.5 hoán đổi và không k.

Có cùng thời gian chạy tiệm cận, tất cả đều được tính vào chi phí (được khấu hao) để chèn vào vectơ và trong danh sách. Danh sách có vẻ chậm hơn (giả định của tôi là, cho mỗi lần chèn nó cần phân bổ một phần tử trên heap qua new và đây là một hoạt động khá chậm. Các chi phí phụ thuộc vào các yếu tố khác, ví dụ như kích thước của các đối tượng được chèn vào, và do đó nó có thể thay đổi cái nào nhanh hơn).

---

Hãy xem xét kỹ hơn trường hợp của bạn, trong đó các số được tạo bởi một phân bổ đồng nhất [0..99].Sau n>>100 chèn chúng ta sẽ có những tình huống sau đây (có một số tay vẫy liên quan, nhưng các ý chính phải rõ ràng):

1. mức cuối cùng (k -thứ) của heap có n/2 yếu tố và bao gồm các con số 50..99. Vì vậy, đối với 50% số có thể (ví dụ: 50..99), không cần phải thay đổi.
2. cấp cuối cùng thứ hai (k-1 -th) của heap có n/4 yếu tố và bao gồm các số 25..49. Điều đó có nghĩa là cần 25% số có thể chính xác 1 ca làm việc.
3. mức k-2 có n/8 yếu tố và bao gồm các số 13..24.
4. Các cấp trên log 100/log 2 chỉ có 0 bên trong. Vì vậy, số ca tối đa có thể là m=log 100/log 2, độc lập với n - số lượng phần tử trong heap.

Vì vậy, tồi tệ nhất chi phí hợp cho chèn sẽ log 100/log 2, chi phí trung bình thậm chí còn nhỏ hơn:

E(insertion)=0*1/2+1*1/4+2*1/8+...<=1.0 

ví dụ: trên trung bình chúng ta chỉ còn lại ít hơn 1 thay đổi mỗi chèn.

NB: Nó không có nghĩa, đó chèn trong đống đã khấu hao chi phí O(1) - nếu bạn muốn chèn số không theo thứ tự ngẫu nhiên, nhưng trước hết tất cả 99 s, sau đó 98 s, ..., sau đó 0 s bạn sẽ có chi phí O(log n) cho mỗi lần chèn.