Dies ist eine häufige Frage im Vorstellungsgespräch, und einige große Unternehmen verwenden diese Frage auch gerne als Frage im Vorstellungsgespräch.
Frage: Es gibt beispielsweise eine 1g-Datei, in der diese ungeordneten und nicht eindeutigen Zahlen gespeichert werden, um die Gesamtsortierung abzuschließen.
Der Implementierungsprozess ist :
1. Lesen Sie zuerst die große Datei Zeile für Zeile, alle 10.000 Zeilen in einer Gruppe, dann sortieren Sie sie und schreiben Sie sie in die Datei . txt, t2.txt... Ein solcher Name, bis die gesamte Datei gelesen und aufgeteilt ist,
2 Dann alle Dateien durchlaufen, zuerst die erste Zeile jeder Datei lesen, sie in das temporäre Sortierarray $tmpNums* einfügen. *, und nehmen Sie dann den Mindestwert, **Legen Sie ihn in das temporäre Speicherarray $nums und zeichnen Sie den Indexwert der aktuellen Position $idx
3 auf. Nehmen Sie eine Zahl aus der Datei, die dem Index entspricht, an dem sich der Mindestwert befindet Wenn es gefunden wird, fügen Sie es in den aktuellen Index des temporären Sortierarrays ein und wiederholen Sie dann den ersten Vorgang. Der zweistufige Vorgang wird ausgeführt, bis der gesamte Inhalt aller Dateien gelesen wurde, und dann wird die gesamte Datei neu angeordnet.Das Folgende ist ein PHP-Democode für die Mehrweg-Merge-Sortierung, bei dem es sich nur um eine einfache Skelettstruktur handelt. Min nimmt beispielsweise den Mindestwertteil an, der zu einer Mindestheap-Implementierung mit fester Länge oder einer Prioritätswarteschlange erweitert werden kann , wodurch der Wert und die Datei, in der er sich befindet, gespeichert werden können
PHP-Mehrweg-Merge-Democode:
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++;
}
}
Empfohlenes Lernen: „PHP-Video-Tutorial“
Referenz:
„Detaillierte Erklärung der K-Way-Merge-Sortierung (tatsächlicher Kampf)“
„Ein Artikel, um mehr über das Problem bei der Sortierung von Dateien/externem Speicher zu erfahren》