c - 在c中排序5d数组

Question

我想弄清楚如何在 C 中对多维数据(5 维)进行排序。我知道使用 5d 数组是一种解决方案，从 阅读 SO 上关于这个主题的其他帖子，许多人发现，如果不是完全不道德，那么在美学上令人反感，以致引起不断的喷射性呕吐……所以我提前道歉。

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

数据如下:

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

有:

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

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

这将在具有 192 gig(不是 meg)RAM 的 12 物理/24 逻辑核心机器上运行，使用 VS 2010 C(不是 C++)。

我假设 qsort 是最有效的排序选项。我已经在 Google 和 SO 上广泛搜索了如何执行此操作，但无济于事。在 PHP 或 C# 等中有针对一维数组、多维数组的答案，但没有针对 C 的答案...或者至少我找不到答案。

Answer 1

cstdlib 中的 qsort 可以工作。该数组的数据类型为 ***data。

首先，假设您要对数组的第一个索引进行排序。您必须编写一个比较器函数来比较两个数据类型****。如果是 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);

就是这样!

然后是效率低下的问题...如果 algorithmRatingFunction 需要很长时间才能完成(我猜是这样)，那么您可能希望对所有 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 数组等。