哪个更快:适当的数据输入或适当的数据结构?

与许多与绩效相关的问题一样,唯一真正明确的答案是编写基准。速度将取决于许多因素,听起来不像是线性算法和二次算法的简单情况(甚至这会对输入大小有额外的依赖性)。

因此,实现这两种方法,在样本数据上运行它们,并对结果计时。这将比我们试图用有限的信息在头脑中解决问题更快、更具决定性。

实际上,这两种方法看起来非常相似。为了存储为特定组合提供分数的所有客户的客户ID,您需要对数据进行排序或执行更昂贵的操作。

你能把空间换成时间吗?如果是,则不进行任何预处理,而是创建一个包含所有组合(10x24)的数组来存储分数。对数据进行处理,并更新特定组合的得分。如果您需要平均分数,请同时存储提供分数的客户总数和数量。

你影响最慢的部分可能是复制内存块。所以要应用的第一种技术是将每一行的值放置在一个结构中,并且只通过指针引用它,直到完成所有的处理。结构应该是这样的:

typedef struct {
 int consumer;
 int product;
 int time;
 int score;
} rowData;

在此基础上,我认为您最好遍历输入行,并构建由使用者和产品标识的结构的二叉树(或其他排序结构),并包含指向所有匹配行数据的指针查找表:

typedef struct {
 int consumer;
 int product;
 rowData * matches;
} matchLut;

一旦所有行都放置在树上的查找表中,就可以处理每个包。

我建议像第二步一样过滤数据,然后按照第一步进行处理。如果你的表现是不可接受的,调优表现。为您的基线设置一些基准,然后尝试一些不同的方法。

在大多数实际情况下,我建议不要仅仅为了基准测试而实现多种方法。性能可能相似。如果它不相似,那么它的性能可能很差,并且明显需要进行调整。您的时间可能更好地用于实现其他特性。

如果内存允许将您的数据存储在一个二维数组中(实际上是三维的,但稍后我会讨论)。此数组将按(product_id,time_period)索引。

如果您对数据的处理允许,那么二维数组的每个元素都可以是新数据的累加器,因此您可以读取一个数据元素,然后调整二维数组的相应元素来反映它。如果这个方法有效,当您读完它时,您的数据将被处理。

如果您的处理要求您同时拥有来自每个数据元素的数据,那么您可以将二维数组中的每个元素作为一个列表(这是第三个D)。如果您不知道每个客户条目的数量(产品ID、时间段),它可能是一个可变长度的列表。读取数据后,需要重新访问二维数组的每个元素以处理每个列表。如何安排数组以及如何访问元素对于性能至关重要。 您可能希望动态地声明这个,但是对于这个例子来说

struct element_t element[NUMBER_OF_PRODUCTS][NUMBER_OF_TIME_PERIODS];
// don't forget to initialize these elements to empty
...
for (p = max_product_id; p >= 0; p--) {
    for (t = max_time_period; t >= 0; t--) {
         process(element[p][t]);
    }
}

如果你想在转移到下一个产品之前处理每个产品,效果会更好,因为。如果要在移动到下一个时间段之前处理每个时间段(对于所有产品),可以交换声明的行、列和循环以获得更好的缓存命中。

您应该注意,这会为您进行排序,而不会说“对数据进行排序”。

如果内存不允许,那么您可能希望在读取数据时将部分数据存储到文件中。这与上面提到的数组/循环组织/缓存命中优化有相同的问题,但它将被放大很多倍。在读取主数据的末尾,您希望能够在移动到下一个之前处理特定临时文件中的所有数据(可能包含给定产品的所有数据(给定时间段的XOR))。尝试这样做的主要缺点是,当您在读取数据时,很可能不得不处理不能同时打开每个临时文件的问题。这可能需要您想出一种执行打开文件交换的方法(与内存交换相同,只是您要交换的是打开的文件而不是内存页)。不过,这将是另一个问题。

我建议您根据最常访问的流程重新排序数据。最频繁访问的数据应该是最容易和最快访问的。

另外,看看 Database Normalization . 这是一个以最少的重复量组织数据的概念,也使访问数据更加高效。

另一个想法是使用索引进行不太流行的数据搜索。

这将产生一个小的数据库表。如果存在完整的消费者/产品/时间矩阵,大约有0.4GB的数据。您考虑过在SQL中运行整个程序吗?即使您不需要我们一个完整的数据库;对于这样大的数据,为每个可能的排序顺序生成一个完整的表并将每个表转储到一个文件也是可行的。然后你可以加载你需要的任何文件,按照你选择的顺序来移动它。

此外,如果您可以并行运行完整的10公里通行证,或者每个通行证至少运行几十次,那么您可能会提前这样做,因为这样会大大减少IO等待和/或缓存未命中。