在C语言中对5维数组进行排序

Question

我正在尝试解决如何在C语言中对多维数据（5个维度）进行排序的问题。我知道使用5D数组是一种解决方案，但从阅读其他SO帖子关于这个主题的文章中得知，许多人认为这种方法在审美上令人难以接受，甚至是不道德的，因此会导致无休止的呕吐...所以预先向大家道歉。

本质上，我有一组传入的数据，必须对其应用一系列离散算法。每个算法都有一组变量，我需要计算每个排列下每个算法的效率排名。最终，我需要一个按照表现最佳到最差排序的列表。整个计算是动态的，因此在一组传入的数据上表现最佳的方法可能在另一组数据上并不是表现最佳的...因此我不能消除任何变量，因为它们可能是性能较差的。

这是数据的样子：

dataValue[ algo ][ lengthVar ][ durationVar ][ plasticityVar ] [ fungibilityVar]

以下是内容：

• 35个算法
• 10种长度变量
• 230个持续时间变量
• 27个可塑性变量
• 400个通用性变量

除了按算法排序外，我还希望能够灵活地按照这5个维度中的任意一个进行排序。

这将在一台拥有12个物理/24个逻辑核心、192 GB（不是MB）RAM，并使用VS 2010 C（而非C ++）的计算机上运行。

我认为qsort可能是最有效的排序选项。我在谷歌和Stack Overflow上进行了广泛搜索，但没有找到如何处理此问题的答案。虽然有关于PHP或C＃中单维数组、多维数组等的解决方案，但没有针对C语言的......至少我没找到。

- PaeneInsula

---

“so aesthetically repugnant so as to provoke unceasing projectile vomiting” 翻译为：“审美上如此令人反感，以至于会引起不断的喷射性呕吐”。 - Mysticial

qsort将排序5D数组的问题转化为比较两个4D数组的问题。只要你知道如何根据它们相应的4D子数组来决定哪个算法更好，就可以使用qsort对数据进行排序。我链接的文档底部有一个小例子，你应该能够根据自己的需要进行调整。 - Sergey Kalinichenko

你是在声明 dataValue 为 dataValue[35][10][230][27][400]，还是说 algorithm 可能有35个值，length 有10个值，duration 有230个值等等？ - Skizz

每个算法都有1023027*400种可能的值。 - PaeneInsula

Answer 1

中的qsort函数可以完成此任务。数组的数据类型为***data。

首先，如果您想要对数组的第一个索引进行排序，您需要编写一个比较函数来比较两个Datatype****。比较器应该在ab小于零时返回一个小于零的值。

int myComparator(void *a, void *b){
    Datatype ****c=(Datatype****)a; Datatype ****d=(Datatype****)b
    return algorithmRatingFunction(b)-algorithmRatingFunction(a);
}

这显然是低效的，因为你需要为每个数据集重新评估算法，并进行比较，但我们稍后再谈论这个问题。获得比较器之后，您可以对数组进行排序：

qsort(data,35,sizeOf(Datatype),myComparator);

就是这样！

还有一个效率的问题... 如果算法评估函数需要很长时间才能完成（我猜是这样），那么你会想要计算所有35个算法一次且仅一次。你可以预先计算分数：

int scores[35];
for(int n=0;n<35;n++)
    scores[n]=algorithmRatingFunction(data[n]);

然后创建另一个整数有序数组：

int ordering[35];
for(int n=0;n<35;n++)
    ordering[n]=n;

因此，“排序”状态对应于数据集的顺序。然后，您可以创建一个新的比较器：

int myFasterComparator(void *a, void *b){
    int c=*(int*)a; int d=*(int*)b
    return scores[c]-scores[d];
}

并在排序时调用它：

qsort(ordering,35,sizeOf(int),myFasterComparator);

然后使用排序方式重组数组，如下所示：

Datatype ****ordereddata[35];
for(int n=0;n<35;n++)
    ordereddata[n]=data[ordering[n]];

其他级别也是如此。就像dasblinkenlight所说的那样，qsort将5d数组排序问题转化为比较两个4d数组的问题。因此，不需要对每个4d数组进行排序，只需比较两个3d数组，依此类推。

- user1030718

---

每个算法都会有大约2500万个分数，因为每个变量组合都会产生一个唯一的结果。例如，algo [0]使用firstVar [0]，2ndVar [0]，3rdVar [0]和4thVar [0]；然后algo [1]使用firstVar [1]，以及[0]用于第2、3和4个变量，依此类推。你的答案还适用吗？ - PaeneInsula

你关于只进行一次计算的想法让我想到了以下内容：对于2500万个分数中的每一个，都进行计算，并将每个分数/变量排列组合成一个0填充的字符串：00000-000nn-000nn-000nn-000nn。然后，我可以使用strcmp比较函数进行1次调用qsort。通过使用不同的strcmp偏移量（例如，strcmp（＆stringA [6]，stringB [6]）等），我可以根据任何“字段”进行排序。 - PaeneInsula

我认为这是非常错误的。qsort 只能对一维对象数组进行排序。qsort(data,35,sizeOf(Datatype),myComparator); 这行代码只会对从 data 开始的前 35 个 Datatype 对象进行排序。然后，你将会交换 Datatype 对象。 - Skizz

啊，我现在明白你的意思了。我之前认为每个算法都是在4D数组的数据集上运行。在这种情况下，0x69的答案对我来说是正确的，只不过我会在结构体中添加一个额外的“分数”变量，用于比较器。如果排序2500万个值不可行，您可以只保留一个前十名列表，并使用二进制搜索将新值插入到它们应该在的位置，然后删除最后一个元素。 - user1030718

Answer 2

我认为你真的需要拒绝因5D效果而呕吐。相反，应该使用结构体：

typedef struct {
    int algorithm;
    int length;
    int duration;
    int plasticity;
    int fungibility;
    int dataValue;
} AlgorithmTestData;

然后定义您的测试数据1D数组：

AlgorithmTestData algoTestCases[NUMBER_OF_TEST_CASES];

如果您不知道测试用例的大小，可以使用malloc动态分配内存。

然后，根据您的比较要求，您将对qsort algoTestCases 1D数组进行排序。

- Agnius Vasiliauskas

---

只要数值不连续（例如算法为0-34，长度为0-9等），这种表格形式看起来更好，因为避免了很多冗余。排序也会更容易。 - Skizz