J'ai appris récemment de Morton coding (Z-order curve) comme une fonction d'appariement de bits. Il m'a été présenté comme un moyen plus rapide de comparer des nombres par rapport au Cantor pairing function. Le fonctionnement du codage de Morton consiste à combiner deux nombres en intercalant leurs bits et en stockant le résultat dans un type de données plus large. Par exemple, entrelacez les bits de deux entiers de 8 bits et stockez le résultat sous la forme d'un entier de 16 bits. Pourquoi voudriez-vous entrelacer les bits au lieu de diviser les deux nombres entre les bits haut et bas du type de données cible? Je m'attendais à utiliser des bits hauts et bas pour être encore plus rapide. Quand pourrait-il y avoir un avantage à les entrelacer?Pourquoi associer des nombres en utilisant l'entrelacement de bits au lieu de les séparer par des bits hauts et bas?
Répondre
Comme la fonction d'appariement de Cantor, et contrairement à la concaténation, il ne place pas de lien a priori sur les coordonnées. En d'autres termes, le codage de Morton peut également être formulé pour des entiers de longueur arbitraire. Ce n'est pas vraiment le cas pour la concaténation, car si tout peut être concaténé, le résultat serait ambigu et son interprétation dépendrait de la taille originale des coordonnées. Les tailles de toutes les dimensions sauf une doivent être fixées pour éviter toute ambiguïté.
Si elle est utilisée dans un contexte où il y a une limite a priori et où la localité n'est pas un problème, la concaténation est évidemment une option encore plus simple.
Cependant, la localisation est un avantage couramment utilisé. Deux coordonnées qui sont à proximité sont principalement mappées relativement proche en termes de leurs valeurs Z. La courbe de Hilbert fonctionne encore mieux à cet effet, mais est plus difficile à encoder, décoder et décaler (et comme la concaténation, elle dépend aussi de la taille de l'espace qui doit être fixée à l'avance). Les coordonnées concaténées préservent la localité dans une seule dimension (mais très bien) et pas dans l'autre (s), mais sont les plus faciles à encoder/décoder/décaler (quand ces choses sont possibles, ce qui signifie que la taille de toutes les dimensions doit être être prédéterminé).