как работает алгоритм внешней сортировки слиянием?

<p>я пытаюсь понять, как работает внешний алгоритм сортировки слиянием (я нашел ответы на один и тот же вопрос, но не нашел того, что мне нужно). я читаю книгу «анализ алгоритмов» джеффри макконнелла и пытаюсь реализовать алгоритм, описанный там.</p><p>например, у меня есть входные данные: <code>3,5,1,2,4,6,9,8,7</code>, и я могу загрузить только 4 числа в память.</p><p>мой первый шаг - прочитать входной файл в виде 4-значных блоков, отсортировать их в памяти и записать один в файл a, а затем в файл b.</p><p>я получил: </p><pre><code>a:[1,2,3,5][7] b:[4,6,8,9] </code></pre><p>теперь мой вопрос, как я могу объединить куски из этих файлов с большими, если они не помещаются в память? джеффри макконнелл написал, что мне нужно прочитать половину фрагментов и объединить их в следующие файлы c и d.</p><p>но я получил неправильную последовательность:</p><pre><code>c:[1,2,4,6,3,8,5,9] d:[7] </code></pre><p>кто-нибудь может привести пример с пошаговой инструкцией, пожалуйста?</p><p>ps: я понимаю, как объединять число за номером, читая из файла, но как мне сделать это с буферами в памяти, чтобы уменьшить количество операций ввода-вывода?</p>

<p>я думаю, что после такого долгого времени у тебя, должно быть, есть ответ. но я все еще предоставляю некоторые примеры ссылок, чтобы помочь кому-то еще, кто задал этот вопрос.</p><p>примечание. перед просмотром этой ссылки вы должны иметь представление о структуре данных <strong>heap</strong> взгляните на <strong> <a href="http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/ln250\_weiss/l17-externalsortex1.htm">пример двусторонней сортировки</a> и <a href="http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/ln250\_weiss/l17-externalsortex2.htm">пример многосторонней внешней сортировки</a> </strong> и вы получите полное представление о реализации алгоритма внешней сортировки</p>

<p>прежде всего, сортируя числа по частям по 4 числа, вы должны получить 3 порции.</p><pre><code>a:[1,2,3,5] b:[4,6,8,9] c:[7] </code></pre><p>затем вы прочитаете половину каждого файла (игнорируйте c, так как он не подходит) и объедините их. итак, вы загрузите в память {[1, 2], [4, 6]}. вы сделаете случайное слияние и запишите результат в новый блок d:</p><pre><code>compare 1 and 4 -> d:[1] compare 2 and 4 -> d:[1, 2] </code></pre><p>теперь часть a, которая была в ram, завершила слияние, так что теперь вам нужно будет перенести вторую половину в память. теперь ваша память будет иметь {[3, 5], [4, 6]}.</p><pre><code>compare 3 and 4 -> d:[1, 2, 3] compare 5 and 4 -> d:[1, 2, 3, 4] compare 5 and 6 -> d:[1, 2, 3, 4, 5] </code></pre><p>все фрагменты a были объединены, так что теперь просто добавьте остаток b в d</p><pre><code>d:[1,2,3,4,5,6,8,9] </code></pre><p>теперь вам придется выполнить тот же процесс с кусками c и d. помните, что c может иметь более одного числа в другом примере. объединяя c и d, вы получите новый фрагмент e, который будет последним отсортированным файлом.</p><p>также обратите внимание, что в более крупном примере вам может понадобиться больше фаз слияния. например, если у вас есть 20 чисел для сортировки, вы создадите 5 кусков по 4 числа, а затем вы будете объединять и объединять два из них каждый раз, что приведет к получению 2 кусков по 8 чисел (плюс один дополнительный из 4 чисел), и затем объедините новые фрагменты в одно из 16 чисел и так далее.</p>

<p>вы будете перебирать файлы одновременно.</p><p>просто начните с начала каждого файла и продолжайте выбирать, какой элемент файла не больше (то есть меньше или равен) другого, выводите этот элемент в новый файл и увеличивайте итератор.</p><p>из вашего последнего утверждения неясно, знаете ли вы это уже или нет, но это все, что вам нужно сделать, потому что:</p><ul> <li><p>вам нужно было бы иметь только одно число в памяти для каждого из файлов, и, конечно, любые индексы и другие переменные, которые предположительно игнорируются для целей этого упражнения.</p></li> <li><p>вам нужно прочитать каждый файл только один раз, так как вы можете держать файлы открытыми в правильном положении во время этого процесса, поэтому вам не нужно снова читать весь файл, чтобы добраться до правильного положения.</p></li> </ul><p>таким образом, для:</p><pre><code>a:[1,2,3,5] b:[4,6,8,9] </code></pre><p>вы начинаете с первого элемента из каждого файла - <code>1</code> и <code>4</code>.</p><p><code>1</code> меньше, поэтому вы выводите его в новый файл и переходите к <code>2</code>.</p><p><code>2</code> меньше, чем <code>4</code>, поэтому вы выводите его и переходите к <code>3</code>.</p><p><code>3</code> меньше, чем <code>4</code>, поэтому вы выводите его и переходите к <code>5</code>.</p><p><code>4</code> меньше, чем <code>5</code>, поэтому вы выводите его и переходите к <code>6</code>.</p><p><code>5</code> меньше, чем <code>6</code>, поэтому вы выводите его, а затем вы достигли конца a.</p><p>теперь просто выведите остаток b: <code>6, 8, 9</code>.</p><p>это дает вам <code>[1,2,3,4,5,6,8,9]</code>.</p>

<p>внешняя сортировка обычно используется, когда вам нужно отсортировать файлы, которые слишком велики, чтобы уместиться в память.</p><p>хитрость заключается в том, чтобы разбить больший входной файл на k отсортированных меньших фрагментов, а затем объединить фрагменты в больший отсортированный файл. для слияния используйте минимальную кучу. к будет зависеть от вашего порога памяти.</p><p>прочитайте определенное количество записей (в зависимости от порога памяти) из каждого чанка и поместите его в очередь на чанк.</p><p>извлеките самый левый элемент (это будет самый маленький элемент, так как элементы в очереди будут отсортированы) из каждой очереди и поместите его в кучу</p><p>поместите минимальный предмет из кучи. обратите внимание, из какой очереди это произошло</p><p>пополнить очередь следующим элементом из соответствующего куска, которого нет в очереди</p><p>выдвиньте самый левый элемент из очереди и поместите его в кучу</p><p>запишите элемент min в выходной файл</p><p>продолжайте описанные выше 4 шага, пока куча не опустеет</p><p>пример кода python (не объединяется на месте)</p><pre><code>import os import heapq import itertools import linecache from collections import deque import sys def external\_sort(input\_directory, input\_file\_name, output\_file\_name): with open(os.path.expanduser(input\_directory + '/' + output\_file\_name), 'w+') as f: heap = [] pages = {} next\_line\_numbers = {} has\_more\_items = {} chunk\_file\_paths, max\_chunk\_size = create\_sorted\_chunks(input\_directory, input\_file\_name) max\_page\_size = max\_chunk\_size // 10 for chunk\_file\_path in chunk\_file\_paths: pages[chunk\_file\_path] = populate\_page(chunk\_file\_path, max\_page\_size) next\_line\_numbers[chunk\_file\_path] = len(pages[chunk\_file\_path]) has\_more\_items[chunk\_file\_path] = true for chunk\_file\_path in chunk\_file\_paths: heapq.heappush(heap, pages[chunk\_file\_path].popleft()) while heap: item, chunk\_file\_path = heapq.heappop(heap) f.write(str(item)+'\n') if has\_more\_items[chunk\_file\_path]: has\_more\_items[chunk\_file\_path] = append\_next(pages, chunk\_file\_path, next\_line\_numbers[chunk\_file\_path]) next\_line\_numbers[chunk\_file\_path] += 1 if pages[chunk\_file\_path]: heapq.heappush(heap, pages[chunk\_file\_path].popleft()) for chunk\_file\_path in chunk\_file\_paths: os.remove(chunk\_file\_path) def populate\_page(chunk\_file\_path, max\_page\_size): chunk = deque() with open(chunk\_file\_path, 'r') as f: for line in itertools.islice(f, 0, max\_page\_size): chunk.append((int(line), chunk\_file\_path)) return chunk def append\_next(chunks, chunk\_file\_path, line\_number): chunk = chunks[chunk\_file\_path] item = linecache.getline(chunk\_file\_path, line\_number) if item and len(item) > 0: chunk.append((int(item), chunk\_file\_path)) has\_more = true else: has\_more = false return has\_more def create\_sorted\_chunks(input\_file\_directory, input\_file\_name): input\_file\_path = os.path.expanduser(input\_file\_directory + '/' + input\_file\_name) suffix = 1 begin, end, tot = 0, 0, 0 chunk\_file\_paths = [] with open(input\_file\_path, 'r') as f: for line in f.readlines(): tot += 1 end = tot//10 while suffix <= 10: buffer = [] chunk\_file\_name = 'temp' + str(suffix) + '.txt' chunk\_file\_path = os.path.expanduser(input\_file\_directory + '/' + chunk\_file\_name) if not os.path.isfile(chunk\_file\_path): with open(os.path.expanduser(input\_file\_path), 'r') as f: for line in itertools.islice(f, begin, end): buffer.append(int(line)) create\_chunk(chunk\_file\_path, buffer) suffix += 1 begin = end end += tot//10 chunk\_file\_paths.append(chunk\_file\_path) return chunk\_file\_paths, tot//10 def create\_chunk(chunk\_file\_path, buffer): buffer.sort() with open(chunk\_file\_path, 'w+') as f: for i in buffer: f.write(str(i) + '\n') if \_\_== '\_\_main\_\_': external\_sort(sys.argv[1], sys.argv[2], sys.argv[3]) </code></pre>

<p>пожалуйста, прочитайте файл <strong>readme</strong>, чтобы правильно понять сортировку слиянием.</p><blockquote> <p>определена пошаговая реализация</p> </blockquote><p> <a href="https://github.com/melvilgit/external-merge-sort/blob/master/readme.md">https://github.com/melvilgit/external-merge-sort/blob/master/readme.md</a> </p>