これは面接でよくある質問であり、一部の大手企業もこの質問を面接の質問として使用することを好みます。 。
質問: たとえば、これらの不規則で固有でない数値が保存されている 1g ファイルがあります。全体の並べ替えを完了するのに 100m を使用するにはどうすればよいですか?
実装プロセスは :
1. まず、グループ内の 10,000 行ごとに大きなファイルを 1 行ずつ読み取り、次にファイルを書き込みます。並べ替え の後、ファイル全体が読み取られて分割されるまで、ファイル名は t1.txt、t2.txt... のようになります (
2)。その後、すべてのファイルを走査し、各ファイルは最初に最初の 1 行で、が一時的な並べ替え配列 $tmpNums** に入れられ、次に最小値が取得され、** が一時的な保存配列 $nums に入れられ、現在のインデックス値が取得されます。位置も同時に記録されます $idx3. From 最小値が位置するインデックスに対応するファイルから次の番号を取得し、それを一時的な並べ替え配列の現在のインデックスに入れて、繰り返しを続けますすべてのファイルのすべての内容が読み取られるまでステップ 2 の操作を繰り返し、その後ファイル全体が並べ替えられます。
次は PHP のマルチウェイ マージ ソートのデモ コードであり、単純なスケルトン構造です。たとえば、min は最小値部分を取り、これを固定長の最小ヒープ実装に拡張できます。または、値とその値が配置されているファイルを保存できる優先キュー。
PHP マルチチャネル マージ デモ コード: function multiWaySort()
{
// 读取所有的文件描述符
$fds = [];
$dir = scandir('./runtime/txt/');
foreach ($dir as $file) {
if ($file != '.' && $file != '..') {
$fds[] = fopen('./runtime/txt/' . $file, 'rb');
}
}
// 读取每个文件的第一行内容，放入临时排序数组
$tmpNums = [];
foreach ($fds as $fd) {
$tmpNums[] = (int)fgets($fd);
}
$nums = [];
$count = 0;
while (true) {
if (empty($tmpNums)) break;
// 最小值放入临时存储数组
$value = min($tmpNums);
$nums[] = $value;
// 读取最小值所在索引，对应的文件下一行内容
$idx = array_search($value, $tmpNums);
$next = fgets($fds[$idx]);
if (!$next) {
unset($tmpNums[$idx]);
unset($fds[$idx]);
} else {
$tmpNums[$idx] = (int)$next;
}
// 临时存储数组到达一定数量追加写入文件一次
if (count($nums) == 20) {
foreach ($nums as $value) {
$f = fopen('./runtime/result.txt', 'ab+');
fwrite($f, $value . PHP_EOL);
}
$nums = [];
}
if ($count == 4999999) {
continue;
}
$count++;
}
}推奨学習: 「
《
K-wayマージソートの詳細解説（実戦）大規模ファイルソート・外部の問題がわかる記事1つ》記憶の整理