이는 일반적인 면접 질문이며 일부 주요 회사에서도 이 질문을 면접 질문으로 사용하는 것을 좋아합니다.
질문: 예를 들어 이러한 무질서하고 고유하지 않은 숫자를 저장하는 1g 파일이 있습니다. 100m를 사용하여 전체 정렬을 완료하는 방법은 무엇입니까?
구현 과정은 :
1. 먼저 큰 파일을 한 줄씩, 10,000줄씩 그룹으로 읽은 다음 정렬하여 파일에 씁니다 . txt, t2.txt... 이러한 이름은 전체 파일을 읽고 분할할 때까지
2. 그런 다음 모든 파일을 탐색하고 먼저 각 파일의 첫 번째 줄을 읽고 임시 정렬 배열 $tmpNums*에 넣습니다. *, 최소값을 취하고, **임시저장 배열 $nums에 넣고, 현재 위치 $idx
3의 인덱스 값을 기록합니다. 3. 최소값이 있는 인덱스에 해당하는 파일에서 숫자를 가져옵니다. 찾은 후 임시 정렬 배열의 현재 인덱스에 넣은 후 첫 번째 작업을 계속 반복합니다. 모든 파일의 내용을 모두 읽을 때까지 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++;
}
}추천 학습: "PHP 비디오 튜토리얼"
K-way 병합 정렬(실제 전투)에 대한 자세한 설명"
"파일 정렬/외부 저장소 정렬 문제에 대해 자세히 알아볼 수 있는 기사》