Erstellen eines sortierten Array effizient aus einer Datei

Question

Ich habe ein Array in der Binärdatei mit der Länge N auf der Festplatte gespeichert. Jedes Element des Arrays ist einmalig und hat einen Wert zwischen 1 bis N, inklusive. Alle Werte zwischen 1 bis Nsind im Array vorhanden. Ich möchte eine Funktion in C++ machen, die einen Vektor von Indizes (nullbasiert), idx der Länge n, erhält und die sortierten Elemente aus der Binärdatei zurückgibt, die an den Indizes genommen wurde.

Beispiel:

// saved_array = [2,6,4,10,7,1,9,3,5,8] with N = 10 

idx = [0,5,8]; // zero-based index 
readAndSortedArray(idx); // returns [1,2,5] 

Das 0-te Element ist 2, das fünfte Element ist 1 und das achte Element ist 5. Die Variable idx wird immer sortiert, aber das gespeicherte Array ist nicht sortiert. Die Länge von idx ist etwa 1% von N und der typische Wert von N ist 10.000.

Mein Code ist derzeit wie folgt.

Da die Funktion viele Male (Millionen mal) aufgerufen wird, möchte ich es effizient implementieren.

Haben Sie Ideen, wie Sie den obigen Algorithmus verbessern können?

Einige meiner Ideen sind:

• setzte das neue Element in die richtige Position direkt (dh nach einem Element aus der Datei, tut binäre Suche für das neue Element zu lesen, und auf dass das neue Element setzen Position), aber dies wird in O(n^2) Zeit ausgeführt (als eine Einfügung O(n) Zeit benötigt)
• Erstellen Sie ein leeres Array der Größe N, markieren Sie die Position des neuen Elements, und am Ende ziehen Sie die Elemente aus dem Array, das ist nicht Null, wird dies in O(N) Zeit ausgeführt werden.

Answer 1

Die einfachste Optimierung Idee hier ist ein Array einmal zu lesen und es dann wieder verwenden:

vector <int> readArray() { /* some code to read it from file */ } 

vector<int> sortedArray(const vector<int>& arr, const vector<int>& idx) { 
    vector<int> elements(idx.size()); 
    for (int i = 0; i < idx.size(); i++) { 
     elements[i] = arr[idx[i]]; 
    } 
    sort(elements.begin(), elements.end()); 
    return elements; 
} 

und dann irgendwo

vector<int> arr(readArray()); 
for (/* yor loop */) { 
    .... 
    some_vec = sortedArray(arr,some_idx) 
    .... 
}