Временная сложность будет O(n log(n)) независимо от количества процессоров и/или количества внешних дисков. Общее время будет равно T(n/a logb(n)), но поскольку a и b являются константами, временная сложность остается неизменной при O(n log(n)), даже если время, скажем, в 10 раз быстрее. .
Мне непонятно, что вы подразумеваете под "параллельной" внешней сортировкой. Я предполагаю несколько ядер или несколько процессоров, но есть ли также несколько дисков? Все N ядер или процессоров совместно используют одну и ту же память, которая содержит только 1k элементов, или каждое ядро или процессор имеет свой собственный «1k» памяти (фактически имея «Nk» памяти)?
внешняя сортировка слиянием в целом
На начальном проходе входной массив считывается кусками размером B (1k элементов), сортируется, а затем записывается в K отсортированных файлов. Конечным результатом этого начального прохода являются K отсортированных файлов размера B (1k элементов). Все остальные проходы будут многократно объединять отсортированные файлы, пока не будет создан один отсортированный файл.
Начальный проход обычно привязан к процессору, и использование нескольких ядер или процессоров для сортировки каждого фрагмента размера B сократит время. Для начального прохода можно использовать любой метод сортировки или любой стабильный метод сортировки.
На этапе слияния возможность выполнять ввод-вывод параллельно с выполнением операций слияния сократит время. Использование многопоточности для перекрытия операций ввода-вывода с операциями слияния сократит время и будет проще, чем использование асинхронного ввода-вывода для выполнения той же задачи. Я не знаю, как использовать многопоточность для сокращения времени операции слияния k-way.
При слиянии k-way файлы считываются небольшими порциями размером B/(k+1). Это позволяет использовать k входных буферов и 1 выходной буфер для k-путевой операции слияния.
Для жестких дисков накладные расходы на произвольный доступ являются проблемой, скажем, скорость передачи составляет 200 МБ/с, а средние накладные расходы на произвольный доступ составляют 0,01 секунды, что соответствует времени передачи 2 МБ. Если размер буфера составляет 2 МБ, то накладные расходы на произвольный доступ эффективно снижают скорость передачи на 1/2 до ~ 100 МБ/с. Если размер буфера составляет 8 КБ, то накладные расходы на произвольный доступ эффективно снижают скорость передачи на 1/250 до ~ 0,8 МБ/с. С небольшим буфером двустороннее слияние будет быстрее из-за накладных расходов на произвольный доступ.
Для твердотельных накопителей в несерверной конфигурации обычно нет очереди команд, а накладные расходы на команды составляют около 0,0001 секунды при чтении и 0,000025 секунды при записи. Скорость передачи составляет около 500 МБ/с для SSD с интерфейсом Sata. Если размер буфера равен 2 МБ, накладные расходы на команду незначительны. Если размер буфера равен 4 КБ, то скорость чтения снижается на 1/12,5 до ~ 40 МБ/с, а скорость записи снижается на 1/3,125 до ~ 160 МБ/с. Поэтому, если размер буфера достаточно мал, двустороннее слияние снова будет быстрее.
На ПК эти сценарии с небольшим буфером маловероятны. В случае сортировки gnu для больших текстовых файлов с настройками по умолчанию выделяется чуть более 1 ГБ оперативной памяти, создаются отсортированные файлы размером 1 ГБ на начальном проходе и выполняется 16-стороннее слияние, поэтому размер буфера составляет 1 ГБ/17 ~. = 60 МБ. (17 для 16 входных буферов, 1 выходной буфер).
Рассмотрим случай, когда все данные умещаются в памяти и память состоит из k отсортированных списков. Временная сложность объединения списков будет O(n log(k)), независимо от того, используется ли двусторонняя сортировка слиянием, слияние пар списков в любом порядке или используется k-сторонняя сортировка слияния для объединения всех списков. списки за один проход.
Я провел некоторые тесты на своей системе, Intel 3770K 3,5 ГГц, Windows 7 Pro 64 бит. Для k-way слияния на основе кучи при k = 16 скорость передачи ~ 235 МБ/с, при k = 4 скорость передачи ~ 495 МБ/с. Для четырехстороннего слияния без кучи скорость передачи ~ 1195 МБ/с. Скорость передачи жесткого диска обычно составляет от 70 МБ/с до 200 МБ/с. Типичная скорость передачи SSD составляет ~ 500 МБ/с. Дорогие твердотельные накопители серверного типа (SAS или PCIe) имеют скорость чтения до ~2 ГБ/с и скорость записи ~1,2 ГБ/с.
person
rcgldr
schedule
16.02.2019
