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

Ответ 1

Думаю, после такого долгого времени вы должны получить ответ. Но я по-прежнему предоставляю некоторые примеры ссылок, чтобы помочь кому-то другому, кто обращается к этому вопросу.

ПРИМЕЧАНИЕ. Перед рассмотрением этой ссылки вы должны иметь представление о структуре данных Heap Взгляните на Пример двухсторонней сортировки и Пример многоуровневой внешней сортировки и вы получите полное представление о реализации внешнего алгоритма сортировки

Ответ 2

Прежде всего, сортируя числа в частях из четырех чисел, вы должны получить 3 куска.

A:[1,2,3,5]  
B:[4,6,8,9]
C:[7]

Затем вы прочтете половину каждого файла (игнорируйте C, так как он не подходит) и объедините их. Таким образом, вы загрузите в память {[1, 2], [4, 6]}. Вы выполните случайное слияние и напишите результат в новом фрагменте D:

Compare 1 and 4 -> D:[1]
Compare 2 and 4 -> D:[1, 2]

Теперь часть A, которая была в ОЗУ, закончила слияние, так что теперь вам придется принести вторую половину в памяти. Теперь ваша память будет иметь {[3, 5], [4, 6]}.

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]

Все фрагменты A были объединены, поэтому теперь просто добавьте остальную часть B в D

D:[1,2,3,4,5,6,8,9]

Теперь вам нужно будет сделать тот же процесс с кусками C и D. Помните, что C может иметь более одного номера в другом примере. После объединения C и D вы получите новый фрагмент E, который будет окончательным отсортированным файлом.

Также обратите внимание, что в большем примере вам может потребоваться больше фаз слияния. Например, если у вас было 20 номеров для сортировки, вы бы создали 5 кусков из 4 чисел, и тогда вы каждый раз объединяли бы и объединяли два из них, в результате получилось бы 2 куска из 8 чисел (плюс один лишний из 4 чисел) и затем объединить новые куски в один из 16 номеров и т.д.

Ответ 3

Вы будете перебирать файлы одновременно.

Просто начните с начала каждого файла и продолжайте выбирать, какой бы элемент файла не был больше (т.е. меньше или равен), чем другой, вывести этот элемент в новый файл и увеличить итератор.

Из вашего последнего утверждения, неясно, знаете ли вы, что это уже сделано, но это все, что вам нужно сделать, потому что:

• Вам нужно будет иметь только один номер в памяти для каждого из файлов и, конечно, любые индексы и другие переменные, которые, по-видимому, игнорируются для целей этого упражнения.

• Вам нужно только один раз прочитать каждый файл, так как вы можете держать файлы открытыми в правильной позиции во время этого процесса, поэтому вам не нужно снова читать весь файл, чтобы добраться до правильной позиции.

Итак, для:

A:[1,2,3,5]
B:[4,6,8,9]

Вы начнете с первого элемента из каждого файла - 1 и 4.

1 меньше, поэтому вы выводите его в новый файл и переходите к 2.

2 меньше 4, поэтому вы выводите его и переходите к 3.

3 меньше 4, поэтому вы выводите его и переходите к 5.

4 меньше, чем 5, поэтому вы выводите его и переходите к 6.

5 меньше, чем 6, поэтому вы выводите это, а затем вы достигли конца A.

Теперь просто выведите оставшуюся часть B: 6, 8, 9.

Это дает вам [1,2,3,4,5,6,8,9].

Ответ 4

Внешняя сортировка обычно используется, когда вам нужно сортировать файлы, которые слишком велики, чтобы вписаться в память.

Трюк состоит в том, чтобы разбить больший входной файл на k отсортированных меньших фрагментов, а затем объединить куски в более крупный отсортированный файл. Для слияния используйте кучу минут. k будет зависеть от вашего порога памяти.

Прочитайте определенное количество записей (в зависимости от порога памяти) от каждого фрагмента и поместите его в очередь на кусок.

Поставьте самый левый элемент (это будет самый маленький элемент, поскольку элементы в очереди будут отсортированы) из каждой очереди и нажмите на кучу

Поместите элемент min из кучи. Обратите внимание, какая очередь из

Пополнение очереди очередным элементом из соответствующего блока, который не находится в очереди

Поместите левый самый элемент из очереди и нажмите его в кучу

Напишите элемент min в выходной файл

Продолжайте вышеуказанные 4 шага до тех пор, пока куча не станет пустой.

Пример кода python (не сливается на месте)

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 __name__ == '__main__':
    external_sort(sys.argv[1], sys.argv[2], sys.argv[3])