Problem jest następujący.
- Istnieje zestaw prostych bytów E, z których każdy ma dołączony zestaw znaczników T. Każda jednostka może mieć dowolną liczbę tagów. Całkowita liczba podmiotów wynosi około 100 milionów, a całkowita liczba tagów to około 5000.
Tak więc początkowe dane są mniej więcej takie:
E1 - T1, T2, T3, ... Tn
E2 - T1, T5, T100, ... Tk
..
Ez - T10, T12, ... Tl
Te początkowe dane są dość rzadko aktualizowane.
Jakoś moja aplikacja generuje logiczne wyrażenie na takich tagach:
T1 i T2 i T3 | (T5 i! T6)
Muszę obliczyć liczbę bytów pasujących do danego wyrażenia (uwaga - nie byty, ale tylko liczba). Oczywiście ten może nie być całkowicie dokładny.
To, co mam teraz, to proste wyszukiwanie w tabeli w pamięci, co daje mi 5-10 sekund na wykonanie pojedynczego wątku.
Jestem ciekawy, czy jest jakiś skuteczny sposób na poradzenie sobie z tymi rzeczami? Jakie podejście poleciłbyś? Czy istnieją do tego jakieś popularne algorytmy lub struktury danych?
Aktualizacja
Trochę wyjaśnienia zgodnie z prośbą.
T
obiekty są w rzeczywistości stosunkowo krótkimi ciągami stałymi. Ale to tak naprawdę nie ma znaczenia - zawsze możemy przypisać niektóre identyfikatory i operować na liczbach całkowitych.- Zdecydowanie możemy je posortować.
algorithms
optimization
Andy
źródło
źródło
T1
samo odniesienie do obiektuE1
,E2
itp?T2 < T3
zawsze tak było?T1
jest albotrue
czyfalse
za danyE
na podstawie danych wejściowych, a nie zmienna? (tj.Model = "V5"
) Czy może jestT1
to zmienne wyrażenieModel = <input>
?Odpowiedzi:
Zrobiłbym to w sql posiadający tabelę linków
EntityCategory
międzyeid
jednostkącid
odwołującą się a kategorią odwołującą się za pomocą self-joins:źródło
Po napisaniu tej odpowiedzi powinienem prawdopodobnie oznaczyć pytanie jako „zbyt ogólne” - od wieków możemy rozmawiać o różnych strategiach, w końcu trzeba będzie przeprowadzić test porównawczy z Twoimi danymi.
Każdy znacznik może być skutecznie reprezentowany przez liczbę całkowitą. Każda jednostka ma zestaw tagów. Ważny jest wybór prawidłowej implementacji zestawu - możliwe są zarówno B-drzewa, jak i posortowane tablice. Z tym zestawem przeprowadzamy tylko testy członkostwa. Ponieważ obie struktury robią to w O (log t) (z t znacznikami na jednostkę), wolałbym tablice ze względu na ich gęstszą reprezentację.
Możemy teraz filtrować wszystkie jednostki w operacji O (n · log t · p) , gdzie p jest średnią długością ścieżki w drzewie decyzji predykatu. To drzewo decyzyjne można zamówić, aby decyzja mogła zostać szybko podjęta. Bez danych statystycznych możliwe jest jedynie wykluczenie typowego podwyrażenia.
Kolejność przeszukiwania jednostek nie jest tak naprawdę ważna. Z drugiej strony może to być korzystne, aby rozwiązać to tak, że podmioty w indeksach
0
doi
wszystkich mają pewien znacznik, podczas gdy reszta nie. Zmniejsza to n podczas wyszukiwania tego konkretnego znacznika (w drzewie decyzyjnym powinien to być pierwszy test). Można to rozszerzyć na wiele poziomów, ale komplikuje to wszystko i zabiera pamięć O (2 k ) z kpoziomy. W przypadku wielu poziomów najpierw należy zdecydować o znacznikach o najwyższym wzmocnieniu, gdzie wzrost to liczba bytów, które nie muszą być sprawdzane, razy prawdopodobieństwo ich odrzucenia. Zysk staje się maksymalny dla szans 50:50 lub gdy 50% bytów ma ten konkretny znacznik. Umożliwiłoby to optymalizację, nawet jeśli wzorce dostępu nie są znane.Można również utworzyć zestawy, które indeksują byty według każdego użytego znacznika - jeden zestaw ze wszystkimi elementami dla
T1
, a drugi dlaT2
. Oczywistą optymalizacją (przestrzeni i czasu) jest zatrzymanie się, gdy zestaw zawiera więcej niż połowę wszystkich elementów, i zapisanie tych elementów, które nie mają tego znacznika - w ten sposób budowanie indeksów dla wszystkich znaczników zajmie mniej niż½ · n · t
miejsce (z t tagów ogółem). Pamiętaj, że zapisywanie zestawów uzupełniających może utrudnić inne optymalizacje. Ponownie chciałbym (posortować) tablice dla zestawów.Jeśli reprezentujesz również swoje jednostki za pomocą zakresu liczb całkowitych, możesz skompresować przestrzeń używaną dla zestawów indeksów, przechowując tylko element początkowy i końcowy ciągłego zakresu. Pod względem implementacji byłoby to prawdopodobnie wykonane za pomocą wysokiego bitu wskazującego, czy wpis jest ograniczeniem zakresu, czy zwykłym.
Jeśli teraz mamy zestawy indeksów (a tym samym statystyki dotyczące tagów), możemy zoptymalizować nasze predykaty, aby najpierw przetestować mało prawdopodobne właściwości (strategia niezawodna). Oznacza to, że jeśli
T1
jest powszechny iT2
rzadki, to predykatT1 & T2
powinien zostać oceniony poprzez iterację przez wszystkieT2
wpisy zestawu indeksów i testowanie każdego elementuT1
.Jeśli zastosujemy posortowane tablice do zaimplementowania zestawów indeksów, wówczas wiele kroków oceny można zaimplementować jako operacje scalania.
T1 & T2
oznacza, że bierzemy listyT1
iT2
, przydzielamy tablicę docelową rozmiar większych danych wejściowych i wykonujemy następujący algorytm, aż oba dane wejściowe będą puste: JeśliT1[0] < T2[0]
, toT1++
(odrzuć głowę). JeśliT1[0] > T2[0]
potemT2++
. Jeżeli obie głowice są równe, skopiuj ten numer na do tablicy docelowej, a przyrost wszystkie trzy wskaźniki (T1
,T2
, docelowy). Jeśli predykatem jestT1 | T2
, to żadne elementy nie są odrzucane, ale mniejszy jest kopiowany. Predykat formyT1 & ¬T2
mogą być również realizowane z wykorzystaniem strategii łączenie, ale¬T1
czyT1 | ¬T2
nie.Należy to wziąć pod uwagę przy zamawianiu drzewka decyzyjnego: uzupełnienia powinny wystąpić albo na RHS
&
, albo na końcu, gdy ustalana jest ostateczna liczba i nie trzeba patrzeć na rzeczywiste elementy.Bez użycia zestawów indeksów każdy wątek może filtrować swoją część bytów i zwracać liczbę elementów pasujących do predykatu, które można zsumować. W przypadku korzystania z zestawów indeksów każdemu wątkowi przypisano jeden węzeł w drzewie decyzyjnym. Pobiera dwa strumienie wejściowe, które odpowiadają uporządkowanym zestawom, i zwraca połączony strumień. Zauważ, że każdy węzeł w drzewie decyzyjnym ma odpowiadający mu zestaw, który reprezentuje wszystkie byty spełniające to podwyrażenie, i że z powodu uporządkowania zbiorów nie trzeba znać całego zestawu na raz, aby je scalić .
Różne strategie, takie jak scalanie zestawów indeksowanych lub filtrowanie przez listę jednostek, można w pewnym stopniu łączyć. Filtrowanie ma bardzo przewidywalną wydajność. Jeśli zapytanie jest bardzo szczegółowe, więc użycie zestawów indeksów drastycznie zmniejsza przestrzeń wyszukiwania, wówczas operacje scalania mogłyby być lepsze. Należy zauważyć, że połączenie wielu dużych zestawów danych wejściowych może skutkować znacznie gorszą wydajnością niż wyszukiwanie z użyciem siły. Bardzo zoptymalizowany algorytm wybierze odpowiednią strategię na podstawie wielkości wejściowej, struktury zapytań i wskaźników statystycznych.
Nawiasem mówiąc, buforowanie częściowych wyników może być korzystne, jeśli oczekuje się, że podobne zapytania będą uruchamiane w przyszłości, nawet jeśli nie przyspieszą początkowego uruchomienia.
źródło