반응형
N-way 병합을위한 알고리즘
양방향 병합은 Mergesort 알고리즘의 일부로 광범위하게 연구됩니다. 하지만 N-way 병합을 수행 할 수있는 가장 좋은 방법을 찾고 싶습니다.
예를 들어, N각각 1 백만 개의 정수를 정렬 한 파일이 있습니다. 1 억 개의 정렬 된 정수가있는 단일 파일로 병합해야합니다.
이 문제에 대한 사용 사례는 실제로 디스크 기반의 외부 정렬입니다. 따라서 실제 시나리오에서는 메모리 제한도 있습니다. 따라서 한 번에 2 개의 파일을 (99 번) 병합하는 순진한 접근 방식은 작동하지 않습니다. 각 배열에 사용할 수있는 작은 슬라이딩 메모리 창만 있다고 가정 해 보겠습니다.
이 N-way 병합에 대한 표준화 된 솔루션이 이미 있는지 확실하지 않습니다. (인터넷 검색은 나에게 많은 것을 말하지 않았습니다) .
그러나 좋은 n-way 병합 알고리즘인지 알고 있다면 algo / link를 게시하십시오.
시간 복잡성 :N 병합 할 파일 ( ) 수를 크게 늘리면 알고리즘의 시간 복잡성에 어떤 영향을 미칠까요?
답변 해 주셔서 감사합니다.
나는이 질문을 어디서도받지 못했지만 흥미로운 인터뷰 질문이 될 수 있다고 생각했습니다. 따라서 태그가 있습니다.
다음 아이디어는 어떻습니까?
- 우선 순위 대기열 만들기
- 각 파일을 반복합니다. f
- 첫 번째 값을 우선 순위 키로 사용하여 쌍 (nextNumberIn (f), f) 을 대기열에 넣습니다.
- 첫 번째 값을 우선 순위 키로 사용하여 쌍 (nextNumberIn (f), f) 을 대기열에 넣습니다.
- 대기열이 비어 있지 않은 동안
- 디큐 헤드 (m, F) 큐
- 출력 m
- 만약 f를 소모하지
- 대기열에 넣기 (nextNumberIn (f), f)
우선 순위 큐에 요소를 추가하는 것은 로그 시간으로 수행 될 수 있으므로 항목 2는 O (N × log N) 입니다. while 루프의 (거의 모든) 반복은 요소를 추가하기 때문에 전체 while 루프는 O (M × log N) 이며 여기서 M 은 정렬 할 총 숫자 수입니다.
모든 파일에 비어 있지 않은 숫자 시퀀스가 있다고 가정하면 M> N이 있으므로 전체 알고리즘은 O (M × log N) 이어야합니다 .
"Polyphase merge"를 검색하고 고전을 확인하십시오-Donald Knuth & EHFriend.
또한 Seyedafsari & Hasanzadeh 가 제안한 Smart Block Merging 을 살펴볼 수 있습니다. 이는 이전 제안과 유사하게 우선 순위 대기열을 사용합니다.
또 다른 흥미로운 이유는 Kim & Kutzner의 In Place Merging Algorithm 입니다.
나는 또한 Vitter의이 논문을 추천한다 : 외부 메모리 알고리즘과 데이터 구조 : 대용량 데이터 다루기 .
한 가지 간단한 아이디어는 병합 할 범위의 우선 순위 큐를 유지하고, 가장 작은 첫 번째 요소가있는 범위가 큐에서 먼저 제거되도록 저장하는 것입니다. 그런 다음 다음과 같이 N-way 병합을 수행 할 수 있습니다.
- 빈 범위를 제외한 모든 범위를 우선 순위 대기열에 삽입합니다.
- 우선 순위 대기열이 비어 있지 않은 경우 :
- 대기열에서 가장 작은 요소를 대기열에서 빼십시오.
- 이 범위의 첫 번째 요소를 출력 시퀀스에 추가합니다.
- 비어 있지 않은 경우 나머지 시퀀스를 우선 순위 대기열에 다시 삽입합니다.
이 알고리즘의 정확성은 본질적으로 양방향 병합이 올바르게 작동한다는 증거의 일반화입니다. 항상 임의의 범위에서 가장 작은 요소를 추가하고 모든 범위가 정렬되면 시퀀스가 전체 정렬 된 상태가됩니다.
이 알고리즘의 런타임 복잡성은 다음과 같이 찾을 수 있습니다. M을 모든 시퀀스의 총 요소 수라고합니다. 바이너리 힙을 사용한다면 우선 순위 큐에서 최대 O (M) 삽입과 O (M) 삭제를 수행합니다. 출력 시퀀스에 기록 된 각 요소에 대해 가장 작은 시퀀스를 꺼내기위한 큐에서 빼기 대기열에 추가하여 나머지 시퀀스를 대기열에 다시 넣습니다. N 개의 요소가있는 바이너리 힙에서 삽입 또는 삭제하는 데 O (lg N) 시간이 걸리기 때문에 이러한 각 단계에는 O (lg N) 작업이 필요합니다. 이것은 O (M lg N)의 순 실행 시간을 제공하는데, 이는 입력 시퀀스의 수에 따라 선형 적으로보다 적게 증가합니다.
더 빨리 얻을 수있는 방법이있을 수 있지만 이것은 꽤 좋은 해결책 인 것 같습니다. 바이너리 힙에 O (N) 오버 헤드가 필요하기 때문에 메모리 사용량은 O (N)입니다. 시퀀스 자체가 아닌 시퀀스에 대한 포인터를 저장하여 이진 힙을 구현하는 경우 병합 할 시퀀스가 정말 우스꽝스럽지 않으면 문제가되지 않습니다. 이 경우 메모리에 맞는 그룹으로 병합 한 다음 모든 결과를 병합하십시오.
도움이 되었기를 바랍니다!
k 개의 정렬 된 배열 (각 길이 n)을 병합하는 간단한 방법에는 O (nk) 시간이 아니라 O (nk ^ 2) 시간이 필요합니다. 처음 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을 참조하십시오 . 다음은 I / O 감소를 에뮬레이트하기 위해 소스에서 버퍼링 된 읽기를 사용하여 힙 기반 k-way 병합에 대한 설명입니다.
public class KWayMerger<T>
{
private readonly IList<T[]> _sources;
private readonly int _bufferSize;
private readonly MinHeap<MergeValue<T>> _mergeHeap;
private readonly int[] _indices;
public KWayMerger(IList<T[]> sources, int bufferSize, Comparer<T> comparer = null)
{
if (sources == null) throw new ArgumentNullException("sources");
_sources = sources;
_bufferSize = bufferSize;
_mergeHeap = new MinHeap<MergeValue<T>>(
new MergeComparer<T>(comparer ?? Comparer<T>.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<T>(-1, source[i]));
//only the last item should trigger the next buffered read
_mergeHeap.Add(new MergeValue<T>(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<T>
{
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<T> : IComparer<MergeValue<T>>
{
public Comparer<T> Comparer { get; private set; }
public MergeComparer(Comparer<T> comparer)
{
if (comparer == null) throw new ArgumentNullException("comparer");
Comparer = comparer;
}
public int Compare(MergeValue<T> x, MergeValue<T> y)
{
Debug.Assert(x != null && y != null);
return Comparer.Compare(x.Value, y.Value);
}
}
다음은MinHeap<T> . 일부 테스트 :
[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<int>(sources, 20).Merge().SequenceEqual(sources.SelectMany(s => s).OrderBy(i => i)));
}
public static IEnumerable<int> 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));
}
저는 N-way 병합을 수행하는이 STL 스타일의 코드를 작성했으며 다른 사람들이 바퀴를 재발 명하지 못하도록 여기에 게시 할 것이라고 생각했습니다. :)
경고 : 약간만 테스트되었습니다. 사용하기 전에 테스트하십시오. :)
다음과 같이 사용할 수 있습니다.
#include <vector>
int main()
{
std::vector<std::vector<int> > v;
std::vector<std::vector<int>::iterator> vout;
std::vector<int> v1;
std::vector<int> 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);
}
또한 컨테이너 자체 대신 반복기 쌍을 사용할 수 있습니다.
Boost.Range를 사용하는 경우 일부 상용구 코드를 제거 할 수 있습니다.
코드:
#include <algorithm>
#include <functional> // std::less
#include <iterator>
#include <queue> // std::priority_queue
#include <utility> // std::pair
#include <vector>
template<class OutIt>
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<class It>
multiway_merge_value_insert_iterator &operator =(It const i)
{
*this->it = *i;
++this->it;
return *this;
}
};
template<class OutIt>
multiway_merge_value_insert_iterator<OutIt>
multiway_merge_value_inserter(OutIt const it)
{ return multiway_merge_value_insert_iterator<OutIt>(it); };
template<class Less>
struct multiway_merge_value_less : private Less
{
multiway_merge_value_less(Less const &less) : Less(less) { }
template<class It1, class It2>
bool operator()(
std::pair<It1, It1> const &b /* inverted */,
std::pair<It2, It2> 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<class T>
bool operator()(T const &a, T const &b) const
{ return std::less<T>()(a, b); }
};
template<class R>
struct multiway_merge_range_iterator
{ typedef typename R::iterator type; };
template<class R>
struct multiway_merge_range_iterator<R const>
{ typedef typename R::const_iterator type; };
template<class It>
struct multiway_merge_range_iterator<std::pair<It, It> >
{ typedef It type; };
template<class R>
typename R::iterator multiway_merge_range_begin(R &r)
{ return r.begin(); }
template<class R>
typename R::iterator multiway_merge_range_end(R &r)
{ return r.end(); }
template<class R>
typename R::const_iterator multiway_merge_range_begin(R const &r)
{ return r.begin(); }
template<class R>
typename R::const_iterator multiway_merge_range_end(R const &r)
{ return r.end(); }
template<class It>
It multiway_merge_range_begin(std::pair<It, It> const &r)
{ return r.first; }
template<class It>
It multiway_merge_range_end(std::pair<It, It> const &r)
{ return r.second; }
template<class It, class OutIt, class Less, class PQ>
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<class It, class OutIt, class Less>
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<It>::value_type
>::type SubIt;
if (std::distance(begin, end) < 16)
{
typedef std::vector<std::pair<SubIt, SubIt> > Remaining;
Remaining remaining;
remaining.reserve(
static_cast<size_t>(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<SubIt, SubIt>,
std::vector<std::pair<SubIt, SubIt> >,
multiway_merge_value_less<Less>
> q((multiway_merge_value_less<Less>(less)));
return multiway_merge(begin, end, out, less, q, distinct);
}
}
template<class It, class OutIt>
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<No_of_files;++i)
{
readers[i]=new BufferedReader(new FileReader(fileList[i]));
}
}
public void createMinHeap() throws IOException {
for(int i=0;i<No_of_files;i++)
{
listString[i]=readers[i].readLine();
listIndex[i]=i;
}
WriteToFile(listString,listIndex);
}
public void WriteToFile(String[] listString,int[] listIndex) throws IOException{
BuildHeap_forFirstTime(listString, listIndex);
while(!(listString[0].equals("zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz")))
{
pw.println(listString[0]);
listString[0]=readers[listIndex[0]].readLine();
MinHeapify(listString,listIndex,0);
}
}
public void BuildHeap_forFirstTime(String[] listString,int[] listIndex){
for(int i=(No_of_files/2)-1;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);
}
}
}
k 정렬 배열 병합을위한 최소 힙 알고리즘의 Java 구현 :
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<PQNode>{
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<PQNode> pq = new PriorityQueue<>();
for(int i=0; i<k; i++) {
int[] kthArray = sortedArrays[i];
totalSize+=kthArray.length;
if(kthArray.length > 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);
}
}
참고 URL : https://stackoverflow.com/questions/5055909/algorithm-for-n-way-merge
반응형
'code' 카테고리의 다른 글
| XAMPP로 SSL 활성화 (0) | 2020.10.18 |
|---|---|
| JavaScript Regexp에서 임의의 수의 그룹을 캡처하는 방법은 무엇입니까? (0) | 2020.10.17 |
| Python 상속 : TypeError : object .__ init __ ()에는 매개 변수가 없습니다. (0) | 2020.10.17 |
| CSS 미디어 쿼리 중복에 대한 규칙은 무엇입니까? (0) | 2020.10.17 |
| sklearn에서 'transform'과 'fit_transform'의 차이점은 무엇입니까 (0) | 2020.10.17 |