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

Вы можете сделать бинарный поиск как этот способ .. Здесь Вы можете предположить, что если Допустимы строка затем сравните с помощью функции сравнения строк, а 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

решения переписать код, чтобы использовать СТЛИ, я не понимаю, почему люди пишут 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, Red Black tree, Splay tree и т. Д., Где вам не нужно перемещать элемент физически.

Answer 8

Если вы сортируете отсортированный список только с несколькими новыми неуместными деталями, то вам следует воспользоваться редким случаем, когда сортировка вставки действительно работает эффективно. Внедрение сортировки в сортированном списке с несколькими остальными значениями места может сортировать в O (n) времени. Вы просто вставляете свои несколько неуместных значений на место, в то время как быстрый сортировка выбирает точку опоры и проходит весь процесс быстрой сортировки. Кроме того, если вы не включаете какой-либо эффективный процесс выбора сводной диаграммы в свой быстрый вид и переходите к подходу «средний из первых трех элементов» в уже отсортированном списке, который вы собираетесь сортировать в O (n^2) время.