Trovare matematicamente sottostringhe numeriche, senza confronto di stringhe
https://stackoverflow.com/questions/231917
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Inizialmente questo era un problema che mi sono imbattuto al lavoro, ma ora è qualcosa che sto solo cercando di risolvere per mia curiosità.
Voglio scoprire se int 'a' contiene int 'b' nel modo più efficiente possibile. Ho scritto del codice, ma sembra non importa quello che scrivo, analizzandolo in una stringa e quindi utilizzare indexOf è due volte più veloce di farlo matematicamente.
La memoria non è un problema (entro limiti ragionevoli), solo pura velocità di elaborazione.
Questo è il codice che ho scritto per farlo matematicamente:
private static int[] exponents = {10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
private static boolean findMatch(int a, int b) {
if (b > a) return false;
if (a == b) return true;
int needleLength = getLength(b);
int exponent = exponents[needleLength];
int subNum;
while (a >= 1) {
subNum = a % exponent;
if (subNum == b)
return true;
a /= 10;
}
return false;
}
private static int getLength(int b) {
int len = 0;
while (b >= 1) {
len++;
b /= 10;
}
return len;
}
Ecco il metodo stringa che sto usando, che sembra superare il metodo matematico sopra:
private static boolean findStringMatch(int a, int b) {
return String.valueOf(a).indexOf(String.valueOf(b)) != -1;
}
Quindi, sebbene questo non sia davvero necessario per me per completare il mio lavoro, mi stavo solo chiedendo se qualcuno potesse pensare a un modo per ottimizzare ulteriormente il mio modo di farlo matematicamente o un approccio completamente nuovo. Ancora una volta la memoria non è un problema, sto solo girando per la massima velocità.
Sono davvero interessato a vedere o ascoltare qualsiasi cosa qualcuno abbia da offrire al riguardo.
MODIFICA: Quando dico contiene intendo che può essere ovunque, quindi ad esempio findMatch (1234, 23) == true
EDIT: per tutti coloro che dicono che questa schifezza è illeggibile e non necessaria: ti manca il punto. Il punto era arrivare a scoprire un problema interessante, non trovare una risposta da utilizzare nel codice di produzione.
Soluzione
Questo è sulla falsariga di Kibbee, ma me ne sono incuriosito prima che pubblicasse e risolvesse:
long mask ( long n ) {
long m = n % 10;
long n_d = n;
long div = 10;
int shl = 0;
while ( n_d >= 10 ) {
n_d /= 10;
long t = n_d % 10;
m |= ( t << ( shl += 4 ));
}
return m;
}
boolean findMatch( int a, int b ) {
if ( b < a ) return false;
if ( a == b ) return true;
long m_a = mask( a ); // set up mask O(n)
long m_b = mask( b ); // set up mask O(m)
while ( m_a < m_b ) {
if (( m_a & m_b ) == m_a ) return true;
m_a <<= 4; // shift - fast!
if ( m_a == m_b ) return true;
} // O(p)
return false;
}
void testContains( int a, int b ) {
print( "findMatch( " + a + ", " + b + " )=" + findMatch( a, b ));
}
testContains( 12, 120 );
testContains( 12, 125 );
testContains( 123, 551241238 );
testContains( 131, 1214124 );
testContains( 131, 1314124 );
Dato che 300 caratteri sono troppo piccoli per discutere, sto modificando questo post principale per rispondere a Pyrolistical.
A differenza del PO, non ero così sorpreso che un indice compilato nativo fosse più veloce del codice Java con le primitive. Quindi il mio obiettivo non era quello di trovare qualcosa che pensavo fosse più veloce di un metodo nativo chiamato miliardi di volte in tutto il codice Java.
L'OP ha chiarito che questo non era un problema di produzione e più lungo le linee di una curiosità inattiva, quindi la mia risposta risolve tale curiosità. La mia ipotesi era che la velocità fosse un problema, quando stava cercando di risolverlo in produzione, ma come una curiosità inattiva, & Quot; Questo metodo verrà chiamato milioni e milioni di volte & Quot; non si applica più. Come ha dovuto spiegare a un poster, non è più perseguito come codice di produzione, quindi la complessità non conta più.
Inoltre fornisce l'unica implementazione sulla pagina che riesce a trovare il " 123 " in " 551241238 " ;, quindi a meno che la correttezza non sia una preoccupazione estranea, lo prevede. Anche lo spazio di soluzione di & Quot; un algoritmo che risolve matematicamente il problema utilizzando primitive Java ma batte il codice nativo ottimizzato & Quot; potrebbe essere VUOTO .
Inoltre, dal tuo commento non è chiaro se hai confrontato le mele con le mele. La specifica funzionale è f (int, int) - & Gt; booleano, non f (String, String) - > booleano (che è una specie di dominio indexOf). Quindi, a meno che tu non abbia testato qualcosa del genere (che potrebbe comunque battere il mio, e non sarei terribilmente sorpreso.) L'overhead aggiuntivo potrebbe consumare un po 'di quel 40% in eccesso.
boolean findMatch( int a, int b ) {
String s_a = "" + a;
String s_b = "" + b;
return s_a.indexOf( s_b ) > -1;
}
Fa gli stessi passaggi di base. log 10 (a) codifica + log 10 (b) codifica + trova effettivamente la corrispondenza, che è anche O ( n ) dove < em> n è il più grande logaritmo.
Altri suggerimenti
dovrebbe essere più veloce, perché il tuo problema è testuale, non matematico. Nota che il tuo & Quot; contiene & Quot; la relazione non dice nulla sui numeri, dice solo qualcosa sulle loro rappresentazioni decimali .
Nota anche che la funzione che vuoi scrivere sarà illeggibile - un altro sviluppatore non capirà mai cosa stai facendo. (Vedi quali problemi hai avuto qui.) La versione di stringa, d'altra parte, è perfettamente chiara.
L'unica ottimizzazione che mi viene in mente è quella di fare la conversione in stringa da solo e confrontare le cifre (da destra a sinistra) mentre fai la conversione. Prima converti tutte le cifre di b, quindi converti da destra su a fino a trovare una corrispondenza sulla prima cifra di b (da destra). Confronta fino a quando tutte le b coincidono o non raggiungi una discrepanza. Se si verifica una mancata corrispondenza, tornare indietro nel punto in cui si inizia a trovare la prima cifra di b, avanzare in a e ricominciare da capo.
IndexOf dovrà fondamentalmente fare lo stesso algoritmo di back tracking, tranne da sinistra. A seconda dei numeri effettivi questo potrebbe essere più veloce. Penso che se i numeri sono casuali, dovrebbe essere dal momento che ci dovrebbero essere molte volte in cui non è necessario convertire tutti un.
Sembra che la tua funzione stia effettivamente andando abbastanza bene, ma un piccolo miglioramento:
private static boolean findMatch(int a, int b) {
if (b > a) return false;
if (a == b) return true;
int needleLength = getLength(b);
int exponent = exponents[needleLength];
int subNum;
while (a > b) {
subNum = a % exponent;
if (subNum == b)
return true;
a /= 10;
}
return false;
}
Solo perché una volta che a è più piccolo di b, non è degno continua a cercare, vero? Buona fortuna e pubblica se trovi la soluzione!
Questo è un problema interessante. Molte delle funzioni di String.class sono in realtà native rendendo il battere String una proposta difficile. Ma ecco alcuni aiutanti:
SUGGERIMENTO 1: diverse operazioni su interi semplici hanno velocità diverse.
Con calcoli rapidi nei programmi di esempio ha mostrato:
% ~ T
* ~ 4T
/ ~ 7T
Quindi vuoi usare la minor divisione possibile a favore della moltiplicazione o del modulo. Gli operatori di sottrazione, addizione e confronto non sono mostrati perché fanno esplodere tutti questi dall'acqua. Inoltre, usando & Quot; final & Quot; il più possibile consente alla JVM di effettuare determinate ottimizzazioni. Accelerando & Quot; getLength & Quot; Funzione:
private static int getLength(final int b) {
int len = 0;
while (b > exponents[len]) {
len++;
}
return len + 1
}
Ciò comporta un miglioramento di 7 volte nella funzione. Si ottiene un'eccezione indexOutOfBounds se b & Gt; il tuo massimo in esponenti. Per risolverlo, puoi avere:
private static int getLength(final int b) {
int len = 0;
final int maxLen = exponents.length;
while (len < maxLen && b > exponents[len]) {
len++;
}
return len + 1;
}
È leggermente più lento e ti dà una lunghezza errata se b è troppo grande, ma non genera un'eccezione.
SUGGERIMENTO 2: la creazione di oggetti / primitive non necessarie e le chiamate al metodo si aggiungono al tempo di esecuzione.
Suppongo che " getLength " non viene chiamato da nessun'altra parte, quindi mentre può essere utile avere una funzione separata, dal punto di vista dell'ottimizzazione è una chiamata di metodo non necessaria e la creazione dell'oggetto " len " ;. Possiamo mettere quel codice esattamente dove lo usiamo.
private static boolean findMatch(int a, final int b) {
if (b > a) return false;
if (a == b) return true;
int needleLength = 0;
while (b > exponents[len]) {
needleLength ++;
}
needleLength++;
final int exponent = exponents[needleLength];
int subNum;
while (a >= 1 && a <= b) {
subNum = a % exponent;
if (subNum == b)
return true;
a /= 10;
}
return false;
}
Inoltre, nota che ho cambiato il ciclo while inferiore per includere anche " a < = b " ;. Non l'ho testato e non sono sicuro che la penalità per iterazione superi il fatto che non sprechi alcuna iterazione. Sono sicuro che c'è un modo per sbarazzarsi della divisione usando la matematica intelligente, ma non riesco a pensarci adesso.
Umm, probabilmente sto completamente fraintendendo la domanda, ma .....
// Check if A is inside B lol
bool Contains (int a, int b)
{
return (a <= b);
}
A meno che tu non voglia sapere se una particolare sequenza di numeri si trova all'interno di un'altra sequenza di numeri.
In tal caso, convertirlo in una stringa sarà più veloce di fare i calcoli per capirlo.
Questo non risponde in alcun modo alla tua domanda, ma è comunque un consiglio :-)
Il nome del metodo findMatch non è molto descrittivo. In questo caso, avrei un metodo statico ContainerBuilder.number(int), che ha restituito un ContainerBuilder, che ha il metodo contains su di esso. In questo modo il tuo codice diventa:
boolean b = number(12345).contains(234);
Juts qualche consiglio a lungo termine!
Oh sì, volevo dire anche che dovresti definire cosa intendi con "contains"
Esiste un modo per calcolare questo in binario? Ovviamente il valore binario di un numero intero contenente il numero intero binario di un altro carattere non significa che il decimale faccia lo stesso. Tuttavia, esiste una sorta di trucco binario che potrebbe essere utilizzato? Forse converti un numero come 12345 in 0001 0010 0011 0100 0101, e poi fai un po 'di spostamento di bit per capire se 23 (0010 0011) è contenuto lì. Poiché il set di caratteri contiene solo 10 caratteri, è possibile ridurre il tempo di calcolo memorizzando i valori di 2 caratteri in un singolo byte.
Modifica
Espandendo un po 'questa idea. se hai 2 numeri interi, A e B e vuoi sapere se A contiene B, controlla prima 2 cose. se A è minore di B, allora A non può contenere B. Se A = B quindi A contiene B. A questo punto è possibile convertirli in stringhe *. Se A contiene lo stesso numero di numeri di caratteri di B, allora A non contiene B, a meno che non siano uguali, ma non saremmo qui se fossero uguali, quindi se entrambe le stringhe hanno la stessa lunghezza, a non contiene b . A questo punto, la lunghezza di A sarà più lunga di B. Quindi, ora puoi convertire le stringhe nei loro valori binari impaccati, come ho notato nella prima parte di questo post. Memorizza questi valori in una matrice di numeri interi. Ora fai un AND bit a bit dei valori interi nella tua matrice, e se il risultato è A, allora A contiene B. Ora sposta la matrice di numeri interi per B, a 4 bit a sinistra, e fai di nuovo il conparison. Fallo finché non inizi a spuntare bit dalla sinistra di B.
* Che * nel paragrafo precedente significa che potresti essere in grado di saltare questo passaggio. Potrebbe esserci un modo per farlo senza usare le stringhe. Potrebbe esserci qualche trucco binario di fantasia che puoi fare per ottenere la rappresentazione binaria piena di cui ho discusso nel primo paragrafo. Ci dovrebbe essere qualche trucco binario che puoi usare, o qualche matematica veloce che convertirà un numero intero nel valore decimale di cui ho discusso prima.
Posso chiederti dove stai usando questa funzione nel tuo codice? Forse c'è un altro modo per risolvere il problema che sta risolvendo che sarebbe molto più veloce. Questo potrebbe essere come quando il mio amico mi ha chiesto di risintonizzare completamente la sua chitarra, e l'ho fatto prima di rendermi conto che avrei potuto abbassare la corda inferiore di un intero passo e ottenere un risultato equivalente.
