Оптимальный k-way шаблон слияния

Question

Мне нужно объединить n отсортированных файлов фиксированных записей разных размеров, используя k одновременных потребителей, где k

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

Простой пример проясняет это. Рассмотрим случай 4 файлов с 1, 1, 10 и 10 записями соответственно и 3 потребителями. Нам нужны два шага слияния для объединения всех файлов. Начните с 3 потребителей на первом этапе. Последовательность слияния ((1, 1, 10), 10) приводит к 12 операциям чтения / записи на (внутреннем) шаге 1 и 22 операциям на (внешнем) шаге 2, что составляет в общей сложности 34 операции. Последовательность (1, (1,10,10)) еще хуже с 21 + 22 = 43 операциями. Напротив, если мы используем только 2 потребителя на первом этапе и 3 на втором этапе, шаблон объединения ((1,1), 10,10) занимает всего 2 + 22 = 24 операции. Здесь наша сдержанность прекрасно окупается.

Мое решение для выбора нужного количества потребителей на каждом этапе заключается в следующем. Все возможные состояния слияния можно упорядочить в ориентированный граф (который, как я полагаю, является решеткой) с количеством операций для перемещения из одного состояния в другое, привязанным к каждому ребру в качестве стоимости. Затем я могу использовать алгоритм кратчайшего пути для определения оптимальной последовательности.

Проблема с этим решением состоит в том, что количество узлов взрывается даже при небольшом количестве файлов (скажем, сотнях) и даже после применения некоторых разумных ограничений (таких как сортировка файлов по размеру и разрешение только слияний из верхних 2). .k этого списка). Более того, я не могу избавиться от ощущения, что может быть «аналитическое» решение этой проблемы или, по крайней мере, простая эвристика, которая очень близка к оптимальной.

Любые мысли приветствуются.

Answer 1

Во-первых, альтернативный алгоритм

read all record keys (N reads) with a fileid
sort them
read all files and place the records in the final position according to the sorted key (N R/W)

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

Преимущество - только N * 2 чтения и N записи.

Вернуться к вашему алгоритму

Стоит ли объединять большие файлы с маленькими файлами в произвольной точке объединения? Нет

• например. (1,1,10,10) -> ((1,10), (1,10)) [2 * 11 операций] -> (11,11) [22 операции] сумма 44. ((1,1) , 10,10) - это только 24.
• Объединение больших и маленьких файлов приводит к тому, что содержимое больших файлов будет перезаписываться в дополнительное время.

Стоит ли сначала объединять большие файлы? нет

• Eg (1,10,10,10) -> (1,10, (10,10)) 20 + 31 операций против ((1,10), 10,10) 11 + 31 операций
• снова мы получаем штраф за многократное выполнение операций с большим файлом.

Стоит ли когда-либо объединять меньше K файлов при последнем объединении? да

• например. (1,2,3,4,5,6) -> (((1,2), 3,4), 5,6) 3 + 10 + 21 против ((1,2,3), (4, 5,6)) 6 + 15 + 21
• повторное объединение самых больших файлов, больше времени - плохая идея

Платит ли за объединение менее K файлов, кроме как при первом объединении? да

• например. ! 1 (1,2,3,4,5,6) -> (((1,2), 3,4), 5,6) 3 + 10 + 21 = 34 против (((1,2,3 ), 4), 5,6)) 6 + 10 + 21 = 37
• файл размера 3 копируется в дополнительное время
• например. № 2 (((1,1), 10), 100,100). Здесь мы используем k = 2 в первых двух шагах, принимая 2 + 12 + 212 = 226 операций. Альтернатива ((1,1), 10,100), 100), которая использует k = 3 на втором шаге: 2 + 112 + 212 = 326 ops

Новая эвристика

while #files is larger than 1
  sum size of smallest files until K or next larger file is greater than the sum.
  K-merge these

ToDo доказывает, что сумма дополнений в этом случае будет меньше, чем у всех других методов.

Answer 2

Могу я представить это по-другому:

Традиционная сложность сортировки слиянием - o (n.ln (n)), но в моем случае с другим размером подсписка, в худшем случае, если один файл большой, а все остальные маленькие (это пример, который вы даете), сложность может быть o (nn): что является плохой сложностью производительности.

Вопрос в том, «как оптимально спланировать подсортировку»?

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

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

1. Моим первым наивным впечатлением было просто отсортировать файлы по размерам и начать с меньших: таким образом, вы будете исключать небольшие файлы во время итераций.

У меня К = 2: в вашем примере 1 1 10 10 -> 2 20 -> 22: Это все еще (20 + 2) + 22 CC, так что 42 CC *

CC: Сравнение или копирование: это количество операций, которое я считаю для сложности 1.

Если у меня есть K = 1 и я повторно введу результат в мой отсортированный файл Array, я получу: (1 1 10 10) -> 2 10 10 -> 12 10 -> (22): 2 CC + 12 + 22 = 46 Для разных значений K сложность может незначительно отличаться

Вычисление сложности этого алгоритма в среднем случае с вероятностью будет очень интересным, но если вы допустите выполнение N² для плохих случаев.

PS:

Тот факт, что k<n - это еще одна проблема: она будет просто решена путем добавления работника на пару файлов в очередь (n / 2 работников в начале) и создания очереди, считываемой k Threads.