比较两个巨大数组的最佳方法

Question

我的任务是在一个输入文件中有 1，000，000 张具有市场价格的卡片，然后在另一个输入文件中具有相同的 1，000，000 张具有更高价格的卡片，我必须比较两者以计算利润。

嵌套的 for 循环：

for(int i = 0; i < marketPriceCards.size(); i++){
    for(int j = 0; j < priceListCards.size(); j++){
        compute profit

是 O（n^2），这太长了。我在想一个哈希表，但我必须做多大？大于 1000000 的质数？

Answer 1

在 Java 中，默认负载系数为 0.75，因此您可以创建大小为以下大小的哈希表：

1.75 * <size of your data>

这应该是一个良好的开端。

顺便说一句，你没有提到你将使用哪种语言。如果是Java，你应该使用HashMap - 而不是Hashtable（仅供参考）。

Answer 2

我不明白你为什么写一个嵌套循环，因为它可以在一个循环 O（n） 中完成。由于您的数据记录在两个大文件中，因此您需要读取它们，并且由于您需要所有数字，因此需要遍历两个文件的全部内容。如果记录少于 100，000，我建议使用 mopen（） 将它们都加载到内存中，但是您有两个大文件，将它们都加载到内存中并不是一个聪明的操作。所以这是我认为你应该做的，以防你有文本文件

cardsFile = fopen ("elapsed.dta", "rt"); 
priceFile = fopen ("elapsed.dta", "rt"); 
while(fgets(aCardline, 80, cardsFile) != NULL)
   {
      sscanf (aCardline, "%ld", &aCard);    
      fgets(aPriceline, 80, priceFile)
      sscanf (aCardline, "%ld", &aPrice);  
      printf ("Card :%s Price :%ldn", aCard, aPrice,);
   }

我认为您必须更改返回卡和价格的方法如果需要详细说明更多数据，可以使用缓冲区。

我个人喜欢将这种大小的数据存储在数据库中。

希望这对你有帮助。