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 ） 时间。