Array oder Datenbank?

[andi24]

Hallo zusammen,

ich habe einen Pool aus 3.000 verschiedenen Zahlenwerten (in einer Textdatei) und möchte von einer bestimmten Zahl wissen, ob sie in diesem Pool vorkommt.

Mir fallen jetzt zwei verschiedene Vorgehensweisen ein:

1) Ich lese die 3.000 Werte in eine Datenbank ein und suche dann einfach per SQL-Abfrage ob mein gesuchter Wert darin enthalten ist

2) Ich speichere die 3.000 Werte in einem Array/Liste und prüfe per liste.find ob mein Wert drin ist

Was würdet ihr mir raten? Aus dem Bauch heraus würde ich vermuten, dass die DB-Geschichte mehr kostet (alleine schon das Einlesen...). Aber kann ich andererseits überhaupt 3.000 Werte in einer Liste speichern?

Vielen Dank für euere Antworten,

Andi

[EyDu]

Hallo.

3000 Werte sind im Normalfall lächerlich wenig. Packe es einfach in eine Liste. Wenn du die Abfrage oft durchführen musst, dann wandle die Liste in eine Menge um.

Statt "find" solltest du auch besser "in" benutzen.

Sebastian

[Hyperion]

Wieso hast Du es nicht ausprobiert?

Code: Alles auswählen

In [6]: l = range(10000)

In [7]: l[999999]
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)

C:\Dokumente und Einstellungen\MECL User 1\Eigene Dateien\<ipython console> in <
module>()

IndexError: list index out of range

In [8]: l[99]
Out[8]: 99

Das ganze passiert extrem schnell. Im schlechtesten Fall ist der Zugriff eben O(n), bei n Einträgen. Ich weiß allerdings nicht, ob CPython da intern Verkettete Listen nutzt, oder direkten Index-Zugriff bietet. Aber Da Du ja nur 3000 Einträge hast, spielt das wohl nicht die große Rolle.

Ich denke, dass relationale Datenbanken da keinen Vorteil bringen.

Evtl. wäre ein Set aber das richtige für Dich. Da die Wert dort def. gehasht werden, sollte der Zugriff dort in O(1) funzen!

[DasIch]

Listen werden als Arrays implementiert, Indexzugriff kostet O(1) eine Suche allerdings O(n) im Gegensatz zu O(1) bei einem set.