更快地交换结构数组中的元素

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

我不确定这是否是您要查找的内容，但加速这些交换的一种简单方法是将指向 "struct data" 的指针存储在 "list" 中，而不是存储整个结构本身。这样，当您交换时，您一次只能交换 4 或 8 个字节（分别用于 32 位和 64 位），而不是高达 256 个字节。

如果您打算连续存储和交换这些结构的所有内存，最好的办法是使用向量内在函数 (SIMD)。这是 guide for gcc. Here's one for msvc.

Answer 2

这是一种典型的变通方法，用于对具有 N 类型 T 元素的数组进行排序，其中假定 N 和 sizeof(T) 都很大。

创建 N 指针到 T 的临时数组。
用指向实际数组中元素的指针填充临时数组。
对临时数组进行排序。（当比较元素时，你必须解引用指针。当交换元素时，你只需要交换单个指针。）
重新排列原始数组中的元素，使它们的顺序与临时数组中指针指向的顺序相同。
再次释放临时数组。

此技术的优点是您只需执行 T 的 O(N) 次交换，而您可能会执行 T* 的 O(N log(N)) 次交换。缺点是您必须分配临时缓冲区并在比较元素时通过额外的指针间接寻址。您必须进行基准测试才能了解这是否适合您的类型。

一种可能的优化是在堆栈上分配临时数组，因为它永远不会超过排序例程。但是，将巨大的数组放在堆栈上可能会导致堆栈溢出，因此请注意大小。

Answer 3

如果不是因为您问的是优化问题，我会认为这是一项家庭作业。不过，分类类的家庭作业通常不涉及优化。尽管如此，您所在的机构会在现实世界中教导您永远不要重新发明轮子，除非收益大于成本。在这种情况下，他们不会。

想象一下，如果您的 x86 最快 代码也ARM 最慢。这是一个很常见的场景，标准库在 <stdlib.h> 中包含两个函数：qsort 和 bsearch。很可能，标准库的作者更了解如何为每个平台编写、测试和调整排序算法。
想象一下，如果 每个进程 运行在每个给定的时间重新发明轮子，导致大量重复的排序函数在内存中保留和交换......一个使用标准库代码的主要好处是它可以在许多进程之间共享，从而减少重复的资源消耗。更少的资源消耗也很可能导致更快的代码，在这种情况下，在多个进程之间共享此资源也可能减少缓存抖动。

要使用qsort和bsearch，您首先需要定义一个比较函数。这可以像包装 strcmp 一样简单，如果您可以保证要排序的字段实际上是一个字符串（即字符序列以 '[=17=]' 结尾）。比较函数需要使用签名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" 的项目。

更快地交换结构数组中的元素

Swapping elements from array of struct faster

c

arrays

swap

struct