Adressbuch effiziente Implementierung

Ich habe über die Implementierung eines Adressbuchs in C++ nachgedacht. Da es für die mobile Anwendung entwickelt wurde, sollte das Adressbuch so wenig Speicher wie möglich verwenden und der Benutzer sollte weiterhin in der Lage sein, Kontakte schnell nach Namen zu suchen oder zu sortieren (Paradoxon, die ich kenne).Adressbuch effiziente Implementierung

Nachdem ich etwas recherchiert habe, fand ich, dass die meisten Leute vorschlagen, dass eine Trie die beste Datenstruktur tp sein würde, die meinen Bedürfnissen entspricht. Genauer gesagt eine radix tree (Patricia Trie). Die Verwendung dieser Datenstruktur wäre auch für die Implementierung von Autocomplete geeignet.

Gibt es andere praktikable Lösungen oder ist es in Ordnung, wenn ich mit dieser Idee Codierung beginnen?

Quelle

2012-04-07 Dan Lincan

Über wie viele Einträge sprechen wir hier? Und wie schnell ist das mobile Gerät? Lohnt es sich wirklich, eine komplexe Datenstruktur zu implementieren? – Michael

Reguläre Adressbuchgröße. Ich denke, niemand hätte mehr als 5000 Kontakte (Tops) –

Vorsicht vor Versuchen für kleine Sammlungen. Obwohl sie ein gutes asymptotisches Verhalten bieten, könnte ihre verborgene Konstante in Zeit und Raum zu groß sein.

Vor allem, Versuche neigen dazu, schlechte Cache-Performance, die das Hauptanliegen für kleine Sammlungen sein sollte.

Angenommen, Ihre Daten sind relativ klein [< 10.000 Einträge], eine std::vector kann gute Cache-Leistung bieten, die wahrscheinlich viel mehr Einfluss als der Größenfaktor sein wird. Daher ist die Suchzeit dafür asymptotisch höher als trie oder ein std :: set, praktisch - es könnte besser sein als beides, dank eines guten Caching-Verhaltens.

Wenn Sie auch die vector sortiert verwalten können, verwenden Sie binary search - Sie können sowohl von der logarithmischen Suchzeit als auch von einem guten Cache-Verhalten profitieren.

(*) Bei dieser Antwort wird davon ausgegangen, dass die Hardware, auf der die App bereitgestellt wird, über CPU-Cache verfügt.

Quelle

2012-04-07 22:18:22 amit

Ist eine binäre Suche auf einem Vektor notwendigerweise schlimmer für Cache-Treffer als das Navigieren eines Trie? –

@OliCharlesworth: Ich glaube, es ist, unter der Annahme, dass die Sammlung ist klein - es [Vecotr '] könnte tatsächlich in den Cache passen. try [even radix tries] neigt dazu, viel Overhead zu haben, und daher ist es viel wahrscheinlicher, dass er den Cache "überläuft". Für kleine Sammlungen könnte dieser Unterschied viel bedeutender sein als das asymptotische Verhalten – amit

Das war, was ich befürchtete, der zusätzliche Overhead auf der Trie. Jetzt, wo Sie darauf hingewiesen haben, dass der Cache einen großen Unterschied haben kann (ich weiß nicht, warum ich nicht darüber nachgedacht habe), sehe ich bei diesem Problem völlig anders aus. –

Versuche sind die besten für diesen Zweck, da sie schnelle Suche, Einfügung und Löschung bieten.

Quelle

2012-04-07 22:11:55 aquasan

Antwort

Verwandte Themen