Code C# pour effectuer une recherche binaire dans un très gros fichier texte

Question

Y at-il une bibliothèque que je peux utiliser pour effectuer une recherche binaire dans un très gros fichier texte (peut être 10GB).

Le fichier est une sorte de fichier journal - chaque ligne commence par une date et une heure. Par conséquent, les lignes sont commandées.

Answer 1

J'ai commencé à écrire le pseudo-code sur la façon de le faire, mais j'ai abandonné car cela peut sembler condescendant. Vous savez probablement comment écrire une recherche binaire, ce n'est vraiment pas compliqué.

Vous ne trouverez pas dans une bibliothèque, pour deux raisons:

1. Ce n'est pas vraiment « recherche binaire » - les tailles de ligne sont différentes, donc vous devez adapter l'algorithme (par exempleCherchez le milieu du fichier, puis cherchez la prochaine "nouvelle ligne" et considérez que c'est le "milieu".
2. Votre format de journal datetime est probablement non standard (ok, il peut sembler "standard", mais pensez un peu .... vous utilisez probablement '[]' ou quelque chose pour séparer la date du message de journal, quelque chose like [10/02/2001 10:35:02] Mon message).

En résumé - Je pense que votre besoin est trop précis et trop simple à mettre en œuvre un code personnalisé pour quelqu'un à la peine d'écrire une bibliothèque :)

Answer 2

L'objet List possède une méthode de recherche binaire.

http://msdn.microsoft.com/en-us/library/w4e7fxsh%28VS.80%29.aspx

Answer 3

Vous devez être en mesure de diffuser le fichier, mais vous aurez également besoin d'un accès aléatoire. Je ne suis pas sûr de la façon dont vous accomplissez ce court de garantie que chaque ligne du fichier contient le même nombre d'octets. Si vous aviez cela, vous pourriez obtenir un flux de l'objet et utiliser la méthode Seek pour vous déplacer dans le fichier, et à partir de là, vous pourriez effectuer votre recherche binaire en lisant le nombre d'octets qui constituent une ligne. Mais encore une fois, ceci n'est valable que si les lignes ont le même nombre d'octets. Sinon, vous sauteriez dans et hors du milieu des lignes.

Quelque chose comme

byte[] buffer = new byte[lineLength]; 
stream.Seek(lineLength * searchPosition, SeekOrigin.Begin); 
stream.Read(buffer, 0, lineLength); 
string line = Encoding.Default.GetString(buffer); 

Answer 4

Comme les longueurs de ligne ne sont pas garantis de la même longueur, vous allez avoir besoin d'une certaine forme de delimiter ligne reconnaissable par exemple retour chariot ou saut de ligne.

Le motif de recherche binaire peut alors être à peu près votre algorithme traditionnel. Cherchez au milieu du fichier (par longueur), cherchez en arrière (octet par octet) au début de la ligne où vous arrivez, identifiée par la séquence de délimiteurs de lignes, lisez cet enregistrement et faites votre comparaison. Selon la comparaison, chercher à mi-hauteur ou en-dessous (en octets) et répéter.

Lorsque vous identifiez l'index de début d'un enregistrement, vérifiez s'il était identique à la dernière recherche. Vous pouvez constater que, lorsque vous vous connectez sur votre enregistrement cible, se déplacer à mi-chemin ne vous mènera pas à un enregistrement différent. par exemple. vous avez des enregistrements adjacents de 100 octets et 50 octets respectivement, donc sauter 75 octets vous ramène toujours au début du premier enregistrement. Si cela se produit, lisez l'enregistrement suivant avant de faire votre comparaison.

Vous devriez constater que vous atteindrez votre cible assez rapidement.

Answer 5

Cela ne devrait pas être trop mauvais sous la contrainte que vous maintenez un Int64 en mémoire pour chaque saut de ligne dans le fichier. Cela dépend vraiment de la longueur moyenne de la ligne de texte, étant donné 1000 octets par ligne que vous regardez autour de (10 000 000 000/1000 * 4) = 40mb. Très gros, mais possible.

Donc, essayez ceci:

1. Scannez le fichier et stocker l'ordinal décalage de chaque ligne d'alimentation dans une liste
2. Binary recherche dans la liste avec un comparateur personnalisé qui scanne le fichier offset et lit le Les données.

Answer 6

Si votre fichier est statique (ou des changements rarement) et vous avez pour exécuter des requêtes « assez » contre, je crois que la meilleure approche sera la création du fichier « index »:

1. Scannez le fichier initial et prendre les parties datetime du fichier ainsi que leurs positions dans l'original (ce qui est pourquoi doit être assez statique) les encoder comment (par exemple: temps unix (10 chiffres complets) + nanosecon ds (zéro rempli 4 chiffres) et la position de la ligne (zéro déposé 10 chiffres). De cette façon, vous aurez un fichier avec des "lignes" cohérentes

2. recherche binaire de préforme sur ce fichier (vous devrez peut-être être un peu créatif afin d'atteindre la recherche de gamme) et obtenir les emplacements appropriés dans le fichier original

3. lire directement à partir du fichier d'origine à partir de l'emplacement donné/lire la plage donnée

vous avez plage de recherche avec O (log (n)) run-time :) (et que vous avez fonctionnalité primitive DB créée)

Inutile de dire que si le fichier de données de fichier est mis à jour "trop" fréquemment ou vous ne lancez pas "assez" de requêtes sur le fichier d'index que vous finissez par passer plus de temps à créer le fichier d'index que vous enregistrez à partir du fichier de requête. Btw, travailler avec ce fichier d'index ne nécessite pas le tri du fichier de données. Comme les fichiers journaux ont tendance à être ajoutés seulement, et triés, vous pouvez accélérer le tout en créant simplement un fichier d'index qui ne contient que les emplacements des marques EOL (zéro-rempli 10 chiffres) dans le fichier de données - de cette façon vous pouvez préformer la recherche binaire directement sur le fichier de données (en utilisant le fichier d'index pour déterminer les positions de recherche dans le fichier original) et si des lignes sont ajoutées au fichier journal, vous pouvez simplement ajouter (ajouter) leurs positions EOL au fichier d'index.