GallopSearch Merge: O (log (n) * log (i)) zamiast O (n)
Poszedłem do przodu i zastosowałem sugestię siwobrodego w komentarzach. Głównie dlatego, że potrzebowałem wysoce wydajnej wersji tego kodu o znaczeniu krytycznym.
- Kod wykorzystuje wyszukiwanie galopowe, które jest O (log (i)), gdzie i jest odległością od bieżącego indeksu, do którego istnieje odpowiedni indeks.
- Kod używa binarySearch for po tym, jak wyszukiwanie galopowe zidentyfikowało właściwy zakres. Ponieważ galop ogranicza to do mniejszego zakresu, wynikowe wyszukiwanie binarne jest również O (log (i))
- Galop i scalanie są wykonywane wstecz. Nie wydaje się to krytyczne dla misji, ale pozwala na łączenie tablic na miejscu. Jeśli w jednej z tablic jest wystarczająco dużo miejsca na przechowywanie wartości wyników, możesz po prostu użyć jej jako tablicy scalającej i tablicy wyników. W takim przypadku należy określić prawidłowy zakres w tablicy.
- Nie wymaga przy tym alokacji pamięci (duże oszczędności w operacjach krytycznych). Po prostu upewnia się, że nie może i nie może nadpisać żadnych nieprzetworzonych wartości (co można zrobić tylko wstecz). W rzeczywistości używasz tej samej tablicy zarówno dla danych wejściowych, jak i wyników. Nie przyniesie to żadnych złych skutków.
- Konsekwentnie używałem Integer.compare (), aby można było to zmienić do innych celów.
- Jest pewna szansa, że trochę się wygłupiałem i nie wykorzystałem informacji, które wcześniej udowodniłem. Na przykład wyszukiwanie binarne w zakresie dwóch wartości, dla których jedna wartość została już sprawdzona. Mógłby istnieć również lepszy sposób na określenie głównej pętli, odwracająca wartość c nie byłaby potrzebna, gdyby zostały połączone w dwie operacje po kolei. Ponieważ wiesz, że za każdym razem będziesz robić jedno, potem drugie. Jest miejsce na trochę lakieru.
Powinien to być najbardziej efektywny sposób, aby to zrobić, ze złożonością czasową O (log (n) * log (i)) zamiast O (n). I w najgorszym przypadku złożoność czasowa O (n). Jeśli twoje tablice są zlepione i mają razem długie ciągi wartości, będzie to przyćmić każdy inny sposób, w przeciwnym razie będzie po prostu lepszy od nich.
Ma dwie wartości odczytu na końcach tablicy scalającej i wartość zapisu w tablicy wyników. Po ustaleniu, która wartość końcowa jest mniejsza, wykonuje galopowe przeszukiwanie tej tablicy. 1, 2, 4, 8, 16, 32 itd. Gdy znajdzie zakres, w którym wartość odczytu drugiej tablicy jest większa. Przeszukuje binarnie w tym zakresie (przecina zakres o połowę, przeszukuje właściwą połowę, powtarza do pojedynczej wartości). Następnie tablica kopiuje te wartości do pozycji zapisu. Należy pamiętać, że kopia jest z konieczności przenoszona w taki sposób, że nie może nadpisać tych samych wartości z obu tablic odczytujących (co oznacza, że tablica zapisu i tablica odczytu mogą być takie same). Następnie wykonuje tę samą operację dla drugiej tablicy, o której wiadomo, że jest mniejsza niż nowa odczytana wartość drugiej tablicy.
static public int gallopSearch(int current, int[] array, int v) {
int d = 1;
int seek = current - d;
int prevIteration = seek;
while (seek > 0) {
if (Integer.compare(array[seek], v) <= 0) {
break;
}
prevIteration = seek;
d <<= 1;
seek = current - d;
if (seek < 0) {
seek = 0;
}
}
if (prevIteration != seek) {
seek = binarySearch(array, seek, prevIteration, v);
seek = seek >= 0 ? seek : ~seek;
}
return seek;
}
static public int binarySearch(int[] list, int fromIndex, int toIndex, int v) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = list[mid];
int cmp = Integer.compare(midVal, v);
if (cmp < 0) {
low = mid + 1;
} else if (cmp > 0) {
high = mid - 1;
} else {
return mid;// key found
}
}
return -(low + 1);// key not found.
}
static public int[] sortedArrayMerge(int[] a, int[] b) {
return sortedArrayMerge(null, a, a.length, b, b.length);
}
static public int[] sortedArrayMerge(int[] results, int[] a, int aRead, int b[], int bRead) {
int write = aRead + bRead, length, gallopPos;
if ((results == null) || (results.length < write)) {
results = new int[write];
}
if (aRead > 0 && bRead > 0) {
int c = Integer.compare(a[aRead - 1], b[bRead - 1]);
while (aRead > 0 && bRead > 0) {
switch (c) {
default:
gallopPos = gallopSearch(aRead, a, b[bRead-1]);
length = (aRead - gallopPos);
write -= length;
aRead = gallopPos;
System.arraycopy(a, gallopPos--, results, write, length);
c = -1;
break;
case -1:
gallopPos = gallopSearch(bRead, b, a[aRead-1]);
length = (bRead - gallopPos);
write -= length;
bRead = gallopPos;
System.arraycopy(b, gallopPos--, results, write, length);
c = 1;
break;
}
}
}
if (bRead > 0) {
if (b != results) {
System.arraycopy(b, 0, results, 0, bRead);
}
} else if (aRead > 0) {
if (a != results) {
System.arraycopy(a, 0, results, 0, aRead);
}
}
return results;
}
Powinien to być najbardziej efektywny sposób, aby to zrobić.
Niektóre odpowiedzi miały zduplikowaną możliwość usuwania. Będzie to wymagało algorytmu O (n), ponieważ musisz faktycznie porównać każdy element. Więc tutaj jest osobna, do zastosowania po fakcie. Nie możesz galopować przez wiele wpisów do końca, jeśli chcesz spojrzeć na wszystkie z nich, chociaż możesz galopować przez duplikaty, jeśli masz ich dużo.
static public int removeDuplicates(int[] list, int size) {
int write = 1;
for (int read = 1; read < size; read++) {
if (list[read] == list[read - 1]) {
continue;
}
list[write++] = list[read];
}
return write;
}
Aktualizacja: poprzednia odpowiedź, nie okropny kod, ale wyraźnie gorszy od powyższego.
Kolejna niepotrzebna hiperoptymalizacja. Nie tylko wywołuje arraycopy dla bitów końcowych, ale także dla początku. Przetwarzanie dowolnego wprowadzającego nienakładania się w O (log (n)) przez wyszukiwanie binarne w danych. O (log (n) + n) jest O (n) iw niektórych przypadkach efekt będzie dość wyraźny, szczególnie w sytuacjach, gdy w ogóle nie ma nakładania się między scalanymi tablicami.
private static int binarySearch(int[] array, int low, int high, int v) {
high = high - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = array[mid];
if (midVal > v)
low = mid + 1;
else if (midVal < v)
high = mid - 1;
else
return mid; // key found
}
return low;//traditionally, -(low + 1); // key not found.
}
private static int[] sortedArrayMerge(int a[], int b[]) {
int result[] = new int[a.length + b.length];
int k, i = 0, j = 0;
if (a[0] > b[0]) {
k = i = binarySearch(b, 0, b.length, a[0]);
System.arraycopy(b, 0, result, 0, i);
} else {
k = j = binarySearch(a, 0, a.length, b[0]);
System.arraycopy(a, 0, result, 0, j);
}
while (i < a.length && j < b.length) {
result[k++] = (a[i] < b[j]) ? a[i++] : b[j++];
}
if (j < b.length) {
System.arraycopy(b, j, result, k, (b.length - j));
} else {
System.arraycopy(a, i, result, k, (a.length - i));
}
return result;
}