Discussion :

[spin0us]

Imaginons un tableau de long.

Est-il possible de savoir si un long appartient a ce tableau sans avoir à le parcourir ?

Et si non existe t'il un autre type de variable qui me permettrait de faire le même genre de test sans tout parcourrir ?

(optimisation quand tu nous tiens )

[Obsidian]

Oui, si tu connais la taille de ton tableau et que celui-ci est trié, alors tu peux procéder par dichotomies successives. En gros, tu tapes dans le milieu de la table, tu regardes si ton élément est plus grand ou plus petit que celui que tu lis. En fonction de cela, tu considères la moitié qui t'intéresse, et tu recommences. Tu obtiens donc à chaque tour des moitiés, puis des quarts puis des huitièmes de tables, et ainsi de suite.

Tu peux donc garantir, par exemple, qu'avec une table de 100 éléments, tu trouveras forcément le bon élément avant le huitième coup.

[Bayard]

qsort() est fait pour cela.

[spin0us]

Donc il n'existe aucune structure en C permettant un accès directe sans aucun parcours.

[Invité]

Bonjour,
Je pense que ce genre de chose n'existe dans aucun langage, ou plutôt, certains langages fournissent des fonctions du type indexof(), mais dans tous les cas il y a une recherche, soit par dichotomie si le tableau est trié, soit d'un bout à l'autre dans le cas contraire.
Le terme "structure" a un sens bien particulier en C.

[Obsidian]

Donc il n'existe aucune structure en C permettant un accès directe sans aucun parcours.

Si, bien sûr que si, pour peu que ta liste soit déjà ordonnée d'une manière ou d'une autre. Et ça, ce n'est pas propre au C, c'est une question d'algorithmique. Lorsque tu cherches un nom dans l'annuaire téléphonique, tu ne te paluches pas le bottin entier. Tu le prends au milieu, puis tu navigues vers son début ou vers sa fin jusqu'à ce que tu trouves le nom qui t'intéresse. Cela dit, il n'y a pas moyen de tomber directement sur le nom recherché dès l'ouverture du livre, sauf coup de chance.

— Si ta question est : existe-t-il une fonction pour le faire à ma place ? La réponse est : oui, il y en a plein ;
— Si ta question est : puis-je accéder directement à un élément dont je connais l'emplacement, là aussi c'est élémentaire (un tableau suffit) ;
— Si ce à quoi tu penses, ce sont les tableaux associatifs d'autres langages comme « password['Obsidian'] », alors ce n'est pas un accès direct à l'élément : il y a bien une recherche qui est effectuée, mais elle est masquée aux yeux du programmeur et c'est bien dommage car elle peut être très longue dans certains cas.

Précise ta pensée.

[spin0us]

— Si ce à quoi tu penses, ce sont les tableaux associatifs d'autres langages comme « password['Obsidian'] », alors ce n'est pas un accès direct à l'élément : il y a bien une recherche qui est effectuée, mais elle est masquée aux yeux du programmeur et c'est bien dommage car elle peut être très longue dans certains cas.

C'était bien cette solution là que je cherchais à reproduire. Maintenant, concrètement j'ai des clients qui arrivent sur une socket d'écoute, ils s'identifient via leur numéro qui est un timestamp unix et j'y associe un numéro de socket pour la durée de l'échange. D'un autre côté j'ai des actions à déclencher et qui cible un numéro précis de boitier. Donc plutôt que de parcourir l'ensemble des boitiers connectés je cherchais un moyen d'atteindre directement le boitier concerné pour accélérer au maximum le temps d'exécution.

[droggo]

Joa,

Je me demande comment tu as pu espérer/envisager que ce que tu désires soit faisable.

Avec un peu de bon sens et/ou de réflexion, tu saurais que ça ne peut pas exister.

[spin0us]

Ben étant un peu plus habitué au php et à la manipulation des tableaux associatifs, je t'avoue que j'espérais qu'il existe un truc un peu similaire. Mais comme l'a indiqué obsidian, ce type de manipulation dans php est opaque et on ne sais pas ce qu'il fait derrière (et donc un parcours).

[droggo]

Soa,

Ben étant un peu plus habitué au php et à la manipulation des tableaux associatifs, je t'avoue que j'espérais qu'il existe un truc un peu similaire. Mais comme l'a indiqué obsidian, ce type de manipulation dans php est opaque et on ne sais pas ce qu'il fait derrière (et donc un parcours).

C'est bien là qu'un peu de bon sens et/ou de réflexion ...

[spin0us]

Ben sait-on jamais, peut-être au travers d'un adressage mémoire calculé en rapport avec le contenu de la variable ... L'imagination des concepteurs est sans limite

[Invité]

Essayons d'analyser le problème.
Un client se connecte. Son ID plus je ne sais quoi produit un long (32 bits).
La solution qui vient à l'esprit est de mémoriser ce nombre dans un tableau, le rang de ce tableau donnera le numéro de la boite.

Vous avez besoin de savoir sur quelle boite est connectée le client dont vous connaissez l'ID. Soit le tableau n'est pas trié et vous faites une recherche séquentielle, statistiquement vous parcourez la moitié du tableau si le client est connecté, sinon, vous parcourez la totalité du tableau.
Ou alors, vous triez le tableau et vous faites une recherche par dichotomie.

Dans votre suggestion, par une "formule" vous faites correspondre une adresse à une valeur en long (32 bits). Autrement dit, un tableau de 4 milliards de positions.

[spin0us]

Je peux éventuellement faire un découpage en fonction du dernier chiffre de l'ID, théoriquement ça diviserait par 10 la taille du tableau à parcourir. Associé à la dichotomie, je devrait être plus rapide en pratique qu'un simple for sur la totalité du tableau ?

[Obsidian]

C'est à dire que la syntaxe « container[clé] » est opaque, c'est en fait une méthode d'appel à une procédure. Tu peux donc appeler la même procédure sous forme de fonction, en C, avec quelque chose du style « trouve(container,clé) ».

Et, effectivement, c'est tellement courant en informatique que ce n'est pas possible que cela n'existe pas déjà. Donc, en creusant un peu, on trouve bsearch() qui fait partie du standard C (et de tous les autres) depuis C89. Les deux premiers arguments sont des pointeurs vers la clé à chercher et le container proprement dit, respectivement. Les trois suivant sont : le nombre d'éléments dans la liste, la taille d'une entrée, et un pointeur vers une fonction de callback capable de comparer deux éléments.

Il existe aussi search.h, définie sous Unix (et Posix), qui proposent plein de fonctions similaires.


Enfin, le C++ (≠ du C) est capable de redéfinir le comportement des opérateurs — dont [] — et la STL s'en sert pour proposer son propre tableau associatif : « map ».

Je peux éventuellement faire un découpage en fonction du dernier chiffre de l'ID, théoriquement ça diviserait par 10 la taille du tableau à parcourir. Associé à la dichotomie, je devrait être plus rapide en pratique qu'un simple for sur la totalité du tableau ?

Oui, c'est le principe de la hash table. Les dichotomies successives sont la forme la plus simple de recherche dans une liste (après le parcours de tous les éléments) parce « 2 » est le plus petit diviseur entier qui soit, et parce que « inférieur » et « supérieur » sont justement les deux états possibles lorsque l'on compare des éléments (à part « égal » bien sûr, mais à ce moment-là, on a trouvé et la recherche s'arrête).

Si tu peux identifier quelque chose avec un critère plus fin, tel que le dernier chiffre d'un nombre en décimal ou, par exemple, la première lettre d'un mot (qui te permettrait dans l'absolu de diviser ta table par 26), ça peut t'apporter beaucoup. Mais dans bon nombre de cas, si ton environnement n'est pas préparé à cela, les résultats seront nuls, voire pénalisants.

En effet, les fonctions d'affichage des nombres les représentent généralement en décimal à l'écran, mais un ordinateur travaille en binaire et pour lui, la base 10 n'est pas plus simple que la base 13 ou la base 7 pour nous. Ça veut dire que pour déterminer le dernier chiffre de ton ID, ton ordinateur va devoir la diviser par 10 et examiner le reste. Et ça, ce n'est pas forcément plus rapide que faire n dichotomies successives, et ce pourra même beaucoup plus long si ton processeur n'est pas doté d'une instruction dédiée de division. Cela ne devient donc rentable que s'il y a vraiment beaucoup d'éléments dans ta liste, ou que leur accès est coûteux (disque, réseau…).

En outre, ça ne fonctionne que si les éléments de ta liste sont répartis uniformément : si tu te bases sur le dernier chiffre pour faire une pré-sélection, mais que tous tes ID finissent par le même chiffre, alors ton gain est nul.

[Invité]

Mais non.
Le seul choix à faire est : tableau trié ou non.
Si vous choisissez le tableau trié, la recherche par dichotomie est particulièrement rapide, mais il faut trier le tableau ou le maintenir trié pour chaque nouveau client.
Dans le second cas, vous économisez le tri, mais la lecture devra se faire séquentiellement.

Donc le chois dépend du nombre de boites, c'est à dire de la taille du tableau, et de la fréquence de connexion/déconnexion.

Si vous devez justifier le choix adopté, il faudra faire des simulation et ce ne sera pas facile. Sinon, je pense qu'en connaissant les chiffres, le choix s'imposera de lui-même.

Concernant la gestion des listes.
Le traitement avec des listes chainées est particulièrement efficace. Mais qsort est aussi très rapide.
En d'autres termes, la question ne devrait pas être posée sous la forme "Existe-t-il des fonctions qui ...", mais "En fonction de çi et de ça quelle méthode adopter"

PS. en fait comme le nombre de boites est connu, la longueur du tableau est fixe, donc les listes chainées sont sans intérêt.
PS2 le "mais non" de mon message était adressé à Spin0us

[spin0us]

On a potentiellement 50 000 clients potentiels (actuellement, mais ce nombre à tendance à croitre). Après, pour l'instant on a atteint 1500 clients simultanés parmi ces 50 000. Ensuite pour chaque client on gère en plus de son ID tout un tas d'autres informations le concernant, le tout stocké dans une structure. Donc actuellement on utilise un tableau de structure pour englober tous les connectés et on le parcours sans arrêt pour identifier le boitier concerné pour chaque action (je sais pas si je suis très clair ). Le tableau de structure est indexé sur l'id de la socket connecté (un int). On défini donc juste un MAX de connections simultanées.

[Obsidian]

Avec 1500 clients simultanés, tu ne verrais pas encore la différence en parcourant le tableau en entier avec une machine moderne. Et quand je dis « moderne », ça englobe les 15 dernières années ! En tout cas, pas en C. Avec un langage interprété, c'est effectivement une autre histoire.

Il faut comprendre que la complexité d'une recherche dichotomique est logarithmique et que, donc, le nombre d'éléments couverts à chaque étape est exponentiel. 2⁷ = 128, donc tu sais que tu auras trouvé ton élément dans une table triée de 100 éléments au septième coup au maximum. Parallèlement, 2¹⁶ = 65.536, ce qui signifie qu'il faut 16 coups maximum pour retrouver un élément dans une liste de 50.000 éléments.

Autrement dit, il est aussi rapide de retrouver un élément parmi 50.000 par dichotomies successives, qu'un élément parmi 16 en lisant le tableau en entier.

Question subsidiaire (et quand je dis « subsidiaire », en fait, c'est probablement la clé de toute l'affaire) : quelle méthode les tableaux associatifs du PHP suivent-ils pour retrouver l'élément repéré par ta clé, à ton avis ?

C'est l'avantage et l'inconvénient des langages interprétés (ou semi-interprétés) de haut niveau comme le PHP. Du temps des huit bits des années 1980, on avait soit le BASIC, soit l'assembleur de sa machine, et la différence entre les deux, en termes de performances, était nettement tranchée. Entre 1990 et aujourd'hui, c'est le PC qui a tout dominé. On ne pouvait plus comparer les architectures entre elles et, parallèlement, les langages compilés ont pris le dessus (C, Turbo Pasal …) et la vitesse des machines et la puissance des machines a augmenté de manière exponentielle aussi, ce qui fait que plus personne n'avait une idée claire des ressources qu'un programme pouvait prendre (100 itérations ou 10000 semblaient être la même chose).

Avec le retour de langages interprétés capables de gérer de grandes quantités de données, ces différences redeviennent sensibles et c'est une bonne chose. Par contre, il y a un tel trou entre les méthodes d'accès proposées par ces langages, tels que les tableaux associatifs, et les mêmes méthodes ré-implémentées artificiellement dans le langage en question, que les premières ont l'air d'être des opérations fondamentales.

[Sve@r]

C'était bien cette solution là que je cherchais à reproduire. Maintenant, concrètement j'ai des clients qui arrivent sur une socket d'écoute, ils s'identifient via leur numéro qui est un timestamp unix et j'y associe un numéro de socket pour la durée de l'échange. D'un autre côté j'ai des actions à déclencher et qui cible un numéro précis de boitier. Donc plutôt que de parcourir l'ensemble des boitiers connectés je cherchais un moyen d'atteindre directement le boitier concerné pour accélérer au maximum le temps d'exécution.

C'est encore un peu flou. Tu parles de timestamp, de boitier. Je vois pas trop comment tu fais le lien.

Mais pourquoi ne pas créer une structure contenant {
n° de socket
actions à déclencher
}

Puis tu crées un tableau tab[] de structures. Quand tu as ton n° "b" de boitier, tu vas directement taper dans tab[b]...

[spin0us]

J'identifie un boitier via un timestamp parce que la première fois qu'il se connecte je lui attribue un numéro qui est le timestamp unix du moment de sa première connection. Donc un tab[b] avec b qui vaut dans les 1234567890 est plus ça fait un peu beaucoup non ?

Le fichier modifiés sont dans des répertoires et portes tous le nom du boitier concerné. En gros si j'ai une modification sur .../toto/1234567890 je dois déclencher une action spécifique sur le boitier 1234567890.

[Sve@r]

J'identifie un boitier via un timestamp parce que la première fois qu'il se connecte je lui attribue un numéro qui est le timestamp unix du moment de sa première connection. Donc un tab[b] avec b qui vaut dans les 1234567890 est plus ça fait un peu beaucoup non ?

Ouaip

Le fichier modifiés sont dans des répertoires et portes tous le nom du boitier concerné. En gros si j'ai une modification sur .../toto/1234567890 je dois déclencher une action spécifique sur le boitier 1234567890.

Donc le timestamp sert aussi de nom de fichier... Pas facile de concilier tout ça. De toute façon t'es grillé. Si ton n° de boitier ne peut pas être un n° d'indice, tu seras obligé de "simuler" le comportement d'un dictionnaire en parcourant ta liste. A partir de là, tu peux étudier plusieurs solutions. Dont une qui sera de passer par des pointeurs
Exemple 1

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
int tab[1000]={..., ..., ...};
int i;
 
for (i=0; i < 1000; i++)
{
    if (tab[i] == ...)     // ça c'est (relativement) super très long
    {
       // trouvé
       break;
    }
}

Exemple 2

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
12
int tab[1000]={..., ..., ...};
int *pt;
int i;
 
for (i=0, pt=tab; i < 1000; i++, pt++)
{
    if (*pt == ...)     // ça c'est (relativement) super plus rapide
    {
       // trouvé
       break;
    }
}

Et si t'as possibilité d'inclure une sentinelle (valeur dont tu es sûr qu'elle ne sera jamais présente par hasard), tu peux éviter la variable "i" (et donc son super long incrément)

Exemple 3

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
int tab[1000]={..., ..., ..., 0};
int *pt;

for (pt=tab; *pt != 0; pt++)     // Encore super plus rapide que dans l'exemple 2
{
    if (*pt == ...)
    {
       // trouvé
       break;
    }
}

Par ailleurs, il a beaucoup été question de dichotomie dans ce topic. La dichotomie a un certain coté assez efficace mais un gros inconvénient qui est qu'on est obligé de l'implémenter de façon récursive (on cherche dans un tableau et selon que le pivot est avant ou après la recherche, on appelle la même fonction sur la moitié gauche ou droite du tableau). Or la récursivité, c'est super hyper long. A chaque appel, faut empiler tout le contexte mémoire pour que la sous-fonction soit libre de travailler ; puis une fois qu'elle a fini faut dépiler le contexte pour revenir à la fonction précédente.

Une autre méthode qui n'a pas été évoquée est le parcours par pas
On définit un pas, par exemple à 10 et on parcours le tableau de 10 en 10.
Dès qu'on a dépassé l'élément, on revient à la dernière position mais le pas passe à 5, etc etc etc

Voici un exemple démo de l'algo de recherche (accessoirement, étant donné qu'on travaille sur des timestamp, travailler en "unsigned" gagne encore une petite optimisation (le proc évite l'extension du bit de signe)

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <stdlib.h>
 
int find(unsigned long *tab, unsigned long need)
{
	unsigned long i;
	unsigned long *deb;
	unsigned long *fin;
	unsigned short pas;
 
	if (*tab == need)
		return 0;
 
	i=0;
	deb=tab;
	for (pas=100; pas > 0; pas=pas >> 1)
	{
		fin=deb;
		while (*fin < need && (fin - tab) < 500000)
		{
			deb=fin;
			fin=fin + pas;
			i++;
			printf("i=%lu, pas=%hu, [%lu-%lu], need=%lu\n", i, pas, *deb, *fin, need);
			if (*fin == need)
				return fin - tab;
		}
	}
	printf("i=%lu, pas=%d, [%lu-%lu], need=%lu\n", i, pas, *deb, *fin, need);
 
	return (-1);
}
 
main() {
 
	srandom(getpid());
	unsigned long tab[500000];
	unsigned long i;
	unsigned long need;
 
	for (i=0; i < 500000; i++)
		tab[i]=i + 1;
 
	// Mettre, selon son choix, la ligne que l'on veut en dernier
	// Ca permettra de faire des tests différents 
	need=tab[0];			// Test recherche premier élément
	need=tab[500000-1];		// Test recherche dernier élément
	need=random() + 500000;		// Test recherche élément non présent
	need=random() % 500000;		// Test recherche élément aléatoire
 
	if ((i=find(tab, need)) != -1)
		printf("need: %lu => tab[%lu]=%lu\n", need, i, tab[i]);
	else
		printf("need: %lu => rien\n", need);
}