Prostą możliwością, która przychodzi na myśl, jest zachowanie skompresowanej tablicy 2 bitów na wartość dla typowych przypadków i oddzielnych 4 bajtów na wartość (24 bity dla indeksu elementu oryginalnego, 8 bitów dla rzeczywistej wartości, więc (idx << 8) | value)) posortowana tablica inni.
Kiedy szukasz wartości, najpierw przeszukujesz tablicę 2bpp (O (1)); jeśli znajdziesz 0, 1 lub 2, jest to wartość, której szukasz; jeśli znajdziesz 3, oznacza to, że musisz to sprawdzić w dodatkowej tablicy. Tutaj przeprowadzisz wyszukiwanie binarne, aby znaleźć indeks, który Cię interesuje, przesunięty w lewo o 8 (O (log (n) z małym n, ponieważ powinno to być 1%) i wyodrębnić wartość z 4- bajt rzecz.
std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;
uint8_t lookup(unsigned idx) {
uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
if(v != 3) return v;
auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
if(ptr == sec_arr.end()) std::abort();
if((*ptr >> 8) != idx) std::abort();
#endif
return (*ptr) & 0xff;
}
void populate(uint8_t *source, size_t size) {
main_arr.clear(); sec_arr.clear();
main_arr.resize((size+3)/4);
for(size_t idx = 0; idx < size; ++idx) {
uint8_t in = source[idx];
uint8_t &target = main_arr[idx>>2];
if(in >= 3) {
sec_arr.push_back((idx << 8) | in);
in = 3;
}
target |= in << ((idx & 3)*2);
}
}
Dla tablicy takiej jak ta, którą zaproponowałeś, powinno to zająć 10000000/4 = 2500000 bajtów dla pierwszej tablicy plus 10000000 * 1% * 4 B = 400000 bajtów dla drugiej tablicy; stąd 2900000 bajtów, czyli mniej niż jedna trzecia oryginalnej tablicy, a najczęściej używana część jest przechowywana razem w pamięci, co powinno być dobre do buforowania (może nawet pasować do L3).
Jeśli potrzebujesz więcej niż 24-bitowego adresowania, będziesz musiał dostosować „pamięć dodatkową”; trywialnym sposobem jego rozszerzenia jest posiadanie 256-elementowej tablicy wskaźników do przełączania 8 pierwszych bitów indeksu i przekazywania dalej do 24-bitowej posortowanej tablicy indeksowanej, jak powyżej.
Szybki test porównawczy
#include <algorithm>
#include <vector>
#include <stdint.h>
#include <chrono>
#include <stdio.h>
#include <math.h>
using namespace std::chrono;
struct XorShift32 {
typedef uint32_t result_type;
static uint32_t min() { return 1; }
static uint32_t max() { return uint32_t(-1); }
uint32_t y;
XorShift32(uint32_t seed = 0) : y(seed) {
if(y == 0) y = 2463534242UL;
}
uint32_t operator()() {
y ^= (y<<13);
y ^= (y>>17);
y ^= (y<<15);
return y;
}
uint32_t operator()(uint32_t limit) {
return (*this)()%limit;
}
};
struct mean_variance {
double rmean = 0.;
double rvariance = 0.;
int count = 0;
void operator()(double x) {
++count;
double ormean = rmean;
rmean += (x-rmean)/count;
rvariance += (x-ormean)*(x-rmean);
}
double mean() const { return rmean; }
double variance() const { return rvariance/(count-1); }
double stddev() const { return std::sqrt(variance()); }
};
std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;
uint8_t lookup(unsigned idx) {
uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
if(v != 3) return v;
auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
if(ptr == sec_arr.end()) std::abort();
if((*ptr >> 8) != idx) std::abort();
#endif
return (*ptr) & 0xff;
}
void populate(uint8_t *source, size_t size) {
main_arr.clear(); sec_arr.clear();
main_arr.resize((size+3)/4);
for(size_t idx = 0; idx < size; ++idx) {
uint8_t in = source[idx];
uint8_t &target = main_arr[idx>>2];
if(in >= 3) {
sec_arr.push_back((idx << 8) | in);
in = 3;
}
target |= in << ((idx & 3)*2);
}
}
volatile unsigned out;
int main() {
XorShift32 xs;
std::vector<uint8_t> vec;
int size = 10000000;
for(int i = 0; i<size; ++i) {
uint32_t v = xs();
if(v < 1825361101) v = 0;
else if(v < 4080218931) v = 1;
else if(v < 4252017623) v = 2;
else {
while((v & 0xff) < 3) v = xs();
}
vec.push_back(v);
}
populate(vec.data(), vec.size());
mean_variance lk_t, arr_t;
for(int i = 0; i<50; ++i) {
{
unsigned o = 0;
auto beg = high_resolution_clock::now();
for(int i = 0; i < size; ++i) {
o += lookup(xs() % size);
}
out += o;
int dur = (high_resolution_clock::now()-beg)/microseconds(1);
fprintf(stderr, "lookup: %10d µs\n", dur);
lk_t(dur);
}
{
unsigned o = 0;
auto beg = high_resolution_clock::now();
for(int i = 0; i < size; ++i) {
o += vec[xs() % size];
}
out += o;
int dur = (high_resolution_clock::now()-beg)/microseconds(1);
fprintf(stderr, "array: %10d µs\n", dur);
arr_t(dur);
}
}
fprintf(stderr, " lookup | ± | array | ± | speedup\n");
printf("%7.0f | %4.0f | %7.0f | %4.0f | %0.2f\n",
lk_t.mean(), lk_t.stddev(),
arr_t.mean(), arr_t.stddev(),
arr_t.mean()/lk_t.mean());
return 0;
}
(kod i dane zawsze aktualizowane w moim Bitbuckecie)
Powyższy kod wypełnia tablicę elementów 10M losowymi danymi rozprowadzanymi jako OP określone w ich poście, inicjuje moją strukturę danych, a następnie:
- wykonuje losowe wyszukiwanie 10M elementów z moją strukturą danych
- robi to samo na oryginalnej tablicy.
(zauważ, że w przypadku wyszukiwania sekwencyjnego tablica zawsze wygrywa o ogromną miarę, ponieważ jest to najbardziej przyjazne dla pamięci podręcznej wyszukiwanie, jakie możesz zrobić)
Te dwa ostatnie bloki są powtarzane 50 razy i mierzone w czasie; na końcu obliczana i drukowana jest średnia i odchylenie standardowe dla każdego typu wyszukiwania, wraz z przyspieszeniem (średnia_szukania / średnia_tablicy).
Skompilowałem powyższy kod za pomocą g ++ 5.4.0 ( -O3 -staticplus kilka ostrzeżeń) na Ubuntu 16.04 i uruchomiłem go na niektórych maszynach; większość z nich pracuje pod systemem Ubuntu 16.04, niektóre starsze, niektóre nowsze. Nie sądzę, aby system operacyjny był w ogóle odpowiedni w tym przypadku.
CPU | cache | lookup (µs) | array (µs) | speedup (x)
Xeon E5-1650 v3 @ 3.50GHz | 15360 KB | 60011 ± 3667 | 29313 ± 2137 | 0.49
Xeon E5-2697 v3 @ 2.60GHz | 35840 KB | 66571 ± 7477 | 33197 ± 3619 | 0.50
Celeron G1610T @ 2.30GHz | 2048 KB | 172090 ± 629 | 162328 ± 326 | 0.94
Core i3-3220T @ 2.80GHz | 3072 KB | 111025 ± 5507 | 114415 ± 2528 | 1.03
Core i5-7200U @ 2.50GHz | 3072 KB | 92447 ± 1494 | 95249 ± 1134 | 1.03
Xeon X3430 @ 2.40GHz | 8192 KB | 111303 ± 936 | 127647 ± 1503 | 1.15
Core i7 920 @ 2.67GHz | 8192 KB | 123161 ± 35113 | 156068 ± 45355 | 1.27
Xeon X5650 @ 2.67GHz | 12288 KB | 106015 ± 5364 | 140335 ± 6739 | 1.32
Core i7 870 @ 2.93GHz | 8192 KB | 77986 ± 429 | 106040 ± 1043 | 1.36
Core i7-6700 @ 3.40GHz | 8192 KB | 47854 ± 573 | 66893 ± 1367 | 1.40
Core i3-4150 @ 3.50GHz | 3072 KB | 76162 ± 983 | 113265 ± 239 | 1.49
Xeon X5650 @ 2.67GHz | 12288 KB | 101384 ± 796 | 152720 ± 2440 | 1.51
Core i7-3770T @ 2.50GHz | 8192 KB | 69551 ± 1961 | 128929 ± 2631 | 1.85
Rezultaty są ... mieszane!
- Ogólnie rzecz biorąc, na większości tych maszyn występuje pewne przyspieszenie, a przynajmniej są one na równi.
- Dwa przypadki, w których tablica naprawdę przewyższa wyszukiwanie "inteligentnej struktury", dotyczą maszyn z dużą ilością pamięci podręcznej i niezbyt obciążonych: Xeon E5-1650 powyżej (pamięć podręczna 15 MB) jest maszyną do nocnego budowania, w tej chwili całkiem bezczynną; Xeon E5-2697 (35 MB pamięci podręcznej) to maszyna do obliczeń o wysokiej wydajności, również w stanie bezczynności. To ma sens, oryginalna tablica mieści się całkowicie w ich ogromnej pamięci podręcznej, więc zwarta struktura danych tylko zwiększa złożoność.
- Po przeciwnej stronie „spektrum wydajności” - ale tam, gdzie macierz jest nieco szybsza, jest skromny Celeron, który zasila mój NAS; ma tak małą pamięć podręczną, że ani tablica, ani „inteligentna struktura” w ogóle się do niej nie mieszczą. Inne maszyny z wystarczająco małą pamięcią podręczną działają podobnie.
- Do Xeon X5650 należy podchodzić z pewną ostrożnością - są to maszyny wirtualne na dość obciążonym dwugniazdowym serwerze maszyny wirtualnej; może się zdarzyć, że chociaż nominalnie ma przyzwoitą ilość pamięci podręcznej, w czasie testu jest kilka razy wywłaszczany przez całkowicie niepowiązane maszyny wirtualne.