modo più efficace per trovare dell'ultima occorrenza char

Consideriamo questa funzione ho scritto reale veloce per trovare l'ultima occorrenza di un determinato carattere in una stringa e restituire la sua posizione all'interno della matrice di caratteri che è fisicamente la stringa:modo più efficace per trovare dell'ultima occorrenza char

size_t strlstchar(const char *str, const char ch) 
{ 
    char *chptr = strrchr(str, ch); 
    return chptr - str; 
}

L'ho appena scritto molto velocemente qui (non ho ancora compilato o richiesto) solo perché ho delle domande su alcune cose.

Per me questa sembra la soluzione più semplice per trovare quale elemento dell'array contiene l'ultima istanza di un particolare char, ma non ho idea di come funzioni. L'ho appena fatto seguendo la documentazione di strrchr, quindi è tecnicamente strrchr a fare tutto il lavoro. Non riesco a immaginare che questo sia il modo migliore (in termini di prestazioni) per raggiungere questo obiettivo e speravo che qualcuno potesse dare qualche input su quale sarebbe il modo migliore per farlo.

È strrchr un modo efficace per farlo? O è meglio lo strrchr meglio per qualche altro uso?

fonte

2012-08-28 Keith Miller

strrchr può restituire NULL, rendendo così difficile prevedere il risultato della funzione quando non riesce a trovare il carattere. In genere "-str" può essere visto come un numero casuale, quindi convertito in size_t, come saprai che non hai trovato il char? – xryl669

L'approccio utilizzato è perfetto, purtroppo le operazioni con gli array sono costose. Strrchr nella maggior parte delle implementazioni semplicemente passa attraverso la stringa a partire dalla sua fine finché non trova un carattere corrispondente. Questo è il tempo O(n). Quindi esegui una sottrazione che è O(1). Non è così male

fonte

2012-08-28 20:34:15

Interessante, e grazie per la rapida risposta, mi sento sempre esitante nell'usare le funzioni di stringa, immagino che sia un habbit o qualcosa di non proprio sicuro del perché mi viene forgiato nel cervello che "se usi una funzione definita in string.h tu stai facendo male " –

@ KeithMiller è sbagliato. Quelle funzioni sono lì per uno scopo. Se esistesse un modo magico e costante per risolvere tutti i problemi algoritmici, gli implementatori di libc lo userebbero.E ricorda sempre la frase Linus Torvalds ha scritto: "Qualsiasi uomo sano di mente sa che K & R aveva ragione" :) –

Le stringhe sono molto lente in C, a causa della loro natura specifica (essendo 0x00 terminato): strrchr() va dall'inizio alla fine del string (o chiamando strlen() per conoscere la fine della stringa, che attraversa l'intera stringa, quindi prendendola dalla fine finché non trova il carattere, o facendolo in un passaggio semplice fino alla fine della stringa). Quindi, dovunque è il tuo personaggio trovato, l'intera stringa viene scansionata! – Parallelis

Dalla documentazione:

restituisce un puntatore all'ultima occorrenza di carattere nella stringa str C.

Così fa esattamente quello che vuoi. Lo scopo della sua esistenza è questo.

È strrchr un modo efficace per farlo?

È quasi sicuramente scritto almeno o meglio di quanto si possa fare da soli.

Oppure lo strrchr è meglio lasciare per qualche altro uso?

No. Ha scritto esattamente per questo scopo.

fonte

2012-08-28 20:37:34

Sarà più veloce se è possibile fornire la lunghezza della stringa, quindi eseguire il ciclo indietro. Quando trovi la prima occorrenza del personaggio ritorna subito.

Se non si conosce la lunghezza basta usare strrchr.

fonte

2012-08-28 20:38:57

Questo è quello che pensavo, ma in tal caso non avrei saputo la lunghezza della stringa a meno che non contenga caratteri NULL o qualcosa del genere, sarebbe addirittura considerato una stringa in quel punto? O solo una parte dei dati? E se ciò fosse più efficiente, perché non è così nella biblioteca standard? Sembra così semplice? Questo è il motivo per cui sono confuso perché a volte le cose non hanno senso per me :( –

Di solito in C non si conosce la lunghezza della stringa, quindi ha più senso non includere la lunghezza in strrchr. È necessario eseguire strlen per ottenere la lunghezza ogni volta che si utilizza strrchr, ma ci sono anche molte funzioni che restituiscono la lunghezza quando hanno successo come scanf. Se il tuo codice ha davvero bisogno di essere più efficiente, puoi tornare indietro. –

modo più efficace per trovare dell'ultima occorrenza char

risposta

Problemi correlati