le plus rapide de l'algorithme de recherche

Je suis en train de mettre en œuvre un algorithme de recherche de plusieurs fichiers XML pour un enregistrement précis.
connu que les enregistrements ne sont pas triés ( je n'ai pas indexé id) .
quel est l'algorithme le plus rapide pour rechercher l'enregistrement ?.


s'il vous plaît laissez-moi savoir si quelque chose n'était pas clair


merci d'avance

  • Naturellement, il semble que vous devriez traiter les fichiers XML et créer un index pour faciliter des recherches rapides.
  • ouais c'est important si vous souhaitez rechercher une seule fois ou plusieurs fois. Parce qu'alors vous pouvez avoir besoin de créer un index. Mais si vous recherchez seulement une fois que cela serait inutile.
  • Question intéressante. Je me demande quand nous allons voir certains commentaires de Moayyad, en particulier concernant la question de l'une ou plusieurs d'accès?
InformationsquelleAutor Moayyad Yaghi | 2010-07-13
  1. 2

    galambalazs est correct: données non Triées signifie que vous devez aller à travers elle à la recherche de ce dont vous avez besoin. Mais c'est seulement aborder une petite partie de la question.

    Dans le traitement de plusieurs fichiers, et probablement la plupart de votre temps de traitement sera repris par fichier I/O. Il faut un long temps, par ordinateur normes, pour trouver un fichier dans un répertoire et de l'ouvrir. Mais c'est un coût que vous devrez engager fondamentalement, peu importe de quel programme vous utilisez en fin de compte.

    Une autre partie de l'équation de la performance est le genre de l'analyseur vous utilisez. Selon la structure de votre fichier XML, vous avez le choix de l'utilisation d'un écrit à la main de l'analyseur, un DOM parser XML ou un analyseur Sax.

    Si les balises entourant votre cherchaient à obtenir des données se produisent toujours sur la même ligne que celle des données et aucune ambiguïté n'est possible, alors la lecture du fichier ligne par ligne et de la recherche, soit par la chaîne de recherche ou regexp est valide possibilité. Beaucoup de personnes, AFIN de protester contre cette regexp correspondance est une manière horrible de processus XML et c'est généralement correct; c'est une façon rapide et sale pour faire des recherches dans un très spécifique et limité de cas, et est très fragile à l'égard de la structure XML fin de compte vous travaillez avec.

    Un DOM parser "inhale" l'ensemble de votre document XML dans une structure en mémoire, que votre application puis pouvez rechercher de manière séquentielle pour ce qu'il est. DOMs sont grands quand vous voulez faire un certain nombre d'opérations complexes sur un arbre XML; pour une recherche séquentielle ils sont une idée horrible parce que

    • la quantité de mémoire nécessaire est proportionnelle à la taille du fichier, un fichier de grande taille pourrait vous exécutez hors de la mémoire.
    • une grande structure de données doit être construit à partir du contenu du fichier. Après une recherche, il sera immédiatement supprimé. Le calcul des ressources de mémoire et mettra fin à la dispersion.

    Par conséquent, le plus recommandé approche serait d'utiliser un parser SAX. Googler trouverez vous un pour votre langue préférée. Un analyseur SAX scanne votre fichier d'entrée une fois, la production d'événements à chaque élément que vous pouvez (et devez!) processus de manière appropriée. Les données sont traitées de manière séquentielle et il n'y a pas de stockage autres que ce que vous décidez de faire avec les données que vous trouvez. Les parseurs SAX sont généralement beaucoup plus rapide que DOM analyseurs mais besoin d'un peu de planification sur la façon de traiter les événements.

    • Aussi, XPath peut être utilisé. Cependant, les détails de l'implémentation des questions. E. g. Java par défaut XPath mise en œuvre est basée sur les DOM parser comme je me souviens bien donc hériter de tous ses implications sur les performances. Mais XPath est si expressif que le surpoids performances sur les occasions =)
    • Maintenant que vous le dites, un sensible et très "XML-y" façon de faire pourrait être d'utiliser XSLT pour transformer un document XML en document d'entrée dans l'arbitraire d'un document de sortie contenant les chaînes de recherche. L'appel ici, c'est que c'est tout à fait possible de brancher un Transformateur pour un SAX source, assurant ainsi (sans doute?) que l'entrée ne seront traitées de manière séquentielle. Ce serait vous permettent de combiner l'expressivité des expressions XPath pour la définition de la recherche avec la vitesse de SAX de l'analyse.
    InformationsquelleAutor Carl Smotricz
  2. 6

    Tout ce que vous devez décider est ici Algorithmes De Tri

    InformationsquelleAutor OddCore
  3. 4

    Sans tri linéaire de recherche est votre meilleur pari. Pensez à ce sujet.

    Et comme je l'ai dit dans les commentaires: c'est important si vous souhaitez rechercher une seule fois ou plusieurs fois. Parce qu'alors vous pouvez avoir besoin de créer un index. Mais si vous recherchez seulement une fois que cela serait inutile.

    InformationsquelleAutor gblazex
  4. 3

    Cela dépend vraiment de combien de fois vous voulez exécuter la tâche sur ces fichiers. Si les dossiers ne sont pas triés, vous pouvez rechercher uniquement à travers eux de manière linéaire. Mais si vous devez le faire le plus souvent sur le même ensemble d'enregistrements, vous pouvez créer un index, ou les trier lors de la première exécution.

    InformationsquelleAutor relet
  5. 0

    Séquentielle, ligne par ligne, de la recherche vient à l'esprit. L'utilisation de plusieurs threads pour prendre plusieurs fichiers à la fois.

    • Si ils sont tous sur le même disque, puis la recherche sera plus susceptible d'e/S et les multiples fils ne va pas profiter beaucoup.
    • Très vrai, mais vous ne savez pas d'où ils viennent ni comment ils sont gros. Aussi, cela dépend de si vous diffusez le fichier ligne par ligne ou de la charge tout en mémoire et ensuite d'analyser.
    InformationsquelleAutor Adam Houldsworth