Obecnie pracuję nad projektem urządzenia osadzonego, w którym mam problemy z wydajnością. Profilowanie zlokalizowało operację O (N), którą chciałbym wyeliminować.

Zasadniczo mam dwie tabliceint A[N] ishort B[N]. Wpisy wA są unikalne i uporządkowane według ograniczeń zewnętrznych. Najczęstszą operacją jest sprawdzenie, czy konkretna wartośća pojawia się wA[]. Rzadziej, ale wciąż powszechna jest zmiana elementuA[]. Nowa wartość nie ma związku z poprzednią wartością.

Ponieważ najczęstszą operacją jest find, to gdzieB[] wchodzi. To posortowana tablica wskaźnikówA[], takieA[B[i]] < A[B[j]] wtedy i tylko wtedy gdyi<j. Oznacza to, że mogę znaleźć wartości wA przy użyciu wyszukiwania binarnego.

Oczywiście, gdy aktualizujęA[k], Muszę znaleźćk wB i przenieś go w nowe miejsce, aby zachować kolejność wyszukiwania. Odkąd znam stare i nowe wartościA[k], to tylkomemmove() podzbioruB[] między starą a nową pozycjąk. To jest operacja O (N), którą muszę naprawić; odkąd stare i nowe wartościA[k] są w zasadzie przypadkowe, poruszam się średnio oN / 2 N / 3 elementy.

Zajrzałem do środkastd::make_heap za pomocą[](int i, int j) { return A[i] < A[j]; } jako predykat. W takim przypadku mogę łatwo to zrobićB[0] wskaż najmniejszy elementAi aktualizacjaB jest teraz tanią operacją równoważenia O (log N). Jednak generalnie nie potrzebuję najmniejszej wartości A, muszę się dowiedzieć, czy występuje jakaś dana wartość. A teraz wyszukiwanie O (N log N)B. (Połowa moich N elementów znajduje się w dzienniku głębokości sterty N, jedna czwarta w (log N) -1 itd.), Co nie jest poprawą w porównaniu z głupim wyszukiwaniem O (N) bezpośrednio wA.

Biorąc pod uwagę, żestd::set ma wstawkę O (log N) i znajdź, powiedziałbym, że powinno być możliwe uzyskanie tej samej wydajności tutaj w celu aktualizacji i znalezienia. Ale jak mam to zrobić? Czy potrzebuję innego zamówieniaB? Inny typ?

B jest obecnie ashort [N] boA iB razem są o wielkości mojej pamięci podręcznej procesora, a moja pamięć główna jest dużo wolniejsza. Przejście od 6 * N do 8 * N bajtów nie byłoby przyjemne, ale nadal jest akceptowalne, jeśli moje wyszukiwanie i aktualizacja przejdą do O (log N).