Discussion :

[mysianne]

Bonjour,
Je voudrais effectuer une recherche dans un tableau (basique allez-vous certainement le dire) mais je veux un algorithme pour effectuer une recherche style SQL. par exemple: il est donnée un tableau d'objet dont les attribut sont

String champ1;
String champ2;

le but et de rechercher l'objet dont l'attribut champ1=texte ou champ2 =texte
les méthodes optimales de recherche que je connais ne peuvent s'appliquer à ce cas. car exigent que le tableau soit au préalable trié. cependant nous ne pouvons trier le tableau sur les deux critère à la fois.
la seule idée que j'ai et dont la complexité ne me satisfait guère, est de procéder en deux temps. C'est-à-dire faire un premier trie sur champ1 et appliquer la recherche dichotomique par exemple. si on ne trouve aucun élément, on trie à nouveau sur champ2 et on recherche.
Si de grâce quelqu'un à une meilleur idée s'il vous plait

toutes mes excuse si mon post ne se trouve pas sur le bon forums.

[thelvin]

..........

La méthode basique, c'est de regarder tous les éléments et garder ceux dont les deux critères correspondent.

Les systèmes utilisés en base de données, consistent à garder les données triées/indexées, pour toutes les combinaisons importantes, à tout moment. Faire une base de données n'est pas franchement trivial, donc reproduire leurs fonctionnalités non plus. Logique.

[mysianne]

Merci pour ta réponse ! je ne veux pas utiliser cette méthode tant que je pense qu'il y a mieux. aussi je continue de creuser en continuant d'attendre d'autres suggestions.

[thelvin]

Bah l'autre méthode, j'en ai parlé : maintenir un index des données, basé sur le double critère voulu.
En Java un tel index peut se faire en utilisant l'ArrayListMultimap<Integer, TaClasse> de la bibliothèque Guava.
Les valeurs contenues seraient les données dans lesquelles chercher, les clés seraient le hachage du double critère voulu pour la valeur concernée. Il faut une Multimap car il y a sûrement plus d'une donnée correspondante.


Si ce double critère change tout le temps, il faut maintenir un index basé sur chaque combinaison possible, ou bien renoncer à faire mieux que la méthode basique. C'est ce que font les bases de données et c'est la réalité ni plus ni moins.

[jdevbe]

Je ne sais pas ce tu appelles une "recherche style SQL", mais je vois que 2 possibilités pour ton problème:
Soit tu fait ta recherche en parcourant l'ensemble des lignes de ton tableau.
Soit tu crée et maintien un index sur ton tableau.

Côté performance, il faut comparer le coût du maintien de l'index avec le gain obtenu pour la recherche.
Si tes données sont modifiées rarement mais recherchées souvent cela est généralement positif.

Si le critère est "champ1=texte ou champ2=texte", un seul index pourrait comporter 2 lignes d'index pour chaque ligne de ton tableau. Cela permet de faire une seule recherche au lieu de 2 si l'on crée 1 index par champ.

[mysianne]

Je trouve l'idée de l'index très intéressante merci à vous