Datenstruktur für schnelle Filterung (Delphi)?

Question

Ich bin einen Teil einer Delphi-Anwendung zu optimieren, wo Listen von Objekten werden anhand verschiedene Kriterien häufig gefiltert. Die Objekte werden in TObjectList Strukturen gehalten, und es ist üblich, einen sehr geringen Prozentsatz zu wählen (ex. 1%) des gesamten Satzes mit jedem Filter. Die Gesamtzahl der Objekte kann in dem 100k Bereich und während Berechnungen der Hauptsatz nicht ändert. Obwohl die Filter nur wenige Eigenschaften angewendet werden, können die Listen nicht in eine solche Art und Weise sortiert werden, dass alle möglichen Kriterien optimieren würde.

Ich suche Vorschläge, wie die Objekte (Datenstrukturen) oder einen Algorithmus zu organisieren, die verwendet werden können, um dieses Problem zu nähern. Vielen Dank!

Filter Beispiel:

  ((Object.A between 5 and 15) AND
  (Object.B < 20) AND
  (Object.C(AParam) > 0)) OR
  (Object.IsRoot(...))

Answer 1

Idee # 1

Führen Sie den Code in einem Profiler. Finden Sie heraus, ob es irgendwelche langsamen Stellen.

Idee # 2

Möglicherweise könnten Sie die Vorteile der Cache-Effekte nehmen, indem Sie Ihre Objekte nacheinander im Speicher zu speichern. (Ich gehe davon aus Sie Ihre Liste gehen sequentiell von Anfang bis Ende.)

Eine Möglichkeit, es zu tun eine Reihe von Datensätzen statt einer Liste von Objekten zu verwenden, könnte sein. Wenn das möglich ist in Ihrem Fall. Denken Sie daran, dass Datensätze in Delphi 2006 können Methoden (aber nicht virtuelle).

Eine weitere Idee könnte sein, Ihre eigene Klasse allocator zu schreiben. Ich habe nie versucht, dass aber hier ist ein Artikel fand ich. vielleicht die Objekte versuchen, zu Fuß einen Zeiger anstelle der TObjectList zu verwenden.

Answer 2

Sie können ein verwenden sortierte Liste das Feld verwendet wird, welches Ihren Such einengt / Filterung höchstens und dann eine binäre Suche den Index / Indizes dieser Kriterien zu erhalten.

Mit Bezug auf Ihr Beispiel oben: Erzeugen eine A-sortierte Liste, die Suche nach dem Indizes von 5 und 15 und so erhalten Sie eine (viel) kleine Liste erhalten (alle Indizes zwischen den beide), wo Sie das überprüfen müssen andere Bereiche (B, C und IsRoot).

Delphi (2009+) Implementierung einer sortierten Liste: DeHL.Collections.SortedList

Answer 3

Ich weiß, dass Sie nicht tiOPF verwenden, aber es gibt viel zu aus dem Quellcode des Projektes zu lernen. Da Sie wahrscheinlich die gefilterten Objekte Schleifen über werden, warum nicht einen Filter Iterator erstellen?

Dieses Gerät ist ein guter Anfang, aber ich denke, dass es einfacher ist, die vollständige Quelle und blättern Sie durch die Dateien zum Download: http://tiopf.svn.sourceforge.net/viewvc/tiopf/tiOPF2/Trunk/Core/tiFilteredObjectList.pas?revision=1469&view = Markup

Diese Lösung nutzt wahrscheinlich eine Menge RTTI: nur eine Liste mit Filtern (Eigenschaftsnamen und Werte) erstellen und eine Schleife über die Objekte. Es wird Ihnen ein Höchstmaß an Flexibilität bieten, aber auf Kosten einer gewissen Geschwindigkeit. Wenn Sie beschleunigen muss ich glaube, die Lösung von Ulrichb zur Verfügung gestellt besser sein wird.

Answer 4

Wenn die Menge der Objekte klein ist, ist es wahrscheinlich keine Rolle, zu viel, wie effizient die Suche ist, wenn das Caching ein Ergebnis kann helfen, wenn oft getan.

Wenn die Menge der Objekte groß ist, würde ich mit einer In-Memory-Datenbank betrachten und mithilfe von SQL die Abfrage zu tun. Die Datenbank kann dann Indizes verwenden, die Dinge so schnell wie möglich zu finden, und Sie die Last auf ein bewährtes Instrument passieren. Ich persönlich verwende DBISAM oder ElevateDB, aber auch andere In-Memory-Datenbanken tun wird. ein echtes Datenbank-Tool verwenden, können Sie die Daten auf der Festplatte leicht bewegen, wenn es wirklich groß wird.

Answer 5

Wenn die Anzahl der Attribute Filter auf klein ist und sie können sortiert werden, warum nicht mehrere Listen, die jeweils, wenn die von einem anderen Attribut sortiert werden? Jede Liste kostet 4 Byte pro Objekt für die Referenz zuzüglich einer kleinen Overhead für die Liste selbst. Natürlich hängt alles ab, ob die Speicheranforderungen erfüllt werden. 2 GB ist nicht so viel, wenn Ihr mit einer Menge von Objekten zu tun ...

Answer 6

Dies ist ein sehr, sehr, sehr schwieriges Problem in allgemeiner Weise zu lösen . Es gibt eine Art von Software, die lange diese den ganzen Tag tut, und es ist ein SQL-Abfrage-Optimierer genannt: das Stück Code in jedem modernen SQL-Engine wird einen Blick auf, was Sie wollen (Abfrage), dann nehmen Sie einen Blick auf die Indizes für Ihre Daten, hat die Selektivität der verfügbaren Indizes und den optimalen Weg, um herauszufinden, alle zu verwenden, die Sie durch Ihre Ergebnismenge zu geben. Nur um zu beweisen das Problem ist sehr schwierig, manchmal die SQL-Abfrage-Optimierer schlägt fehl und erzeugt sichtbar ineffizient Pläne.

Ich bin mir ziemlich sicher, dass Sie nicht möchten, dass eine vollwertige Abfrageoptimierer zu implementieren, so sind hier einige Tipps, wie Sie Ihre Anfragen schnell genug zu machen:

(1) einige Felder auswählen, die in Ihren Abfragen häufig verwendet werden und Indizes auf ihnen aufgebaut. Diese Felder müssen eine gute Selektivität bieten: Do not Index auf einem „boolean“ Wert, würden Sie gerade Zeit verlieren Strukturen komplexe binäre Suche durchlaufen, wenn Sie könnte genauso schnell (oder schneller) Blick auf die ganze Liste

(2) Für jedes gegebene Abfrage wählen Sie ONE Single-Index-Vorfilter die Daten und die Anwendung alle anderen Filter one-by-one (ohne Optimierung).

In Ihrem Beispiel: Erstellen Sie Indizes für die „A“ und „B“ ein. „C“ scheint eine Funktion zu sein, so dass zum Index unmöglich ist. „IsRoot“ scheint ein Boolean zurück, die nicht wert Indizierung ist.

Die Datenstrukturen verwenden, um Ihre Daten vollständig auf Ihren Daten abhängen. Wenn die Leistung entscheidend ist implementieren mehrere und Tests durchführen. Wenn es nicht entscheidend ist nur Ihre Favoritenliste Sortieralgorithmus und durchgeführt werden!