GUID : Fallait mieux travaille a l'ecole

Dev
1

Bon, vue que j’ai (presque) pas fait d’etude… y a un certain nombre de choses que je ne sais pas faire…

… comme par example le problem suivant :
je doit generer des identifiant uniques, pour tout une series d’objets :
contraintes :

  • je veux que mon ID tienne sur 32 bit (64bit accepter si vraiment vraiment y a pas mieux)
  • je veux pouvoir regenere l’ID a partir de l’objet a la vole, et que quelque soit la plateform, l’heure, l’ordre d’execution ou quoi que ce soit d’autre : et que ce soit toujours la meme ID.
  • et plus rigolo (mais ca c’est bonus ) : je voudrais pouvoir regenere l’objet en fonctions de son ID

(et quand je dis “objet”, je parle du type de l’objet, pas de son contenu, donc le premier qui me dit fait une hashtable/checksum sur les donnees s’en prends une, et j’utiliserais les mains de Titan ! )

j’oubliais : je ne peux pas m’appuyer sur l’OS, donc pas de : “ha mais oui, dans linux tu as un service…” ni de “bah utilise le GUID toolkit du framework windows” merci.

[Edit j’ai oublie un truc]
Ce message a été édité par c0unt0 le 05/08/2003

2

Interessant comme probleme, mais moi, je suis nul en objet.

Maintenant, quelques question quand meme:

Est ce que tu veux un systeme de ce type:

id_object=retrieve_id_object(objet);

Ou un truc memotechnique (donc qui n’est pas en runtime)?

Perso, je pense pour un systeme runtime. En gros, tu recois un objet
mais tu ne sais pas ce que c’est.

De la meme maniere, tu a l’ID de l’objet, et il faut un creer un.

Pour la creation de l’objet, je vois pas ou est le probleme: un select
case par rapport a l’ID (bourrin) et ca marche. Evidement, si t’as 100
objets, ca va etre galere

Pour l’identification, j’avoue que je vois pas trop: C’est trop
dangereux de se baser sur la taille. Y a pas moyen de recuperer le type
d’un objet en C++? (genre ident_object(void object))

Personnelement, je ferais un truc comme ca (je sais pas si c’est
possible en objet):

struct objet1 {

  int id;

  [… def de l’objet…]

}

Je sais que les sizeof(int) premiers octets de l’objet sont
l’identifiant, je peux le recuperer facilement.

Ouais, acces direct a la memoire, c’est mal, en objet… ^_^;;

En esperant que mes delires aident ceux a meme de t’aider

LoneWolf

Bon, ca doit pas marcher, mon truc ;_;

3

oui mais :

  • je ne suis pas en c++, mais en C !
    on pourrait dire que je fait de la programmation oriente object, mais en C.
    le principe, c’est que je peux loader ou creer tout plein d’object, avec tout plein de donnees dedans :
    ce que je fait c’est
objecttype = createtype(); AddType(objecttype,properties1); AddType(objecttype,properties2);
puis je fait :
object = creeObject(objecttype); saveObject(object);
tout les type d'object sont stocker dans une bibliotheque. Au chargement je voudrais pouvoir verifier si le type est deja declare, si oui, je l'utilise, sinon je creer un nouveau type.. J'ai un nombre de types d'objets potentiels quasi-ilimite,et non previsible : donc je ne peux pas faire de switch de barbare ! ce que je cherche c'est un moyen de genere un identifiant unique durant la creation du type, et qui soit unique de chez uniques !
4

Alors je récapitule pour mes neuronnes fatigués.

En gros tu veux pouvoir associer un ID unique à des types de données que tu créé à la volée. Sachant que si tu créés un même type (meme propriétés à l’interieur) tu veux qu’il est le même ID … j’ai bon ?

Juste une question, c’est quoi une propriété pour toi ? Un nom, un type et une valeur ? Ou juste un nom et une valeur (pas de typage) ?

vu que je suis pas sur d’avoir bien compris le problème je ne m’aventurerais pas plus loin pour l’instant …

5

une “propriete” ca peut etre : un ““nom”” (bon dans la vrais vie c’est une ID 32bit : mais on peut considere ca comme un nom : c’est unique par propriete), accompagne d’un type (qui peut avoir une taille nulle)

6

[quote]ce que je fait c’est

objecttype = createtype(); AddType(objecttype,properties1); AddType(objecttype,properties2);
[/quote] J'ai bien une idee, mais j'ai une question avant: Est ce que le nombre de proprietes est fixe?

LoneWolf

Ca peut le faire. J’espere

7

hey hey… trop facile :
il peut varier entre 0 et n : 0 etant juste l’objet de base, n etant l’objet avec toute ces proprietes…
et un autre petit detail : je ne connais aucune des proprietes a l’avance : certaine n’existe pas encore

8

On recapitule:

_Les objets sont un ensemble de proprietes, qui doivent etre generable
en runtime, et surtout, identifiable uniquement.

_Les proprietes sont elle aussi generables a la volee.

J’ai bien une idee simple, mais ca limite le nombre de proprietes au
nombre de bits de l’identifiant: genre:

propriete 1

propriete 2

propriete 4

propriete 8

Du coup, un OU binaire et tu as ton identifiant.

Ca serait plus facile si les proprietes etaient fixes des le depart

LoneWolf

Petit joueur sur ce coup la

9

Pas mal, mais 32 proprietes : c’est pas assez… on peut facilement monte a plus, voir meme il n’y a pas de limites aux nombre de proprietes, (pour le moment on en compte 68… et ca continue a monte…) (et puis celui la je l’ai deja fait ailleurs )

10

ok, c0unt0, plan B:

chaque propriete est numerote de 1 a n, et n est incremente a chaque
creation. Donc, pour un objet, on a un truc:

Objet foo:

propriete 6

propriete 18

propriete 1

propriete 25

A la creation, tu genere une chaine de ce type: 6_18_1_25 et tu la
balance dans un machin genre MD5, qui va te creer un identifiant unique.

Pour moi, y a 2 problemes:

_Le cout du MD5

_C’est sensible a l’ordre des proprietes.

D’un autre cote, je ne vois pas de solution simple: j’espere que mes
delires t’aideront a trouver une solution

Ah, je la veux bien, la solution

LoneWolf

C’est sympa de se remuer les neurones, des fois.

11

Huhu vous vous debattez un peu sur un des problemes ultimes de l’info

Creer une fonction de Hash parfaite c’est pas facile et la litterature sur le sujet est plus qu’abondante. Une petite recherche google devrait t’eclairer sur le sujet.

Maintenant il y a pas de “recette” miracle, en general la fonction de hash pour pas sombrer dans des trucs ultra trop lents est a customizer en fonction des donees, c’est pour ca que sur chaque objet en C# ou en Java par exemple il y a une fonction GetHashCode()… qui est censee faire ce que tu decris. La beautee de l’objet bien sur c’est que le systeme est generique et extensible, t’as pas besoin de savoir a priori le type de tes objets et comment ils vont calculer leur propre fonction de hash pour que ca marche.

Enfin c’est beau Apres tu les mets dans une hashtable et hop t’as des lookup d’objets super rapide.

Tout depend aussi de ce que tu as besoin d’identifier uniquement. Si c’est une instance d’un objet, son hashcode peut etre simplement son emplacement memoire (c’est d’ailleurs en general l’implementation de base de GetHashCode sur Object en C# ou en Java). Si un objet est rendu unique par l’ensemble de toutes ses proprietes c’est plus complique mais on peut s’en sortir par type de proprietes MD5 est une belle fonction de hash mais c’est une fonction de hash cryptographique, ca rajoute toute une complexite dont t’as pas besoin. Si t’as besoin de plus de details pour t’en sortir je peux aller plus loin mais je suis pas super pointu en fonction de hash non plus 

Ce message a été édité par GloP le 05/08/2003

12

Alors alors, ça va être assez chaud. Tu as un pool de n (68 actuellement) propriétés, donc le nombre de types possibles est de 2^n (2^68 ici). Par conséquent, théoriquement, il te faut n bits (68 bits) pour être assuré d’avoir un GUID en bonne et due forme. Le gros problème, c’est que tu ne veux que 32 bits [exigence 1], et qu’en plus, n>>68. Bien sûr, dans les cas usuels, tes 2^n types théoriques sont loin d’être tous utilisés. D’habitude, on incrémente sans se prendre la tête, ou bien on chope l’emplacement mémoire, mais tu veux un GUID sophistiqué : c’est même un vrai hash en fait (cf [exigence 2]). Laissons donc le bonus [option 3] de côté pour l’instant en attendant des précisions car la génération inverse en fonction du GUID avec les données qu’on connaît, ben c’est chaud (rien que choper les 68 premières propriétés à partir des 32 bits).
 
Bref, il va falloir que tu nous en donnes un peu plus, entre autres,

  • les ordres de grandeur du nombre total de propriétés
      (par ex. n<~2^7=128, n<~2^10=1024, ou n<~2^14=16384) 
    et du nombre de propriétés maximal que peut posséder un type
      (par ex. pas plus de 2^7=128 propriétés à la fois),
    - si beaucoup de propriétés sont incompatibles,
      (par ex. les propriétés des reptiles et des oiseaux)
    - si les propriétés peuvent être rassemblées en familles non équiprobables (avec une répartition grossière à se mettre sous la dent),…
     
    Euh, quand je me relis, finalement c’est en gros :

[quote]Maintenant, il n’y a pas de “recette” miracle, en général la fonction de hash pour pas sombrer dans des trucs ultra trop lents est à customizer en fonction des données…[/quote]Comme quoi, le hash, ça fait pas toujours rire…

Ce message a été édité par xentyr le 06/08/2003

13

Question con:

la création de types est obligatoire ?

Je demande parce qu’étant donnée qu’il n’existe pas de solution miracle
pour le hash (et qu’en plus j’imagine que le prog dois tourner vite),
le mieux serait sans dout de se passer de types. Maintenant si ils sont
indispensables, et pour reprendre ce que disait Xentyr, soit tu as une
ID de n bits (pour n propriétés existantes), soit tu vas avoir besoin
d’une table de correspondance type-ID, et là bonjour les temps de
parcours et de maintenance de la table en question.

Si ce n’est pas indiscret, tu utilises les types pour quels opérations ?
Ce message a été édité par Twin le 06/08/2003

14

bon merci les gens, a l’arrive je vais faire un mix entre une table de hash, base sur les id des proprietes : genre si j’ai les propriete 12,120 et 33 (que je limite a un maximum de 255 proprietes differentes en multiplexe : cad avec une categorie + une propriete, parce que bon, faudrait voir a pas me faire ch*** non plus )

unsigned char futurehash[3]= {12,33,120};

que je hash, sachant que je trie par IDs…
et pis ca ira bien

(sinon oui j’en ai besoin, mais ca je vous dirais pas pourquoi )
[edit]
je ne fait pas de reconstruction base sur l’uid, et je teste sur la taille global de mon object en plus du GUID, pour plus de securite !

en tout cas merci a tous : ca ma aide a reflechir, meme si j’en arrivait souvent aux meme conclusion que vous genre moins de 5 secondes avant de passer sur cafzone pour verifier ce qui se passe
Ce message a été édité par c0unt0 le 06/08/2003