Challenge : creer une ID unique a partir d'un couple unique d'ID.

Challenge : creer une ID unique a partir d'un couple unique d'ID. - Algo - Programmation

Marsh Posté le 27-03-2003 à 18:37:30    

Voila mon probleme :
 
J'ai une Id auquelle correspond une BBox.
l'Id correspond en fait a l'adresse memoire d'une structure.
La structure BBox contient les 4 coordonnees d'une BBox.
A partir de l'ID et de la BBox je veux construire une table de hash qui puisse detecter si on est sur la meme ID/BBox.
Je precise que bien sur chaque couple ID/BBox est unique.
Comment stocker ca dans une Hash, la contrainte etant que l'ID est un int, et que je dois stocker dans ma Hash un int egalement.

Reply

Marsh Posté le 27-03-2003 à 18:37:30   

Reply

Marsh Posté le 27-03-2003 à 18:41:59    

Quels sont les domaines de valeurs de ID et BBox ?


---------------
get amaroK plugin
Reply

Marsh Posté le 27-03-2003 à 18:55:41    

ID : int (adressage memoire sur 32 bits)
et int pour chaque coordonnee

Reply

Marsh Posté le 27-03-2003 à 19:09:58    

remarque c'est foireux mon truc, faut forcement du 64 bits pour tout stocker a priori :/

Reply

Marsh Posté le 27-03-2003 à 19:10:53    

joce a écrit :

ID : int (adressage memoire sur 32 bits)
et int pour chaque coordonnee


on peut avoir les bornes de tout le monde ?¿?

Reply

Marsh Posté le 27-03-2003 à 19:11:13    

ok, mais si Id peut prendre a priori toutes les valeurs disponibles  pour un int, alors c'est impossible !


---------------
get amaroK plugin
Reply

Marsh Posté le 27-03-2003 à 19:11:55    

nraynaud a écrit :


on peut avoir les bornes de tout le monde ?¿?


ha ba je suis pas le seul !¡!


---------------
get amaroK plugin
Reply

Marsh Posté le 27-03-2003 à 19:16:40    

bobuse a écrit :

ok, mais si Id peut prendre a priori toutes les valeurs disponibles  pour un int, alors c'est impossible !


si, mais il se démerde avec les collisions.

Reply

Marsh Posté le 27-03-2003 à 19:20:32    

bobuse a écrit :


ha ba je suis pas le seul !¡!

¿­­­¯-_¡

Reply

Marsh Posté le 27-03-2003 à 23:17:26    

et un binary tree?
 
l'id correspond a la decision suis-je dans l'espace pointé par
la normale codé en binaire?
 
Ceci dit la fonction de hachage est aussi rapide
que le parcours de l'arbre :D
 
LeGreg


---------------
voxel terrain render engine | animation mentor
Reply

Marsh Posté le 27-03-2003 à 23:17:26   

Reply

Marsh Posté le 28-03-2003 à 00:46:16    

legreg a écrit :

et un binary tree?
 
l'id correspond a la decision suis-je dans l'espace pointé par
la normale codé en binaire?
 
Ceci dit la fonction de hachage est aussi rapide
que le parcours de l'arbre :D
 
LeGreg

mon problème c'est une question de capacité de stockage :/

Reply

Marsh Posté le 28-03-2003 à 08:12:26    

CRC32 [:dawa]
 
(j'utilise ca a tout va, mais evidemment ca ne te garantira pas que plusieurs couple obtiennent le meme resultat)

Reply

Marsh Posté le 28-03-2003 à 09:42:42    

Sous quel OS ? Le pointeur, il pointe sur un objet de quelle taille ?


---------------
FAQ fclc++ - FAQ C++ - C++ FAQ Lite
Reply

Marsh Posté le 28-03-2003 à 10:08:10    

le code doit etre portable, pour l'instant c'est solaris.
sinon pour la bbox c'est une structure de 4 int

Reply

Marsh Posté le 28-03-2003 à 13:23:10    

Donc tu peux déjà diviser le pointeur par sizeof(ta_struct) ce qui te donne en quelque sorte un numéro de struct et non plus une adresse.
4 int = 16 octets.
Apres tu peux oser une optimisation, à toi de vérifier qu'elle est portable :
avant la première allocation d'objet, tu alloue un objet initial.
Son adresse va alors te servir de base, car les allocations futures vont se faire au dessus de cette adresse.
Donc, pour chaque pointeur, tu lui soustrait cette valeur et tu le divise par sizeof(ta_struct).


---------------
FAQ fclc++ - FAQ C++ - C++ FAQ Lite
Reply

Marsh Posté le 28-03-2003 à 13:34:45    

c'est pas con tout ca :o

Reply

Marsh Posté le 28-03-2003 à 15:04:11    

Juste pour info, c'est quoi une BBox ?
Et je comprend pas c'est quoi la 2° clé ? Le pointeur (qui est unique) ne te suffit pas ?


---------------
FAQ fclc++ - FAQ C++ - C++ FAQ Lite
Reply

Marsh Posté le 28-03-2003 à 15:04:51    

HelloWorld a écrit :

Juste pour info, c'est quoi une BBox ?
Et je comprend pas c'est quoi la 2° clé ? Le pointeur (qui est unique) ne te suffit pas ?


Bounding Box ?

Reply

Marsh Posté le 28-03-2003 à 15:11:22    

une bon vieux codage de gödel, appelé godelisation devrait faire l'affaire je pense ...
bien sur je ne sais pas ce que c'est qu'une bbox, mais bon...
[edit : maintenant je sais ..]
 
pour ceux qui ne connaisse pas http://www.brics.dk/RS/96/5/BRICS-RS-96-5.pdf, sinon vous pouvez me demander on vient juste de l'apprendre...
 
[edit ] sinon après reflexion, je suis sur que le numero de godel sera ton ami !!
En fait le principe c'est que avec ce truc, tu peux coder n'importe quelle sequence en un seul nombre et ce de manière unique, maintenant a toi d'implémenter l'algo, qui est tout con (au pire quelques exponentielles, et le calcul de quelques nombres premiers...)


Message édité par boubours le 28-03-2003 à 15:16:08

---------------
coming soon
Reply

Marsh Posté le 28-03-2003 à 15:15:11    

HelloWorld a écrit :

Juste pour info, c'est quoi une BBox ?
Et je comprend pas c'est quoi la 2° clé ? Le pointeur (qui est unique) ne te suffit pas ?

non
en fait j'ai une grosse structure qui contient entre autre une id et une bbox.
pour une meme id on peut avec deux bbox positionnees differemment.
(BBox c'est effectivement bounding box)

Reply

Marsh Posté le 28-03-2003 à 15:16:57    

une des contraintes egalement c'est qu'il faut que la manipulation soit tres rapide, donc algo tres simple :o

Reply

Marsh Posté le 28-03-2003 à 15:22:33    

Combien de bbox peux-tu avoir pour un meme id ?
Et connais-tu le nombre de bbox pour un id donné ?


---------------
FAQ fclc++ - FAQ C++ - C++ FAQ Lite
Reply

Marsh Posté le 28-03-2003 à 15:32:58    

HelloWorld a écrit :

Combien de bbox peux-tu avoir pour un meme id ?
Et connais-tu le nombre de bbox pour un id donné ?

non, ce parametre n'est pas connu, la structure contenant ces infos est mise a jour a chaque fois (pas de liste chainee ou de structure avec des infos par rapport a ca donc)


Message édité par joce le 28-03-2003 à 15:35:19
Reply

Marsh Posté le 28-03-2003 à 15:38:47    

joce a écrit :

une des contraintes egalement c'est qu'il faut que la manipulation soit tres rapide, donc algo tres simple :o


 
 


on code une liste (x,y) par  
(x,y)-> 2^x * 3^y = n
ex2(n)=x
ex3(n)=y


n est le codage unique de la liste (x,y) [c'est le numero de goedel]...
donc si tu trouves que c'est dur a faire, ben la je peux vraiment rien pour toi...
DSL bye


---------------
coming soon
Reply

Marsh Posté le 02-04-2003 à 09:27:52    

boubours a écrit :


 
 


on code une liste (x,y) par  
(x,y)-> 2^x * 3^y = n
ex2(n)=x
ex3(n)=y


n est le codage unique de la liste (x,y) [c'est le numero de goedel]...
donc si tu trouves que c'est dur a faire, ben la je peux vraiment rien pour toi...
DSL bye


si x et y sont des ints je doute que 2^x * 3^y soit stockable dans un int :D
Sinon je me serais pas emmerdé j'aurais concatené x et y et les paddant en préalable :D

Reply

Marsh Posté le 02-04-2003 à 09:30:23    

joce a écrit :


si x et y sont des ints je doute que 2^x * 3^y soit stockable dans un int :D


ben t'as qu'a stocker le résultat dans un registre du MMX [:sinclaire]
 
[:dehors2]


---------------
J'ai un string dans l'array (Paris Hilton)
Reply

Marsh Posté le 02-04-2003 à 09:44:05    

Harkonnen a écrit :


ben t'as qu'a stocker le résultat dans un registre du MMX [:sinclaire]
 
[:dehors2]

il est ou le registre du MMX sur mon processor SPARC ? :D

Reply

Marsh Posté le 02-04-2003 à 09:46:24    

joce a écrit :

il est ou le registre du MMX sur mon processor SPARC ? :D

ils font quelle taille les registres du SPARC ?


---------------
J'ai un string dans l'array (Paris Hilton)
Reply

Marsh Posté le 02-04-2003 à 09:59:33    

HotShot a écrit :

Si t'as un couple d'ID c'est que tu t'y es mal pris. Utilise class="" à la place.

ouais mais non j'ai des problemes avec le javascript apres

Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed