Traitement de gros fichiers texte

Question

Problème: J'ai un énorme fichier texte brut (supposer de 3gig), je dois passer par chaque mot du fichier et découvrez qu'un mot apparaît combien de fois dans le fichier.

Ma solution proposée: Divisez le fichier énorme en plusieurs fichiers et chaque fichier fractionné aura des mots de manière triée. Par exemple, tous les mots commençant par & "; a &"; sera stocké dans un & "; _a.dic &"; fichier. Donc, à tout moment, nous n’exécuterons pas plus de 26 fichiers.

Le problème dans cette approche est,

Je peux utiliser des flux pour lire le fichier, mais je voulais utiliser des threads pour lire certaines parties du fichier. Par exemple, lisez 0-1024 octets avec un thread séparé (au moins 4 à 8 threads basés sur le nombre de processeurs présents dans la boîte). Est-ce possible ou suis-je en train de rêver?

Une meilleure approche?

Remarque: il doit s'agir d'une solution pure basée sur c ++ ou c. Aucune base de données, etc. n'est autorisée.

Answer 1

Vous devez consulter ' La pratique de la programmation ' par Kernighan et Pike, et plus précisément le chapitre 3.

En C ++, utilisez une carte basée sur les chaînes et un nombre (std::map<string,size_t>, IIRC). Lisez le fichier (une fois - il est trop gros pour être lu plus d'une fois), divisez-le en mots au fur et à mesure (pour définir le terme "mot") et incrémentez le nombre dans l'entrée de carte pour chaque mot trouvé.

En C, vous devrez créer la carte vous-même. (Ou recherchez les & Quot; interfaces C et mises en œuvre de David Hanson & Quot ;.)

Vous pouvez aussi utiliser Perl, Python ou Awk (qui ont tous des tableaux associatifs, équivalents à une carte).

Answer 2

Je ne pense pas que l'utilisation de plusieurs threads qui lisent des parties du fichier en parallèle va beaucoup aider. Je suppose que cette application est liée à la bande passante et à la latence de votre disque dur, et non au décompte des mots. Une telle version multithread pourrait en réalité être pire car & "Quasi-aléatoire &"; l'accès aux fichiers est généralement plus lent que " fichier linéaire " accès.

Si le processeur est vraiment occupé dans une version mono-thread, une accélération potentielle est possible. Un thread pouvait lire les données en gros morceaux et les placer dans une file d'attente de capacité limitée. Un groupe d'autres threads de travail pourrait opérer chacun sur son propre morceau et compter les mots. Une fois les tâches de travail de comptage terminées, vous devez fusionner les compteurs de mots.

Answer 3

D'abord, choisissez la structure de données pour la sauvegarde des mots.

Le choix évident est la carte. Mais peut-être qu'un Trie vous servirait mieux. Dans chaque nœud, vous enregistrez le compte pour le mot. 0 signifie que ce n'est qu'une partie d'un mot. Vous pouvez vous insérer dans le fichier en utilisant un flux et en lisant votre fichier à base de caractères.

Deuxième - multithreading oui ou non? Celui-ci n'est pas facile à répondre. En fonction de la taille de la structure de données et de la parallélisation de la réponse, la réponse peut être différente.

1. Singlethreaded - simple et facile à mettre en œuvre.
2. Multithread avec plusieurs threads de lecture et une base de données. Ensuite, vous devez synchroniser l'accès à la structure de données. Dans un Trie, il vous suffit de verrouiller le nœud dans lequel vous vous trouvez afin que plusieurs lecteurs puissent accéder à la structure de données sans trop d'interférences. Un arbre à auto-équilibrage peut être différent, notamment lors du rééquilibrage.
3. Multithread avec plusieurs threads de lecteurs, chacun avec sa propre structure de données. Chaque thread construit sa propre structure de données lors de la lecture d'une partie du fichier. Une fois que chacun est terminé, les résultats doivent être combinés (ce qui devrait être facile).

Une chose à laquelle vous devez penser - vous devez trouver une limite de mot pour chaque fil de départ, mais cela ne devrait pas poser de gros problème (par exemple, chaque fil marche de son début à la première limite de mot et commence là, à la terminer chaque fil termine le mot sur lequel il travaille).

Answer 4

Vous pouvez utiliser un second thread pour analyser les données après les avoir lues, mais vous ne gagnerez probablement pas énormément en le faisant. Essayer d'utiliser plus d'un thread pour lire les données va presque certainement ralentir la vitesse plutôt que de l'améliorer. L'utilisation de plusieurs threads pour traiter les données est inutile - le traitement sera beaucoup plus rapide que la lecture, donc même avec un seul thread supplémentaire, la vitesse du disque sera limitée.

Un moyen (possible) de gagner beaucoup de vitesse consiste à contourner les courants habituels - alors que certains sont presque aussi rapides que ceux de C FILE *, je ne connais rien de vraiment plus rapide, et certains sont beaucoup plus lents . Si vous utilisez cette application sur un système (Windows, par exemple) dont le modèle d’E / S est sensiblement différent de celui du C, vous pouvez gagner beaucoup plus avec un peu de soin.

Le problème est assez simple: le fichier que vous lisez est (potentiellement) plus grand que l’espace de cache dont vous disposez - mais vous ne gagnerez rien en cache, car vous n'allez pas relire des morceaux du fichier. déposer à nouveau (au moins si vous faites les choses judicieusement). En tant que tel, vous voulez indiquer au système de contourner toute mise en cache et de simplement transférer les données aussi directement que possible du lecteur de disque vers votre mémoire, où vous pourrez les traiter. Dans un système de type Unix, c'est probablement open() et read() (et cela ne vous rapportera pas beaucoup). Sous Windows, il s’agit de CreateFile et ReadFile passer l'indicateur FILE_FLAG_NO_BUFFERING à <=> - et le débit sera probablement environ deux fois plus rapide si vous le faites correctement.

Vous avez également obtenu des réponses recommandant d'effectuer le traitement à l'aide de divers concepts parallèles. Je pense que ceux-ci sont fondamentalement erronés. À moins que vous ne fassiez quelque chose d'horriblement stupide, le temps nécessaire pour compter les mots du fichier ne durera que quelques millisecondes de plus que la simple lecture du fichier.

La structure que j’utiliserais serait d’avoir deux tampons de, disons, un mégaoctet chacun. Lire les données dans un tampon. Tournez ce tampon sur votre thread de comptage pour compter les mots qu'il contient. Pendant ce temps, lisez les données dans le deuxième tampon. Lorsque cela est fait, permutez les tampons et continuez. Il faut un peu plus de traitement en échangeant les tampons pour traiter un mot qui peut franchir la limite d'un tampon à un autre, mais c'est assez trivial (fondamentalement, si le tampon ne se termine pas par un blanc espace, vous êtes toujours dans un mot lorsque vous commencez à utiliser le prochain tampon de données).

Tant que vous êtes certain que ce logiciel ne sera utilisé que sur une machine multiprocesseur (multi-core), l'utilisation de vrais threads convient parfaitement. S'il y a une chance que cela se produise sur une machine monocœur, vous feriez mieux d'utiliser un seul thread avec des E / S superposées.

Answer 5

Comme d'autres l'ont indiqué, le goulot d'étranglement sera constitué par les E / S du disque. Je vous suggère donc d’utiliser des E / S superposées. Cela inverse la logique du programme. Au lieu de choisir votre code pour déterminer quand utiliser les E / S, vous indiquez simplement au système d’exploitation d’appeler votre code dès qu’il a terminé un peu d’E / S. Si vous utilisez les ports d'achèvement d'E / S , vous pouvez même indiquer le Le système d'exploitation doit utiliser plusieurs threads pour traiter les fragments de fichier.

Answer 6

solution à base de c?

Je pense que Perl est né dans ce but précis.

Answer 7

flux n'a qu'un seul curseur. Si vous accédez au flux avec plusieurs threads à la fois, vous ne serez pas sûr de lire où vous voulez. La lecture se fait à partir de la position du curseur.

Ce que je voudrais faire est de n'avoir qu'un seul thread (peut-être le principal) qui lit le flux et envoie des octets de lecture à d'autres threads.

Par exemple:

• Le fil #i est prêt et demandez au fil principal de lui donner la partie suivante,
• Le fil principal lit 1 Mo suivant et les fournit au fil 1,
• Le fil de discussion #i lit le 1 Mo et compte les mots que vous voulez,
• Le fil de discussion #i termine son travail et redemande le prochain Mo.

De cette manière, vous pouvez séparer la lecture de flux en analyse de flux.

Answer 8

Ce que vous recherchez, c'est RegEx. Ce thread Stackoverflow sur les moteurs de regex c ++ devrait vous aider:

C ++: quelle bibliothèque d'expressions régulières dois-je utiliser?

Answer 9

Tout d’abord, je suis presque sûr que C / C ++ n’est pas le meilleur moyen de gérer cela. Idéalement, vous utiliseriez aussi un peu de carte / réduction pour le parallélisme.

Mais, en tenant compte de vos contraintes, voici ce que je ferais.

1) Divisez le fichier texte en morceaux plus petits. Vous n'êtes pas obligé de faire cela à la première lettre du mot. Divisez-les simplement en fragments de 5000 mots, par exemple. En pseudocode, vous feriez quelque chose comme ceci:

index = 0

numwords = 0

mysplitfile = openfile (index-split.txt)

while (bigfile > > mot)

mysplitfile << word

numwords ++

if (numwords > 5000)

    mysplitfile.close()

    index++

    mysplitfile = openfile(index-split.txt)

2) Utilisez une structure de données de carte partagée et des pthreads pour créer de nouveaux threads afin de lire chacun des sous-fichiers. Encore une fois, pseudocode:

maplock = create_pthread_lock ()

sharedmap = std :: map ()

pour chaque fichier index-split.txt:

spawn-new-thread(myfunction, filename, sharedmap, lock)

dump_map (sharedmap)

annule ma fonction (nom du fichier, sharedmap) {

localmap = std::map<string, size_t>();

file = openfile(filename)

while (file >> word)

    if !localmap.contains(word)
         localmap[word] = 0

    localmap[word]++

acquire(lock)
for key,value in localmap
    if !sharedmap.contains(key)
         sharedmap[key] = 0

    sharedmap[key] += value
release(lock)

}

Désolé pour la syntaxe. J'ai écrit beaucoup de python ces derniers temps.

Answer 10

Pas C, et un peu moche, mais il n'a fallu que 2 minutes pour frapper:

perl -lane '$h{$_}++ for @F; END{for $w (sort {$h{$b}<=>$h{$a} || $a cmp $b} keys %h) {print "$h{$w}\t$w"}}' file > freq

Boucle sur chaque ligne avec -n
Divisez chaque ligne en @F mots avec -a
Chaque $_ hachage incrémenté de mots %h
Une fois que le END de file a été atteint,
sort le hachage par la fréquence $h{$b}<=>$h{$a}
Si deux fréquences sont identiques, triez-les par ordre alphabétique $a cmp $b
Imprimer la fréquence $h{$w} et le mot $w
Rediriger les résultats vers le fichier 'freq'

J'ai exécuté ce code sur un fichier texte de 3,3 Go contenant 580 000 000 mots.
Perl 5.22 terminé en 173 secondes.

Mon fichier d'entrée avait déjà la ponctuation supprimée et convertie en majuscule en minuscule, en utilisant ce morceau de code:
perl -pe "s/[^a-zA-Z \t\n']/ /g; tr/A-Z/a-z/" file_raw > file
(durée d'exécution de 144 secondes)

Le script de comptage de mots peut également être écrit en awk:
awk '{for (i=1; i<=NF; i++){h[$i]++}} END{for (w in h){printf("%s\t%s\n", h[w], w)}}' file | sort -rn > freq