2025年如何排序10亿个数--外排小试

科技前沿 • 2025-03-23 07:00 • 阅读 27

大家好，我是讯享网，很高兴认识大家。

0.思路

10亿个32位整数需要4G左右的内存，一次性载入内存是不现实的，必须要采用外排。第一次接触，当然是从最简单的办法入手。

我们可以利用大容量的外存作为中转，将10亿个数切分成小块，每一块排序好后写入外存。
切分完成后，对这些小块进行归并排序。同时在归并排序过程中，获得最大（小）值将实时写入文件，这样就可以保证低内存占用。

注：下面的例子为升序排序

1.切分10亿个数

假设’billion’文件为包含10亿个32位整数数的二进制文件，我们需要将’billion’切分为n个小块（我取n为100，即每块个数）暂存在外存。其中每块文件均需被排序，这里我用的是c的库函数qsort

需要注意的是，如果块大小过大（比如我取的*4字节），块将无法作为auto数组分配，只能设为静态数组

static __int32 piece[PIECESIZE]; //PIECESIZE为块大小 FILE *billion = fopen( "billion", "rb" ); int i = 0; while( i < TOTAL / PIECESIZE ){ //TOTAL为billion文件中整数的数量 //读取一块 fseek( billion, PIECESIZE * i, SEEK_SET ); fread( piece, sizeof( *piece ), PIECESIZE, billion ); //排序 qsort( piece, PIECESIZE, sizeof( *piece ), comp ); char fileName[200]; snprintf( fileName, sizeof(fileName), "piece/piece%d.bin", i ); //输出 FILE *outFile = fopen( fileName, "wb" ); fwrite( piece, sizeof( *piece ), PIECESIZE, outFile ); fclose( outFile ); ++i; }

讯享网

讯享网int comp( const void *a, const void *b ) { return *(__int32*)a - *(__int32*)b; }

2.对这n块进行归并排序

10亿个文件已经切分成n块了，并且这n块已经为有序，于是我们可以利用归并排序读取这n块，并将每次的结果实时写入文件。在这期间内存的消耗将维持在很低的水平。

FILE *outFile = fopen( "out", "wb" ); FILE *fileList[FILEAMOUNT]; //FILEAMOUNT即为块的数量 int i; //打开n个块 for( i = 0; i < FILEAMOUNT; ++i ){ char filePath[200]; snprintf( fileName, sizeof(fileName), "piece/piece%d.bin", i ); fileList[i] = fopen( filePath, "rb" ); } //每个块读取第一个（最小的）元素 int numbers[ FILEAMOUNT ]; for( i = 0; i < FILEAMOUNT; ++i ){ fread( numbers + i, sizeof( __int32 ), 1, fileList[i] ); } int n = 0; //归并 while( 1 ){ int minIndex = MinIndex( numbers ); if( minIndex == -1 ) break; //所有文件读取完毕 //实时写入 fwrite( numbers + minIndex, sizeof( __int32 ), 1, outFile ); ++n; fread( numbers + minIndex, sizeof( __int32 ), 1, fileList[minIndex] ); if( feof( fileList[minIndex] ) ){ numbers[minIndex] = -1; //本文件读取完毕 } } //操作完成，关闭文件 for( i = 0; i < FILEAMOUNT; ++i ){ fclose( fileList[i] ); } fclose( outFile );

其中MinIndex函数获取数组中最小的值的下标，同时遇到-1会跳过（因为我用-1作为文件读取完毕的标记）。MinIndex函数如果返回-1则代表所有文件读取完毕（数组中全是-1）

讯享网int MinIndex( int *arr ) { int i, index = -1; for( i = 0; i < FILEAMOUNT; ++i ){ if( arr[i] == -1 ) continue; //判断文件是否读取完毕 if( index == -1 || arr[index] > arr[i] ) index = i; } return index; }

2025年如何排序10亿个数--外排小试

0.思路

1.切分10亿个数

2.对这n块进行归并排序

3.总结

相关推荐