Poprawianie przechodzenia przez tablicę dwa razy (zagnieżdżona pętla w tej samej tablicy)

Question

Mam duży zestaw danych, które chcę przejrzeć, aby ustalić różne statystyki zbioru danych od punktu w czasie "D1" do punktu z czasem w przyszłości "D2". Zasadniczo, chcę dodać do bazy danych za każdym razem, gdy różnica między wartościami jest większa niż 10. Na przykład:

Datum[] data = x; 
for(Datum d1 : data){ 
    Datum[] tail = y; //From d1 up to 10 elements ahead 
    for(Datum d2 : tail){ 
     //Calculate difference 
     if((d2.val - d1.val) > 10){ 
      //Insert into database 
     } 
    } 
} 

Moje pytanie brzmi, czy istnieje lepszy algorytm/metody w ten sposób? Ponieważ 9 elementów od ogona jest ponownie użytych w następnej iteracji zewnętrznej pętli, czy mogę w jakiś sposób z tego skorzystać? Moim celem było zredukowanie tego do znacznie mniejszego niż (Big-O Notation) O (n), ale nie mogę tego objąć. Zazwyczaj znalezienie pary D1, D2 spełniającej kryteria oznacza, że ​​następny element D1 będzie miał większą szansę na dopasowanie również. Czy mogę wykorzystać to na swoją korzyść?

Staram się, aby to było tak wydajne, jak to tylko możliwe, ponieważ zbiór danych jest tak duży.

Answer 1

Oparta na indeksie pętla może działać znacznie lepiej niż iterator, ponieważ można bezpośrednio indeksować oryginalną tablicę i unikać kopiowania do nowej tablicy. Miałbyś znacznie lepszą lokalizację pamięci, mniejsze prawdopodobieństwo fałszywego udostępniania itp.

Answer 2

Pierwszą rzeczą, którą zrobiłbym, to profilować typowy zestaw danych i dowiedzieć się, gdzie nadejdzie czas. Powinno to dać wskazówki, gdzie skupić się na optymalizacji.

Zakładając, że obliczenia są tak proste, jak odejmowanie/porównywanie, a tablice są szybko dostępne, to propozycja optymalizacji zapisywania w bazie danych powinna być kolejnym priorytetem. Na przykład wypisanie pliku tekstowego i użycie wkładki zbiorczej może dać bardzo szybką wydajność w porównaniu do pojedynczych instrukcji wstawiania. Jeśli będziesz trzymał się oddzielnych wkładek i używasz JDBC, aktualizacje wsadowe będą bardzo pomocne, ponieważ pozwalają uniknąć opóźnień w komunikacji z bazą danych.

Jeśli to nadal nie jest wystarczająco szybkie, należy rozważyć podzielenie tablicy na N partycji i sprawdzenie, czy każda partycja jest przetwarzana przez osobny wątek. Będzie to szczególnie skuteczne, jeśli przetwarzanie jest związane z procesorem.

Wreszcie, poszukaj optymalizacji na poziomie kodu, takich jak unikanie iteratorów za pomocą indeksu. Jeśli liczba elementów zapisanych w bazie danych jest niewielka w porównaniu do liczby iterowanych elementów, to tworzenie iteratora może być wąskim gardłem.

Jeśli liczba elementów jest większa niż 10, a co najważniejsze, więcej niż można zmieścić w pamięci cpu, skuteczniejsze będzie rozbicie skanowania na mniejsze bloki. Na przykład, zamiast skanować 1000 elementów z danych2, podziel je na (powiedzmy) 10 skanów po 100, przy każdym z 10 skanów, używając innej wartości d1. Jest to podobne do tego, w jaki sposób multiplikacja macierzy jest implementowana w sposób blokowy i lepiej wykorzystuje bufory cpu.

Chociaż używasz dwóch pętli, które zwykle są algorytmami O (N^2), druga pętla ma stały rozmiar - 10 elementów, więc zmniejsza się do prostego stałego współczynnika - robisz z grubsza czynnik 10 dodatkowych prac.

Answer 3

to, co masz, to klasyczny algorytm linii rzutów, który jest O (k * n) zk "nakładaniem" lub częścią, w której przebiega pętla wewnętrzna. w Twoim przypadku jest to maksymalna 10 bez względu n jest

Datum[] data = x; 
for(int i=0;i<data.length;i++){ 
    Datum d1=data[i]; 
    Datum[] tail = y; //From d1 up to 10 elements ahead 
    for(int j=i+1;j<Math.min(i+10,data.length);i++){ 
     d2 = data[j]; 
     //Calculate difference 
     if((d2.val - d1.val) > 10){ 
      //Insert into database 

      break;//inner loop 
     } 
    } 
} 

Answer 4

Jest asymptotycznie szybszy sposób, aby rozwiązać ten problem, ale mam poważne wątpliwości co do tego, czy będzie to działać szybciej w praktyce z powodu swojej wielkości okna (10) jest tak mały.Jeśli chcesz zwiększyć ten rozmiar - który nazywam k - by być większy, możesz rozważyć wybór takiego podejścia, jak poniżej.

Kiedy używasz tego algorytmu, trzeba utrzymać okno elementów k, który obsługuje dwie operacje:

1. wstawić nowy element, eksmisji najstarszych.
2. Zwraca wszystkie elementy większe niż pewna wartość.

Jednym ze sposobów na zrobienie tego będzie przechowywanie wszystkich elementów w strukturze danych łączącej zrównoważone drzewo wyszukiwania binarnego i kolejkę. Kolejka zawiera wszystkie k elementów zapisanych w kolejności, w jakiej pojawiają się w oryginalnej sekwencji, i jest używana tak, abyśmy pamiętali, który element należy eksmitować, kiedy musimy dodać nowy element. Zrównoważony BST przechowuje kopię każdego z tych elementów przechowywanych w posortowanej kolejności. Oznacza to, że można wdrożyć powyższe operacje takie jak to:

1. Włóż nowy element, eksmisji najstarszą: Dodaj nowy element do kolejki i BST. Następnie usuń kolejkę z kolejki, aby uzyskać najstarszy element, a następnie usuń go z BST. Runtime: O (log k), ponieważ BST zawiera k elementów.
2. Zwróć wszystkie elementy większe niż pewną wartość: Za pomocą BST znajdź najmniejszy element co najmniej tak duży jak ten w czasie O (log n). Następnie zeskanuj przez BST i wypisz wszystkie elementy co najmniej tak duże jak ten element. Zajmuje to czas O (z), gdzie z jest całkowitą liczbą znalezionych dopasowań.

Łącznie, jeśli masz n elementów i łącznie par z, które musisz wstawić do bazy danych, algorytm ten zajmie czas O (n log k + z). Aby to zobaczyć, pamiętaj, że wykonujemy w sumie n kopii operacji (1), która zajmuje każdy czas O (log k). Wykonujemy również n kopii operacji (2), która zajmuje O (n log k) czas, aby znaleźć następców, a następnie O (z) całkowity czas we wszystkich iteracjach, aby wyświetlić listę wszystkich pasujących par.

Asymptotyczne środowisko wykonawcze tego algorytmu jest dobre w porównaniu z pierwotnie opublikowanym algorytmem O (nk). Zakładając, że liczba dopasowań nie jest "naprawdę ogromna" (powiedzmy, w kolejności nk), będzie to znacznie szybsze, gdy zwiększysz n i k.

Jeśli wartości, które przechowujesz, są liczbami całkowitymi w małym zakresie (powiedzmy 0-10 000), możesz przyspieszyć to jeszcze bardziej, zastępując zrównoważony BST strukturą danych zoptymalizowaną dla liczb całkowitych, taką jak van Emde Boas tree, która zmniejsza to do O (n log log k + z). Ponownie, jest to tylko szybsze asymptotycznie, a jeśli trzymasz k stałej 10, to prawie na pewno nie jest tego warte.

Mam nadzieję, że to pomoże!