Ich arbeite derzeit an einem Embedded-Geräte-Projekt, bei dem Leistungsprobleme auftreten. Bei der Profilerstellung wurde eine O (N) -Operation gefunden, die ich beseitigen möchte.

Grundsätzlich habe ich zwei Arraysint A[N] undshort B[N]. Einträge inA sind einzigartig und werden nach äußeren Randbedingungen geordnet. Am häufigsten wird überprüft, ob ein bestimmter Wert vorliegta erscheint inA[]. Weniger häufig, aber immer noch üblich ist die Änderung eines Elements vonA[]. Der neue Wert hat nichts mit dem vorherigen Wert zu tun.

Da die häufigste Operation der Fund ist, ist das der OrtB[] kommt herein. Es ist eine sortierte Reihe von Indizes inA[], so dassA[B[i]] < A[B[j]] dann und nur dann, wenni<j. Das bedeutet, dass ich Werte in finden kannA mit einer binären Suche.

Natürlich, wenn ich updateA[k], Ich muss findenk imB und verschieben Sie es an eine neue Position, um die Suchreihenfolge beizubehalten. Da kenne ich die alten und neuen Werte vonA[k], das ist nur einmemmove() einer Teilmenge vonB[] zwischen der alten und der neuen Position vonk. Dies ist die O (N) -Operation, die ich reparieren muss. seit den alten und neuen werten vonA[k] sind im Wesentlichen zufällig, ich bewege mich im Durchschnitt überN / 2 N / 3 Elemente.

Ich habe nachgesehenstd::make_heap mit[](int i, int j) { return A[i] < A[j]; } als Prädikat. In diesem Fall kann ich leicht machenB[0] Zeigen Sie auf das kleinste Element vonAund AktualisierungB ist jetzt ein billiger O (log N) Ausgleichsvorgang. Im Allgemeinen benötige ich jedoch nicht den kleinsten Wert von A, sondern muss herausfinden, ob ein bestimmter Wert vorhanden ist. Und das ist jetzt eine O (N log N) Suche inB. (Die Hälfte meiner N Elemente befindet sich in der Heap-Tiefe log N, ein Viertel in (log N) -1 usw.), was keine Verbesserung gegenüber einer dummen O (N) Suche direkt in istA.

Bedenkt, dassstd::set hat O (log N) eingefügt und gefunden, ich würde sagen, dass es möglich sein sollte, hier die gleiche Leistung für Update und Suche zu erhalten. Aber wie mache ich das? Brauche ich eine andere Bestellung fürB? Ein anderer Typ?

B ist derzeit einshort [N] daA undB zusammen sind etwa die Größe meines CPU-Cache, und mein Hauptspeicher ist viel langsamer. Es wäre nicht schön, von 6 * N auf 8 * N Bytes zu wechseln, aber immer noch akzeptabel, wenn meine Suche und mein Update auf O (log N) gehen.