[python] schnell strings mit bestimmtem präfix finden

hi,

gibt es eine builtin python struktur, mit der ich schnell alle strings mit einem gegebenem präfix finden kann?

pre-fix schrieb:

hi,

gibt es eine builtin python struktur, mit der ich schnell alle strings mit einem gegebenem präfix finden kann?

string.startswith("deinpraefix")

dfgdfgdfg schrieb:

pre-fix schrieb:

hi,

gibt es eine builtin python struktur, mit der ich schnell alle strings mit einem gegebenem präfix finden kann?

string.startswith("deinpraefix")

ah jo, für einen string. aber wenn ich eine liste nehme

for i in sequence:
   if i.startswith(prefix)
      do_foo_on_i(i)

ist das Omega(n). Wenn ich das in einen Baum packe, geht das sicher besser. Frage: was ist die beste Struktur dafür, und gibt es die in Python schon?

Ja, dann mach es halt so. Dann kannst du die Präfixe in O(l) erfragen, mit l = Präfixlänge. Allerdings dürfte die Konstruktion dieser Struktur einiges kosten und es gibt auch kein geeignetes Builtin dafür.

borg

du könntest ein dict nehmen, welches die präfixes als keys hat und listen von strings mit den prefixes als values. an die liste mit den values kommst du dann noch mit .values() (vorsicht, sind dann listen in listen du brauchst also eine doppelte for schleife, ändert aber nichts an der laufzeit) und an die elemente kommst du dann mit dict[key] in O(1), also du kannst dann sowas machen wie results = map(do_foo_on_i, dict[prefix])