2

我正在尝试在一个非常大的数据集上实现一个 i/o 密集型快速排序（C++ qsort）。为了速度，我想一次将一大块数据读入缓冲区，然后使用 qsort 在缓冲区内对其进行排序。（我目前正在处理文本文件，但想尽快转向二进制文件。）但是，我的数据由可变长度记录组成，并且需要告诉 qsort 记录的长度才能进行排序。有什么办法可以标准化吗？我唯一能想到的是相当复杂：我的程序当前从缓冲区读取，直到它遇到换行符（ascii 中的“10”），将每个字符转移到另一个数组。当它找到换行符（输入文件中的分隔符）时，它用空字符填充该记录的缓冲区中剩余的空间数（记录大小设置为 30）。这样，我应该得到一个充满固定大小记录的缓冲区来提供 qsort。

我知道我的方法有几个问题，一个是它很笨拙，另一个是记录大小可能会大于 30，但通常要小得多。有没有更好的方法来做到这一点？

同样，我当前的代码甚至不起作用。当我调试它时，它似乎正在将字符从一个缓冲区传输到另一个缓冲区，但是当我尝试打印出缓冲区时，它只包含第一条记录。

这是我的代码：

FILE *fp;
unsigned char *buff;
unsigned char *realbuff;
FILE *inputFiles[NUM_INPUT_FILES];
buff = (unsigned char *) malloc(2048);
realbuff = (unsigned char *) malloc(NUM_RECORDS * RECORD_SIZE);

fp = fopen("postings0.txt", "r");
if(fp)
{
    fread(buff, 1, 2048, fp);


    /*for(int i=0; i <30; i++)
     cout << buff[i] <<endl;*/

    int y=0;
    int recordcounter = 0;

    //cout << buff;
    for(int i=0;i <100; i++)
    {
        if(buff[i] != char(10))
        {
            realbuff[y] = buff[i];
            y++;
            recordcounter++;
        }        
        else
        {
            if(recordcounter < RECORD_SIZE)
                for(int j=recordcounter; j < RECORD_SIZE;j++)
                {
                    realbuff[y] = char(0);
                    y++;
                }
            recordcounter = 0;
        }
    } 

    cout << realbuff <<endl;   
    cout << buff;
}
else 
    cout << "sorry";

非常感谢，bsg

4

2 回答 2

1

qsort 函数只能在固定长度的记录上工作（就像你说的那样）。为了对可变长度记录进行排序，您需要一个指向它们的指针数组，然后让 qsort 对指针数组进行排序。这也可能更有效，因为指针的移动速度比大块数据快得多。

std::sort 也是如此，推荐使用它，因为它是类型安全的。只需确保提供一个比较谓词（小于函数），将指针作为其参数作为第三个参数。

于 2010-03-03T06:37:08.170 回答
0

使用c++ 文件流解析文件怎么样？

查看此示例（网站名称很奇怪，无意冒犯！！），它将记录作为STL 向量返回 ，然后您可以使用STL 排序算法。

于 2010-03-03T06:47:18.220 回答