5

我的文本文件中有大约 2500 万个整数，由行分隔。我的第一个任务是获取这些整数并对其进行排序。我实际上已经实现了读取整数并将它们放入数组中（因为我的排序函数将未排序的数组作为参数）。但是，从文件中读取整数是一个非常漫长且昂贵的过程。我已经搜索了许多其他解决方案以获得更便宜和有效的方法，但我无法找到一种能够处理这种尺寸的解决方案。因此，您的建议是从巨大的（约 260MB）文本文件中读取整数。以及如何有效地获得相同问题的行数。

ifstream myFile("input.txt");

int currentNumber;
int nItems = 25000000;
int *arr = (int*) malloc(nItems*sizeof(*arr));
int i = 0;
while (myFile >> currentNumber)
{
    arr[i++] = currentNumber;
}

这就是我从文本文件中获取整数的方式。这并不复杂。我假设行数是固定的（实际上是固定的）

顺便说一句，它当然不会太慢。在配备 2.2GHz i7 处理器的 OS X 中，它在大约 9 秒内完成读取。但我觉得它可能会好很多。

4

8 回答 8

8

最有可能的是，对此的任何优化都可能影响很小。在我的机器上，读取大文件的限制因素是磁盘传输速度。是的，提高读取速度可以稍微提高一点，但很可能，你不会从中得到太多。

我在之前的测试中发现 [我会看看是否可以在其中找到答案 - 我在“SO 的实验代码”目录中找不到源代码] 最快的方法是使用mmap. 但它只比使用ifstream.

编辑：我自制的以几种不同方式读取文件的基准。 读取文件时获取行与读取整个文件然后根据换行符拆分

与往常一样，基准衡量基准衡量的内容，对环境或代码编写方式的微小更改有时会产生很大的不同。

编辑：以下是“从文件中读取数字并将其存储在向量中”的一些实现：

#include <iostream>
#include <fstream>
#include <vector>
#include <sys/time.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sys/mman.h>
#include <sys/types.h>
#include <fcntl.h>


using namespace std;

const char *file_name = "lots_of_numbers.txt";

void func1()
{
    vector<int> v;
    int num;
    ifstream fin(file_name);
    while( fin >> num )
    {
    v.push_back(num);
    }
    cout << "Number of values read " << v.size() << endl;
}


void func2()
{
    vector<int> v;
    v.reserve(42336000);
    int num;

    ifstream fin(file_name);
    while( fin >> num )
    {
    v.push_back(num);
    }
    cout << "Number of values read " << v.size() << endl;
}

void func3()
{
    int *v = new int[42336000];
    int num;

    ifstream fin(file_name);
    int i = 0;
    while( fin >> num )
    {
    v[i++] = num;
    }
    cout << "Number of values read " << i << endl;
    delete [] v;
}


void func4()
{
    int *v = new int[42336000];
    FILE *f = fopen(file_name, "r");
    int num;
    int i = 0;
    while(fscanf(f, "%d", &num) == 1)
    {
    v[i++] = num;
    }
    cout << "Number of values read " << i << endl;
    fclose(f);
    delete [] v;
}    

void func5()
{
    int *v = new int[42336000];
    int num = 0;

    ifstream fin(file_name);
    char buffer[8192];
    int i = 0;
    int bytes = 0;
    char *p;
    int hasnum = 0;
    int eof = 0;
    while(!eof)
    {
    fin.read(buffer, sizeof(buffer));
    p = buffer;
    bytes = 8192;
    while(bytes > 0)
    {
        if (*p == 26)   // End of file marker...
        {
        eof = 1;
        break;
        }
        if (*p == '\n' || *p == ' ')
        {
        if (hasnum)
            v[i++] = num;
        num = 0;
        p++;
        bytes--;
        hasnum = 0;
        }
        else if (*p >= '0' &&  *p <= '9')
        {
        hasnum = 1;
        num *= 10;
        num += *p-'0';
        p++;
        bytes--;
        }
        else 
        {
        cout << "Error..." << endl;
        exit(1);
        }
    }
    memset(buffer, 26, sizeof(buffer));  // To detect end of files. 
    }
    cout << "Number of values read " << i << endl;
    delete [] v;
}

void func6()
{
    int *v = new int[42336000];
    int num = 0;

    FILE *f = fopen(file_name, "r");
    char buffer[8192];
    int i = 0;
    int bytes = 0;
    char *p;
    int hasnum = 0;
    int eof = 0;
    while(!eof)
    {
    fread(buffer, 1, sizeof(buffer), f);
    p = buffer;
    bytes = 8192;
    while(bytes > 0)
    {
        if (*p == 26)   // End of file marker...
        {
        eof = 1;
        break;
        }
        if (*p == '\n' || *p == ' ')
        {
        if (hasnum)
            v[i++] = num;
        num = 0;
        p++;
        bytes--;
        hasnum = 0;
        }
        else if (*p >= '0' &&  *p <= '9')
        {
        hasnum = 1;
        num *= 10;
        num += *p-'0';
        p++;
        bytes--;
        }
        else 
        {
        cout << "Error..." << endl;
        exit(1);
        }
    }
    memset(buffer, 26, sizeof(buffer));  // To detect end of files. 
    }
    fclose(f);
    cout << "Number of values read " << i << endl;
    delete [] v;
}


void func7()
{
    int *v = new int[42336000];
    int num = 0;

    FILE *f = fopen(file_name, "r");
    int ch;
    int i = 0;
    int hasnum = 0;
    while((ch = fgetc(f)) != EOF)
    {
    if (ch == '\n' || ch == ' ')
    {
        if (hasnum)
        v[i++] = num;
        num = 0;
        hasnum = 0;
    }
    else if (ch >= '0' &&  ch <= '9')
    {
        hasnum = 1;
        num *= 10;
        num += ch-'0';
    }
    else 
    {
        cout << "Error..." << endl;
        exit(1);
    }
    }
    fclose(f);
    cout << "Number of values read " << i << endl;
    delete [] v;
}


void func8()
{
    int *v = new int[42336000];
    int num = 0;

    int f = open(file_name, O_RDONLY);

    off_t size = lseek(f, 0, SEEK_END);
    char *buffer = (char *)mmap(NULL, size, PROT_READ, MAP_PRIVATE, f, 0);

    int i = 0;
    int hasnum = 0;
    int bytes = size;
    char *p = buffer;
    while(bytes > 0)
    {
    if (*p == '\n' || *p == ' ')
    {
        if (hasnum)
        v[i++] = num;
        num = 0;
        p++;
        bytes--;
        hasnum = 0;
    }
    else if (*p >= '0' &&  *p <= '9')
    {
        hasnum = 1;
        num *= 10;
        num += *p-'0';
        p++;
        bytes--;
    }
    else 
    {
        cout << "Error..." << endl;
        exit(1);
    }
    }
    close(f);
    munmap(buffer, size);
    cout << "Number of values read " << i << endl;
    delete [] v;
}






struct bm
{
    void (*f)();
    const char *name;
};

#define BM(f) { f, #f }

bm b[] = 
{
    BM(func1),
    BM(func2),
    BM(func3),
    BM(func4),
    BM(func5),
    BM(func6),
    BM(func7),
    BM(func8),
};


double time_to_double(timeval *t)
{
    return (t->tv_sec + (t->tv_usec/1000000.0)) * 1000.0;
}

double time_diff(timeval *t1, timeval *t2)
{
    return time_to_double(t2) - time_to_double(t1);
}



int main()
{
    for(int i = 0; i < sizeof(b) / sizeof(b[0]); i++)
    {
    timeval t1, t2;
    gettimeofday(&t1, NULL);
    b[i].f();
    gettimeofday(&t2, NULL);
    cout << b[i].name << ": " << time_diff(&t1, &t2) << "ms" << endl;
    }
    for(int i = sizeof(b) / sizeof(b[0])-1; i >= 0; i--)
    {
    timeval t1, t2;
    gettimeofday(&t1, NULL);
    b[i].f();
    gettimeofday(&t2, NULL);
    cout << b[i].name << ": " << time_diff(&t1, &t2) << "ms" << endl;
    }
}

结果（两次连续运行，向前和向后运行以避免文件缓存的好处）：

Number of values read 42336000
func1: 6068.53ms
Number of values read 42336000
func2: 6421.47ms
Number of values read 42336000
func3: 5756.63ms
Number of values read 42336000
func4: 6947.56ms
Number of values read 42336000
func5: 941.081ms
Number of values read 42336000
func6: 962.831ms
Number of values read 42336000
func7: 2572.4ms
Number of values read 42336000
func8: 816.59ms
Number of values read 42336000
func8: 815.528ms
Number of values read 42336000
func7: 2578.6ms
Number of values read 42336000
func6: 948.185ms
Number of values read 42336000
func5: 932.139ms
Number of values read 42336000
func4: 6988.8ms
Number of values read 42336000
func3: 5750.03ms
Number of values read 42336000
func2: 6380.36ms
Number of values read 42336000
func1: 6050.45ms

总之，正如有人在评论中指出的那样，整数的实际解析占整个时间的相当大的一部分，因此读取文件并不像我最初所说的那么重要。即使是读取文件的一种非常幼稚的方式（使用fgetc()beats ifstream operator>>for integers。

可以看出，使用mmapto 加载文件比通过 读取文件稍快fstream，但只是稍微快一点。

于 2013-02-27T15:41:34.937 回答
3

您可以使用外部排序对文件中的值进行排序，而无需将它们全部加载到内存中。排序速度将受到您的硬盘驱动器能力的限制，但您将能够处理非常大的文件。这是实现。

于 2013-02-27T16:11:40.870 回答
0

尝试读取整数块并解析这些块，而不是逐行读取。

于 2013-02-27T15:38:29.670 回答
0

一种可能的解决方案是将大文件分成更小的块。分别对每个块进行排序，然后将所有已排序的块一一合并。

编辑：显然这是一种行之有效的方法。请参阅http://en.wikipedia.org/wiki/External_sorting上的“外部合并排序”

于 2013-02-27T15:42:19.470 回答
0

260MB 不算大。您应该能够将整个内容加载到内存中，然后对其进行解析。进入后，您可以使用嵌套循环读取行尾之间的整数并使用常用函数进行转换。在您开始之前，我会尝试为您的整数数组预分配足够的内存。

哦，您可能会发现粗糙的旧 C 风格文件访问函数是此类事情的更快选择。

于 2013-02-27T15:42:46.520 回答
0

你没有说你是如何阅读这些价值观的，所以很难说。尽管如此，实际上只有两个解决方案：`someIStream

anInt andfscanf( someFd, "%d", &anInt )` 从逻辑上讲，它们应该具有相似的性能，但实现方式有所不同；两者都值得尝试和衡量。

要检查的另一件事是您如何存储它们。如果你知道你有大约 2500 万，reserve那么在阅读它们之前做一个 3000 万std::vector可能会有所帮助。vector用 3000 万个元素构建 . 然后在看到结尾时修剪它也可能更便宜，而不是使用push_back.

最后，您可能会考虑编写一个immapstreambuf, 并将其用于mmap输入，然后直接从映射内存中读取它。甚至手动迭代它，调用 strtol（但这是更多的工作）；所有的流媒体解决方案可能最终都会调用strtol，或类似的东西，但首先要围绕调用做重要的工作。

编辑：

FWIW，我在我的家用机器（一个相当新的 LeNova，运行 Linux）上做了一些非常快速的测试，结果让我感到惊讶：

  • 作为参考，我使用 std::cin >> tmpand进行了简单、幼稚的实现，v.push_back( tmp );没有尝试优化。在我的系统上，这运行了不到 10 秒。

  • 简单的优化，例如reserve在向量上使用，或者最初创建大小为 25000000 的向量，并没有太大变化——时间仍然超过 9 秒。

  • 使用一个非常简单mmapstreambuf的 ，时间下降到大约 3 秒 - 使用最简单的循环， noreserve​​等。

  • 使用fscanf，时间下降到不到 3 秒。我怀疑 Linux 的实现FILE*也使用 mmap（并且std::filebuf不使用）。

  • 最后，使用 a mmapbuffer，迭代 two char*，并使用 stdtol 进行转换，时间下降到不到一秒，

这些测试完成得非常快（编写和运行所有测试不到一个小时），而且远非严格（当然，不要告诉您有关其他环境的任何信息），但差异让我感到惊讶。我没想到会有这么大的差异。

于 2013-02-27T15:49:40.253 回答
0

我会这样做：

#include <fstream>
#include <iostream>
#include <string>

using namespace std;

int main() {

    fstream file;
    string line;
    int intValue;
    int lineCount = 0;
    try {
        file.open("myFile.txt", ios_base::in); // Open to read
        while(getline(file, line)) {
            lineCount++;
            try {
                intValue = stoi(line);
                // Do something with your value
                cout << "Value for line " << lineCount << " : " << intValue << endl;

            } catch (const exception& e) {
                cerr << "Failed to convert line " << lineCount << " to an int : " << e.what() << endl;
            }
        }
    } catch (const exception& e) {
        cerr << e.what() << endl;
        if (file.is_open()) {
            file.close();
        }
    }

    cout << "Line count : " << lineCount << endl;

    system("PAUSE");
}
于 2013-02-27T15:53:10.507 回答
0

使用 Qt 将非常简单：

QFile file("h:/1.txt");
file.open(QIODevice::ReadOnly);
QDataStream in(&file);

QVector<int> ints;
ints.reserve(25000000);

while (!in.atEnd()) {
    int integer;
    qint8 line; 
    in >> integer >> line; // read an int into integer, a char into line
    ints.append(integer); // append the integer to the vector
}

最后，您拥有ints可以轻松排序的 QVector。如果文件格式正确，行数与向量的大小相同。

在我的机器 i7 3770k @4.2 Ghz 上，读取 2500 万个整数并将它们放入向量中大约需要 490 毫秒。从普通机械硬盘读取，而不是 SSD。

将整个文件缓冲到内存中并没有太大帮助，时间下降到 420 毫秒。

于 2013-02-27T15:58:31.673 回答