Adakah optimasi untuk akses acak pada array yang sangat besar ketika nilai dalam 95% kasus adalah 0 atau 1?

Apakah ada kemungkinan optimasi untuk akses acak pada array yang sangat besar (saat ini saya gunakan uint8_t, dan saya bertanya tentang apa yang lebih baik)

uint8_t MyArray[10000000];

ketika nilai pada posisi apa pun dalam array adalah

• 0 atau 1 untuk 95% dari semua kasus,
• 2 dalam 4% kasus,
• antara 3 dan 255 dalam 1% kasus lainnya?

Jadi, adakah yang lebih baik dari uint8_tarray yang digunakan untuk ini? Seharusnya secepat mungkin untuk mengulang seluruh array dalam urutan acak, dan ini sangat berat pada bandwidth RAM, jadi ketika memiliki lebih dari beberapa thread melakukan itu pada saat yang sama untuk array yang berbeda, saat ini seluruh bandwidth RAM cepat jenuh.

Saya bertanya karena rasanya sangat tidak efisien untuk memiliki array sebesar itu (10 MB) ketika sebenarnya diketahui bahwa hampir semua nilai, terlepas dari 5%, akan bernilai 0 atau 1. Jadi ketika 95% dari semua nilai dalam array sebenarnya hanya membutuhkan 1 bit, bukan 8 bit, ini akan mengurangi penggunaan memori hampir sebesar urutan besarnya. Rasanya seperti harus ada solusi yang lebih efisien memori yang akan sangat mengurangi bandwidth RAM yang diperlukan untuk ini, dan sebagai hasilnya juga secara signifikan lebih cepat untuk akses acak.

Kemungkinan sederhana yang muncul di pikiran adalah untuk menjaga array terkompresi 2 bit per nilai untuk kasus-kasus umum, dan 4 byte terpisah per nilai (24 bit untuk indeks elemen asli, 8 bit untuk nilai aktual, jadi (idx << 8) | value)) array yang diurutkan untuk yang lain.

Ketika Anda mencari nilai, pertama-tama Anda melakukan pencarian di array 2bpp (O (1)); jika Anda menemukan 0, 1 atau 2 itu nilai yang Anda inginkan; jika Anda menemukan 3 itu berarti Anda harus mencarinya di array sekunder. Di sini Anda akan melakukan pencarian biner untuk mencari indeks minat Anda bergeser ke kiri oleh 8 (O (log (n) dengan n kecil, karena ini harus menjadi 1%), dan ekstrak nilainya dari 4- byte byte.

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    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 the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

Untuk array seperti yang Anda usulkan, ini harus mengambil 10000000/4 = 2500000 byte untuk array pertama, ditambah 10000000 * 1% * 4 B = 400000 byte untuk array kedua; karenanya 2900000 byte, yaitu kurang dari sepertiga dari array asli, dan bagian yang paling sering digunakan disimpan dalam memori, yang seharusnya bagus untuk caching (bahkan mungkin cocok dengan L3).

Jika Anda membutuhkan pengalamatan lebih dari 24-bit, Anda harus mengubah "penyimpanan sekunder"; cara sepele untuk memperluasnya adalah memiliki array pointer elemen 256 untuk beralih di atas 8 bit indeks dan meneruskan ke array diurutkan diindeks 24-bit seperti di atas.

Tolok ukur cepat

#include <algorithm>
#include <vector>
#include <stdint.h>
#include <chrono>
#include <stdio.h>
#include <math.h>

using namespace std::chrono;

/// XorShift32 generator; extremely fast, 2^32-1 period, way better quality
/// than LCG but fail some test suites
struct XorShift32 {
    /// This stuff allows to use this class wherever a library function
    /// requires a UniformRandomBitGenerator (e.g. std::shuffle)
    typedef uint32_t result_type;
    static uint32_t min() { return 1; }
    static uint32_t max() { return uint32_t(-1); }

    /// PRNG state
    uint32_t y;

    /// Initializes with seed
    XorShift32(uint32_t seed = 0) : y(seed) {
        if(y == 0) y = 2463534242UL;
    }

    /// Returns a value in the range [1, 1<<32)
    uint32_t operator()() {
        y ^= (y<<13);
        y ^= (y>>17);
        y ^= (y<<15);
        return y;
    }

    /// Returns a value in the range [0, limit); this conforms to the RandomFunc
    /// requirements for std::random_shuffle
    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) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    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 the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        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; // 42.5%
        else if(v < 4080218931) v = 1; // 95.0%
        else if(v < 4252017623) v = 2; // 99.0%
        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;
}

(kode dan data selalu diperbarui di Bitbucket saya)

Kode di atas mengisi array elemen 10M dengan data acak yang didistribusikan sebagai OP yang ditentukan dalam pos mereka, menginisialisasi struktur data saya dan kemudian:

• melakukan pencarian acak elemen 10M dengan struktur data saya
• melakukan hal yang sama melalui array asli.

(perhatikan bahwa dalam kasus pencarian berurutan array selalu menang dengan ukuran besar, karena ini adalah pencarian yang paling ramah terhadap cache yang dapat Anda lakukan)

Dua blok terakhir ini diulang 50 kali dan waktunya; pada akhirnya, mean dan standar deviasi untuk setiap jenis pencarian dihitung dan dicetak, bersama dengan speedup (lookup_mean / array_mean).

Saya mengkompilasi kode di atas dengan g ++ 5.4.0 ( -O3 -static, ditambah beberapa peringatan) di Ubuntu 16.04, dan menjalankannya di beberapa mesin; kebanyakan dari mereka menjalankan Ubuntu 16.04, beberapa Linux yang lebih tua, beberapa Linux yang lebih baru. Saya tidak berpikir OS harus relevan sama sekali dalam hal ini.

            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

Hasilnya ... campuran!

1. Secara umum, pada sebagian besar mesin ini ada semacam speedup, atau setidaknya mereka setara.
2. Dua kasus di mana array benar-benar mengalahkan "struktur cerdas" lookup berada pada mesin dengan banyak cache dan tidak terlalu sibuk: Xeon E5-1650 di atas (15 MB cache) adalah mesin build malam, saat ini cukup menganggur; Xeon E5-2697 (35 MB cache) adalah mesin untuk kalkulasi kinerja tinggi, juga pada saat idle. Masuk akal, array asli cocok sepenuhnya dalam cache besar mereka, sehingga struktur data yang ringkas hanya menambah kompleksitas.
3. Di sisi berlawanan dari "spektrum kinerja" - tetapi di mana lagi array sedikit lebih cepat, ada Celeron sederhana yang memberi kekuatan pada NAS saya; ia memiliki sangat sedikit cache sehingga array maupun "struktur pintar" tidak cocok sama sekali. Mesin lain dengan cache cukup kecil melakukan hal yang sama.
4. Xeon X5650 harus diambil dengan hati-hati - mereka adalah mesin virtual pada server mesin virtual dual-socket yang cukup sibuk; mungkin saja itu, meskipun secara nominal ia memiliki jumlah cache yang layak, selama waktu pengujian itu akan didahului oleh mesin virtual yang sama sekali tidak terkait beberapa kali.

Pilihan lain bisa jadi

• periksa apakah hasilnya 0, 1 atau 2
• jika tidak lakukan pencarian rutin

Dengan kata lain sesuatu seperti:

unsigned char lookup(int index) {
    int code = (bmap[index>>2]>>(2*(index&3)))&3;
    if (code != 3) return code;
    return full_array[index];
}

di mana bmapmenggunakan 2 bit per elemen dengan nilai 3 yang berarti "lain".

Struktur ini sepele untuk diperbarui, menggunakan memori 25% lebih banyak tetapi sebagian besar terlihat hanya dalam 5% kasus. Tentu saja, seperti biasa, apakah itu ide yang baik atau tidak tergantung pada banyak kondisi lain sehingga satu-satunya jawaban adalah bereksperimen dengan penggunaan nyata.

Ini lebih dari "komentar panjang" daripada jawaban yang konkret

Kecuali jika data Anda adalah sesuatu yang terkenal, saya ragu ada yang bisa langsung menjawab pertanyaan Anda (dan saya tidak tahu apa pun yang cocok dengan deskripsi Anda, tapi kemudian saya tidak tahu SEGALANYA tentang semua jenis pola data untuk semua jenis kasus penggunaan). Data jarang adalah masalah umum dalam komputasi kinerja tinggi, tetapi biasanya "kami memiliki array yang sangat besar, tetapi hanya beberapa nilai yang bukan nol".

Untuk pola yang tidak diketahui seperti milik saya, tidak ada yang akan TAHU secara langsung mana yang lebih baik, dan itu tergantung pada perincian: seberapa acak akses acak - apakah sistem mengakses kelompok item data, atau apakah itu benar-benar acak seperti dari generator nomor acak yang seragam. Apakah data tabel benar-benar acak, atau adakah urutan 0 lalu urutan 1, dengan hamburan nilai lainnya? Pengkodean jangka panjang akan berfungsi dengan baik jika Anda memiliki urutan cukup panjang 0 dan 1, tetapi tidak akan berfungsi jika Anda memiliki "kotak-kotak 0/1". Juga, Anda harus menyimpan tabel "titik awal", sehingga Anda dapat bekerja dengan cepat ke tempat yang relevan.

Saya tahu sejak lama bahwa beberapa database besar hanyalah sebuah tabel besar dalam RAM (data pelanggan pertukaran telepon dalam contoh ini), dan salah satu masalah di sana adalah bahwa cache dan optimisasi halaman-tabel pada prosesor cukup tidak berguna. Penelepon sangat jarang sama dengan seseorang yang baru-baru ini menelepon seseorang, bahwa tidak ada data yang dimuat sebelumnya, itu hanya murni acak. Tabel-halaman besar adalah pengoptimalan terbaik untuk jenis akses tersebut.

Dalam banyak kasus, kompromi antara "kecepatan dan ukuran kecil" adalah salah satu hal yang harus Anda pilih dalam rekayasa perangkat lunak [dalam rekayasa lain, kompromi itu tidak harus terlalu banyak]. Jadi, "membuang-buang memori untuk kode yang lebih sederhana" seringkali merupakan pilihan yang lebih disukai. Dalam hal ini, solusi "sederhana" sangat mungkin lebih baik untuk kecepatan, tetapi jika Anda memiliki "lebih baik" digunakan untuk RAM, maka mengoptimalkan ukuran meja akan memberi Anda kinerja yang cukup dan peningkatan ukuran yang baik. Ada banyak cara berbeda untuk mencapai hal ini - seperti yang disarankan dalam komentar, bidang 2 bit tempat dua atau tiga nilai paling umum disimpan, dan kemudian beberapa format data alternatif untuk nilai lainnya - tabel hash akan menjadi milik saya. pendekatan pertama, tetapi daftar atau pohon biner dapat bekerja juga - sekali lagi, itu tergantung pada pola di mana "bukan 0, 1 atau 2" Anda berada. Sekali lagi, itu tergantung pada bagaimana nilai-nilai "tersebar" di tabel - apakah mereka dalam kelompok atau mereka lebih dari pola yang terdistribusi secara merata?

Tetapi masalah dengan itu adalah bahwa Anda masih membaca data dari RAM. Anda kemudian menghabiskan lebih banyak kode untuk memproses data, termasuk beberapa kode untuk mengatasi "ini bukan nilai umum".

Masalah dengan algoritma kompresi yang paling umum adalah bahwa mereka didasarkan pada urutan pembongkaran, sehingga Anda tidak dapat mengaksesnya secara acak. Dan overhead membagi data besar Anda menjadi potongan-potongan, katakanlah, 256 entri sekaligus, dan membuka kompresi 256 menjadi array uint8_t, mengambil data yang Anda inginkan, dan membuang data yang tidak terkompresi, sangat tidak mungkin memberi Anda baik kinerja - dengan asumsi itu penting, tentu saja.

Pada akhirnya, Anda mungkin harus menerapkan satu atau beberapa ide dalam komentar / jawaban untuk diuji, melihat apakah itu membantu menyelesaikan masalah Anda, atau apakah bus memori masih menjadi faktor pembatas utama.

Apa yang saya lakukan di masa lalu adalah menggunakan hashmap di depan bitset.

Ini membagi dua ruang dibandingkan dengan jawaban Matteo, tetapi mungkin lebih lambat jika pencarian "pengecualian" lambat (yaitu ada banyak pengecualian).

Namun, sering kali, "cache adalah raja".

Kecuali ada pola pada data Anda, tidak mungkin ada optimasi kecepatan atau ukuran yang masuk akal, dan - dengan asumsi Anda menargetkan komputer normal - 10 MB juga bukan masalah yang besar.

Ada dua asumsi dalam pertanyaan Anda:

1. Data sedang disimpan dengan buruk karena Anda tidak menggunakan semua bit
2. Menyimpannya lebih baik akan membuat segalanya lebih cepat.

Saya pikir kedua asumsi ini salah. Dalam kebanyakan kasus, cara yang tepat untuk menyimpan data adalah menyimpan representasi paling alami. Dalam kasus Anda, ini yang Anda pilih: byte untuk angka antara 0 dan 255. Representasi lain akan lebih kompleks dan karenanya - semua hal lain dianggap sama - lebih lambat dan lebih rentan kesalahan. Untuk perlu mengalihkan dari prinsip umum ini, Anda memerlukan alasan yang lebih kuat daripada berpotensi enam bit "terbuang" pada 95% data Anda.

Untuk asumsi kedua Anda, akan benar jika, dan hanya jika, mengubah ukuran array menghasilkan lebih sedikit cache yang hilang. Apakah ini akan terjadi hanya dapat ditentukan secara definitif dengan membuat profil kode kerja, tapi saya pikir sangat tidak mungkin untuk membuat perbedaan besar. Karena Anda akan secara acak mengakses array dalam kedua kasus tersebut, prosesor akan berjuang untuk mengetahui bit data mana yang akan di-cache dan disimpan dalam kedua kasus tersebut.

Jika data dan akses terdistribusi secara acak secara acak, kinerja mungkin akan bergantung pada fraksi akses mana yang menghindari cache cache tingkat luar. Mengoptimalkan yang membutuhkan pengetahuan tentang ukuran array yang dapat ditampung dalam cache. Jika cache Anda cukup besar untuk menampung satu byte untuk setiap lima sel, pendekatan yang paling sederhana adalah dengan memiliki satu byte yang menahan lima basis-tiga nilai yang dikodekan dalam rentang 0-2 (ada 243 kombinasi dari 5 nilai, sehingga akan cocok dalam satu byte), bersama dengan array 10.000.000 byte yang akan ditanyakan setiap kali nilai dasar-3 menunjukkan "2".

Jika cache tidak terlalu besar, tetapi bisa menampung satu byte per 8 sel, maka tidak mungkin untuk menggunakan nilai satu byte untuk memilih dari semua 6.561 kemungkinan kombinasi dari nilai delapan basis-3, tetapi karena satu-satunya efek dari mengubah 0 atau 1 ke 2 akan menyebabkan pencarian yang tidak perlu, kebenaran tidak akan membutuhkan dukungan semua 6.561. Sebaliknya, orang dapat fokus pada 256 nilai "paling berguna".

Terutama jika 0 lebih umum daripada 1, atau sebaliknya, pendekatan yang baik mungkin menggunakan 217 nilai untuk menyandikan kombinasi 0 dan 1 yang mengandung 5 atau lebih sedikit 1, 16 nilai untuk menyandikan xxxx0000 hingga xxxx1111, 16 untuk menyandikan 0000xxxx melalui 1111xxxx, dan satu untuk xxxxxxxx. Empat nilai akan tetap untuk penggunaan lain apa pun yang mungkin ditemukan. Jika data didistribusikan secara acak seperti yang dijelaskan, sebagian kecil dari semua kueri akan mencapai byte yang berisi hanya nol dan satu (dalam sekitar 2/3 dari semua kelompok delapan, semua bit akan menjadi nol dan satu, dan sekitar 7/8 dari mereka akan memiliki enam atau lebih sedikit 1 bit); sebagian besar dari mereka yang tidak akan mendarat dalam byte yang berisi empat x, dan akan memiliki peluang 50% untuk mendarat di nol atau satu. Dengan demikian, hanya sekitar satu dari empat pertanyaan yang memerlukan pencarian array besar.

Jika data didistribusikan secara acak tetapi cache tidak cukup besar untuk menangani satu byte per delapan elemen, orang dapat mencoba menggunakan pendekatan ini dengan setiap byte menangani lebih dari delapan item, tetapi kecuali ada bias yang kuat terhadap 0 atau menuju 1 , pecahan nilai yang dapat ditangani tanpa harus melakukan pencarian dalam array besar akan menyusut karena jumlah yang ditangani oleh setiap byte meningkat.

Saya akan menambahkan jawaban @ o11c , karena kata-katanya mungkin sedikit membingungkan. Jika saya perlu menekan bit terakhir dan siklus CPU saya akan melakukan hal berikut.

Kita akan mulai dengan membangun pohon pencarian biner seimbang yang menampung 5% kasus "sesuatu yang lain". Untuk setiap pencarian, Anda berjalan pohon dengan cepat: Anda memiliki 10.000.000 elemen: 5% di antaranya di pohon: maka struktur data pohon menampung 500.000 elemen. Berjalan dalam waktu O (log (n)) ini, memberi Anda 19 iterasi. Saya bukan ahli dalam hal ini, tapi saya kira ada beberapa implementasi yang efisien-memori di luar sana. Mari kita tebak angka:

• Pohon seimbang, sehingga posisi subtree dapat dihitung (indeks tidak perlu disimpan di simpul pohon). Cara yang sama heap (struktur data) disimpan dalam memori linier.
• Nilai 1 byte (2 hingga 255)
• 3 byte untuk indeks (10000000 membutuhkan 23 bit, yang cocok dengan 3 byte)

Total, 4 byte: 500000 * 4 = 1953 kB. Sesuai dengan cache!

Untuk semua kasus lainnya (0 atau 1), Anda dapat menggunakan bitvector. Perhatikan bahwa Anda tidak dapat mengabaikan 5% kasus lainnya untuk akses acak: 1,19 MB.

Kombinasi keduanya menggunakan sekitar 3.099 MB. Dengan menggunakan teknik ini, Anda akan menghemat faktor 3,08 memori.

Namun, ini tidak mengalahkan jawaban @Matteo Italia (yang menggunakan 2,76 MB), sangat disayangkan. Adakah yang bisa kita lakukan ekstra? Bagian yang paling banyak memakan memori adalah 3 byte indeks di pohon. Jika kita bisa turun ke 2, kita akan menghemat 488 kB dan total penggunaan memori adalah: 2,622 MB, yang lebih kecil!

Bagaimana kita melakukan ini? Kita harus mengurangi pengindeksan menjadi 2 byte. Sekali lagi, 10000000 membutuhkan 23 bit. Kita harus bisa menjatuhkan 7 bit. Kita cukup melakukan ini dengan mempartisi kisaran 10.000.000 elemen menjadi 2 ^ 7 (= 128) wilayah dari 78125 elemen. Sekarang kita dapat membangun pohon yang seimbang untuk masing-masing daerah ini, dengan rata-rata 3906 elemen. Memilih pohon yang tepat dilakukan oleh divisi sederhana dari indeks target dengan 2 ^ 7 (atau bithift>> 7 ). Sekarang indeks yang diperlukan untuk menyimpan dapat diwakili oleh 16 bit yang tersisa. Perhatikan bahwa ada beberapa overhead untuk panjang pohon yang perlu disimpan, tetapi ini dapat diabaikan. Perhatikan juga bahwa mekanisme pemisahan ini mengurangi jumlah iterasi yang diperlukan untuk berjalan di pohon, ini sekarang mengurangi menjadi 7 iterasi lebih sedikit, karena kita menjatuhkan 7 bit: hanya 12 iterasi yang tersisa.

Perhatikan bahwa Anda secara teoritis dapat mengulangi proses untuk memotong 8 bit berikutnya, tetapi ini akan mengharuskan Anda untuk membuat 2 ^ 15 pohon seimbang, dengan ~ 305 elemen rata-rata. Ini akan menghasilkan 2,143 MB, dengan hanya 4 iterasi untuk berjalan di pohon, yang merupakan speedup yang cukup besar, dibandingkan dengan 19 iterasi yang kami mulai.

Sebagai kesimpulan akhir: ini mengalahkan strategi vektor 2-bit dengan sedikit penggunaan memori, tetapi merupakan keseluruhan perjuangan untuk diterapkan. Tetapi jika itu bisa membuat perbedaan antara menyesuaikan cache atau tidak, mungkin patut dicoba.

Jika Anda hanya melakukan operasi baca, lebih baik tidak menetapkan nilai ke indeks tunggal tetapi untuk interval indeks.

Sebagai contoh:

[0, 15000] = 0
[15001, 15002] = 153
[15003, 26876] = 2
[25677, 31578] = 0
...

Ini dapat dilakukan dengan sebuah struct. Anda juga mungkin ingin mendefinisikan kelas yang serupa dengan ini jika Anda menyukai pendekatan OO.

class Interval{
  private:
    uint32_t start; // First element of interval
    uint32_t end; // Last element of interval
    uint8_t value; // Assigned value

  public:
    Interval(uint32_t start, uint32_t end, uint8_t value);
    bool isInInterval(uint32_t item); // Checks if item lies within interval
    uint8_t getValue(); // Returns the assigned value
}

Sekarang Anda hanya perlu beralih melalui daftar interval dan memeriksa apakah indeks Anda berada di salah satu dari mereka yang dapat menjadi jauh lebih sedikit memori intensif rata-rata tetapi biaya lebih banyak sumber daya CPU.

Interval intervals[INTERVAL_COUNT];
intervals[0] = Interval(0, 15000, 0);
intervals[1] = Interval(15001, 15002, 153);
intervals[2] = Interval(15003, 26876, 2);
intervals[3] = Interval(25677, 31578, 0);
...

uint8_t checkIntervals(uint32_t item)

    for(int i=0; i<INTERVAL_COUNT-1; i++)
    {
        if(intervals[i].isInInterval(item) == true)
        {
            return intervals[i].getValue();
        }
    }
    return DEFAULT_VALUE;
}

Jika Anda memesan interval dengan ukuran menurun, Anda meningkatkan probabilitas bahwa item yang Anda cari ditemukan lebih awal yang selanjutnya mengurangi rata-rata memori dan penggunaan sumber daya CPU Anda.

Anda juga dapat menghapus semua interval dengan ukuran 1. Masukkan nilai yang sesuai ke dalam peta dan periksa hanya jika item yang Anda cari tidak ditemukan dalam interval. Ini juga harus meningkatkan kinerja rata-rata sedikit.

Dahulu kala, saya hanya bisa mengingat ...

Di universitas kami mendapat tugas untuk mempercepat program pelacak ray, yang harus dibaca dengan algoritma berulang-ulang dari buffer array. Seorang teman mengatakan kepada saya untuk selalu menggunakan RAM-baca yang merupakan kelipatan dari 4Bytes. Jadi saya mengubah array dari pola [x1, y1, z1, x2, y2, z2, ..., xn, yn, zn] ke pola [x1, y1, z1.0, x2, y2, z2 , 0, ..., xn, yn, zn, 0]. Berarti saya menambahkan bidang kosong setelah setiap koordinat 3D. Setelah beberapa pengujian kinerja: Itu lebih cepat. Singkat cerita: Baca kelipatan 4 Bytes dari array Anda dari RAM, dan mungkin juga dari posisi awal yang tepat, jadi Anda membaca sebuah cluster kecil di mana indeks yang dicari berada di dalamnya dan membaca indeks yang dicari dari cluster kecil ini di cpu. (Dalam kasus Anda, Anda tidak perlu memasukkan bidang isian, tetapi konsepnya harus jelas)

Mungkin juga kelipatan lainnya bisa menjadi kunci dalam sistem yang lebih baru.

Saya tidak tahu apakah ini akan berhasil untuk Anda, jadi jika tidak berhasil: Maaf. Jika berhasil, saya akan senang mendengar tentang beberapa hasil tes.

PS: Oh dan jika ada pola akses atau indeks yang diakses terdekat, Anda dapat menggunakan kembali kluster yang di-cache.

PPS: Bisa jadi, bahwa beberapa faktor lebih seperti 16Bytes atau sesuatu seperti itu, sudah terlalu lama, yang saya ingat persis.

Melihat ini, Anda dapat membagi data Anda, misalnya:

• bitet yang diindeks dan mewakili nilai 0 (std :: vector akan berguna di sini)
• bitet yang diindeks dan mewakili nilai 1
• a std :: vector untuk nilai 2, berisi indeks yang merujuk pada nilai ini
• peta untuk nilai-nilai lain (atau std :: vector>)

Dalam hal ini, semua nilai muncul hingga indeks yang diberikan, sehingga Anda bahkan dapat menghapus salah satu dari bitet dan mewakili nilai yang hilang di yang lain.

Ini akan menghemat beberapa memori untuk kasing ini, meskipun akan membuat kasing terburuk. Anda juga akan membutuhkan lebih banyak daya CPU untuk melakukan pencarian.

Pastikan untuk mengukur!

Seperti Mats menyebutkan dalam komentar-jawabannya, sulit untuk mengatakan apa sebenarnya solusi terbaik tanpa mengetahui secara spesifik jenis data apa yang Anda miliki (misalnya, apakah ada jangka panjang 0's, dan seterusnya), dan seperti apa pola akses Anda terlihat seperti (apakah "acak" berarti "di semua tempat" atau hanya "tidak sepenuhnya secara linear" atau "setiap nilai tepat sekali, hanya secara acak" atau ...).

Yang mengatakan, ada dua mekanisme yang muncul dalam pikiran:

• Array bit; yaitu, jika Anda hanya memiliki dua nilai, Anda dapat mengompresi array Anda dengan faktor 8; jika Anda memiliki 4 nilai (atau "3 nilai + yang lainnya"), Anda dapat mengompres dengan faktor dua. Yang mungkin tidak sepadan dengan masalahnya dan akan membutuhkan tolok ukur, terutama jika Anda memiliki pola akses yang benar - benar acak yang lolos dari cache Anda dan karenanya tidak mengubah waktu akses sama sekali.
• (index,value)atau (value,index)meja. Yaitu, memiliki satu tabel yang sangat kecil untuk case 1%, mungkin satu table untuk case 5% (yang hanya perlu menyimpan indeks karena semuanya memiliki nilai yang sama), dan bit array terkompresi besar untuk dua case terakhir. Dan dengan "tabel" maksud saya sesuatu yang memungkinkan pencarian relatif cepat; yaitu, mungkin hash, pohon biner, dan sebagainya, tergantung pada apa yang Anda miliki dan kebutuhan aktual Anda. Jika subtitle ini sesuai dengan cache level 1/2 Anda, Anda mungkin beruntung.

Saya tidak terlalu akrab dengan C, tetapi dalam C ++ Anda dapat menggunakan char yang tidak ditandatangani untuk mewakili integer dalam kisaran 0 - 255.

Dibandingkan dengan int normal (sekali lagi, saya berasal dari dunia Java dan C ++ ) di mana diperlukan 4 byte (32 bit), char yang tidak ditandatangani memerlukan 1 byte (8 bit). jadi itu mungkin mengurangi ukuran total array sebesar 75%.

Anda telah dengan ringkas menggambarkan semua karakteristik distribusi array Anda; melemparkan array .

Anda dapat dengan mudah mengganti array dengan metode acak yang menghasilkan output probabilistik yang sama dengan array.

Jika konsistensi penting (menghasilkan nilai yang sama untuk indeks acak yang sama), pertimbangkan untuk menggunakan filter bloom dan / atau peta hash untuk melacak klik berulang. Namun, jika array Anda diakses secara acak, ini sama sekali tidak perlu.