Szukam wysoce wydajnej struktury danych do przechowywania danych podobnych do poniższych.
Identyfikatory Zamówienie 1 Zamówienie 2 -------------------------- 1 1,2 1 1 2 2,5 2 3 3 1,7 4 7 4 6 3 0
Muszę być w stanie kwerendy tej struktury w taki sposób, że daje mi listę wszystkich identyfikatorów zawierających wyraz tagów - wspieranie AND
i OR
i NOT
operacje. Na przykład. ((1 lub 2) i nie 7)
Potrzebuję też być w stanie określić kolejność wyników (Order1 lub Order2) i być w stanie określić maksymalną liczbę wierszy zwracanych z opcjonalnym przesunięciem. Kluczowe znaczenie ma wydajność przy pobieraniu pierwszych 30–100 wyników.
Na koniec potrzebuję taniego sposobu na wyszukanie „relacji znaczników”, na przykład chcę wiedzieć, które znaczniki „odnoszą się” do znaczników (1 LUB 2) i na jakiej częstotliwości. Oznacza, które tagi pojawiają się w tym samym zestawie co 1 LUB 2 ... uporządkowane według częstotliwości.
Masz pojęcie o tym, która struktura danych (lub zestaw struktur) byłaby wysoce wydajna dla tego rodzaju pracy?
(Chciałbym użyć tego jako dowodu koncepcji przeprojektowania otagowanych stron rodziny witryn SE)
źródło
Odpowiedzi:
To nie jest dokładnie odpowiedź na efektywną strukturę danych, ale raczej rozwinięcie komentarzy @bbejot i @Kaveh, podających wymachujący ręką argument, dlaczego biorąc pod uwagę bieżące pytanie, nie powinniśmy oczekiwać czegoś, co będzie o wiele lepsze niż wyszukiwanie cała baza danych. Argument opiera się na redukcji z SAT, hipotezie o wykładniczym czasie i wielu machaniu ręką.
Załóżmy, że mamy do różnych znaczników, wtedy możemy myśleć o każdym identyfikatorze jako związanym z bitvektorem x o długości | x | = n gdzie x j = 1, jeśli mamy j -ty znacznik, a x j = 0 w przeciwnym razie. Ponieważ nie ma rzeczywistych ograniczeń dotyczących wyglądu bazy danych, mogę założyć, że ma ona identyfikatory od 1 do 2 n, przy czym k -ty identyfikator ma powiązany wektor znaczników kn x | x | =n xjot= 1 jot xjot= 0 1 2)n k k napisane binarnie. Pola zamówienia mogą być dowolne, ponieważ tylko utrudniają problem. Otóż, jeśli otrzymamy arbitralne zapytanie , O R i N O Ts, to po prostu zadajemy pytanie SAT dotyczące n zmiennych. Zgodnie z hipotezą wykładniczą dotyczącą czasu, nie możemy oczekiwać, że będzie to znacznie szybsze niż 2 n ... lub innymi słowy, nie możemy oczekiwać, że będzie to znacznie szybsze niż przeszukiwanie całej bazy danych.A N.re O R N.O T n 2)n
Nie należy oczekiwać wydajnego wyszukiwania w długości zapytania (poprzez redukcję do SAT). Nie powinniśmy również oczekiwać dużo lepszego niż przeglądanie wszystkich pozycji w bazie danych według wykładniczej hipotezy czasowej.
źródło
To dość prosta odpowiedź, ale uważam, że jest skuteczna:
Map Tag ([Id],[Id])
Map Id (Set Tag)
Id
źródło