Java najszybsze tworzenie i filtrowanie tablicy 2D

Witam,

Mam pytanie z javy oraz poniekąd z algorytmiki. Mój problem polega na tym, że potrzebuję rady bardziej doświadczonych programistów Javy. Otóż głównym celem jest najszybsze możliwe tworzenie tablicy dwuwymiarowej a następnie filtrowanie jej wykorzystując kolumny i zwracać pasujące wiersze. Przykład

Załóżmy 1000 wierszy i 5 kolumn: A, B, C, D, E. Wartości to double. Jak najszybciej przefiltrować tablicę przy warunkach typu A > 4 AND B < 11 AND D = WIND.

Problem wydajności jest o tyle istotny, że taka musi być tworzona kilka setek/tysięcy razy przy założeniu, że wierszy jest zazwyczaj dużo (aktualnie największy problem ma nieco ponad 1000 wierszy, ale może się zdarzyć np. 5000) a kolumn całkiem mało (max 30-40). Jak to ugryźć najszybciej?

Rozwiązanie oczywiste to Double[rows][cols] - ale w jaki sposób filtrować taką tablicę, aby wyciągnąć całe wiersze do nowej tablicy? Dynamicznie zmniejszać przeszukiwaną tablicę (w sensie wyciągamy wszystkie, które pasują do A > 4, w kolejnej iteracji mamy już mniej elementów w nowej tablicy i szukamy B < 11)? Czy Double i pętle for to najlepsze rozwiązanie czy może jest jakiś myk na to?

Z góry dzięki za wszystkie pomysły!

Pozdrawiam,
Adam

Myk polega na odpowiednim dobraniu struktur i algorytmów do danego problemu. Ty podsuwasz jakieś tam rozwiązanie, ale my nawet problemu nie znamy.

Tam, gdzie masz konkretną wartość to HashMapa i klucze. Generalnie musisz podać więcej szczegółów - przykładowych zapytań.

Poza tym - może załóż sobie indeksy jakieś ?

Po samym opisie mozna wnioskowac, ze potrzebujesz indeksow przyspieszajacego wyszukiwanie. Najprosciej - wez jakas baze danych, ktora oferuje tego typu zapytania (w zasadzie kazda) pozakladaj indeksy na kolumny, po ktorych chcesz wyszukiwac, cala prace baza robi za ciebie.
Jezeli koniecznie chcesz sam to implementowac to bedziesz potrzebowal dwoch rzeczy:

• drzewa przyspieszajacego wyszukiwanie (najprosciej drzewko BST)
• szybkich operacji na zbiorach (czyli czesc wspolna, sume, etc).
  Rozbijasz zapytanie na proste podzapytania operujace na pojedynczych kolumnach. Wyszkujesz uzywajac drzewa numery indeksow dla poszczegolnych kolumn. Potem zgodnie z zapytaniem robisz czesc wspolna lub sume na zbiorach indeksow, ktore masz z poprzedniego kroku.
  Oczywiscie taki schemat jest daleki od optymalnego ale raczej nie ludz sie, ze zaimplementujesz optymalnie samemu to co robia silniki baz danych.

Baza danych jest na wyrost. Po pierwsze takie wyszukania idą w setki / tysiące, po drugie nie ma sensu podciągać bazy pod prosty problem...

Ja już to mam zaimplementowane, tylko niestety jest to trochę za wolne. Cała idea jest mniej więcej taka (pseudokod):

for(e : examples) {
boolean _t = true;
for(cond : warunki){
if (cond != e.column(cond.col)){
_t = false;
break;
}
if(_t) add2list(e);
}

gdzie cond.col - to znany numer kolumny do sprawdzenia

Cały problem polega na tym, że o ile pętle idą dosyć szybko to wyciąganie e.column(cond.col) jest bardzo wolne. Stąd moje pytanie o strukturę, która wyciągnie to w najszybszy sposób, najlepiej O(1) jeśli się da.

Przyspieszyc moze ci stworzenie indeksow na wszystkich kolumnach. Indeksem moze byc drzewo BST, w ktorym kluczem sa double z tablicy, a wartosciami sa ich pozycje w tablicy. Wyszukanie w drzewie pojedynczego elementu zajmuje O(log n). Jak masz nierownosc to wyszukujesz poddrzewo a nastepnie dodajesz wszystkie elementy z poddrzewa. Dodatkowa optymalizacja to jest np. zaczynanie wyszukiwania od kolumny, w ktorej przewidujesz, ze zwroci najmniej wartosci - bo wtedy ograniczasz maksymalnie liczbe elementow, ktore musisz wyszukac w pozostalych drzewach (przewidywac mozesz roznymi heurystykami - np. mozesz zaczac od rownosci zamiast od nierownosci). Podczas przeszukiwania dodajesz pozycje do hash setu- w pierwszy zapytaniu dodajesz wszystkie, w kazdym kolejnym zapytaniu wyrzucasz z hash setu pozycje ktorych nie ma w pozostalych zapytaniach.

Pseudo kod moze wygladac tak:

h[] = construct BST indexes on each column
m = empty hash set
while(queries is not empty)
{
   q = choose most optimal query and remove it from queries
   t = h[q.col]
   iter = iterator that will iterate on all element that satisfies query q in tree t

    mark all elements in m as not used
    while(iter.hasNext())
    {
      e = iter.next();
      if(q is first handled query)
      {
        mark e as used
        m.add(e) //add all elements if query is first handled query
      }
      else
      {
        if(e in m) {mark e as used;}
      }
    }
    remove all elements marked as not used from m
}
result = m

Ewentualnie zamiast drzew BST mozesz sobie posortowac kazda kolumne z osobna i wyszukiwac binarnie.

W O(1) raczej tego nie zrobisz - musialbys miec do czynienia z nieduzymi liczbami calkowitymi (wtedy moglbys zastosowac hash mape jako indeks) a nie z doublami.

0x200x20 dzięki za pomysł, sprawdzę jak to będzie działało :)

Cały problem polega na tym, że o ile pętle idą dosyć szybko to wyciąganie e.column(cond.col) jest bardzo wolne.

A co się dzieje w tym e.column(cond.col)?

Na początek warto wiedzieć:

• jak często zmieniają się dane w tabeli?
• jaka jest złożoność zapytań, tzn co w nich jest?
• czy zapytania się powtarzają, a jeśli tak to jak często?
• jak dużo jest zapytań?

Jeśli chodzi o BST, to w Javie jest klasa TreeSet i zawiera metody subSet, headSet i tailSet, które wraz z odpowiednim Comparatorem mogą służyć jako metody do robienia zapytań. Po otrzymanym subSecie/ headSecie/ tailSecie najlepiej iterować za pomocą for-eacha (tak powinno być najszybciej).

Tablice w Javie dziedziczą po Object, ale nie nadpisują jego equals() ani hashCode(). Dzięki temu, jeśli zrobisz HashSet<Typ[]> to dostaniesz coś w rodzaju IdentityHashSet<Typ[]> i tutaj się to może przydać.

Wibowit napisał(a):

Cały problem polega na tym, że o ile pętle idą dosyć szybko to wyciąganie e.column(cond.col) jest bardzo wolne.

A co się dzieje w tym e.column(cond.col)?

Dla mnie wygląda to jak geter ze struktury klasy, po przeanalizowaniu kolejnych odniesień jest to geter z klasy zwanej FastVector, która odwołuje się już bezpośrednio do klasy Object. Wywołanie to zwraca zatem element object[index] - index to ten cond.col.

Wibowit napisał(a):

Na początek warto wiedzieć:

• jak często zmieniają się dane w tabeli?

To ma być tablica 2D, nie tabela. Tablica jest jednym z parametrów wywoływanej metody, gdzie wywołanie metody idzie w tysiące lub nawet setki tysięcy. Nie jest istotne, że to się liczy dajmy na to 4-5h. To nie problem natury "wynik na już", raczej coś co ma się przeliczyć w rozsądnym czasie (czyli max 24h) :) Tablica jako taka nie zmienia się przy tym za każdym wywołaniem metody. Zawsze zmienia się drugi parametr, którym są warunki do wyciągnięcia odpowiednich przykładów.

Wibowit napisał(a):

• jaka jest złożoność zapytań, tzn co w nich jest?
• czy zapytania się powtarzają, a jeśli tak to jak często?
• jak dużo jest zapytań?

Nie ma zapytań, bo to nie tabela :) Nie chcę podciągać pod to bazy danych, bo za dużo tam wywołań... Problem nie jest bazodanowy, tylko strukturalno-algorytmiczny.
Nadal główne pytanie brzmi:

Jak najlepiej dobrać strukturę, aby przeczesywanie i wyciąganie odpowiednich wierszy było najszybsze. Np. o ile szybsza jest struktura (skróty myślowe...) double[][] od Object[][]

Metoda BruteForce, którą napisałem wygląda tak (pseudokod):

for(przyklady){
	boolean _c = true;
	for(warunek : warunki_do_spelnienia){
		if(sprawdz_warunek(przyklad, warunek)) {
			_c = false; 
			break;
		}
	}
	if(_c) zapisz_przyklad();
}

gdzie

sprawdz_warunek(przyklad, warunek) {
	if(przyklad.columna(id) warunek.relacja warunek)
		return false; // spelnia warunek, czyli nie wejdzie do ifa ustawiajacego _c = false
	else
		return true; // nie spelnia warunku, odrzucamy przyklad
}

warunek.relacja to element ze zbioru {<=, >, =}

czyli przykład:

czy przyklad[0] (wiersz z tablicy) spełnia np taki warunek, A <= 3.5 AND C > 7.2 AND E == 10.3 (mamy 3 warunki i wszystkie muszą być spełnione, aby przykład przeszedł dalej)

przy założeniu, że kolumny tablicy nazywamy A, B, C, D, E

jeśli coś jest jeszcze niejasne to opiszę :)

Tablica jako taka nie zmienia się przy tym za każdym wywołaniem metody.

W takim razie zamiast drzew BST mozesz sobie dac zwykla posortowana tablice jako indeks (albo np. tablice permutacji jezeli chcesz zaoszczedzic troche pamieci).

Tablica jest jednym z parametrów wywoływanej metody, gdzie wywołanie metody idzie w tysiące lub nawet setki tysięcy

W takim przypadku indeksy na pewno pomoga (musisz tylko utworzyc te indeksy raz dla stworzonej tablicy a nie za kazdym razem dla zestawow querisow)

Nawiasem mowiac jak w tej tablicy jest tylko kilka tysiecy elementow to spokojnie moglbys mapowac tebele do bazy danych, tworzyc indeksy i wyszukiwac. Bazy danych sa wlasnie optymalizowane do obslugi duzej ilosci zapytan. Podejrzewam, ze te kilkadziesiat tysiecy zapytan nawet slaba baza jak sqlite obsluzyla by w mniej niz kilka minut. No chyba, ze masz jakas ogromna liczbe kolumn (ale skoro je numerujesz literami to raczej nie masz).

Kolumn jest stosunkowo mało, liczby wierszy w zasadzie też (co to jest 5000 :)). Ale wywołań jest kilka(naście/dziesiąt) tysięcy (może być więcej). Stąd boję się o wydajność wrzucania tego do bazy i odpytywania. Chodzi oto, że nie tablica jest duża a ogromna jest liczba zapytań - w zasadzie są sprawdzane wszystkie możliwości (funkcję oceniającą mam). Inna sprawa, że faktycznie najłatwiej wtedy wyciągnąć interesujące wiersze, bo wystarczy najprostsze zapytanie z where...

Hmm, kilkadziesiąt tysięcy elementów * kilkadziesiąt tysięcy zapytań to kilkaset milionów przeskanowanych obiektów. Zakładając, że przeskanowanie jednego obiektu to tysiąc operacji wychodzi w sumie jakieś kilkaset miliardów operacji procesora dziennie. Biorąc pod uwagę to, że dzisiejsze procki mogą robić miliardy operacji na sekundę, wykonanie dziennego obciążenia powinno trwać od kilku do kilkunastu minut. Oczywiście to bardzo z grubsza oszacowania.

Najlepiej gdybyś podał kompilujący się kod obrazujący problem. Tzn struktury danych o wielkościach takich jak masz w rzeczywistości i tak samo zapytania rzeczywistych rozmiarów. Wtedy można by więcej pomóc.