Perché il C++ implementato string::find() non utilizza KMP algorithm (e non viene eseguito in O(N + M)) e viene eseguito in O(N * M)? È corretto in C++ 0x? Se la complessità della ricerca corrente non è O(N * M), che cos'è?C++ stringa :: trovare la complessità
PS: Mi dispiace dire string::find()
così quello che l'algoritmo è implementato in gcc? è quel KMP? se no, perché? L'ho provato e il tempo di esecuzione indica che viene eseguito in O(N * M)
Perché lo string :: substr() implementato da C++ non utilizza l'algoritmo KMP (e non viene eseguito in O (N + M)) e viene eseguito in O (N * M)?
suppongo che voi dire find(), piuttosto che substr() che non ha bisogno di cercare e dovrebbe essere eseguito in tempo lineare (e solo perché deve copiare il risultato in una nuova stringa).
Lo standard C++ non specifica i dettagli dell'implementazione e in alcuni casi specifica solo i requisiti di complessità. Gli unici requisiti di complessità delle operazioni std::string sono che size(), max_size(), operator[], , c_str() e data() sono tutti costanti. La complessità di qualsiasi altra cosa dipende dalle scelte fatte da chiunque abbia implementato la libreria che stai utilizzando.
Il motivo più probabile per scegliere una ricerca semplice su qualcosa come KMP è evitare di richiedere ulteriore spazio di archiviazione. A meno che la stringa da trovare sia molto lunga e la stringa da cercare contenga molte corrispondenze parziali, il tempo impiegato per allocare e liberare sarebbe probabilmente molto più del costo della complessità extra.
È corretto in C++ 0x?
No, C++ 11 non aggiunge alcun requisito di complessità a std::string e sicuramente non aggiunge dettagli di implementazione obbligatori.
Se la complessità del substr attuale non è O (N * M), che cos'è?
Questa è la complessità peggiore, quando la stringa da cercare contiene molte corrispondenze parziali lunghe. Se i personaggi hanno una distribuzione abbastanza uniforme, la complessità media sarebbe più vicina a O(N). Quindi, scegliendo un algoritmo con la migliore complessità del caso peggiore, è possibile rendere molto più lenti i casi più tipici.
Lo so, ma perché non implementano l'algoritmo più veloce (KMP)? – Farzam
@ Farzam: (a) è più difficile da implementare correttamente; (b) richiede allocazione di memoria, e ha solo una minore * peggiore * complessità, quindi nella pratica sarà probabilmente più lento per i casi d'uso più comuni. –
ma è più veloce per N grandi. possono fare 'O (N * M)' per N piccoli e KMP per N grandi. Richiede anche la memoria O (N), quindi l'ordine di memoria generale non cambia. – Farzam
Da dove viene l'impressione che lo std::string::substr() non utilizzi un algoritmo lineare? In effetti, non posso nemmeno immaginare come implementare in un modo che abbia la complessità che hai citato. Inoltre, non c'è molto di un algoritmo coinvolto: è possibile che tu pensi che questa funzione faccia qualcosa di diverso da quello che fa? std::string::substr() crea appena una nuova stringa iniziando dal primo argomento e utilizzando il numero di caratteri specificato dal secondo parametro oi caratteri fino alla fine della stringa.
Potrebbe riferirsi a std::string::find() che non ha requisiti di complessità o std::search() che è effettivamente consentito fare confronti O (n * m). Tuttavia, questo è un implementatore dando la libertà di scegliere tra un algoritmo che ha la migliore complessità teorica rispetto a quella che non ha bisogno di memoria aggiuntiva. Poiché l'assegnazione di quantità arbitrarie di memoria è generalmente indesiderabile a meno che non sia specificamente richiesto, sembra ragionevole farlo.
serie La C++ non dettare le caratteristiche prestazionali di substr (o molte altre parti, tra cui il find si è più probabile riferimento a un M*N complessità).
Principali aspetti funzionali aspetti della lingua (con alcune eccezioni come le funzioni non-legacy sort, ad esempio).
Le implementazioni sono anche gratuite per implementare qsort come un bubble sort (ma solo se vogliono essere ridicolizzati e possibilmente andare fuori mercato).
Per esempio, ci sono solo sette (molto piccole) sotto-punti nella sezione 21.4.7.2 basic_string::find di C++ 11 e nessuno di loro specificare parametri di prestazione.
Non sono sicuro di 'qsort()' ma 'std :: sort()' è richiesto per avere complessità O (n * ln (n)) in C++ 2011. In C++ 2003 è stato possibile avere una complessità O (n * n) per avere [quicksort] (http://en.wikipedia.org/wiki/Quicksort) essere una scelta valida per un algoritmo ma è stato dimostrato che è possibile ottenere prestazioni del caso normali simili con [introsort] (http://en.wikipedia.org/wiki/Introsort) come si otterrebbe per quicksort pur avendo una complessità del caso peggiore di O (n * ln (n)). Un implementatore è libero di utilizzare un algoritmo diverso con la stessa peggiore complessità del caso. –
'qsort' non ha requisiti come quello, è puramente funzionale, come in C. Ancora più importante, mentre alcune parti di C++ hanno requisiti come questo,' substr' e 'find' non fanno parte di quel sottoinsieme. Ma hai sollevato un buon punto sul materiale non ereditario, quindi l'ho aggiunto alla risposta. – paxdiablo
Dove vengono fornite le informazioni sulla libreria C++? Se intendi dire string::search e in realtà non usa l'algoritmo KMP, allora suggerisco che è perché l'algoritmo non è generalmente più veloce di una semplice ricerca lineare a causa della necessità di costruire una tabella di corrispondenza parziale prima che la ricerca possa procedere.
ma la costruzione della tabella di corrispondenza può essere eseguita anche in tempo lineare. (per esempio se N, M = 10^6: N * M = 10^12 ma KMP farà circa 10 * 10^6 operazioni che è circa 10^5 volte più veloce dell'altra. – Farzam
@Farzam: Quindi quanto spesso il caso N = M = 10^6 si verifica in pratica? Penso che il caso tipico potrebbe essere più simile a N = 100, M = 5. Anche la maggior parte searchstring probabilmente fallirà il confronto dopo 1 o 2 caratteri, quindi la performance essere più come O (N). Quindi per i casi tipici il sovraccarico di metodi più complessi può essere sostanziale – Grizzly
FYI, La stringa :: find in gcc/libstdC++ e llvm/libcxx era molto lenta. In alcuni casi è stato notevolmente migliorato di 20 volte. Si potrebbe voler controllare la nuova implementazione:
GCC: PR66414 ottimizzare std :: string :: trovare https://github.com/gcc-mirror/gcc/commit/fc7ebc4b8d9ad7e2891b7f72152e8a2b7543cd65
Vediamo nel libro CLRS. Nella pagina 989 della terza edizione abbiamo il seguente esercizio:
Supponiamo che pattern P e il testo T sono scelti a caso stringhe di, rispettivamente, lunghezza m e n, dal d-ary alfabeto Ʃ d = {0; 1; ...; d}, dove d> = 2. Prova che il numero atteso di confronti carattere per carattere fatte dal ciclo implicito nella linea 4 dell'algoritmo ingenuo è
su tutte le esecuzioni di questo ciclo. (Supponiamo che l'algoritmo ingenuo smetta di confrontare i caratteri per un dato turno una volta che trova un disallineamento o corrisponda all'intero schema.) Quindi, per le stringhe scelte casualmente, l'algoritmo ingenuo è abbastanza efficiente.
NAIVE-STRING-MATCHER(T,P)
1 n = T:length
2 m = P:length
3 for s = 0 to n - m
4 if P[1..m] == T[s+1..s+m]
5 print “Pattern occurs with shift” s
Dimostrazione:
Per un solo turno ci si aspetta di effettuare 1 + 1/d + ... + 1/d^{m-1} confronti. Ora usa la formula di sommatoria e moltiplica per numero di turni validi, che è n - m + 1.□
Forse intendete 'string :: find'? –
'substr' non esegue alcuna ricerca. Ti riferisci a 'find'? – Mat
scusate, si significo 'find' – Farzam