Czy ktoś może zademonstrować mi bardziej wydajny algorytm kartezjański niż ten, którego obecnie używam (zakładając, że taki jest). Rozejrzałem się dookoła i trochę googlełem, ale nie widzę niczego oczywistego, więc mogłem coś przegapić.

foreach (int i in is) {
   foreach (int j in js) {
      //Pair i and j
   }
}

Jest to bardzo uproszczona wersja tego, co robię w moim kodzie. Dwie liczby całkowite to klawisze wyszukiwania, które służą do pobierania jednego / więcej obiektów, a wszystkie obiekty z dwóch odnośników są łączone w nowe obiekty.

Ten mały blok kodu w znacznie większym, bardziej złożonym systemie staje się dużym wąskim gardłem wydajności, ponieważ zbiór danych działa w skali. Niektóre z nich mogą zostać złagodzone przez ulepszenie struktur danych używanych do przechowywania obiektów i odnośników, ale głównym problemem, jaki uważam, jest nadal obliczanie samego produktu kartezjańskiego.

Edytować

Więc trochę więcej informacji na temat mojego specyficznego wykorzystania algorytmu, aby zobaczyć, czy mogą istnieć jakieś sztuczki, których mogę użyć w odpowiedzi na komentarz Marca. Ogólny system to silnik zapytań SPARQL, który przetwarza zapytania SPARQL na zestawy danych wykresu, SPARQL jest językiem opartym na wzorcach, więc każde zapytanie składa się z szeregu wzorców, które są dopasowane do wykresów. W przypadku, gdy dwa kolejne wzorce nie mają wspólnych zmiennych (są rozłączne), konieczne jest obliczenie iloczynu kartezjańskiego rozwiązań wytworzonych przez dwa wzorce, aby uzyskać zestaw możliwych rozwiązań dla całego zapytania. Może istnieć dowolna liczba wzorów i być może będę musiał obliczać produkty kartezjańskie wiele razy, co może prowadzić do dość wykładniczej ekspansji możliwych rozwiązań, jeśli zapytanie składa się z szeregu rozłącznych wzorów.

Jakoś z istniejących odpowiedzi wątpię, czy istnieją jakieś sztuczki, które mogłyby mieć zastosowanie

Aktualizacja

Pomyślałem, że opublikuję aktualizację tego, co zaimplementowałem, aby zminimalizować potrzebę tworzenia produktów kartezjańskich, a tym samym zoptymalizować silnik zapytań. Zauważ, że nie zawsze jest możliwe całkowite wyeliminowanie zapotrzebowania na produkty, ale prawie zawsze możliwe jest zoptymalizowanie, aby rozmiar dwóch połączonych zestawów był znacznie mniejszy.

Ponieważ każdy BGP (Basic Graph Pattern), który jest zestawem Triple Patterns, jest wykonywany jako blok (w istocie), silnik może dowolnie zmieniać kolejność wzorów w BGP w celu uzyskania optymalnej wydajności. Na przykład rozważmy następujący BGP:

?a :someProperty ?b .
?c :anotherProperty ?d .
?b a :Class .

Wykonane jako zapytanie wymaga produktu kartezjańskiego, ponieważ wyniki pierwszego wzoru są rozłączne od drugiego wzoru, więc wyniki pierwszych dwóch wzorców są iloczynem kartezjańskim ich indywidualnych wyników. Wynik ten będzie zawierał znacznie więcej wyników, niż potrzebujemy, ponieważ trzeci wzór ogranicza możliwe wyniki pierwszego wzorca, ale nie stosujemy tego ograniczenia do późniejszego. Ale jeśli zmienimy kolejność tak:

?b a :Class .
?a :someProperty ?b .
?c :anotherProperty ?d .

Nadal będziemy potrzebować produktu kartezjańskiego, aby uzyskać ostateczne wyniki, ponieważ drugi i trzeci wzór są nadal rozłączne, ale poprzez zmianę kolejności ograniczamy rozmiar wyników drugiego wzoru, co oznacza, że ​​rozmiar naszego kartezjańskiego produktu będzie znacznie mniejszy.

Istnieje kilka innych optymalizacji, których dokonujemy, ale nie zamieściłem ich tutaj, ponieważ zaczynają one dość szczegółowo omawiać wewnętrzne mechanizmy SPARQL. Jeśli ktoś jest zainteresowany dalszymi szczegółami, po prostu zostaw komentarz lub wyślij mi tweet @ RobVesse