为什么我的程序很慢？我怎样才能提高效率？

Question

我有一个程序执行Block Nested循环连接(链接文本).基本上它的作用是,它将文件(比如10GB文件)中的内容读入buffer1(比如400MB),将其放入哈希表中.现在将第二个文件(比如10GB文件)的内容读入缓冲区2(比如说100MB),看看buffer2中的元素是否存在于哈希中.输出结果无关紧要.我现在只关心程序的效率.在这个程序中,我需要从两个文件一次读取8个字节,所以我使用long long int.问题是我的程序效率很低.我怎样才能提高效率？

//我编译使用 g++ -o hash hash.c -std=c++0x

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdint.h>
#include <math.h>
#include <limits.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

typedef std::unordered_map<unsigned long long int, unsigned long long int> Mymap; 
int main()
{

uint64_t block_size1 = (400*1024*1024)/sizeof(long long int);  //block size of Table A - division operator used to make the block size 1 mb - refer line 26,27 malloc statements.
uint64_t block_size2 = (100*1024*1024)/sizeof(long long int);   //block size of table B

int i=0,j=0, k=0;
uint64_t x,z,l=0;
unsigned long long int *buffer1 = (unsigned long long int *)malloc(block_size1 * sizeof(long long int));
unsigned long long int *buffer2 = (unsigned long long int *)malloc(block_size2 * sizeof(long long int));

Mymap c1 ;                                                          // Hash table
//Mymap::iterator it;

FILE *file1 = fopen64("10G1.bin","rb");  // Input is a binary file of 10 GB
FILE *file2 = fopen64("10G2.bin","rb");

printf("size of buffer1 : %llu \n", block_size1 * sizeof(long long int));
printf("size of buffer2 : %llu \n", block_size2 * sizeof(long long int));


while(!feof(file1))
        {
        k++;
        printf("Iterations completed : %d \n",k);
        fread(buffer1, sizeof(long long int), block_size1, file1);                          // Reading the contents into the memory block from first file

        for ( x=0;x< block_size1;x++)
            c1.insert(Mymap::value_type(buffer1[x], x));                                    // inserting values into the hash table

//      std::cout << "The size of the hash table is" << c1.size() * sizeof(Mymap::value_type) << "\n" << endl;

/*      // display contents of the hash table 
            for (Mymap::const_iterator it = c1.begin();it != c1.end(); ++it) 
            std::cout << " [" << it->first << ", " << it->second << "]"; 
            std::cout << std::endl; 
*/

                while(!feof(file2))
                {   
                    i++;                                                                    // Counting the number of iterations    
//                  printf("%d\n",i);

                    fread(buffer2, sizeof(long long int), block_size2, file2);              // Reading the contents into the memory block from second file

                    for ( z=0;z< block_size2;z++)
                        c1.find(buffer2[z]);                                                // finding the element in hash table

//                      if((c1.find(buffer2[z]) != c1.end()) == true)                       //To check the correctness of the code
//                          l++;
//                  printf("The number of elements equal are : %llu\n",l);                  // If input files have exactly same contents "l" should print out the block_size2
//                  l=0;                    
                }
                rewind(file2);
                c1.clear();                                         //clear the contents of the hash table
    }

    free(buffer1);
    free(buffer2);  
    fclose(file1);
    fclose(file2);
}

更新:

是否可以直接从文件中读取一个块(比如400 MB)并使用C++流读取器将其直接放入哈希表中？我认为可以进一步减少开销.

Answer 1

程序的运行时间为 (l ₁ x bs ₁ xl ₂ x bs ₂ )（其中 l ₁是第一个文件中的行数，bs ₁是第一个缓冲区的块大小，l ₂是第一个缓冲区的块大小）。第二个文件中的行数，bs ₂是第二个缓冲区的块大小），因为您有四个嵌套循环。由于您的块大小是恒定的，因此您可以说您的顺序是 O(nx 400 xmx 400) 或 O(1600mn)，或者在最坏的情况下为 O(1600n ² )，最终实际上是 O(n ² )。

如果您执行以下操作，则可以拥有 O(n) 算法（伪代码如下）：

map = new Map();
duplicate = new List();
unique = new List();

for each line in file1
   map.put(line, true)
end for

for each line in file2
   if(map.get(line))
       duplicate.add(line)
   else
       unique.add(line)
   fi
end for

现在duplicate将包含重复项目的列表，并将unique包含唯一项目的列表。

在原始算法中，您无需为第一个文件中的每一行遍历第二个文件。所以你实际上最终失去了哈希的好处（它给你 O(1) 的查找时间）。当然，这种情况下的权衡是您必须将整个 10GB 存储在内存中，这可能没有多大帮助。通常在这种情况下，需要在运行时和内存之间进行权衡。

可能有更好的方法来做到这一点。我需要再考虑一下。如果没有，我很确定有人会想出更好的主意:)。

更新

如果您能找到一种好方法来散列该行（从第一个文件中读入的行），以便获得唯一值（即该行与该行之间的一对一映射），您可能可以减少内存使用量哈希值）。本质上你会做这样的事情：

for each line in file1
   map.put(hash(line), true)
end for

for each line in file2
   if(map.get(hash(line)))
       duplicate.add(line)
   else
       unique.add(line)
   fi
end for

这里的hash函数是执行散列的函数。这样您就不必将所有行存储在内存中。您只需存储它们的哈希值。这可能对你有一点帮助。即便如此，在最糟糕的情况下（您要比较两个相同或完全不同的文件），您仍然可能会获得 10Gb 的内存用于 或duplicate列表unique。如果您只是存储一些唯一或重复的项目而不是项目本身，则可以避免丢失一些信息。