J'ai besoin de trouver le plus haut ordre 1 sur certains longs, intens et shorts en Java. Par exemple, si j'avais un char qui ressemblait à Maintenant, je sais que vous pouvez le faire en utilisant un Pour boucle comme: mais cela est bien plus lent que ce que je veux faire. Je sais que les processeurs modernes ont des instructions qui font cela sur puce. Je veux donc savoir comment je peux apporter un appel à cela plutôt que d'avoir une boucle explicite. Edit: Bonus Points Si vous pouvez simplement retourner les indices de tous ceux de la primitive. merci. 00110101 , j'ai besoin d'une méthode qui retournera 2 (index du plus haut ordre 1).
6 Réponses :
Je ne sais pas de frapper une instruction CPU, mais je sais que ce sera beaucoup plus vite si vous déroulez la boucle et utilisez un masquage explicite de bits.
En outre, un caractère n'est pas 8 bits ... Je pense que vous pourriez avoir voulu dire un octet.
Je pensais à C de style Chant (ils sont de 8 bits à droite? ...). Les caractères de Java sont-ils 2 octets pour le support Unicode?
La page " Les hacks de bits Twiddling " contient beaucoup de hacks bits. On est de savoir comment trouver le Index du bit de commande le plus élevé .
J'utilisais ces algorithmes dans mon code Java, mais la plupart d'entre eux ont été ajoutés à l'API de la plate-forme au cours des dernières années.
Cependant, la méthode de séquence de Bruijn est toujours marginalement plus rapide que la méthode de la division et de conquérir utilisée dans le numéro d'intégré Numberfleadingzeros et NumberOraileerSeros .
Autant que je puisse dire, le Pentium et les amis n'ont pas d'instruction prête pour cela. Donc, la chose à faire est d'utiliser un algorithme décent.
La clé pour obtenir votre réponse rapidement est d'utiliser une recherche binaire. Vous envisagez un Le code fonctionne dans un gros arbre laid de 64 si des déclarations, mais seule une fraction de ceux-ci sera jamais exécutée, alors le temps d'exécution est bon.
Si vous avez besoin d'un code d'échantillon, je peux le faire. Mais je préférerais pas. long avec 64 bits? 6 comparaisons vous donneront votre plus haut bit, à chaque fois.
Il n'est pas nécessaire d'être exprimé à l'aide d'un arbre, voir ma réponse.
Comme je l'ai commenté, j'aime l'élégance du code mais je doute que sa performance soit acceptable.
Cette méthode utilise une belle approche Divide-Conquer, copiée ici pour votre avis: P> integer.numberfleadingzeros (i) + 1 code> public static int numberOfLeadingZeros(int i) {
// HD, Figure 5-6
if (i == 0)
return 32;
int n = 1;
if (i >>> 16 == 0) { n += 16; i <<= 16; }
if (i >>> 24 == 0) { n += 8; i <<= 8; }
if (i >>> 28 == 0) { n += 4; i <<= 4; }
if (i >>> 30 == 0) { n += 2; i <<= 2; }
n -= i >>> 31;
return n;
}
L'algorithme est élégant, mais le changement est horriblement lent afaik.
Mieux vaut changer 8 fois (pire des cas), que 32, comme généraliser la boucle de la question. (Et cela suppose que le compilateur JIT se déroule la boucle, sinon la générale de la branche dominerait.
Y a-t-il une référence pour changer d'être "horriblement lent" en Java? Je n'ai jamais entendu ça.
Les changements ne doivent pas être plus lents en Java. Java a le iushr (non signé à droite) instruction Bytecode 0x7c , avec 2 arguments. Ceci devrait traduire 1: 1 à une instruction d'assemblage SHR sur n'importe quelle machine X86.
Les quarts de travail ne sont pas lents et de toute façon, le JIT reconnaît probablement le numéro de vue de l'analyse et la transforment en un petit nombre d'instructions qui effectuent la numérisation dans le matériel.
Je n'ai aucune idée si cela est plus rapide. Mais il n'a pas de boucle.
if(i==0) return -1;
highest=0;
if (i & 0xffff0000)
{
highest+=16;
i>>=16;
}
if (i & 0xff00)
{
highest+=8;
i>>=8;
}
if (i & 0xf0)
{
highest+=4;
i>>=4;
}
if (i & 0xC)
{
highest+=2;
i>>=2;
}
if (i & 0x2)
{
highest+=1;
}
return highest;
Java étant compilé dans le bytecode indépendant de la plate-forme, vous ne pouvez pas vous attendre à la prise en charge des instructions de la CPU. Sinon, votre code ou votre integer.highestonit () devrait être aussi rapide que possible.
Eh bien, je suis d'accord en principe, mais je pense que Java fait certaines choses à la plate-forme des moyens dépendants de la plate-forme (pour l'efficacité), mais ils retombent sur une implémentation Java si la plate-forme n'est pas coopérative. J'espérais que c'était l'un d'entre eux ...
Bien sûr, les JVMS sont spécifiques à la plate-forme, mais pour votre cas, le compilateur JIT devrait détecter votre véritable intention du bytecode, ce qui peut être difficile. Mais si la vitesse est de l'essence, vous pouvez envisager d'utiliser un assembleur indépendant de la plate-forme, c'est-à-dire une bibliothèque C et JNI.
Êtes-vous en cours d'exécution sur une grande machine Endian?
J'étais sous l'impression que Java a manipulé l'endianness à sa manière dans la JVM, mais en supposant que cela ne l'utilise pas, je vais utiliser un Intel C2D, si peu d'Endian.
Exécuter votre code, je reçois 0, pas 2.
Hors de curiosité: qu'essayez-vous de résoudre ce problème ne peut être résolu que par ce type de bidonville?
@uknown, mon code est en arrière, il trouve le bit de commande le plus bas. que ce soit élevé ou faible n'a pas d'importance. @Bart k, j'écris un bustif pour échecs. J'aimerais abandonner Java et le faire en C, mais j'ai beaucoup de code de réseau laid que je ne veux pas avoir à réécrire dans C.
Si vous êtes plus à l'aise de manipulation de bits en C, pourquoi ne pas utiliser JNI? De plus, si vous essayez d'obtenir tous les indeces «On», votre algorithme peut-être que votre algorithme ne bénéficie peut-être pas d'utiliser un champ de bit ... est un champ de bits vraiment la meilleure structure de données pour ce que vous faites?
Je ne savais pas que la manipulation des bits était si différente en Java. Qu'essayez-vous de faire cela que vous feriez facilement en C?
@ Twolfe18 Une approche que vous voudrez peut-être essayer est d'écrire votre application en Java. Lorsque cela fonctionne comme il le devait, vous optimisez, éventuellement en écrivant une partie des substances de niveau inférieures dans C utilisant JNI, comme suggéré Kevin Day. Aller offtopique; Robert Hyatt a écrit plusieurs belles articles sur les échecs du bus.
@uknown, c'est à peu près ce que je prévois de faire. En ce moment, j'ai une méthode pour trouver le plus haut ordre 1, et je pourrais le désactiver avec JNI plus tard.
Remarque: la surcharge JNI sera plus que de manger des microgailles que vous recevez de cette opération C unique.