Effiziente Traversal eines Änderungs

Question

Ich habe eine Liste von Änderungen in einer Liste - Hinzufügungen und Löschungen. Die Liste könnte sehr groß sein -. 10'000 Artikel sagen

Ich möchte nach der Änderung des Zustands der Liste wissen 9'000.

Ich könnte die Liste von Anfang an zu Fuß den ganzen Weg 9'000 zu ändern. Das scheint ein bisschen langatmig zu mir.

Ich könnte eine Liste der Elemente und Rekord halten, wenn sie hinzugefügt sind, und wenn sie gelöscht sind, dann diese Liste gehen, um zu sehen, was bei einer bestimmten Änderung in der Liste ist. Wenn Hinzufügungen und Löschungen gleich wahrscheinlich wäre, würde ich die Anzahl der Listenelemente halbieren würde ich zu Fuß durch brauchen ...

Aber Big O-Notation sagt, dass die Größe des Problems Halbieren macht die Sache nicht effizienter (wenn ich es richtig verstanden habe).

ich bei jeder 100.en oder 1000. Änderung des Zustands der Liste zwischenspeichern kann ... aber auch hier großes O sagt, dass die Anzahl der Elemente von ‚n‘ Dividieren macht die Sache nicht effizienter.

Was ist also der effizienteste Weg, dies zu tun? Gibt es einen effizienten Weg, dies zu tun?

Weitere Informationen: Insbesondere bin ich Tracking-Speicherzuordnungen / Aufheben dieser Zuordnungen in einem benutzerdefinierten allocater. Jede Zuordnung / Aufhebung der Zuordnung ist ein Ereignis in der Liste. Jede Zuordnung hat eine eindeutige ID. Ich würde gerne wissen, was zur Zeit nach (z) 9'000 Ereignissen zugeordnet ist.

Meine erste Idee war zu speichern, für jede ID, das Ereignis zugeordnet wurde und das Ereignis es freigegeben wurde. Dann diese Liste zu Fuß bis zu der ersten Zuteilung deren alloc Ereignis größer als 9000. Aber wie ich schon sagte, dies würde nur die Anzahl der Elemente halbieren, die ich brauchen würde, durch zu gehen.

ich den Punkt durch Mike F aus wie - vom nächsten 100. Artikel zu Fuß konstant Zeit ...

Answer 1

Wenn Sie den Zustand der Liste jedes X-te Änderung zwischenzuspeichern, dann können Sie eine binäre hacken tun, um zwei im Cache gespeicherten Zustände zu erhalten unten begrenzen die Änderung, die Sie suchen, dann gehen Sie bei den meisten X Artikel zum Artikel zu erhalten selbst. Das ist O (log N), mehr oder weniger.

Aber generell große O Komplexität zu reduzieren, ist das Mittel, nicht das Ende. Wenn Ihre Liste im Allgemeinen 10.000 Artikel sind, dann sollten Sie sich Sorgen darüber schnell für N machen = 10.000, wäre es durch die Komplexität zu reduzieren, oder nur um es schneller zu machen.

Edit: Hoppla, ich habe Ihre Frage nur vorsichtiger. Wenn Sie den Status all (zB) 100 Artikel zwischenzuspeichern, bist du nicht, so dass Sie nicht einmal eine binäre hacken tun müssen - Sie springen einfach direkt zum nächsten Cache gespeicherten Zustand und gehen höchstens 100 Artikel zum Artikel zu erhalten selbst. Also das ist eine konstante Zeit Algorithmus nicht?

Answer 2

Welche Art von Struktur arbeiten Sie mit? Es gibt nicht eine effiziente Möglichkeit, eine generische Datenstruktur zu gehen, aber es gibt Tausende von Optimierungsmethoden und effiziente Methoden für spezifische Strukturen.

Und ja, wenn Sie einen Algorithmus, die O (n) Zeit Komplexität ist, die Anzahl der Elemente halbiert wird es nicht von O ändern (n) Komplexität ... aber es wird bedeuten, dass jeder neue Artikel nur die Hälfte hat die Wirkung, die sie ursprünglich hatte. Big O-Notation ist eine gute Möglichkeit, Algorithmen zu klassifizieren, aber es ist wirklich nicht in Effizienz erhält außer in großer Zahl (ein gutes Beispiel ist das Sortieren. Quicksort schlechte Komplexität als mergesort im schlimmsten Fall ... aber man kann quicksort implementieren effizienter als mergesort für fast jede Anwendung andere als diejenigen, die sich mit Millionen von Artikeln)

Sortieren

Answer 3

‚Timestamp‘ oder jedes Einfügen und Löschen markieren, dann wäre es eine einfache Traversal nimmt Änderungen zu finden (O (n)).