come velocizzare l'accesso casuale dell'array 2D? [chiuso]

L'accesso agli elementi dell'array è O (1) in termini di tempo. Non puoi fare di meglio. Cambia il tuo algoritmo.

2 ^ 10 = 1000 (approssimativamente)
2 ^ 20 = 1000 (all'incirca) x 1000 (approssimativamente) = 1.000.000 (approssimativamente)
2 ^ 30 = 1000 (all'incirca) x 1.000.000 (approssimativamente) = 1.000.000.000 (circa)

Poiché l'array non è dimensionato su un limite di potenza di due, per calcolare l'indirizzo di qualsiasi cella a cui stai accedendo ci vorrà qualche brutto aritmetico.

Supponendo che occorra, ad esempio, 100 tick di clock per fare qualsiasi cosa tu stia facendo a ciascun elemento, e un clock a 1 GHz, stai parlando di 100 secondi con NOTHING che sta succedendo. Sono circa due minuti.

Stai chiamando 100.000 * sizeof (arr [0]) * 1 gigabyte per il tuo array. Supponendo che tu stia usando un linguaggio che virtualizza e scambia su disco, stai per battere (termine tecnico) il santo frack dal tuo dispositivo di swap.

È DAVVERO necessario pensarci ancora.

Ispirato alla risposta di VinyleEm, il mio suggerimento per una struttura dati personalizzata

La tua matrice è troppo grande per la memoria. Le mappe hash e gli alberi rb hanno un sovraccarico per voce e ogni voce deve memorizzare sia value che i , che già aggiunge fino a 8 byte escludendo il sovraccarico. Potrebbero essere necessari alcuni trucchi personalizzati per ridurre al minimo l'overhead sia della memoria che dei calcoli.

Suggerirei di suddividere le voci 2 ^ 30 in pezzi, ad es. 2 ^ 10 pezzi di (massimo) 2 ^ 20 voci ciascuno. Ogni pezzo può essere un vettore ordinato di coppie di indice e valore.

Pensando, se sono 2 ^ 15 pezzi di 2 ^ 15 voci max ciascuno, allora l'indice all'interno di ogni pezzo può essere memorizzato in due byte. Il valore è 4 byte, quindi il totale è 6 byte per voce. O qualsiasi altro break-up con 2 ^ 16 o meno voci massime.

Utilizzo totale della memoria: number_of_actual_entries * 6 byte + additional_overhead (che stimano essere di circa 1 MB). [1]

Mantenere le voci ordinate in qualsiasi momento sarà lento, quindi è meglio usare semplicemente emplace_back () e ordinare alla fine.

Questo ha il vantaggio aggiuntivo che il working set della memoria attiva è ridotto: quando si aggiungono voci, è attiva solo la fine di ogni vettore, mentre durante l'ordinamento è attivo solo un vettore. Ciò migliora il comportamento della cache e mantiene lo scambio al minimo.

std::vector<std::pair<short, int>> arr[1 << 15];

// Fill the entries
for(int i = 0; i < (1 << 28); ++i) // Whatever
{
  int value = foo(i); // Or whatever you calculate

  int piece = (value >> 15);
  short entry = (value && 0x7fff);
  arr[piece].emplace_back(entry, i);
}

// Now sort everything
for(int j = 0; j < (1 << 15); ++j)
{
  std::sort(arr[j].begin(), arr[j].end(),
    [](std::pair<short,int> lhs, std::pair<short,int> rhs)
      { return lhs.first < rhs.first; }
}

// Datastructure is ready to be used

[1] Alla maggior parte dei compilatori deve essere detto di non allineare quei sei byte, per evitare di sprecare altri due byte sul padding.

Bene, penso di sapere cosa vuoi. Si desidera salvare 2 ^ 28 valori in una struttura dati, in modo da poter eseguire una ricerca inversa rapida (ricerca di indici con un valore specifico). Ci sono 3 metodi che puoi usare qui.

Invece di usare array statici, puoi utilizzare i vettori 2 ^ 30 e farli crescere mentre inserisci valori, o una mappatura hash dai valori agli array, oppure puoi usare qualcosa come un albero rosso-nero. Tutte queste alternative continueranno ad occupare memoria in GB (dopotutto, 2 ^ 28 interi prenderanno 1GB più memoria per qualsiasi struttura di dati che si sta utilizzando).

Approccio vettoriale. Utilizzerai i vettori 2 ^ 30. Funziona perché, in generale, devi solo aggiungere 2 ^ 28 numeri interi.

arr = new vector[2^30];
for (int i = 0;i < 2^28; i++) {
    value = ...; // 0 <= value < 2^30
    arr[value].add(i);
}

Approccio alla tabella hash. Questo approccio funziona bene solo se l'insieme di valori che si genera è più piccolo del totale 2 ^ 30 possibile. Altrimenti, è peggio dell'approccio precedente.

table = new HashTable();
for (int i = 0;i < 2^28; i++) {
    value = ...;
    if (!table.find(value)) {
        table[value] = new vector();
    }
    table[value].add(i);
}

Approccio Red Black Tree - Gli alberi red-black vengono forniti come strutture dati standard nella maggior parte delle lingue, come TreeSet / TreeMap in Java, set / map in C ++ STL ecc. Puoi usarli o implementarli di tua scelta. I nodi in questo albero sono ordinati in base ai valori di tupla (valore, indice), che rendono possibile la ricerca veloce. All'interno di questo albero, puoi cercare valori o indici con un valore specifico.

tree = new redBlackTree();
for (int i = 0;i < 2^28; i++) {
    value = ...;
    tree.insert(pair(value, i));
}