Discussion :

[Pypiou]

Bonjour,

Je voudrais connaitre vos avis ...

Si vous aviez des enregistrements d'une table mis dans un container en mémoire qui permet l'accès direct (pour la dichotomie)
un "array de record" par exemple.

et que la clé soit sur 4 à 5 caractères de type Alphanumérique avec les caractères pris entre 0 et 9 ou entre A et Z (soit 36 symboles possibles)

(On rencontre le cas en gestion)

Si un besoin d'optimisation vitesse se faisait sentir pour des recherches en quantités.

Feriez-vous une recherche dans ce container mémoire par recherche dichotomique sur les clés ?

ou un accès direct a l'aide d'un index supplémentaire (array of integer) avec des entiers en base 36 ?
(oui, 3BZ09 est un nombre en base 36)


(pour la suite, A symbolise un chiffre en base 36)

En sachant que le cout mémoire d'un index AAAAA
est de (36^5) entiers sur 4 octets, soit quasiment 250Mo (241Mo), cela est inutilisable.

Par contre un index AAAA "coute" environ 6,7 Mo.

Personnellement je proposerais l'accès direct pour un index AA,AAA et AAAA et la dichotomie pour un index AAAAA,AAAAAA et +.

(Il doit cependant pourvoir exister un mix entre les 2 méthodes, pratique pour les très gros index)

Merci

[ShaiLeTroll]

Personnellement, je préfère récupérer et charger le minimum de données !
Si tu as un DB comme MySQL ou Oracle, crois-tu vraiment pour écrire un algo d'indexation meilleur que celui de tels spécialistes ?

Sur une table de comptabilité avec plus de 5 millions de lignes de compta, MySQL 4.1 ne mettait même pas 100µs à me renvoyer un résultat
Seule la 1ere exécution pouvait monter à 10ms le temps du prépare

Avec mon Serveur MySQL, un vieux Win2K avec 256Mo de RAM, Client WinXP 512Mo de RAM, j'aurais j'ai l'idée de charger cela en mémoire, dès que le SWAP entre en jeu, c'est divise les performances par 100, géré un gros tableau directement dans un fichier devient plus rapide que passer par la RAM qui swappe en permanence !

Pour la conversion Base36, j'ai écrit ceci ConversionIntToBase, faudra un jour que je fasse sa réciproque

Je suppose que tes données sont déjà triées à la lecture depuis la DB ?

Si tu n'as que 36 Symboles, fait un arbre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
TArbre= class
  Branches : array[0..35] of TBranche;
TBranche = class
  Branches : array of TBranche;

Si tu veux je l'ai déjà écrit en D7, uHashList : THashStringList et TTreeHashingObjectList
THashStringList :
Utilse une TStringList pour le Code comme ton 3BZ09
Et Objects[] pour les données
Essaye de voir ce que donne déjà DataFromCode

Une fois la liste remplie, la TStringList et son Find son assez rapide !
C'est le remplissage qui pêche faudrait en bidouiller une, pour la remplir pré-triée et lui forcer le Sorted sans qu'elle tente de re-trier ce qui est déjà triée


TTreeHashingObjectList :
A part le 1er niveau qui est directement un tableau fixe [Char], le reste c'est des tableaux dynamiques avec des boucles !

Il existe dans IniFiles THashedStringList qui via un petit calcul de Hash gère les positions dans une TStringList


Une fois rempli, j'ignore exactement sa taille mais il ne contient QUE ce qui existe
Je n'ai jamais eu le temps de l'expérimenter à fond !
Si tu en as l'occasion !

3BZ09 et 4BZ09 en Base36 = 5597433 et 7277049
La plus grande valeur ZZ ZZZ = 58 786 560 si je me trompe pas
D'ailleurs ZZZ ZZZ = 2 176 782 335
Cela reste dans les valeurs du Cardinal 32Bit
Intéressante approche !

J'ai bidouillé une TCardinalBitTreeNode pour un sujet sur Phidels
Si cela peut te donner des idées

[Pypiou]

Merci pour les infos.

Dans mon cas, la paye
je ne peux pas charger qu'une partie d'un plan de paye
puisque pour savoir ce qui est utilisé il faut l’exécuter sur des données
donc je suis obligé de tout charger !
(select * from table)

Je pense avoir compris comment fonctionne tes classes THashStringList et TTreeHashingObjectList.

Mais toute ma réflexion consiste a éviter les recherches aux maximum (je ne peux pas tout le temps les eviter)

ta classe TTreeHashingObjectList est bien, mais faut construire l'arbre.
et je suis pas sur que l'arbre tienne moins de place qu'un vrai index !!!
faudra que je me penche sur ce genre de solution.



Pour un index AAAAA et +,
je proposerais ce que j'ai dit à la fin de mon précédent message :

Un tableau avec le 1er caractère comme index (comme dans ta classe TTreeHashingObjectList),
sauf que ce tableau indexe des parties de mon tableau de données
ensuite ce sont ces parties qui seront analysée par dichotomie.

c'est un mélange entre indexation et recherche
ça permet de pré-découper un tableau en 36 parties.

Par exemple pour chercher ABZ15:

[ShaiLeTroll]

Pour commencer, un simple Array[0..35] of TStringList
la TStringList en Sorted True utilise pour sa recherche une dichotomie, voir le code dans Classes.pas, TStringList.Find...
Au lieu d'utiliser de Record, utilise des TObject stockés dans Objects[], tu n'auras pas besoin de faire de redirection vers un autre tableau

Sinon copie le code IniFiles THashedStringList et change la recherche dans TStringHash.Find par ta dichotomie ainsi que TStringHash.HashOf par un mécanisme plus simple

Je pense qu'il te faut te lancer, fourni nous un premier jet de code, on t'aidera à le corriger

Question : quelle volume cela donne ?
Millier de ligne ? une TStringList Sorted True seule sera suffisante
Millions de ligne ? Array[0..35] of TStringList aidera
Milliards de ligne ? oublie le chargement en mémoire !

On a bcp discuter ses les performances de recherche de doublon sur des millions de lignes, c'est la que cela commence à devenir lent

En dessous de la centaine de millier, un petite progression pour le chargement pour faire patientez l'utilisateur, qui a déjà attendu le SQL qui doit déjà prendre du temps
Ensuite les IndexOf ou Find sont quasi-instantanés !

[Pypiou]

Mon volume de donnée
correspond à au maximum 6 à 8 fois 10000 enregistrements de tables.

les 6-8, c'est 6-8 tables différentes.

Ça sera long si je le fait, il faudra que je remplisse a la main ces lignes
et même quand j'en aurais remplis une centaine (celles de base)
je ne verrais sans doute pas de différences dans les différents algos de recherche.

Je vais réaliser le programme et remplir les 6 tables en même temps
puisque qu'ils dépendent l'un de l'autre et que je ne connais rien à l'avance.

Je m’aperçois par contre que le programme sera en C++Builder et pas en Delphi.

Le coeur du programme c'est le calcul d'un bulletin de paye,
donc il y aura des recherches, beaucoup de recherches et dans les 6 tables !