Discussion :

[sbadecoder]

On dispose d'un tab1:array[0..500 000] of byte dans lequel il y a des valeurs de 1..100 - disons générées par random.

1) Quel est l'algorithme le plus rapide pour récupérer les indices de tab1 pour une valeur fixe disons de 55.


On dispose d'un tab2:array[0..5 000 000] of cardinal dans lequel il y a des valeurs de 1..600 000 - disons générées par random.

2) Quel est l'algorithme le plus rapide pour récupérer les indices de tab2 pour une série de valeurs déterminées ainsi :
par exemple valeur de base 12345 (comprise entre 1..100 000) et 12345 + k * 100000.
On recherche donc tous les indices où tab2 contient 12345, 112345, 212345, ..., 512345 (< 600 000).

[ShaiLeTroll]

N'avez pas déjà posé la même question sur la recherche de motif binaire dans un binaire ?
Algorithme de recherche d'une liste de mots dans un texte ?
On avait déjà dans ce sujet réduit la recherche de texte à un sous-ensemble de l'ASCII à peu près la même chose que les valeurs de 1 à 100, c'est toujours la même chose avec des nombres, cela reste du binaire.


Au final, ça sert à quoi tout ça, non parce que je ne vois pas immédiatement d'application à un projet profesionnel, cela ressemble à des exercices scolaires souvent débiles.
Donnez le contexte, peut-être qu'une approche sera émis pour résoudre le problème initial.

[sbadecoder]

Oui pour 1), il est vrai que cela se rejoint. Donc je conserve uniquement la question 2).

Sachant que là, c'est un peu différent puisqu'il existe un lien entre la série de valeurs recherchées selon par exemple v(k) = base + k * 100 000
donc la question est de savoir si un algorithme optimisée, dans ce cas, existe.

[ShaiLeTroll]

Vous pouvez l'algo de la même façon que le premier

Votre tableau de cardinal c'est juste des octets qui se suivent, comme pour la recherche du mot ETE en ASCII dans une chaine ASCII, c'est la même chose que chercher 12345 dans un binaire, juste le travail se fait toujours sur des "mots" de 4 octets.
Votre but c'est quoi savoir la position, dans ce cas un AlphaSort sur un Tab<Valeur, Position>
Votre but c'est de compter les références, dans ce cas un BucketSort


La série et le lien entre les valeurs de la série a une petite importance
non pas sur le motif, en dehors des 5 premiers bits identiques, tout le reste est différent en binaire (même si en décimal cela se ressemble)
Comme l'idée est rechercher 6 mots différents dans le tableau, et que les mots recherchés soient croissants, je ferais d'abord un Tri du tableau, un simple QuickSort que les TList fournit, puis tout simplement une recherche par dichotomie de la première valeur, et comme la suivante est plus grande profiter de cela pour s'occuper de la suite en repartant de la position trouvée, du coup, cela sera de plus en plus rapide en arrivant à la fin du tableau trié

Si il y a besoin d'avoir les positions, un TDictionary<Cardinal, Integer> pour retrouver la position initiale
Mais le TDictionary sera moins performant sur ce cas précis, cela n'utilise pas un Tri croissant et c'est plutôt conçu pour optimiser une table avec des clés chaines.

Comme, je manipule que des GUID en forme chaine ou des PHP Session, c'est toujours des chaines, j'utilise une TStringList, d'ailleurs, ou je travaille actuellement, leur TOptimizedStringList est plus performant dans l'utilisation d'un petit dictionnaire de Session.
Je commencerais par reprendre le code de TIntegerBucketList en une TCardinalBucketList, c'est à dire remplacer NativeInt (qui diffère selon 32 ou 64 Bits) par un Cardinal, c'est le même principe que le TDictionary<Valeur, Position>.



Mais bon, on sait toujours pas à quoi cela va servir !
D'ou vienne les données ?
Pourquoi de l'aléatoire ?

[sbadecoder]

Dans la mesure où les premiers bits identiques ne semblent pas permettre d'optimiser l'algorithme et vu que la recherche concerne des mots plutôt courts (moins de 10 caractères en général, 4 bytes ici pour mon cardinal).

Je vais retenir la recherche par AnsiStrings.PosEx (suffisante pour mon utilisation) qui donne de très bons temps sur les tests effectués.

Éventuellement, adapter PosEx pour une recherche par cardinal qui devrait être plus rapide pour mon tableau du même type.