pitone di ricerca efficiente stringa

Eventuali duplicati:
How is string.find implemented in CPython?pitone di ricerca efficiente stringa

Ho letto molti post qui nello stack overflow a confronto le prestazioni di ricerca di stringa (ad esempio Python string search efficiency, Is this the most efficient way to search for a substring?, substring in python, ecc ...)

Ho anche guardato la fonte c l'implementazione ode di contiene abstract.c.

Per quanto vedo l'implementazione built-in è un iterativo uno: python docs

Fa pitone avere un'implementazione di tecniche più sufficienti per la ricerca di una stringa: Boyer–Moore Algorithm, Rabin–Karp algorithm, ecc ... ?? ?

EDIT

La domanda è stata estesa: Python: Improving sub-string search by embedding sophisticated algorithms.

fonte

2012-09-03 Michael

rel: http://stackoverflow.com/questions/681649/how-is-string-find-implemented-in-cpython – georg

+1 sarà interessante confrontarlo con Rabin-Karp – Michael

@Martijn Pieters: avviso che ho posto questa domanda prima di aver aggiunto il link a string_contains. – Michael

L'effettiva attuazione stringa di ricerca CPython è qui:

http://hg.python.org/cpython/file/tip/Objects/stringlib/fastsearch.h

sembra utilizzare Boyer-Moore.

fonte

2012-09-03 09:05:29 georg

Grazie, io accetterò questa risposta, anche se mi interessa se c'è una tale implementazione anche per Rabin Karp. – Michael

Vedere il commento sull'altra risposta, non è B-M, è ispirato (semplificato) da B-M con alcuni Horspool e domenica gettati dentro. Vedi http://effbot.org/zone/stringlib.htm. –

L'implementazione di base non fornisce questo livello di funzionalità.

Troverete le implementazioni per Boyer-Moore o Rabin-Karp per Python utilizzando Google.

fonte

2012-09-03 09:03:02

Mentre in senso stretto CPython non usa BMRK può fornire prestazioni sublimate (buona cosa) usando algoritmo basato su BM: [The stringlib Library] (http://effbot.org/zone/stringlib.htm) – jfs

pitone di ricerca efficiente stringa

risposta

Problemi correlati