Swapping elements from array of struct faster

Question

I have this struct:

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]

I create an array of this struct and sort them with a quicksort algorithm. To do that I must swap element using this function:

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));
}

I have 16 element in my struct, and i have to repeat 16 times this function to swap them all. My question is : Is there another simpler,faster or nicer way to proceed, or can we optimize this function ?

Maybe create an array of pointers to those structs and swap the pointers instead of the actual structs? — chrk, Jan 29 '17 at 01:36
If you have to swap the actual structures instead of using pointers, `data tmp; tmp = list[ i ]; list[ i ] = list[ j ]; list[ j ] = tmp;` is certainly *simpler* code. And it might very well be a lot faster, too. — Andrew Henle, Jan 29 '17 at 01:43
to swap a whole struct, need to use something like `memmove()` or `memcpy()`. on the whole struct. Note: @AndrewHenle, just using the name of the struct instance will not copy the whole struct — user3629249, Jan 29 '17 at 18:10
@user3629249: using structure assignment to copy structs as shown by AndrewHenle works correctly for shallow copies, and that's all that's required here. — mhawke, Jan 30 '17 at 03:08
@user3629249 *to swap a whole struct, need to use something like `memmove()` or `memcpy()`. on the whole struct.* That's not correct. See **6.5.16.1 Simple assignment** of the [C Standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf): "One of the following shall hold: ... the left operand has an atomic, qualified, or unqualified version of a **structure or union type compatible with the type of the right**" See also http://stackoverflow.com/questions/2302351/assign-one-struct-to-another-in-c — Andrew Henle, Jan 30 '17 at 11:22

score 2 · Accepted Answer · answered Jan 29 '17 at 01:43

2

This is a typical workaround to sort a array with N elements of type T where both N and sizeof(T) are assumed to be large.

Create a temporary array of N pointers to T.
Fill the temporary array with pointers to the elements in your actual array.
Sort the temporary array. (When comparing elements, you have to dereference the pointers. When exchanging elements, you only have to swap single pointers.)
Rearrange the elements in your original array such that they are in the same order as pointed to by the pointers in your temporary array.
Free the temporary array again.

This technique has the advantage that you only have to perform O(N) swaps of T while you might do O(N log(N)) swaps of T*. The downside is that you'll have to allocate the temporary buffer and go through an additional pointer indirection when comparing elements. You'll have to benchmark in order to see whether or not this pays off for your type.

A possible optimization is to allocate the temporary array on the stack as it never outlives the sorting routine. Putting huge arrays on the stack might cause a stack overflow, though, so be careful about the size.

answered Jan 29 '17 at 01:43

5gon12eder

24,280
5
45
92

Wow actually i had to perfom `O(N^2)`swaps, but thanks to you i might able to reduce drastically the processing time – Maxime Deletraz Jan 29 '17 at 02:03
How come your quick sort is causing O(N^2) swaps? It might do in its worst case degradation but you'd normally expect O(N log(N)) on average. Note that the difference between O(N^2) and O(N log(N)) will be much more significant than the one between O(N log(N)) and O(N). – 5gon12eder Jan 29 '17 at 02:10
This is because I choice the pivot arbitrarily and there are few unique in this selection – Maxime Deletraz Jan 29 '17 at 02:23
In that case, 3-way quick sort or merge sort might be promising alternatives to look into. The “sort an array of pointers instead” trick can still be applied. – 5gon12eder Jan 29 '17 at 02:29
Note that the OP stated the array has 16 elements. That rarely qualifies as "large". – Peter Jan 29 '17 at 02:38

score 1 · Answer 2 · answered Jan 29 '17 at 01:43

I'm not sure this is what you're looking for, but a simple way to speed up these swaps would be to store pointers to "struct data" in "list", rather than storing the entire structs themselves. That way when you swap, you only swap 4 or 8 bytes at a time (for 32-bit and 64-bit respectively), instead of a whopping 256 bytes.

If you're set on storing and swapping all the memory for those structs contiguously, your best bet is to use vector intrinsics (SIMD). Here's a guide for gcc. Here's one for msvc.

score 1 · Answer 3 · answered Jan 29 '17 at 02:40

If it weren't for the fact that you're asking about optimisation, I'd assume this is a homework task. Homework tasks of the sorting variety don't usually involve optimisation, though. Nonetheless, your institution would've taught you in the real world never to reinvent the wheel unless the benefits outweigh the costs. In this case, they don't.

Imagine if your fastest for x86 code were also slowest for ARM. This is such a common scenario the standard library includes two functions within <stdlib.h>: qsort and bsearch. The odds are, the authors of the standard library have a better idea of how to write, test and tune a sorting algorithm for each platform.
Imagine if every process running at every given time reinvented the wheel, leading to lots of duplicate sorting functions being kept and swapped around in memory... One major benefit to using standard library code is that it can be shared among many processes, leading to less duplicate resource consumption. Less resource consumption also happens to most likely lead to faster code, and in this case sharing this resource between multiple processes is also likely to reduce cache thrashing.

To use qsort and bsearch you first need to define a comparison function. This can be as simple as wrapping strcmp, if you can guarantee that the field to sort based on is in fact a string (i.e. the character sequence ends with a '\0'). The comparison function needs to use the signature int compare(void const *x, void const *y);, for example:

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

Calling qsort(list, sizeof list / sizeof *list, sizeof *list, compare_data_by_name); will sort list.

Calling bsearch(&(data){ .name = "fred" }, list, sizeof list / sizeof *list, sizeof *list, compare_data_by_name); will retrieve an item with "fred" as the name.

Well ! I didn't know about `qsort`and `bsearch` so thanks I will a try. This is not a homework and im not reinventing the wheel either, basically I just would to get a formated in an array of struct and sort them fastly because this might be useful for some tasks — Maxime Deletraz, Jan 29 '17 at 02:57

Swapping elements from array of struct faster

3 Answers3