Perché la classe String di Java non implementa un indexOf () più efficiente?

"Efficienza" è tutto incentrato sui compromessi e l'algoritmo "migliore" dipenderà da molti fattori. Nel caso di indexOf() , uno di questi fattori è la dimensione prevista delle stringhe.

L'algoritmo di JDK è basato su un semplice riferimento indicizzato in array di caratteri esistenti. Il Knuth-Morris-Pratt di cui fai riferimento deve creare un nuovo int[] che abbia le stesse dimensioni della stringa di input. Per Boyer-Moore , hai bisogno di diverse tabelle esterne, almeno una delle quali è bidimensionale (credo: io mai implementato BM).

Quindi la domanda diventa: stiamo allocando gli oggetti aggiuntivi e le tabelle di ricerca degli edifici controbilanciati dall'aumento delle prestazioni dell'algoritmo? Ricorda, non stiamo parlando di un passaggio da O (N ² ) a O (N), ma semplicemente una riduzione del numero di passi compiuti per ogni N.

E mi aspetto che i progettisti JDK abbiano detto qualcosa del tipo "per stringhe inferiori ai caratteri X, il semplice approccio è più veloce, non ci aspettiamo un uso regolare delle stringhe più lungo di quello, e le persone che usano stringhe più lunghe sapranno come ottimizzare le loro ricerche. "

L'algoritmo di ricerca di stringhe standard efficiente che tutti conoscono è Boyer-Moore . Tra le altre cose è necessario creare una tabella di transizione delle stesse dimensioni del set di caratteri. Nel caso di ASCII, questo è un array con 256 voci, che è un sovraccarico costante che paga su stringhe lunghe, e non rallenta le stringhe piccole di abbastanza per chiunque a preoccuparsi. Ma Java usa caratteri a 2 byte che rendono la tabella di 64 KB. Nell'uso normale, questo sovraccarico supera la velocità prevista da Boyer-Moore, quindi Boyer-Moore non ne vale la pena.

Naturalmente la maggior parte di quella tabella avrà la stessa voce, quindi potresti pensare di memorizzare le eccezioni in modo efficiente e quindi fornire valori predefiniti per tutto ciò che non fa parte delle eccezioni. Sfortunatamente, i modi per farlo vengono con il sovraccarico di ricerca che li rende troppo costosi per essere efficienti. (Per un problema, ricorda che se uno prende un ramo inatteso provoca uno stallo della pipeline e quelli tendono ad essere costosi.)

Si noti che con Unicode questo problema dipende molto dalla codifica. Quando Java è stato scritto, Unicode si adattava a 64 K, quindi Java usava solo 2 byte per carattere e la lunghezza della stringa era semplicemente il numero di byte diviso per 2. (Questa codifica era chiamata UCS-2.) Ciò lo rese veloce a passa a qualsiasi carattere particolare o estrae una sottostringa particolare e l'inefficienza di indexOf() non è un problema. Sfortunatamente Unicode è cresciuto, quindi un personaggio Unicode non sempre si adatta a un personaggio Java. Ciò ha portato Java nei problemi di dimensioni che stavano cercando di evitare. (La loro codifica ora è UTF-16.) Per compatibilità con le versioni precedenti non potevano cambiare la dimensione di un carattere Java, ma ora c'è un meme che i caratteri Unicode e i caratteri Java sono la stessa cosa. Non lo sono, ma pochi programmatori Java lo sanno, e ancor meno sono suscettibili di incontrarlo nella vita quotidiana. (Si noti che Windows e .NET hanno seguito lo stesso percorso, per gli stessi motivi.)

In alcuni altri linguaggi e ambienti viene invece utilizzato UTF-8. Ha le buone proprietà che ASCII è valido Unicode e Boyer-Moore è efficiente. Il compromesso è che non prestare attenzione ai problemi con byte variabili ti colpisce molto più ovviamente di quanto non faccia in UTF-16.

Si tratta principalmente di questo: il miglioramento più ovvio è da Boyer-Moore, o qualche variante di esso. B-M e le varianti, tuttavia, vogliono davvero un'interfaccia completamente diversa.

In particolare, Boyer-Moore e le derivate funzionano davvero in due fasi: prima si esegue un'inizializzazione. Questo crea una tabella basata esclusivamente sulla stringa che stai cercando per . Questo crea una tabella che puoi usare per cercare quella stringa tutte le volte che vuoi.

Certamente potrebbe adattarsi all'interfaccia esistente memorizzando la tabella e utilizzandola per ricerche successive della stessa stringa di destinazione. Non penso che si adatterebbe molto bene all'intenzione originale di Sun per questa funzione: che si tratti di un blocco elementare di basso livello che non dipenderebbe da molto altro. Rendendogli una funzione di livello superiore che dipende da un bel po 'di altre infrastrutture significherebbe (tra le altre cose) che dovresti assicurarti che nessuna delle infrastrutture di memoizzazione utilizzate possa mai utilizzare la ricerca della sottostringa.

Penso che il risultato più probabile sarebbe semplicemente la reimplementazione di qualcosa di simile (ad esempio, una routine di ricerca autonoma) con un nome diverso, con una routine di livello superiore con il nome esistente. Tutto sommato, penso che probabilmente avrebbe più senso scrivere semplicemente una nuova routine di livello superiore con un nuovo nome.

L'ovvia alternativa sarebbe quella di usare una sorta di versione ridotta del memoizing, che (ad esempio) memorizzava staticamente una sola tabella e la riutilizzava se la stringa di destinazione era identica a quella usata per crea il tavolo. Questo è certamente possibile, ma sarebbe molto meno ottimale per molti casi d'uso. Rendere il thread-safe sarebbe anche non banale.

Un'altra possibilità sarebbe quella di esporre esplicitamente la natura in due fasi della ricerca di B-M. Dubito che a qualcuno piacerebbe davvero quell'idea - comporta un costo piuttosto elevato (goffaggine, mancanza di familiarità) e poco o nessun beneficio per molti casi d'uso (la maggior parte degli studi sull'argomento indica che la lunghezza media della corda è qualcosa come 20 caratteri).