Algorytm łączenia dwóch posortowanych tablic z minimalną liczbą porównań

Podano dwa posortowane tablice a , b typu T o rozmiarze n i m . Szukam algorytmu, który łączy dwie tablice w nową tablicę (o maksymalnym rozmiarze n + m).

Jeśli masz tanią operację porównania, jest to dość proste. Wystarczy pobrać z tablicy z najniższym pierwszym elementem, aż jeden lub oba tablice zostaną całkowicie przejrzane, a następnie dodaj pozostałe elementy. Coś takiego: /programming/5958169/how-to-merge-two-sorted-arrays-into-a-sorted-array

Jednak sytuacja zmienia się, gdy porównywanie dwóch elementów jest znacznie droższe niż kopiowanie elementu z tablicy źródłowej do tablicy docelowej . Na przykład możesz mieć tablicę dużych liczb całkowitych o dowolnej dokładności lub ciągów, gdzie porównanie może być dość drogie. Załóżmy, że tworzenie tablic i kopiowanie elementów jest bezpłatne, a jedyne, co kosztuje, to porównywanie elementów.

W takim przypadku chcesz połączyć dwie tablice z minimalną liczbą porównań elementów . Oto kilka przykładów, w których powinieneś być w stanie zrobić znacznie lepiej niż prosty algorytm scalania:

a = [1,2,3,4, ... 1000]
b = [1001,1002,1003,1004, ... 2000]

Lub

a = [1,2,3,4, ... 1000]
b = [0,100,200, ... 1000]

W niektórych przypadkach prosty algorytm scalania będzie optymalny

a = [1,3,5,7,9,....,999]
b = [2,4,6,8,10,....,1000]

Dlatego algorytm powinien idealnie z wdziękiem zdegradować i wykonać maksymalnie n + m-1 porównań w przypadku, gdy tablice są przeplatane, lub przynajmniej nie być znacznie gorszy.

Jedną z rzeczy, które powinny być całkiem dobre w przypadku list o dużej różnicy wielkości, byłoby użycie wyszukiwania binarnego do wstawienia elementów mniejszej tablicy do większej tablicy. Ale to nie pogorszy się z wdziękiem, jeśli obie listy będą tego samego rozmiaru i przeplatane.

Jedyną rzeczą dostępną dla elementów jest (całkowita) funkcja porządkowania, więc żaden schemat, który powoduje, że porównania są tańsze, nie jest możliwy.

Jakieś pomysły?

Wymyśliłem ten kawałek w Scali . Uważam, że jest optymalny pod względem liczby porównań, ale nie jestem w stanie tego udowodnić. Przynajmniej jest to o wiele prostsze niż rzeczy, które znalazłem w literaturze.

A od czasu oryginalnego posta napisałem post na blogu o tym, jak to działa.

Normalny algorytm sortowania scalającego - krok scalania z normalnie stosuj porównania n + m -1, gdzie jedna lista ma rozmiar n, a druga lista ma rozmiar m. Zastosowanie tego algorytmu jest najprostszym podejściem do połączenia dwóch posortowanych list.

Jeśli porównania są zbyt drogie, możesz zrobić dwie rzeczy - albo zminimalizować liczbę porównań, albo zminimalizować koszt porównań.

Skupmy się na minimalizacji kosztu porównania. Ty i tylko Ty możesz zdecydować, czy porównywane dane mogą być kwantowane, czy nie. Jeśli potrafisz je skwantyfikować, to jest forma implementacji metody mieszającej, która zachowuje porządek. Np. Jeśli Twoje dane są porównywane według nazwy, to pierwsza nazwa, ... możesz zabrać pierwszą do znaków w nazwie „Klaehn, Ruediger” i zredukować / skwantyzować swój element danych do „Kl.Ru”, jeśli go porównasz do „Packer, The” zachowujesz kolejność „Pa.Th” - możesz teraz zastosować tańszy algorytm porównywania, porównując zmniejszone wartości. Ale jeśli znajdziesz inny „Kl.Ru”, masz teraz prawie wartość i możesz teraz przejść na droższe podejście porównujące te elementy.

Jeśli możesz wyodrębnić tę skwantyzowaną wartość z danych, szybciej niż jej porównanie, jest to pierwsza rzecz, którą robisz, najpierw porównujesz skwantowaną lub zakodowaną wartość. Należy pamiętać, że wartość tę należy obliczyć tylko raz, aby można ją było obliczyć podczas tworzenia elementu danych.

Wspomniałem również o innym sposobie zminimalizowania porównań.

Zajrzałem do klasycznej książki TAOCP - Tom 3 - Sortowanie i wyszukiwanie (str. 197-207, sekcja 5.3.2), która zawiera pełne 10 stron na ten temat. Znalazłem dwa odniesienia do algorytmów, które są szybsze niż porównania n + m-1.

Najpierw jest algorytm scalania Hwang-Lin, a drugi ulepszenie autorstwa Glenna K. Manachera - oba są cytowane przez TAOCP, a także algorytm Christena, który zbliża się do dolnej granicy potrzebnych porównań, na specjalnych warunkach na długości n i m z list.

Algorytm Manachera został przedstawiony w Journal of the ACM Vol. 26 Numer 3 na stronach 434–440: „Znaczące ulepszenia algorytmu łączenia Hwan-Lin”. lista z elementami m i lista z elementami n mogą mieć różną długość, ale należy je również oderwać liczbą elementów, które zawierają m <= n

Algorytm Hwang-Lin rozbija listy, aby je scalić, oprócz mniejszych list i sortuje listy, porównując pierwszy element każdej podlisty i decydując, czy niektóre elementy podlisty należy porównać, czy nie. Jeśli pierwsza lista jest mniejsza niż druga lista, wówczas jest duża szansa, że ​​kolejne elementy dłuższej listy można przenieść na wynikową listę bez porównania. Jeśli pierwszy element małej ist jest większy niż pierwszy element podzielonej większej listy, wszystkie elementy przed listą podrzędną można skopiować bez porównania.

Analizę średnich przypadków łączącego się alorithm Hwanga i Lin (Vega, Frieze, Santha) w rozdziale 2 można znaleźć pseudokod algorytmu HL. Co jest o wiele lepsze niż mój opis. I możesz zobaczyć, dlaczego jest mniej porównań - algorytm wykorzystuje wyszukiwanie binarne, aby znaleźć indeks, gdzie wstawić element z krótszej listy.

Jeśli listy nie są przeplatane, jak w poprzednim przykładzie, w większości przypadków powinna pozostać mniejsza i większa. To wtedy algorytm HL zaczyna działać lepiej.

Załóżmy, że dwie tablice mają elementy N i M, N ≥ M, a wszystkie elementy są różne.

Jeśli posortowana tablica zawiera element x z N, a następnie element y z M lub odwrotnie, x i y musiały zostać porównane, w przeciwnym razie nie wiedzielibyśmy, w jakiej kolejności należą. (Nie może istnieć łańcuch innych elementów, powiedzmy a, b, c, gdzie wiemy, że x <a <b <c <y, na przykład, ponieważ nie ma elementów między x i y. Więc x i y musiały zostać porównane bezpośrednio.

Jeśli N> M, możliwe jest utworzenie tablicy, w której każdy element M jest poprzedzony i poprzedzony elementem N, co oznacza, że ​​potrzebne są co najmniej 2M porównania - nawet jeśli używasz niedeterministycznego algorytmu sortowania, który może zgadnij, które liczby porównać. (Co to oznacza: Załóżmy, że masz N duże, M = 1. Wyszukiwanie binarne wymaga kroków O (log2 N); algorytm niedeterministyczny zgadłby, do którego z dwóch elementów należy jeden element drugiej tablicy, i dokonał dwóch porównań z potwierdzić przypuszczenie).