Recherche mathématique de sous-chaînes numériques sans comparaison de chaîne
https://stackoverflow.com/questions/231917
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
C’était à l’origine un problème que j’avais rencontré au travail, mais c’est maintenant quelque chose que j’essaie simplement de résoudre pour ma propre curiosité.
Je veux savoir si int 'a' contient l'international 'b' de la manière la plus efficace possible. J'ai écrit du code, mais il semble que peu importe ce que j'écris, il est analysé dans une chaîne puis utiliser indexOf est deux fois plus rapide que de le faire mathématiquement.
La mémoire n’est pas un problème (dans des limites raisonnables), mais une vitesse de traitement extrêmement rapide.
C’est le code que j’ai écrit pour le faire mathématiquement:
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;
}
Voici la méthode de chaîne que j'utilise, qui semble l'emporter sur la méthode mathématique ci-dessus:
private static boolean findStringMatch(int a, int b) {
return String.valueOf(a).indexOf(String.valueOf(b)) != -1;
}
Donc, bien que cela ne soit pas vraiment nécessaire pour terminer mon travail, je me demandais si quelqu'un pourrait penser à un moyen d'optimiser davantage ma façon de le faire mathématiquement, ou à une approche totalement nouvelle. Encore une fois, la mémoire n’est pas un problème, je ne fais que viser la vitesse.
Je suis vraiment intéressé de voir ou d'entendre tout ce que quelqu'un a à offrir à ce sujet.
ÉDITER: Lorsque je dis «je veux dire», il peut être n'importe où, par exemple, findMatch (1234, 23) == true
ÉDITER: Pour tous ceux qui disent que cette merde est illisible et inutile: vous ne comprenez rien. Il s’agissait de résoudre un problème intéressant sans chercher de solution dans le code de production.
La solution
C’est dans la ligne de Kibbee, mais cela m’intrigue un peu avant qu’il ne poste et travaille:
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 );
Étant donné que 300 caractères, c'est beaucoup trop peu pour pouvoir argumenter, j'édite ce post principal pour répondre à Pyrolistical.
Contrairement à l'OP, je n'étais pas étonné qu'un indexOf compilé natif soit plus rapide que le code Java avec des primitives. Mon objectif n'était donc pas de trouver quelque chose que je pensais être plus rapide qu'une méthode native appelée zillions de fois dans le code Java.
Le PO expliquait clairement qu'il ne s'agissait pas d'un problème de production mais plutôt d'une curiosité oisive. Ma réponse a donc résolu cette curiosité. J'imaginais que la vitesse était un problème lorsqu'il tentait de la résoudre en production, mais par curiosité inutile, & "Cette méthode s'appellera des millions et des millions de fois &"; ne s'applique plus. Comme il a dû expliquer à une personne qui l'a fait remarquer, ce n'est plus considéré comme un code de production et la complexité n'a plus d'importance.
De plus, il fournit la seule implémentation de la page qui parvient à trouver le " 123 " dans " 551241238 " ;, donc à moins que la correction ne soit une préoccupation étrangère, elle fournit cela. Également l'espace solution de & "; Un algorithme qui résout le problème de manière mathématique en utilisant des primitives Java mais bat le code natif optimisé &"; pourrait être VIDE .
De plus, votre commentaire ne précise pas si vous avez comparé des pommes à des pommes. La spécification fonctionnelle est f (int, int) - & Gt; boolean, not f (String, String) - > booléen (qui est un peu le domaine de indexOf). Donc, à moins que vous ne testiez quelque chose comme ceci (qui pourrait toujours battre le mien, et je ne serais pas terriblement surpris), les frais généraux supplémentaires pourraient engloutir une partie de cet excès de 40%.
boolean findMatch( int a, int b ) {
String s_a = "" + a;
String s_b = "" + b;
return s_a.indexOf( s_b ) > -1;
}
Il fait les mêmes étapes de base. log 10 (a) codage + log 10 (b) codage + recherche effective de la correspondance, ce qui correspond également à O ( n ) où < em> n est le plus grand logarithme.
Autres conseils
Cela devrait être plus rapide, car votre problème est textuel et non mathématique. Notez que le & Quot; contient votre & Quot; relation ne dit rien sur les nombres, mais seulement sur leurs représentations décimales .
Notez également que la fonction que vous souhaitez écrire sera illisible - un autre développeur ne comprendra jamais ce que vous faites. (Voyez quel problème vous avez eu ici.) La version avec cordes est parfaitement claire.
La seule optimisation à laquelle je puisse penser est de faire la conversion en chaîne par vous-même et de comparer les chiffres (de droite à gauche) au fur et à mesure de la conversion. Convertissez d’abord tous les chiffres de b, puis effectuez la conversion de la droite sur a jusqu’à ce que vous trouviez une correspondance sur le premier chiffre de b (de droite). Comparez jusqu'à ce que tous les éléments correspondent ou que vous rencontriez un problème. Si vous décelez une discordance, revenez au point où vous commencez à faire correspondre le premier chiffre de b, avancez a et recommencez.
IndexOf devra faire essentiellement le même algorithme de suivi en arrière, sauf en partant de la gauche. En fonction des chiffres réels, cela peut être plus rapide. Je pense que si les nombres sont aléatoires, cela devrait être le cas, car il devrait y avoir de nombreuses fois où il n’est pas nécessaire de convertir tous les éléments.
On dirait que votre fonction se porte plutôt bien, mais une petite amélioration:
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;
}
Ce n’est pas parce qu’une fois que a est plus petit que b, qu’il ne vaut pas la peine de regarder. Bonne chance et postez si vous trouvez la solution!
C'est un problème intéressant. De nombreuses fonctions de String.class sont en fait natives, ce qui rend difficile de battre String. Mais voici quelques aides:
CONSEIL 1: Différentes opérations sur les entiers simples ont des vitesses différentes.
Des calculs rapides dans des exemples de programmes ont montré:
% ~ T
* ~ 4T
/ ~ 7T
Donc, vous voulez utiliser le moins de division possible en faveur de la multiplication ou du modulo. Les opérateurs de soustraction, d’addition et de comparaison ne sont pas montrés, ce qui les chasse hors de l’eau. De plus, en utilisant & Quot; final & Quot; autant que possible, permet à la machine virtuelle Java d’effectuer certaines optimisations. Accélérer votre & Quot; getLength & Quot; fonction:
private static int getLength(final int b) {
int len = 0;
while (b > exponents[len]) {
len++;
}
return len + 1
}
Cela donne une amélioration 7x environ de la fonction. Vous obtenez une exception indexOutOfBounds si b & Gt; votre max en exposants. Pour résoudre ce problème, vous pouvez avoir:
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;
}
C'est un peu plus lent et vous donne une longueur incorrecte si b est trop grand, mais il ne lève pas d'exception.
CONSEIL 2: La création d'objet / primitive inutile et les appels de méthode s'ajoutent au temps d'exécution.
Je suppose que & «getLength &»; n'est appelé nulle part ailleurs, alors, même s'il peut être intéressant d'avoir une fonction distincte, du point de vue de l'optimisation, il s'agit d'un appel de méthode inutile et de la création de l'objet & "; len &" ;. Nous pouvons mettre ce code là où nous l’utilisons.
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;
}
Notez également que j’ai modifié la boucle while en bas pour inclure également & «a &; lt; = b &» ;. Je n'ai pas testé cela et je ne suis pas sûr que la pénalité de perquisition dépasse le fait que vous ne gaspillez pas d'itérations. Je suis sûr qu'il y a un moyen d'éliminer la division en utilisant des mathématiques intelligentes, mais je ne peux pas y penser pour le moment.
Hmm, je comprends probablement mal la question, mais .....
// Check if A is inside B lol
bool Contains (int a, int b)
{
return (a <= b);
}
Sauf si vous souhaitez savoir si une séquence de nombres particulière se trouve dans une autre séquence de nombres.
Dans ce cas, le convertir en chaîne SUIS plus rapide que de faire le calcul pour le comprendre.
Cela ne répond en aucun cas à votre question, mais c'est quand même un conseil: -)
Le nom de la méthode findMatch n'est pas très descriptif. Dans ce cas, j'aurais une méthode statique ContainerBuilder.number(int), qui renvoyait un ContainerBuilder, qui contenait la méthode contains. De cette façon, votre code devient:
boolean b = number(12345).contains(234);
Juts quelques conseils pour le long terme!
Oh oui, je voulais dire aussi, vous devez définir ce que vous entendez par & "contient &";
.Existe-t-il un moyen de calculer cela en binaire? De toute évidence, la valeur binaire d'un entier contenant l'entier binaire d'un autre caractère ne signifie pas que le décical fait la même chose. Cependant, existe-t-il une sorte de piège binaire qui pourrait être utilisé? Peut-être convertir un nombre tel que 12345 en 0001 0010 0011 0100 0101, puis effectuer un décalage de bit pour déterminer si 23 (0010 0011) y est contenu. Comme votre jeu de caractères ne comprend que 10 caractères, vous pouvez réduire le temps de calcul en stockant les valeurs de 2 caractères dans un seul octet.
EDIT
Développer un peu cette idée. si vous avez 2 nombres entiers, A et B, et que vous voulez savoir si A contient B, vous devez d'abord vérifier 2 choses. si A est inférieur à B, alors A ne peut pas contenir B. Si A = B, A contient B. À ce stade, vous pouvez les convertir en chaînes *. Si A contient le même nombre de nombres de caractères que B, alors A ne contient pas B, sauf s'ils sont égaux, mais nous ne serions pas ici s'ils sont égaux. Par conséquent, si les deux chaînes ont la même longueur, a ne contient pas b. . À ce stade, la longueur de A sera plus longue que celle de B. Vous pouvez donc maintenant convertir les chaînes en leurs valeurs binaires condensées, comme je l’ai indiqué dans la première partie de cet article. Stockez ces valeurs dans un tableau d'entiers. Maintenant, vous faites un AND au niveau des bits dans votre tableau, et si le résultat est A, alors A contient B. Maintenant, vous déplacez le tableau d’entiers pour B, vers la gauche 4 bits, et faites à nouveau la convergence. Faites-le jusqu'à ce que vous commenciez à extraire des bits à gauche de B.
* Cela * dans le paragraphe précédent signifie que vous pourrez peut-être ignorer cette étape. Il peut y avoir un moyen de faire cela sans utiliser de chaînes du tout. Il peut y avoir une astuce binaire sophistiquée que vous pouvez faire pour obtenir la représentation binaire emballée dont j'ai parlé dans le premier paragraphe. Il devrait y avoir une astuce binaire que vous pouvez utiliser, ou quelques calculs rapides qui convertiront un entier en valeur décimale dont j'ai déjà parlé.
Puis-je vous demander où vous utilisez cette fonction dans votre code? Peut-être y a-t-il un autre moyen de résoudre le problème en cours, qui serait beaucoup plus rapide. C'est peut-être comme lorsque mon ami m'a demandé de réaccorder complètement sa guitare, et je l'ai fait avant de réaliser que j'aurais pu simplement baisser la corde du bas de tout un pas et obtenir un résultat équivalent.
