Nous avons toujours l’habitude de donner des numéros uniques à des objets pour les identifier. Et cette règle est encore plus présente dans le développement logiciel. Ce que nous appelons communément Id. Nous utilisons souvent des Int (entier codés sur 4 octets sur la plupart des processeurs) ou encore des long quand nous avons de nombreux objets à identifier et que Int ne nous donne pas la précision nécessaire. Ainsi le premier objet prend l’Id n1, le second l’Id n2 ect.
Certaines personnes utilisent des couleurs pour différencier leur objet dans le développement d’applications visuelles; l’objet rouge, jaune ou gris par exemple. La combinaison RVB (Rouge, Vert, Bleu) a fait ces preuves vu sa popularité… On utilise souvent une graduation sur 1 octet (8bits) pour chacun des composants. Ainsi la couleur {255, 0, 0} est du rouge foncé et {100, 100, 100} du gris moyennement clair. On peut avoir donc exactement 256*256*256 couleurs soit 16 777 216 couleurs différentes pour une graduation sur 8bits. Pour plus d’informations sur le RVB
Il peut y arriver que dans votre super-application vous ayez besoin d’une relation bijective entre votre Id et la couleur de l’objet. En d’autres termes vous aimeriez pouvoir convertir votre Id en couleur RVB et votre couleur en Id de façon unique. Ne me parlez pas d’une simple addition des valeurs de chaque composant RVB car l’application n’est pas ainsi bijective. En effet {255, 45, 0} et {100, 100, 100} ont tous deux la même somme.
Nous voulons donc construire une bijection entre l’ensemble fini des entiers
{1, 2, 3… 100, 101,…16 777 216} et l’ensemble fini des couleurs (graduation sur 8bits pour chaque composant). La solution proposée doit être sous forme de 2 d’algorithmes. Le premier algorithme doit renvoyer une couleur unique en prenant en entrée un entier compris entre [1, 16 777 216], et le second doit faire l’opération inverse.
J’attends vos propositions de solutions. Vous pouvez la publier en tant que commentaire a cet post. La solution sera fourni la semaine prochaine !!!
Romain a dit
Il suffit de faire la conversion en binaire et de retirer 1 si tu part de l’ID ou d’ajouter 1 si tu part de la couleur … Et ensuite tu refait ta conversion binaire => entier ou binaire => couleur ….
erickedji a dit
On peut considérer le problème comme une conversion entre la base 10 et la base 256, avec un décalage (pour passer de l’intervalle [0, 16777215] à [1, 16777215]). Soit en pseudo-code/python:
def int2rvb(n):
n = n – 1 # normaliser
b = n % 256
v = (n % (256**2)) / 256
r = (n % (256**3)) / 256**2
return (r, v, b)
def rvb2int(r, v, b):
return r*(256**2) + v*256 + b + 1
Prudence est mère de sureté
:
for i in range(1, 16777217):
(r, v, b) = int2rvb(i)
if (i != rvb2int(r, v, b)):
print “Aïe!”
Une dernière chose, si je trouve un code comme int2rvb chez un programmeur, j’appele maître “Hong Shan Optimisation” pour lui filer une bonne fessée (lol)
erickedji a dit
Oulala! WordPress a complètement détruit l’identation dans le code, ce qui va enrager l’interprêtateur python
Voir ici pour une version correctement indentée: http://gist.github.com/98950
ktangao a dit
J’adore la simplicité de Romain et la force de frappe d’Eric. Cependant, toujours pas de solution valable.
@Romain faut 2 algorithmes…
@Eric je prends juste un exemple pour desavouer ta proposition
pour n=3, la fonction Int2rvb retourne: (3.0517578125e-05, 0.0078125, 2) … Ce qui n’est pas une valeur (r,v,b) correcte… De la rigueur SVP … lol
erickedji a dit
Aïe! t’as raison Khaled, mon algorithme quick-n-dirty compte sur la division entière que fait l’opérateur ‘/’ dans python. Il faut plutôt (dans int2rvb):
n = n – 1 # normaliser
b = n % 256
v = ((n – b) % (256**2)) / 256
r = ((n – v – b) % (256**3)) / 256**2
Heureusement que Dijkstra n’est pas dans les parages, il m’aurait donné une bonne fessée
ktangao a dit
Beaucoup mieux Eric… Il faut avouer que la première proposition n’était pas vraiment une bijection (j’ai obtenu 16777216 Aie dans mon interpréteur
)…
Cependant 2/3 ne retourne pas 0 dans mon Shell… Et sérieusement Dijkstra trouvera plus optimum comme algo lol…
erickedji a dit
Ah sacré Khaled!
S’il faut un algorithme optimum, j’imagine qu’on doit pouvoir faire plus que la factorisation des constates (256**2, etc).
Le temps d’arriver à la maison et je sort une armée de shifts et de XORs pour voir ce que ça va donner, surtout que ça sent les puissances de 2 à plein nez
catwell a dit
Petite solution C : http://friendpaste.com/3Z9plfQVWhSOy7Ga0WCpM8
Mais c’est quand même un choix discutable de prendre [[1,16777216] comme ensemble et pas [[0,16777215]] (qui simplifierait quelques passages…).
ktangao a dit
Je trouve la proposition de Catwell impeccable… S’il faut oublier le fait qu’un commentaire commence par // (ooops ça a été corriger dans la nouvelle version) en C
et que la fonction atoi() se trouve dans l’entête stdlib.h et aussi la valeur s de début qui ne sert à rien hehe… Voila, plus besoin d’attendre la semaine prochaine pour avoir une solution optimale lol…
Il faut noter que les décalages binaires sont beaucoup plus efficaces que les divisions ce qui fait de la dernière proposition la meilleure. Mais l’idée y est dans toutes les propositions et merci d’avoir jouer le jeu.
Cette technique est l’une des méthodes utilisée pour sélectionner les composants dans les applications OpenGl. La terminologie utilisée pour ces couleurs est pickingColor. http://gpwiki.org/index.php/OpenGL_Selection_Using_Unique_Color_IDs
erickedji a dit
@ Catwell: bravo, je m’incline!
Utiliser des shifts pour la multiplication, et exploiter le fait qu’un un unsigned char tient sur 8 bits donne une solution optimale. Et puis comme ont dit, “real men code in C”
@Khaled:
Si la lisibilité du code est en jeu, il est préférable d’éviter de remplacer les multiplications/divisions par des puissances de 2 par des shifts. Les compilateurs modernes savent le faire, sans qu’on soit obligé de masquer quelque peu l’intention du code. Jette un coup d’oeil ici: http://www.strchr.com/what_your_compiler_can_do_for_you
Fais pas trop attention à mon “premature optimization is the root of all evils” sur twitter. Vu que tu travailles avec du code très low-level qui doit tourner le plus vite possible, tu as tout intérêt à exploiter les manipulations de bits. Le travail de Hsieh (http://www.azillionmonkeys.com/qed/optimize.html) et surtout le très célèbre “Bit twiddling hacks” (http://graphics.stanford.edu/~seander/bithacks.html) sont utiles, quand le compilateur atteint ses limites.
@bientôt.
ktangao a dit
Une dernière chose pou les lecteurs, j’ajouterai a la suite des commentaires les sites web qui traitent de la manipulation binaire… Juste pour avoir une référence rapide.
1- http://www.azillionmonkeys.com/qed/optimize.html
2- http://graphics.stanford.edu/~seander/bithacks.html
3- http://bits.stephan-brumme.com/
4- http://jheriko-rtw.blogspot.com/2009/04/understanding-and-improving-fast.html
catwell a dit
Même algorithmiquement je trouve ça plus simple de raisonner sur les décallages de bits. C’est trois paquets de huit bits qu’on colle l’un à côté de l’autre en mémoire… Pas besoin de passer par des maths pour ça.
Je sais bien que le compilateur optimise tout ça, mais quand on veut faire une multiplication par 4, on écrit a*=4, et quand on veut faire du zéro-padding ou un truc du genre on écrit a<<=2, ça me semble logique
D’ailleurs je trouve dommage que Python ne sache pas bien gérer ce genre de choses. Je sais bien que ça ne colle pas avec sa philosophie mais avoir des structures de données du genre bitset peut être utile parfois, même pour du prototypage. Je préfère coder en Python qu’en C, d’habitude !
erickedji a dit
@Catwell
T’as parfaitement raison. Je ne sais plus où j’ai lu que les abstractions ne sont utiles que si l’on sait ce que l’on est en train d’abstraire.
Sur l’exemple de Khaled, utiliser Python m’a fait penser au niveau des valeurs entières, et pas au niveau des paquets de bits. Résultat: je manque la solution élégante qui s’appuie sur le constat que l’entier correspondant à une valeur RGB est juste, en mémoire, la juxtaposition des trois valeurs.
C’est rafraichissant de parler avec des informaticiens qui savent ce qu’ils disent. Au passage, si tu rencontres Sussman, demande lui un autographe pour moi
Il m’a illuminé avec SICP, et c’est avec regret que j’ai appris que Scheme a été remplacé. Heureusement que le remplaçant est Python, et pas (je vais déclencher un flamewar) … Java!
catwell a dit
J’aurais du mal à rencontrer Sussman, je ne suis pas au MIT mais à Télécom Bretagne actuellement, et à Cranfield (UK) l’an prochain