Алгоритм слияния N-way

Двухстороннее слияние широко изучается как часть алгоритма Mergesort. Но мне интересно узнать, как можно выполнить слияние N-way?

Допустим, у меня есть N файлов, которые отсортировали по 1 миллиону целых чисел. Я должен объединить их в один файл, который будет содержать эти 100 миллионов отсортированных целых чисел.

Пожалуйста, имейте в виду, что прецедент для этой проблемы – это фактически внешняя сортировка, основанная на дисках. Поэтому в реальных сценариях также будет ограничение памяти. Таким образом, наивный подход к объединению 2 файлов за раз (99 раз) не будет работать. Допустим, у нас есть только небольшое скользящее окно памяти, доступное для каждого массива.

Я не уверен, есть ли стандартное решение для этого слияния N-way. (Гуглинг не сказал мне много) .

Но если вы знаете, хороший алгоритм слияния n-way, отправьте сообщение algo / link.

Сложность времени: если мы значительно увеличим количество файлов ( N ), которые будут объединены, как это повлияет на временную сложность вашего алгоритма?

Спасибо за ваши ответы.

Меня нигде не спрашивали, но я чувствовал, что это может быть интересный вопрос для интервью. Поэтому помечены.

Как насчет следующей идеи:

  1. Создание очереди приоритетов
  2. Итерации через каждый файл f
    1. введите следующую пару (nextNumberIn (f), f), используя первое значение в качестве приоритетного ключа
  3. Пока очередь не пустая
    1. dequeue head (m, f) очереди
    2. выход m
    3. если f не исчерпан
      1. enqueue (nextNumberIn (f), f)

Поскольку добавление элементов в очередь приоритетов может быть выполнено в логарифмическом времени, элемент 2 представляет собой O (N × log N) . Поскольку (почти все) итерации цикла while добавляет элемент, весь цикл while представляет собой O (M × log N), где M – общее количество номеров для сортировки.

Предполагая, что все файлы имеют непустую последовательность чисел, мы имеем M> N и, следовательно, весь алгоритм должен быть O (M × log N) .

Найдите «Polyphase merge», посмотрите classику – Дональд Кнут и EHFriend.

Кроме того, вы можете взглянуть на предлагаемое Smart Block Merging by Seyedafsari & Hasanzadeh, которое, подобно предыдущим предложениям, использует очереди приоритетов.

Другим интересным мотивом является алгоритм слияния на месте Ким и Кутцнер.

Я также рекомендую эту статью Виттером: алгоритмы внешней памяти и структуры данных: обработка массивных данных .

Одна простая идея состоит в том, чтобы сохранить приоритетную очередь диапазонов для слияния, сохраненных таким образом, чтобы диапазон с наименьшим первым элементом удалялся сначала из очереди. Затем вы можете выполнить слияние N-way следующим образом:

  1. Вставьте все диапазоны в очередь приоритетов, исключая пустые диапазоны.
  2. Хотя очередь приоритетов не пуста:
    1. Удалите наименьший элемент из очереди.
    2. Добавьте первый элемент этого диапазона к выходной последовательности.
    3. Если он не пуст, вставьте оставшуюся часть последовательности в очередь приоритетов.

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

Сложность выполнения этого алгоритма можно найти следующим образом. Пусть M – общее число элементов во всех последовательностях. Если мы используем двоичную кучу, то мы делаем не более O (M) вложений и O (M) удалений из очереди приоритетов, так как для каждого элемента, записанного в выходную последовательность, есть делюкс, чтобы вытащить наименьшую последовательность, за которой следует enqueue, чтобы вернуть остальную часть последовательности в очередь. Каждый из этих шагов выполняет операции O (lg N), поскольку вставка или удаление из двоичной кучи с N элементами в ней занимает O (lg N). Это дает чистое время работы O (M lg N), которое растет меньше, чем линейно с количеством входных последовательностей.

Там может быть способ сделать это еще быстрее, но это похоже на довольно хорошее решение. Использование памяти – O (N), поскольку для бинарной кучи нам нужны служебные данные O (N). Если мы реализуем двоичную кучу, сохраняя указатели на последовательности, а не сами последовательности, это не должно быть слишком большой проблемой, если у вас нет действительно смешного количества последовательностей для слияния. В этом случае просто объедините их в группы, которые вписываются в память, а затем объедините все результаты.

Надеюсь это поможет!

Простой подход к объединению отсортированных массивов k (каждый из длины n) требует O (nk ^ 2) времени, а не O (nk) времени. Как и при слиянии первых 2 массивов, это занимает 2n времени, тогда, когда вы сливаете третью с выходом, это занимает 3n времени, так как теперь мы объединяем два массива длиной 2n и n. Теперь, когда мы объединим этот вывод с четвертым, это слияние требует 4n времени. Таким образом, последнее слияние (когда мы добавляем k-й массив в наш уже отсортированный массив) требует k * n времени. Таким образом, требуемое общее время составляет 2n + 3n + 4n + … k * n, которое является O (nk ^ 2).

Похоже, мы можем сделать это в O (kn), но это не так, потому что каждый раз, когда наш массив, который мы объединяем, увеличивается по размеру.
Хотя мы можем добиться лучшей границы, используя разделить и победить. Я все еще работаю над этим и отправляю решение, если найду его.

См. http://en.wikipedia.org/wiki/External_sorting . Вот мой подход к объединению k-way на основе кучи, используя буферизованное считывание из источников для эмуляции сокращения ввода / вывода:

 public class KWayMerger { private readonly IList _sources; private readonly int _bufferSize; private readonly MinHeap> _mergeHeap; private readonly int[] _indices; public KWayMerger(IList sources, int bufferSize, Comparer comparer = null) { if (sources == null) throw new ArgumentNullException("sources"); _sources = sources; _bufferSize = bufferSize; _mergeHeap = new MinHeap>( new MergeComparer(comparer ?? Comparer.Default)); _indices = new int[sources.Count]; } public T[] Merge() { for (int i = 0; i <= _sources.Count - 1; i++) AddToMergeHeap(i); var merged = new T[_sources.Sum(s => s.Length)]; int mergeIndex = 0; while (_mergeHeap.Count > 0) { var min = _mergeHeap.ExtractDominating(); merged[mergeIndex++] = min.Value; if (min.Source != -1) //the last item of the source was extracted AddToMergeHeap(min.Source); } return merged; } private void AddToMergeHeap(int sourceIndex) { var source = _sources[sourceIndex]; var start = _indices[sourceIndex]; var end = Math.Min(start + _bufferSize - 1, source.Length - 1); if (start > source.Length - 1) return; //we're done with this source for (int i = start; i <= end - 1; i++) _mergeHeap.Add(new MergeValue(-1, source[i])); //only the last item should trigger the next buffered read _mergeHeap.Add(new MergeValue(sourceIndex, source[end])); _indices[sourceIndex] += _bufferSize; //we may have added less items, //but if we did we've reached the end of the source so it doesn't matter } } internal class MergeValue { public int Source { get; private set; } public T Value { get; private set; } public MergeValue(int source, T value) { Value = value; Source = source; } } internal class MergeComparer : IComparer> { public Comparer Comparer { get; private set; } public MergeComparer(Comparer comparer) { if (comparer == null) throw new ArgumentNullException("comparer"); Comparer = comparer; } public int Compare(MergeValue x, MergeValue y) { Debug.Assert(x != null && y != null); return Comparer.Compare(x.Value, y.Value); } } 

Вот одна возможная реализация MinHeap . Некоторые тесты:

 [TestMethod] public void TestKWaySort() { var rand = new Random(); for (int i = 0; i < 10; i++) AssertKwayMerge(rand); } private static void AssertKwayMerge(Random rand) { var sources = new[] { GenerateRandomCollection(rand, 10, 30, 0, 30).OrderBy(i => i).ToArray(), GenerateRandomCollection(rand, 10, 30, 0, 30).OrderBy(i => i).ToArray(), GenerateRandomCollection(rand, 10, 30, 0, 30).OrderBy(i => i).ToArray(), GenerateRandomCollection(rand, 10, 30, 0, 30).OrderBy(i => i).ToArray(), }; Assert.IsTrue(new KWayMerger(sources, 20).Merge().SequenceEqual(sources.SelectMany(s => s).OrderBy(i => i))); } public static IEnumerable GenerateRandomCollection(Random rand, int minLength, int maxLength, int min = 0, int max = int.MaxValue) { return Enumerable.Repeat(0, rand.Next(minLength, maxLength)).Select(i => rand.Next(min, max)); } 

Я написал эту часть кода в стиле STL, которая делает слияние N-way, и подумала, что я разместил ее здесь, чтобы помочь другим не изобретать колесо. 🙂

Предупреждение: это только слегка протестировано. Испытание перед использованием. 🙂

Вы можете использовать его следующим образом:

 #include  int main() { std::vector > v; std::vector::iterator> vout; std::vector v1; std::vector v2; v1.push_back(1); v1.push_back(2); v1.push_back(3); v2.push_back(0); v2.push_back(1); v2.push_back(2); v.push_back(v1); v.push_back(v2); multiway_merge(v.begin(), v.end(), std::back_inserter(vout), false); } 

Он также позволяет использовать пары iteratorов вместо самих контейнеров.

Если вы используете Boost.Range, вы можете удалить часть кода шаблона.

Код:

 #include  #include  // std::less #include  #include  // std::priority_queue #include  // std::pair #include  template struct multiway_merge_value_insert_iterator : public std::iterator< std::output_iterator_tag, OutIt, ptrdiff_t > { OutIt it; multiway_merge_value_insert_iterator(OutIt const it = OutIt()) : it(it) { } multiway_merge_value_insert_iterator &operator++(int) { return *this; } multiway_merge_value_insert_iterator &operator++() { return *this; } multiway_merge_value_insert_iterator &operator *() { return *this; } template multiway_merge_value_insert_iterator &operator =(It const i) { *this->it = *i; ++this->it; return *this; } }; template multiway_merge_value_insert_iterator multiway_merge_value_inserter(OutIt const it) { return multiway_merge_value_insert_iterator(it); }; template struct multiway_merge_value_less : private Less { multiway_merge_value_less(Less const &less) : Less(less) { } template bool operator()( std::pair const &b /* inverted */, std::pair const &a) const { return b.first != b.second && ( a.first == a.second || this->Less::operator()(*a.first, *b.first)); } }; struct multiway_merge_default_less { template bool operator()(T const &a, T const &b) const { return std::less()(a, b); } }; template struct multiway_merge_range_iterator { typedef typename R::iterator type; }; template struct multiway_merge_range_iterator { typedef typename R::const_iterator type; }; template struct multiway_merge_range_iterator > { typedef It type; }; template typename R::iterator multiway_merge_range_begin(R &r) { return r.begin(); } template typename R::iterator multiway_merge_range_end(R &r) { return r.end(); } template typename R::const_iterator multiway_merge_range_begin(R const &r) { return r.begin(); } template typename R::const_iterator multiway_merge_range_end(R const &r) { return r.end(); } template It multiway_merge_range_begin(std::pair const &r) { return r.first; } template It multiway_merge_range_end(std::pair const &r) { return r.second; } template OutIt multiway_merge( It begin, It const end, OutIt out, Less const &less, PQ &pq, bool const distinct = false) { while (begin != end) { pq.push(typename PQ::value_type( multiway_merge_range_begin(*begin), multiway_merge_range_end(*begin))); ++begin; } while (!pq.empty()) { typename PQ::value_type top = pq.top(); pq.pop(); if (top.first != top.second) { while (!pq.empty() && pq.top().first == pq.top().second) { pq.pop(); } if (!distinct || pq.empty() || less(*pq.top().first, *top.first) || less(*top.first, *pq.top().first)) { *out = top.first; ++out; } ++top.first; pq.push(top); } } return out; } template OutIt multiway_merge( It const begin, It const end, OutIt out, Less const &less, bool const distinct = false) { typedef typename multiway_merge_range_iterator< typename std::iterator_traits::value_type >::type SubIt; if (std::distance(begin, end) < 16) { typedef std::vector > Remaining; Remaining remaining; remaining.reserve( static_cast(std::distance(begin, end))); for (It i = begin; i != end; ++i) { if (multiway_merge_range_begin(*i) != multiway_merge_range_end(*i)) { remaining.push_back(std::make_pair( multiway_merge_range_begin(*i), multiway_merge_range_end(*i))); } } while (!remaining.empty()) { typename Remaining::iterator smallest = remaining.begin(); for (typename Remaining::iterator i = remaining.begin(); i != remaining.end(); ) { if (less(*i->first, *smallest->first)) { smallest = i; ++i; } else if (distinct && i != smallest && !less( *smallest->first, *i->first)) { i = remaining.erase(i); } else { ++i; } } *out = smallest->first; ++out; ++smallest->first; if (smallest->first == smallest->second) { smallest = remaining.erase(smallest); } } return out; } else { std::priority_queue< std::pair, std::vector >, multiway_merge_value_less > q((multiway_merge_value_less(less))); return multiway_merge(begin, end, out, less, q, distinct); } } template OutIt multiway_merge( It const begin, It const end, OutIt const out, bool const distinct = false) { return multiway_merge( begin, end, out, multiway_merge_default_less(), distinct); } 
 Here is my implementation using MinHeap... package merging; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.io.PrintWriter; public class N_Way_Merge { int No_of_files=0; String[] listString; int[] listIndex; PrintWriter pw; private String fileDir = "D:\\XMLParsing_Files\\Extracted_Data"; private File[] fileList; private BufferedReader[] readers; public static void main(String[] args) throws IOException { N_Way_Merge nwm=new N_Way_Merge(); long start= System.currentTimeMillis(); try { nwm.createFileList(); nwm.createReaders(); nwm.createMinHeap(); } finally { nwm.pw.flush(); nwm.pw.close(); for (BufferedReader readers : nwm.readers) { readers.close(); } } long end = System.currentTimeMillis(); System.out.println("Files merged into a single file.\nTime taken: "+((end-start)/1000)+"secs"); } public void createFileList() throws IOException { //creates a list of sorted files present in a particular directory File folder = new File(fileDir); fileList = folder.listFiles(); No_of_files=fileList.length; assign(); System.out.println("No. of files - "+ No_of_files); } public void assign() throws IOException { listString = new String[No_of_files]; listIndex = new int[No_of_files]; pw = new PrintWriter(new BufferedWriter(new FileWriter("D:\\XMLParsing_Files\\Final.txt", true))); } public void createReaders() throws IOException { //creates array of BufferedReaders to read the files readers = new BufferedReader[No_of_files]; for(int i=0;i=0;--i) MinHeapify(listString,listIndex,i); } public void MinHeapify(String[] listString,int[] listIndex,int index){ int left=index*2 + 1; int right=left + 1; int smallest=index; int HeapSize=No_of_files; if(left <= HeapSize-1 && listString[left]!=null && (listString[left].compareTo(listString[index])) < 0) smallest = left; if(right <= HeapSize-1 && listString[right]!=null && (listString[right].compareTo(listString[smallest])) < 0) smallest=right; if(smallest!=index) { String temp=listString[index]; listString[index]=listString[smallest]; listString[smallest]=temp; listIndex[smallest]^=listIndex[index]; listIndex[index]^=listIndex[smallest]; listIndex[smallest]^=listIndex[index]; MinHeapify(listString,listIndex,smallest); } } в Here is my implementation using MinHeap... package merging; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.io.PrintWriter; public class N_Way_Merge { int No_of_files=0; String[] listString; int[] listIndex; PrintWriter pw; private String fileDir = "D:\\XMLParsing_Files\\Extracted_Data"; private File[] fileList; private BufferedReader[] readers; public static void main(String[] args) throws IOException { N_Way_Merge nwm=new N_Way_Merge(); long start= System.currentTimeMillis(); try { nwm.createFileList(); nwm.createReaders(); nwm.createMinHeap(); } finally { nwm.pw.flush(); nwm.pw.close(); for (BufferedReader readers : nwm.readers) { readers.close(); } } long end = System.currentTimeMillis(); System.out.println("Files merged into a single file.\nTime taken: "+((end-start)/1000)+"secs"); } public void createFileList() throws IOException { //creates a list of sorted files present in a particular directory File folder = new File(fileDir); fileList = folder.listFiles(); No_of_files=fileList.length; assign(); System.out.println("No. of files - "+ No_of_files); } public void assign() throws IOException { listString = new String[No_of_files]; listIndex = new int[No_of_files]; pw = new PrintWriter(new BufferedWriter(new FileWriter("D:\\XMLParsing_Files\\Final.txt", true))); } public void createReaders() throws IOException { //creates array of BufferedReaders to read the files readers = new BufferedReader[No_of_files]; for(int i=0;i=0;--i) MinHeapify(listString,listIndex,i); } public void MinHeapify(String[] listString,int[] listIndex,int index){ int left=index*2 + 1; int right=left + 1; int smallest=index; int HeapSize=No_of_files; if(left <= HeapSize-1 && listString[left]!=null && (listString[left].compareTo(listString[index])) < 0) smallest = left; if(right <= HeapSize-1 && listString[right]!=null && (listString[right].compareTo(listString[smallest])) < 0) smallest=right; if(smallest!=index) { String temp=listString[index]; listString[index]=listString[smallest]; listString[smallest]=temp; listIndex[smallest]^=listIndex[index]; listIndex[index]^=listIndex[smallest]; listIndex[smallest]^=listIndex[index]; MinHeapify(listString,listIndex,smallest); } } 

}

Java-реализация алгоритма минимальной кучи для слияния k отсортированных массивов:

 public class MergeKSorted { /** * helper object to store min value of each array in a priority queue, * the kth array and the index into kth array * */ static class PQNode implements Comparable{ int value; int kth = 0; int indexKth = 0; public PQNode(int value, int kth, int indexKth) { this.value = value; this.kth = kth; this.indexKth = indexKth; } @Override public int compareTo(PQNode o) { if(o != null) { return Integer.valueOf(value).compareTo(Integer.valueOf(o.value)); } else return 0; } @Override public String toString() { return value+" "+kth+" "+indexKth; } } public static void mergeKSorted(int[][] sortedArrays) { int k = sortedArrays.length; int resultCtr = 0; int totalSize = 0; PriorityQueue pq = new PriorityQueue<>(); for(int i=0; i 0) { PQNode temp = new PQNode(kthArray[0], i, 0); pq.add(temp); } } int[] result = new int[totalSize]; while(!pq.isEmpty()) { PQNode temp = pq.poll(); int[] kthArray = sortedArrays[temp.kth]; result[resultCtr] = temp.value; resultCtr++; temp.indexKth++; if(temp.indexKth < kthArray.length) { temp = new PQNode(kthArray[temp.indexKth], temp.kth, temp.indexKth); pq.add(temp); } } print(result); } public static void print(int[] a) { StringBuilder sb = new StringBuilder(); for(int v : a) { sb.append(v).append(" "); } System.out.println(sb); } public static void main(String[] args) { int[][] sortedA = { {3,4,6,9}, {4,6,8,9,12}, {3,4,9}, {1,4,9} }; mergeKSorted(sortedA); } } 
Interesting Posts

Ошибка входа для пользователя «NT AUTHORITY \ NETWORK SERVICE»

Делегаты, почему?

Firefox не может отображать иконки из набора шрифтов Awesome Webfont

Компьютер не загружается, показывает ошибку PXE и ​​/ или «операционная система не найдена», «нет загрузочного устройства», «вставить загрузочный носитель» или другую аналогичную ошибку

Как заставить браузер перемещаться по URL-адресу в JavaScript

Есть ли 128-битное целое число в gcc?

Сколько проходов достаточно с Memtest?

Храните закрытие в виде переменной в Swift

Хранилище типов данных типа C ++

В Java, как мне получить доступ к внешнему classу, когда я не во внутреннем classе?

Могу ли я создать колоду Anki из файла .CSV?

Какова цель символа плюса перед переменной?

Подготовленное заявление JDBC. setDate (…) не экономит время, просто дату .. Как я могу сэкономить время?

Печать только аннотаций pdf

Спасение Windows XP после форматирования загрузочного диска

Давайте будем гением компьютера.