Verknüpfte Listen oder Hash-Tabellen?

Question

Ich habe eine verknüpfte Liste von etwa 5000 Einträgen ("NOT" gleichzeitig eingefügt), und ich bin die Liste durchlaufen, auf der Suche nach einem bestimmten Eintrag bei Gelegenheiten (obwohl dies nicht sehr oft), sollte ich Hash-Tabelle als eine optimale Wahl für diesen Fall, anstelle der verknüpften Liste (die doppelt verknüpft ist & linear) ? Verwendung von C in Linux.

Answer 1

Ob die Verwendung einer Hashtabelle optimaler ist oder nicht, hängt vom Anwendungsfall ab, den Sie nicht im Detail beschrieben haben. Wichtiger ist jedoch, dass Sie sich vergewissern, dass der Engpass der Leistung in diesem Teil des Codes liegt. Wenn dieser Code nur ab und zu aufgerufen wird und nicht in einem kritischen Pfad liegt, ist es sinnlos, den Code zu ändern.

Answer 2

Wenn Sie mit einem Profiler noch nicht herausgefunden haben, dass der Code der langsame Teil der Anwendung ist, sollten Sie noch nichts unternehmen.

Wenn es langsam ist, aber der Code getestet ist, funktioniert und klar ist, und es andere langsamere Bereiche gibt, die Sie beschleunigen können, tun Sie diese zuerst.

Wenn es fehlerhaft ist, dann müssen Sie es auf jeden Fall zu beheben, gehen für die Hash-Tabelle, wie es schneller als die Liste sein wird. Dies setzt voraus, dass die Reihenfolge, in der die Daten durchlaufen werden, keine Rolle spielt. Wenn es Ihnen wichtig ist, was die Einfügereihenfolge ist, dann bleiben Sie bei der Liste (Sie können Dinge mit einer Hash-Tabelle tun und die Reihenfolge beibehalten, aber das macht den Code viel komplizierter).

Da Sie die Liste nur gelegentlich durchsuchen müssen, ist die Wahrscheinlichkeit, dass dies einen erheblichen Engpass in Ihrem Code darstellt, gering.

Eine weitere Datenstruktur, die man sich ansehen sollte, ist eine "Sprungliste", mit der man einen großen Teil der Liste überspringen kann. Dazu muss die Liste jedoch sortiert werden, was den Code je nach Aufgabe insgesamt langsamer machen kann.

Answer 3

Haben Sie Messungen durchgeführt und einen Leistungsabfall bei der Suche festgestellt? A hash_map ou hash table sollte gut sein.

Answer 4

Wenn Sie die Liste der Reihe nach durchlaufen müssen (nicht um Elemente zu suchen, sondern um sie anzuzeigen), ist eine verknüpfte Liste eine gute Wahl. Wenn man sie nur speichert, um Elemente nachschlagen zu können, ist eine Hash-Tabelle einer verketteten Liste weit überlegen (für alle außer der schlechtesten Hash-Funktion).

Wenn Ihre Anwendung beide Arten von Operationen erfordert, sollten Sie beide beibehalten und diejenige verwenden, die für eine bestimmte Aufgabe geeignet ist. Der Speicher-Overhead wäre gering, da Sie nur eine Kopie jedes Elements im Speicher halten und die Datenstrukturen Zeiger auf diese Objekte speichern müssten.

Wie bei jedem Optimierungsschritt, den Sie unternehmen, sollten Sie Ihren Code messen, um den tatsächlichen Engpass zu finden, bevor Sie irgendwelche Änderungen vornehmen.

Answer 5

Wenn Sie Wert auf Leistung legen, sollten Sie das unbedingt tun. Wenn Sie regelmäßig durch die Datei iterieren, um ein bestimmtes Element zu finden, lohnt es sich, eine Hash-Tabelle zu verwenden. Wenn es sich jedoch um einen seltenen Fall handelt und die gewöhnliche Verwendung der Liste keine Suche ist, dann gibt es keinen Grund, sich darüber Gedanken zu machen.