C++ - 將項目添加到排序陣列的最快方法

Question

我有一個包含大約200 000個項目的數據庫，按用戶名排序。現在，當我將一個項目添加到數組結尾並調用我的快速排序函數對該數組進行排序時，幾乎需要一秒進行排序，這是不可接受的。絕對有一些優化可以完成。例如，如果我順序比較從n-1到0的每個字符串，然後相應地移動項目，性能要大得多。

其他的想法是，我可以執行二進制搜索從0到n-1，以及不是事實上的搜索，但類似的東西利用我已經排序的數組。然而，我沒有寫出一個適當的函數，它會返回一個索引，我的新元素應該被放置。

void quick_sort(int left, int right) 
{ 
    int i = left, j = right; 
    if (left >= right) return; 
    char pivotC[128]; 
    DataEntry *tmp; 

    strcpy_a(pivotC, sizeof pivotC, User[(left + right)/2]->username); 

    while (i <= j) 
    { 
     while (StringCompare(User[i]->username, pivotC)) 
      i++; 
     while (StringCompare(pivotC, User[j]->username)) 
      j--; 
     if (i <= j) 
     { 
      tmp = User[i]; 
      User[i] = User[j]; 
      User[j] = tmp; 
      i++; 
      j--; 
     } 
    } 
    if (left < j) 
     quick_sort(left, j); 
    if (i < right) 
     quick_sort(i, right); 
} 

任何幫助，非常感謝。

Answer 1

int add(Container c, int r, int l, Unit t) 
{ 
    if(c[r]>t) 
     return r; 
    if(c[l]<t) 
     return l+1; 
    if(c[r]==c[l]) 
    { 
     if(c[r]==t) 
      return -1; 
     return -1; 
    } 
    int m=(r+l)/2; 
    if(c[m]==t) 
      return -1; 
    if(c[m]>t) 
      return add(c,m,l,t); 
    if(c[m]<t) 
      return add(c,r,m,t); 
} 

它可能會給你你需要添加索引...我希望它可以help.It假設你不需要它的時候已經增加。

Answer 2

簡單，直接的方法原因二進制搜索太主流了。只需要幾行：

int where_to_add(int array[], int element) 
{ 
    int i; 
    for (i = length; i >= 0 && array[i-1] > element; i--); 
    return i; 
} 

讓我知道這是不是你要找的人

Answer 3

你可以做二進制搜索像這樣的答案。這裏你可以假設，如果val爲字符串然後使用字符串比較函數進行比較，並將int AR []設置爲字符串，或者將它們映射爲整數。由於數組排序，我認爲二進制搜索將會給你最好的性能。

int bsearch(int AR[], int N, int VAL) 
{ 
    int Mid,Lbound=0,Ubound=N-1; 

    while(Lbound<=Ubound) 
    { 
     Mid=(Lbound+Ubound)/2; 
     if(VAL>AR[Mid]) 
      Lbound=Mid+1; 
     else if(VAL<AR[Mid]) 
      Ubound=Mid-1; 
     else 
      return Mid; 
    } 

    return 0; 
} 

Answer 4

，如果你想學習如何編碼的二進制搜索，否則再利用重新發明輪子是細越好。

std::lower_bound在已排序的範圍[first, last)上執行二進制搜索，如果已存在，則將迭代器返回到搜索的元素x;否則迭代器將指向大於x的第一個元素。由於標準容器公開的insert會在迭代器之前插入，因此可以按原樣使用此迭代器。這是一個簡單的例子。

#include <algorithm> 
#include <iostream> 
#include <iterator> 
#include <vector> 

int main() 
{ 
    std::list<int> data = { 1, 5, 7, 8, 12, 34, 52 }; 

    auto loc = std::lower_bound(data.begin(), data.end(), 10); 
    // you may insert 10 here using loc 
    std::cout << *loc << '\n'; 

    loc = std::lower_bound(data.begin(), data.end(), 12); 
    // you may skip inserting 12 since it is in the list (OR) 
    // insert it if you need to; it'd go before the current 12 
    std::cout << *loc << '\n'; 
} 

Answer 5

的解決方案是重寫代碼使用STL，我不明白爲什麼人們用C編寫C++代碼。

您需要用戶的矢量

std::vector<User> users; 
//then you can keep it ordered at each insertion 
auto it = upper_bound(users.begin(), users.end(), user_to_insert, 
    [](auto& lhs, auto& rhs) { /* implementation left to the reader */}); 
users.insert(it, user_to_insert); 

現在具有相同的功能在一個更漂亮和乾淨的方式

Answer 6

二進制搜索將是有限的利益，因爲你總有需要插入和這將是一個耗時的操作（O（N））。所以你的第一個想法是線性搜索，然後插入就足夠了;你可以結合在一個單一的後向循環。 （這是StraightInsertionSort的一個步驟。）

處理動態排序列表的真正有效方法是通過維護平衡樹或使用散列表。

Answer 7

從我所看到的情況來看，您使用C數組來存儲條目，這意味着無論何時嘗試插入新條目都會導致大量條目數量的巨大損失，因爲您可能需要移動很多條目數組中的條目。

如果你打算保留一個C數組並且不使用一些stl有序的容器（大部分都是考慮std :: map），你可以嘗試將你的C數組拆分成兩個數組。一個將是第一個數組，其中包含您的密鑰和第二個數組元素的索引。您仍然需要對第一個數組進行排序，但其元素只有兩個字（一個用於鍵，一個用於索引），而不是包含鍵和一些值的大塊，並且應該更快。當插入一個項目時，您將在第二個數組的末尾分配索引並將其作爲一對鍵插入到第一個數組中。如果你打算動態地移除一個元素，你可以變得更聰明一點，但是你的問題看起來並不能覆蓋它。

但即便如此，它可能仍然太慢，所以你應該確實考慮std :: map或者使用AVL，紅黑樹，Splay樹等二進制樹等一些算法，而不需要移動元素物理。

Answer 8

如果您只對幾個新的不適合的尾隨項目進行排序，那麼您應該利用罕見的插入排序實際上有效的情況。在排序列表上實現插入排序，只有少數尾隨值可以在O（n）時間排序。您只需將幾個不合適的值插入到位，而快速排序則是選取一個數據透視表並執行整個快速排序過程。另外，如果你沒有在快速排序中加入一些有效的數據透視選擇過程，並且在已經排序的列表中使用某些「前三項的平均值」方法，那麼你將在O（n^2 ） 時間。