подкачка элементы из массива структуры быстрее

Question

У меня есть эта структура:

typedef struct data{ 
    char name[100], pseudo[100]; 
    int num0, num1, num2, num3, num4; 
    long int lnum0, lnum1, lnum2, lnum3, lnum4; 
    double dnum0, dnum1; 
}data; 
data list[50] 

я создаю массив этой структуры и сортировать их с помощью алгоритма быстрой сортировки. Для этого я должен поменять элемент с помощью этой функции:

void swap(data list[], i, j){ 
    data tmp; 

    tmp.num1 = list[i].num1 
    list[i].num1 = list[j].num1 
    list[j].num1 =tmp.num1 
    //using memmove to avoid overlaping from the strcpy function 
    memmove(temp.name,list[i].name,strlen(list[i].name)); 
    memmove(list[i].name,list[j].name,strlen(list[j].num1)); 
    memmove(list[j].name,tmp.name,strlen(tmp.name)); 
} 

У меня есть 16 элемент в моей структуры, и я должен повторить 16 раз эту функцию, чтобы поменять их все. Мой вопрос: есть ли еще более простой, быстрый или более удобный способ, или мы можем оптимизировать эту функцию?

Answer 1

Это типичный обходной путь для сортировки массива с N элементов типа T где оба N и sizeof(T) предполагаются большими.

1. Создание временного массива Nуказателей к T.
2. Заполните временный массив указателями на элементы в вашем фактическом массиве.
3. Сортировка временного массива. (При сравнении элементов вам нужно разыменовать указатели. При обмене элементами вам нужно только обменивать отдельные указатели.)
4. Переупорядочить элементы в исходном массиве так, чтобы они находились в том же порядке, на который указывали указатели в ваш временный массив.
5. Освободите временный массив снова.

Этот метод имеет то преимущество, что у вас есть только для выполнения O(N) свопы T в то время как вы могли бы сделать O(N log(N)) свопы T*. Недостатком является то, что вам придется выделять временный буфер и пропустить дополнительную ссылку указателя при сравнении элементов. Вам нужно будет проверить, действительно ли это окупается для вашего типа.

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

Answer 2

Я не уверен, что это то, что вы ищете, но простой способ ускорить эти свопы заключается в том, чтобы хранить указатели на «структурированные данные» в «списке», а не на хранение всех самих структур. Таким образом, когда вы меняете, вы меняете только 4 или 8 байтов за раз (для 32-разрядных и 64-бит соответственно) вместо колоссальных 256 байтов.

Если вы настроены на сохранение и замену всей памяти для этих структур, вам лучше всего использовать векторные свойства (SIMD). Вот guide for gcc. Вот one for msvc.

Answer 3

Если бы не тот факт, что вы спрашиваете об оптимизации, я бы предположил, что это домашняя задача. Однако домашние задания сортировочного сорта обычно не связаны с оптимизацией. Тем не менее, ваше учреждение научило вас в реальном мире никогда не изобретать велосипед, если выгоды не перевесят затраты. В этом случае они этого не делают.

• Представьте, если ваш быстрый для x86 код также медленнее для ARM.Это такой общий сценарий, что стандартная библиотека включает в себя две функции в пределах <stdlib.h>: qsort и bsearch. Скорее всего, авторы стандартной библиотеки лучше понимают, как писать, тестировать и настраивать алгоритм сортировки для каждой платформы.
• Представьте себе, если каждый процесс работает в любое время, изобретает колесо, что приводит к большому количеству повторяющихся функций сортировки, которые хранятся и обмениваются в памяти ... Одним из основных преимуществ использования стандартного библиотечного кода является то, что он может использоваться совместно многие процессы, что приводит к меньшему дублированию потребления ресурсов. Меньшее потребление ресурсов также, скорее всего, приводит к более быстрому коду, и в этом случае совместное использование этого ресурса между несколькими процессами также, вероятно, приведет к сокращению кэширования.

Чтобы использовать qsort и bsearch, сначала необходимо определить функцию сравнения. Это может быть так же просто, как обертывание strcmp, если вы можете гарантировать, что поле для сортировки на основе является фактически строкой (то есть последовательность символов заканчивается на '\0'). Функция сравнения должна использовать подпись int compare(void const *x, void const *y);, например:

int compare_data_by_name(void const *x, void const *y) { 
    data const *foo = x, *bar = y; 
    return strcmp(foo->name, bar->name); 
} 

qsort(list, sizeof list/sizeof *list, sizeof *list, compare_data_by_name); Вызов будет сортировать list.

Позвоните по номеру bsearch(&(data){ .name = "fred" }, list, sizeof list/sizeof *list, sizeof *list, compare_data_by_name);, чтобы получить товар с именем "fred".