Operacje na wektorze drzewa (SIMD)

Question

Jakie są ogólne wskazówki/wskazówki dotyczące operacji drzewa wektoryzacji? Układ pamięci mądry, mądry algorytm itp

Niektóre domeny specyficzne rzeczy:

• Każdy węzeł rodzic będzie miał sporo (20 - 200), węzły potomne.
• Każdy węzeł ma małe prawdopodobieństwo posiadania węzłów potomnych.
• Operacje na drzewie to głównie spacery warunkowe.
• Wydajność chodzenia po drzewie jest ważniejsza niż prędkość wstawiania/usuwania/wyszukiwania.

Answer 1

Uważaj, jest to bardzo trudne do wdrożenia. W zeszłym roku zespół Intela, Oracle i UCSC zaprezentował niesamowite rozwiązanie "FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs". Wygrali "Best Paper Award 2010" by ACM SIGMOD.

Answer 2

Ze względu na losowy charakter drzew nie jest oczywiste, że spacery wektoryzacji będą dla ciebie dużym plusem.

Ułożyłbym drzewo jako płaską tablicę (macierzystych, węzłowych) "węzłów", posortowanych według rodzica, dzięki czemu można przynajmniej odwiedzić dzieci węzła razem. Oczywiście to nie daje wiele, jeśli twoje drzewo nie jest "grube" (tj. Mała liczba dzieci średnio dla węzła).

Jednak najlepszym rozwiązaniem jest podkreślenie brutalnej mocy SIMD, ponieważ naprawdę nie można wykonywać przypadkowych skoków z listy za pomocą tego interfejsu API.

Edit: Nie chciałbym wyrzucić normalną klasę drzewo najprawdopodobniej mają jednak wdrożyć drogę SIMD i sprawdzić, czy rzeczywiście zyskać niczego, nie jestem przekonany, będziesz ...

Answer 3

A co z wykorzystaniem algorytmów teorii grafów spektralnych? Powinny być dużo łatwiejsze do wektoryzacji, ponieważ zajmują się macierzami.