Bonsoir.
Je cherche à optimiser une (pas si) bête opération de recherche de bit dans
un nombre entier.
C'est trivial à faire avec une boucle de décalage, mais c'est précisément ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).
La structure du nombre/bitfield est la suivante, de droite (LSbit) à gauche
(MSbit):
- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.
Exemple:
...001101001111111
Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7
Un sous-problème peut être d'éliminer les 1 de la partie gauche...
Je n'ai pas encore trouvé de formule fiable. Avez-vous une idée ?
Bonsoir.
Je cherche à optimiser une (pas si) bête opération de recherche de bit dans
un nombre entier.
C'est trivial à faire avec une boucle de décalage, mais c'est précisément ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).
La structure du nombre/bitfield est la suivante, de droite (LSbit) à gauche
(MSbit):
- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.
Exemple:
...001101001111111
Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7
Un sous-problème peut être d'éliminer les 1 de la partie gauche...
Je n'ai pas encore trouvé de formule fiable. Avez-vous une idée ?
Bonsoir.
Je cherche à optimiser une (pas si) bête opération de recherche de bit dans
un nombre entier.
C'est trivial à faire avec une boucle de décalage, mais c'est précisément ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).
La structure du nombre/bitfield est la suivante, de droite (LSbit) à gauche
(MSbit):
- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.
Exemple:
...001101001111111
Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7
Un sous-problème peut être d'éliminer les 1 de la partie gauche...
Je n'ai pas encore trouvé de formule fiable. Avez-vous une idée ?
Je cherche à optimiser une (pas si) bête opération de recherche de
bit dans un nombre entier.
Je cherche à optimiser une (pas si) bête opération de recherche de
bit dans un nombre entier.
Je cherche à optimiser une (pas si) bête opération de recherche de
bit dans un nombre entier.
Sinon, c'est plus simple de les enlever que de les compter:
int remove_ones_on_right(int bitfield){
/*
0101011111111
+1 0101100000000
xor 0000111111111
shift 0000011111111
- 0101000000000
*/
assert(bitfield>0);
return(bitfield-((bitfield^(bitfield+1))>>1));
}
0101011111111
+1 0101100000000
xor 0000111111111
shift 0000011111111
- 0101000000000
*/
assert(trame>0);
Sinon, c'est plus simple de les enlever que de les compter:
int remove_ones_on_right(int bitfield){
/*
0101011111111
+1 0101100000000
xor 0000111111111
shift 0000011111111
- 0101000000000
*/
assert(bitfield>0);
return(bitfield-((bitfield^(bitfield+1))>>1));
}
0101011111111
+1 0101100000000
xor 0000111111111
shift 0000011111111
- 0101000000000
*/
assert(trame>0);
Sinon, c'est plus simple de les enlever que de les compter:
int remove_ones_on_right(int bitfield){
/*
0101011111111
+1 0101100000000
xor 0000111111111
shift 0000011111111
- 0101000000000
*/
assert(bitfield>0);
return(bitfield-((bitfield^(bitfield+1))>>1));
}
0101011111111
+1 0101100000000
xor 0000111111111
shift 0000011111111
- 0101000000000
*/
assert(trame>0);
Bonsoir.
Je cherche à optimiser une (pas si) bête opération de recherche de bit dans
un nombre entier.
C'est trivial à faire avec une boucle de décalage, mais c'est précisément ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).
La structure du nombre/bitfield est la suivante, de droite (LSbit) à gauche
(MSbit):
- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.
Exemple:
...001101001111111
Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7
Un sous-problème peut être d'éliminer les 1 de la partie gauche...
Je n'ai pas encore trouvé de formule fiable. Avez-vous une idée ?
Bonsoir.
Je cherche à optimiser une (pas si) bête opération de recherche de bit dans
un nombre entier.
C'est trivial à faire avec une boucle de décalage, mais c'est précisément ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).
La structure du nombre/bitfield est la suivante, de droite (LSbit) à gauche
(MSbit):
- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.
Exemple:
...001101001111111
Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7
Un sous-problème peut être d'éliminer les 1 de la partie gauche...
Je n'ai pas encore trouvé de formule fiable. Avez-vous une idée ?
Bonsoir.
Je cherche à optimiser une (pas si) bête opération de recherche de bit dans
un nombre entier.
C'est trivial à faire avec une boucle de décalage, mais c'est précisément ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).
La structure du nombre/bitfield est la suivante, de droite (LSbit) à gauche
(MSbit):
- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.
Exemple:
...001101001111111
Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7
Un sous-problème peut être d'éliminer les 1 de la partie gauche...
Je n'ai pas encore trouvé de formule fiable. Avez-vous une idée ?
Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.
Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.
Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.
Je cherche à optimiser une (pas si) bête opération de recherche de bit
dans
un nombre entier.
C'est trivial à faire avec une boucle de décalage, mais c'est précisément
ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).
La structure du nombre/bitfield est la suivante, de droite (LSbit) à
gauche
(MSbit):
- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.
Exemple:
...001101001111111
Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7
Je cherche à optimiser une (pas si) bête opération de recherche de bit
dans
un nombre entier.
C'est trivial à faire avec une boucle de décalage, mais c'est précisément
ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).
La structure du nombre/bitfield est la suivante, de droite (LSbit) à
gauche
(MSbit):
- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.
Exemple:
...001101001111111
Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7
Je cherche à optimiser une (pas si) bête opération de recherche de bit
dans
un nombre entier.
C'est trivial à faire avec une boucle de décalage, mais c'est précisément
ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).
La structure du nombre/bitfield est la suivante, de droite (LSbit) à
gauche
(MSbit):
- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.
Exemple:
...001101001111111
Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7
En news:f36acg$tkk$, Laurent Deniau écrivit:Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.
Mon idée (mais je n'ai pas testé) c'est que ce switch est plein, donc le
compilateur va le remplacer par un goto calculé, en principe plus rapide
qu'une cascade de 3 tests.
Après, c'est une optimisation temps contre espace, cache localité etc. et
pour savoir à quel niveau il faut mettre la barre je ne suis pas partant
pour rentrer dans le détail... (et en plus j'ai vaguement l'idée que les
résultats dépendent des données et de la babasse).
En news:f36acg$tkk$1@cernne03.cern.ch, Laurent Deniau écrivit:
Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.
Mon idée (mais je n'ai pas testé) c'est que ce switch est plein, donc le
compilateur va le remplacer par un goto calculé, en principe plus rapide
qu'une cascade de 3 tests.
Après, c'est une optimisation temps contre espace, cache localité etc. et
pour savoir à quel niveau il faut mettre la barre je ne suis pas partant
pour rentrer dans le détail... (et en plus j'ai vaguement l'idée que les
résultats dépendent des données et de la babasse).
En news:f36acg$tkk$, Laurent Deniau écrivit:Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.
Mon idée (mais je n'ai pas testé) c'est que ce switch est plein, donc le
compilateur va le remplacer par un goto calculé, en principe plus rapide
qu'une cascade de 3 tests.
Après, c'est une optimisation temps contre espace, cache localité etc. et
pour savoir à quel niveau il faut mettre la barre je ne suis pas partant
pour rentrer dans le détail... (et en plus j'ai vaguement l'idée que les
résultats dépendent des données et de la babasse).
Pour les curieux, en voici deux variantes lisibles :
int bitcount1(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);
x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);
x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);
return x;
}
int bitcount2(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0x70707070) >> 4) + (x & 0x07070707);
x = ((x & 0x0F000F00) >> 8) + (x & 0x000F000F);
x = (x >> 16) + (x & 0x0000001F);
return x;
}
Pour les curieux, en voici deux variantes lisibles :
int bitcount1(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);
x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);
x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);
return x;
}
int bitcount2(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0x70707070) >> 4) + (x & 0x07070707);
x = ((x & 0x0F000F00) >> 8) + (x & 0x000F000F);
x = (x >> 16) + (x & 0x0000001F);
return x;
}
Pour les curieux, en voici deux variantes lisibles :
int bitcount1(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);
x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);
x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);
return x;
}
int bitcount2(unsigned x) {
x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
x = ((x & 0x70707070) >> 4) + (x & 0x07070707);
x = ((x & 0x0F000F00) >> 8) + (x & 0x000F000F);
x = (x >> 16) + (x & 0x0000001F);
return x;
}
Bonsoir.
"Patrick 'Zener' Brunet" a écrit dans
le message news: f34nr2$oi5$Je cherche à optimiser une (pas si) bête opération de recherche de bit
dansun nombre entier.
C'est trivial à faire avec une boucle de décalage, mais c'est précisément
ceque j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).
La structure du nombre/bitfield est la suivante, de droite (LSbit) à
gauche(MSbit):
- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.
Exemple:
...001101001111111
Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7
Enchanté que cela vous ait intéressé, et merci pour toutes ces idées.
Je crois que c'est Pascal Bourguignon qui a donné le déclic, par rapport à
mon besoin spécifique bien sûr, avec le +1 (dire que j'avais essayé avec la
négation et le Xor !).
En fait, par rapport à mon besoin, je pense pouvoir me passer ainsi du
comptage, et atteindre directement le résultat voulu.
Voilà à quoi ça sert:
______________________
Je développe une classe C++ d'arbres combinant de multiples possibilités, et
que je vais utiliser dans un projet de compilateur (donc gros volume de
données + impératif de performances + divers trucs à moi...).
Cet arbre doit être navigable de toutes les manières possibles, et la
solution naïve implique 5 pointeurs de chaînage par noeud, donc déjà 20
octets sans la charge utile, ce qui est prohibitif.
D'où l'idée de représenter l'arbre comme binaire, afin d'utiliser une
représentation en tableau, sans aucun pointeur. Evidemment l'arbre est non
balancé, et donc le tableau sera creux, mais j'ai une solution en vue pour
çà.
Donc ça donne (passer en fonte à pas fixe):
|
A-
|
|
B--C--D--E-
| | | |
| |
| J--K--L-
| | | |
|
F--G--H--I-
| | | |
A = 1
Down(i) = 2.i
Right(i) = 2.i + 1
Et le pattern binaire du problème est la forme générale d'une valeur
Right(i).
Si on lui applique la formule suivante:
Up(i) = i / ((i ^ (i + 1)) + 1) ^ est le Xor et / la division entière
On atteint directement son parent, sans aucune itération.
La formule est valide aussi pour les premiers descendants.
Et pour atteindre le Nème descendant, on a:
Child(i,n) = (i << n) | ((1 << (n - 1)) - 1) | est le Or inclusif
Finalement, le comptage de bits pourrait permettre à un noeud descendant de
connaître son rang, mais je ne pense pas en avoir besoin.
Toutefois je salue le BITCOUNT(x) que je ne connaissais pas (je suis très
autodidacte en informatique).
Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester
virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)
Bonsoir.
"Patrick 'Zener' Brunet" <use.link.in.signature@ddress.invalid> a écrit dans
le message news: f34nr2$oi5$1@shakotay.alphanet.ch...
Je cherche à optimiser une (pas si) bête opération de recherche de bit
dans
un nombre entier.
C'est trivial à faire avec une boucle de décalage, mais c'est précisément
ce
que j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).
La structure du nombre/bitfield est la suivante, de droite (LSbit) à
gauche
(MSbit):
- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.
Exemple:
...001101001111111
Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7
Enchanté que cela vous ait intéressé, et merci pour toutes ces idées.
Je crois que c'est Pascal Bourguignon qui a donné le déclic, par rapport à
mon besoin spécifique bien sûr, avec le +1 (dire que j'avais essayé avec la
négation et le Xor !).
En fait, par rapport à mon besoin, je pense pouvoir me passer ainsi du
comptage, et atteindre directement le résultat voulu.
Voilà à quoi ça sert:
______________________
Je développe une classe C++ d'arbres combinant de multiples possibilités, et
que je vais utiliser dans un projet de compilateur (donc gros volume de
données + impératif de performances + divers trucs à moi...).
Cet arbre doit être navigable de toutes les manières possibles, et la
solution naïve implique 5 pointeurs de chaînage par noeud, donc déjà 20
octets sans la charge utile, ce qui est prohibitif.
D'où l'idée de représenter l'arbre comme binaire, afin d'utiliser une
représentation en tableau, sans aucun pointeur. Evidemment l'arbre est non
balancé, et donc le tableau sera creux, mais j'ai une solution en vue pour
çà.
Donc ça donne (passer en fonte à pas fixe):
|
A-
|
|
B--C--D--E-
| | | |
| |
| J--K--L-
| | | |
|
F--G--H--I-
| | | |
A = 1
Down(i) = 2.i
Right(i) = 2.i + 1
Et le pattern binaire du problème est la forme générale d'une valeur
Right(i).
Si on lui applique la formule suivante:
Up(i) = i / ((i ^ (i + 1)) + 1) ^ est le Xor et / la division entière
On atteint directement son parent, sans aucune itération.
La formule est valide aussi pour les premiers descendants.
Et pour atteindre le Nème descendant, on a:
Child(i,n) = (i << n) | ((1 << (n - 1)) - 1) | est le Or inclusif
Finalement, le comptage de bits pourrait permettre à un noeud descendant de
connaître son rang, mais je ne pense pas en avoir besoin.
Toutefois je salue le BITCOUNT(x) que je ne connaissais pas (je suis très
autodidacte en informatique).
Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester
virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)
Bonsoir.
"Patrick 'Zener' Brunet" a écrit dans
le message news: f34nr2$oi5$Je cherche à optimiser une (pas si) bête opération de recherche de bit
dansun nombre entier.
C'est trivial à faire avec une boucle de décalage, mais c'est précisément
ceque j'espère éviter, au profit d'une formule astucieuse utilisant les
opérateurs de base de C: arithmétiques, binaires et logiques (a priori le
pattern tiendra sur 32 bits, donc dans un entier machine).
La structure du nombre/bitfield est la suivante, de droite (LSbit) à
gauche(MSbit):
- un certain nombre (non encore connu) de 1,
- un 0,
- le reste est un pattern binaire quelconque.
Exemple:
...001101001111111
Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7
Enchanté que cela vous ait intéressé, et merci pour toutes ces idées.
Je crois que c'est Pascal Bourguignon qui a donné le déclic, par rapport à
mon besoin spécifique bien sûr, avec le +1 (dire que j'avais essayé avec la
négation et le Xor !).
En fait, par rapport à mon besoin, je pense pouvoir me passer ainsi du
comptage, et atteindre directement le résultat voulu.
Voilà à quoi ça sert:
______________________
Je développe une classe C++ d'arbres combinant de multiples possibilités, et
que je vais utiliser dans un projet de compilateur (donc gros volume de
données + impératif de performances + divers trucs à moi...).
Cet arbre doit être navigable de toutes les manières possibles, et la
solution naïve implique 5 pointeurs de chaînage par noeud, donc déjà 20
octets sans la charge utile, ce qui est prohibitif.
D'où l'idée de représenter l'arbre comme binaire, afin d'utiliser une
représentation en tableau, sans aucun pointeur. Evidemment l'arbre est non
balancé, et donc le tableau sera creux, mais j'ai une solution en vue pour
çà.
Donc ça donne (passer en fonte à pas fixe):
|
A-
|
|
B--C--D--E-
| | | |
| |
| J--K--L-
| | | |
|
F--G--H--I-
| | | |
A = 1
Down(i) = 2.i
Right(i) = 2.i + 1
Et le pattern binaire du problème est la forme générale d'une valeur
Right(i).
Si on lui applique la formule suivante:
Up(i) = i / ((i ^ (i + 1)) + 1) ^ est le Xor et / la division entière
On atteint directement son parent, sans aucune itération.
La formule est valide aussi pour les premiers descendants.
Et pour atteindre le Nème descendant, on a:
Child(i,n) = (i << n) | ((1 << (n - 1)) - 1) | est le Or inclusif
Finalement, le comptage de bits pourrait permettre à un noeud descendant de
connaître son rang, mais je ne pense pas en avoir besoin.
Toutefois je salue le BITCOUNT(x) que je ne connaissais pas (je suis très
autodidacte en informatique).
Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester
virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)
Patrick 'Zener' Brunet wrote:"Patrick 'Zener' Brunet" a écrit
dans
le message news: f34nr2$oi5$[...]
Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester
virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)
Et peut-etre regarder les "Judy Array" qui font exactement ca, non?
http://judy.sourceforge.net/
Patrick 'Zener' Brunet wrote:
"Patrick 'Zener' Brunet" <use.link.in.signature@ddress.invalid> a écrit
dans
le message news: f34nr2$oi5$1@shakotay.alphanet.ch...
[...]
Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester
virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)
Et peut-etre regarder les "Judy Array" qui font exactement ca, non?
http://judy.sourceforge.net/
Patrick 'Zener' Brunet wrote:"Patrick 'Zener' Brunet" a écrit
dans
le message news: f34nr2$oi5$[...]
Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc rester
virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)
Et peut-etre regarder les "Judy Array" qui font exactement ca, non?
http://judy.sourceforge.net/