Wiele algorytmów działa przy użyciu merge algorithm, aby scalić dwie różne posortowane tablice w jedną posortowaną tablicę. Przykładowo, jeżeli na wejściu tabliceAlgorytm scalania pamięci i adaptacji?
1 3 4 5 8
i
2 6 7 9
Przejęcie tych tablic byłby Array
1 2 3 4 5 6 7 8 9
Tradycyjnie, wydaje się, że dwa różne podejścia do łączenia posortowane tablice (zwróć uwagę, że przypadek łączenia połączonych list jest zupełnie inny). Po pierwsze, istnieją algorytmy scalania out-of-place, które działają poprzez przydzielenie tymczasowego bufora do przechowywania, a następnie przechowywanie wyniku scalenia w tymczasowym buforze. Po drugie, jeśli te dwie macierze są częścią tej samej macierzy wejściowej, są in-place merge algorithms, które wykorzystują tylko O (1) dodatkową przestrzeń pamięci i zmieniają dwie sąsiadujące sekwencje w jedną posortowaną sekwencję. Te dwie klasy algorytmów działają w czasie O (n), ale algorytm łączenia poza miejscem ma zwykle znacznie niższy stały współczynnik, ponieważ nie ma tak rygorystycznych wymagań dotyczących pamięci.
Moje pytanie brzmi, czy istnieje znany algorytm łączenia, który może "interpolować" pomiędzy tymi dwoma podejściami. Oznacza to, że algorytm używałby gdzieś pomiędzy pamięcią O (1) i O (n), ale im więcej pamięci ma do dyspozycji, tym szybciej działa. Na przykład, gdybyśmy mieli zmierzyć bezwzględną liczbę odczytów/zapisów tablic wykonywanych przez algorytm, może on mieć środowisko wykonawcze w postaci ng (s) + f (s), gdzie s jest ilością dostępnej dla niego przestrzeni i g (s) i f (s) są funkcjami uzyskanymi z dostępnej przestrzeni. Zaletą tej funkcji jest to, że może ona próbować scalić dwie tablice w najbardziej efektywny sposób z uwzględnieniem ograniczeń pamięci - im więcej pamięci jest dostępnej w systemie, tym więcej pamięci z niej korzysta i (najlepiej) tym lepsza wydajność, jaką miałaby .
Bardziej formalnie algorytm powinien działać w następujący sposób. Jako dane wejściowe podaje się tablicę A składającą się z dwóch sąsiednich, posortowanych zakresów, zmieniających rozmieszczenie elementów w tablicy tak, aby elementy były całkowicie posortowane według kolejności. Algorytm może wykorzystywać przestrzeń zewnętrzną, a jej wydajność powinna być najgorszym przypadkiem O (n) we wszystkich przypadkach, ale powinna przebiegać progresywnie szybciej, biorąc pod uwagę większą ilość przestrzeni pomocniczej do wykorzystania.
Czy ktoś zna algorytm tego rodzaju (lub wie gdzie szukać, aby znaleźć opis jednego?)
http://stackoverflow.com/questions/3156599/merge-two-sorted-parts-of-an-array-with-constant-memory-in-on-on- – necromancer
@ agksmehx- Dzięki za link. Jednak nie sądzę, że jest to dokładnie to, czego szukam.Jestem już świadomy, że możesz scalić O (1) dodatkową przestrzeń, a to pytanie jest głównie pytaniem, czy istnieje sposób na algorytm scalania, który stopniowo zwiększa się, dając więcej wolnej przestrzeni, którą ci dajesz, tak abyś mógł otrzymasz, powiedzmy, 100 MB dodatkowej przestrzeni na 500 MB danych, scaliłbyś się szybciej niż gdybyś miał 10 MB na 500 MB danych. – templatetypedef
Jakie są wejścia i wyjścia? Czy piszecie do jednej z tablic wejściowych lub do osobnej tablicy? (Podejrzewam, że to pierwsze, bo jeśli to drugie, to nie jest problem.) – MSN