4

我正在从文件中读取大量数据：

//abc.txt

10  12  14  15  129

-12 14 -18  -900 -1234

145 12 13
12

32 68 51 76 -59 -025 

- - - - etc

fun(char *p, int x, int y, int z) {

}

我尝试使用atoi, strtok，但是当数组太大并且sscanf速度也很慢时，它们会非常耗时。

如何提高海量数据的性能？

我strtok用于解析。我正在寻找解析每一行的快速方法。

我正在阅读每一行，然后将每一行解析为：

 char * ptr;
 ptr = strtok (str," ");
 while (ptr != NULL)
 {
    int value1 = atoi(ptr) ;
    ptr = strtok (NULL, " ");
 }
  • 有什么快速的方法可以将字符串解析成int?
  • 有没有比上面的代码更快的替代方法？我正在使用atoi转换char *为int.
  • 我可以使用其他快速方法转换char *为int吗？
4

5 回答 5

3

你找错地方了。问题不在于解析，除非您正在做一些真正奇怪的事情。在现代 N Ghz CPU 上，每行所需的周期很小。影响性能的是物理 I/O。旋转的东西往往以 10 秒 / 秒的速度运行。

我也怀疑问题在于文件的物理读取，因为这将有效地缓存在文件系统缓存中。

不，正如samy.vilar 所暗示的，这个问题几乎可以肯定是虚拟内存问题：

...数组太大了...

使用系统监视器/psinfo/top 查看您的应用程序。几乎可以肯定，它正在增加一个大型工作集，因为它构建了一个内存阵列，并且您的操作系统正在将其分页到磁盘。

所以忘记阅读作为一个问题。您真正的问题是如何操作内存中的庞大数据集。这里的方法是多种多样的：

  • 不。批量处理数据和操作批次。
  • 使用节省空间的存储（例如紧凑的元素）。
  • 分配更多的内存资源。

SO上有很多关于这个的讨论。

于 2012-06-18T09:22:10.240 回答
3

要将 ASCII 字符串转换为整数值，您不能比atoi正在执行的操作快得多，但您可以通过实现内联使用的转换函数来加快速度。下面的版本将指针递增超过扫描的数字，因此它与语义不匹配atoi，但它应该有助于提高解析器效率，如下图所示。（显然缺少错误检查，所以如果需要，请添加它。）

static inline int my_parsing_atoi(const char *&s) {
    if (s) {
        bool neg = false;
        int val = 0;
        if (*s == '-') { neg = true; ++s; }
        for (;isdigit(*s);++s) val = 10*val + (*s - '0');
        return neg ? -val : val;
    }
    return 0;
}

const char *p = input_line;
if (p) {
    p += strspn(p, " ");
    while (*p) {
        int value1 = my_parsing_atoi(p);
        p += strspn(p, " ");
    }
}

确保您已经正确地分析了您的代码，以便您知道您的例程受计算限制而不是 I/O 限制。大多数情况下，您会受到 I/O 限制，下面的建议是缓解这种情况的方法。

如果您正在使用 C 或 C++ 文件读取例程，例如freador fstream，您应该会获得已经非常有效的缓冲读取，但您可以尝试使用底层操作系统调用（例如 POSIX read）来读取更大块中的文件同时加快文件读取效率。真正花哨的是，您可以在处理文件时执行文件的异步读取，可以使用线程，也可以使用aio_read. 您甚至可以使用mmap，这将消除一些数据复制开销，但如果文件非常大，您将需要管理地图，以便您munmap扫描文件mmap的部分和要扫描的新部分。

我使用如下代码对上面的解析例程和 OP 的例程进行了基准测试：

clock_t before_real;
clock_t after_real;
struct tms before;
struct tms after;
std::vector<char *> numbers;
make_numbers(numbers);
before_real = times(&before);
for (int i = 0; i < numbers.size(); ++i) {
    parse(numbers[i]);
}
after_real = times(&after);
std::cout << "user: " << after.tms_utime - before.tms_utime
          << std::endl;
std::cout << "real: " << after_real - before_real
          << std::endl;

和之间的区别在于real，user这real是挂钟时间，user而是操作系统运行进程所花费的实际时间（因此上下文切换不计入运行时间）。

我的测试让我的例程运行速度几乎是 OP 例程的两倍（g++ -O3在 64 位 Linux 系统上编译）。

于 2012-06-18T06:06:06.063 回答
1

If your file is truly huge, then the IO is what's killing you, and not the parsing. Every time you read a line, you're executing a system call, which can be quite expensive.

A more efficient alternative may be to use Memory-Mapped File IO. If you're working on a POSIX system such as Linux, you can use the mmap command which loads the file all at once and returns a pointer to its location in memory. The memory manager then takes care of reading and swapping the file in/out as you access data through that pointer.

This would look something like this

#include <sys/mman.h>
int fd = open( 'abc.txt' , O_RDONLY );
char *ptr = mmap( NULL , length , PROT_READ , MAP_PRIVATE , fd , 0 );

but I would strongly advise you to read the man page and find the best options for yourself.

于 2012-06-18T09:44:52.063 回答
0

  1. 如果您的文件包含 int 数字，则可以使用operator>>，但这是 c++ 唯一的解决方案。就像是 ：

    std::fstream f("abc.txt");
int value = 0;
f >> value

  2. 如果您将文件转换为包含二进制数字表示，您将有更多选项来提高性能。它不仅避免将数字从字符串解析为类型，而且您还有其他选项来访问您的数据（例如使用mmap）。

于 2012-06-18T05:57:11.007 回答
0

首先，一般建议是始终使用分析来检查它实际上是缓慢的翻译，而不是其他东西，例如从磁盘物理读取文件。

您可以通过编写自己的最小数字解析函数来提高性能。strtok 修改字符串，所以它不会是最佳速度，如果您知道所有数字都是十进制整数，并且您不需要任何错误检查，您可以稍微简化翻译。

一些没有 strtok 的代码可能会加速一行的处理，如果它实际上是翻译而不是（例如）I/O 问题。

void handle_one_number(int number) {
    // ....
}

void handle_numbers_in_buffer(char *buffer) {
    while (1) {
        while (*buffer != '\0' && isspace(*buffer))
            ++buffer;
        if (*buffer == '\0')
            return;
        int negative = 0;
        if (*buffer == '-') {
            negative = 1;
            ++buffer;
        }
        int number = 0;
        while (isdigit(*buffer)) {
            number = number * 10 + *buffer - '0';
            ++buffer;
        }
        if (negative)
            number = -number;
        handle_one_number(number);
    }
}

我实际上去运行了一些基准测试。我曾预计 I/O 会占主导地位，但事实证明（通常需要注意的是“在我的特定系统上，使用我的特定编译器”）解析数字需要相当多的时间。

通过从 strtok 版本更改为我上面的代码，我设法将翻译 1 亿个数字（文本已经在内存中）的时间从 5.2 秒缩短到 1.1 秒左右。从慢速磁盘（Caviar Green）读取时，我测量到从 5.9 秒到 3.5 秒的改进。从 SSD 读取数据时，我测量到从 5.8 秒到 1.8 秒的改进。

我还尝试使用 直接读取文件while (fscanf(f, "%d", ....) == 1) ....，但结果要慢得多（10 秒），可能是因为 fscanf 是线程安全的，并且更多的调用需要更多的锁定。

（Ubuntu 11.04 上的 GCC 4.5.2 具有 -O2 优化，每个版本的多次执行，在运行之间刷新磁盘缓存，i7 处理器。）

于 2012-06-18T06:11:55.880 回答