Leggyakoribb szó több text fájlban párhuzamosítva C++-ban

Leggyakoribb szó több text fájlban párhuzamosítva C++-ban
2014-06-18T15:22:32+02:00
2014-07-29T08:43:07+02:00
2022-12-01T10:00:41+01:00
thehornet
Sziasztok!
Kaptam egy feladatot, ami így hangzik:
"Hozzon létre egy olyan C nyelvben írt programot, amely képes párhuzamosított eljárással kikeresni több szövegállományból azt a szót, amely az összes közül a leggyakrabban fordul elő."
Ezen kívül "szakirodalom gyanánt" ezt ajánlotta a yanárom: Colin Campbel, Ade Miller: Parallel Programming with Microsoft Visual C++, 2011 (24. oldal, Exercises 1.f.). Az a gond a szakirodalommal, hogy ott csak rédésként szerepel a feladatom (hogy megoldható-e egyáltalán).
Az lenne a kérésem, hogy valaki tudna-e egy ilyen progit írni? A lényeg a párhuzamosításon van, vagyis a bevitt fájlok párhuzamos feldolgozásán OpenMP segítségével.

Az igazság az, hogy csináltam valamit, de nem működik. Nagyon gagyiul először a fájlokat egy fájllá gyűrném össze (temp.txt) és utána abból keresné ki a leggyakoribb szót. Ez is több, mint a semmi, de ez sem működik.
Mindenesetre felteszem ide az összeszedett kódot, hátha valaki valamit kihámoz belőle.

// Project X.cpp : Defines the entry point for the console application. // #include"stdafx.h" #include <stdio.h> #include <stdlib.h> #include <iostream> #include "omp.h" #include "time.h" int fajlfelfuzes() { FILE *befilenev, *kifilenev; char ch, file[20]; int i=0, fajlszam; ///PROBAKENT // printf("Hany fajllal szeretne dolgozni? Kerem vigye be: "); // scanf_s("%d",&fajlszam); printf("Kerem vigyen be harom a fajlnevet: \n"); while (i!=3) //// ITT A GOND: NEM TUDOM HOGYAN KELL KILEPNI A CIKLUSBOL ENTERREL { // printf("A(z) %d. fajl neve a %d-bol: ",i,fajlszam); gets_s(file); // printf("\n"); befilenev = fopen(file,"r"); kifilenev = fopen("temp.txt","a"); //temp.txt-be irja a bekert fajlok tartalmat while( ( ch = fgetc(befilenev) ) != EOF ) fputc(ch,kifilenev); fputc(' ',kifilenev); //Az utolso szo utan hagy egy ures helyet, hogy ne irodjanak egybe a szavak i++; //PROBAKENT fclose(befilenev); fclose(kifilenev); } return 0; } /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// int szamlalo_szimpla(FILE *bemenofile) { FILE *befilenev, *fp; int szam=0, result=0; char a[80][80], string[10000], text[1000], words[1000][1000], temp[1000]; int i, j, k, n, count, vegallas; i = j = k = n = 0; int max=0; for(szam=0; szam<result; szam++) { fp=fopen("temp.txt","r"); if((fopen_s(&fp, a[szam], "r")) != NULL) { return(-1); } while(fgets(string, 10000, fp) != NULL) { printf_s(string); // copying each and every word from the string while (string[i] != EOF && string[i] != '\n') { if (string[i] == ' ') { words[j][k] = '\0'; k = 0; j++; } else { words[j][k++] = string[i]; } i++; } } words[j][k] = '\0'; n = j; // sort the words in the given string for (i = 0; i < n; i++) { strcpy_s(temp, words[i]); for (j = i + 1; j <= n; j++) { if (strcmp(words[i], words[j]) > 0) { strcpy_s(temp, words[j]); strcpy_s(words[j], words[i]); strcpy_s(words[i], temp); } } // find the frequency of each word and print the results while (i <= n) { count = 1; if (i != n) { for (j = i + 1; j <= n; j++) { if (strcmp(words[i], words[j]) == 0) { count++; } } } printf("%s\t%d\n", words[max], count); i = i + count; } } i = 0; // az osszeset hogy kiirja // find the frequency of each word and print the results while (i <= n) { count = 1; if (i != n) { for (j = i + 1; j <= n; j++) { if (strcmp(words[i], words[j]) == 0) { count++; } } } // count - indicates the frequecy of word[i] if (count > max ){ max = count; } // printf("\t\t\t%d\n", max); // skipping to the next word to process i = i + count; } } return 0; } int main() { fajlfelfuzes(); szamlalo_szimpla("temp.txt"); system("pause"); return 0; }
Van valamilyen ötletetek? Köszönöm előre is!
Mutasd a teljes hozzászólást!

  • Nem álltam neki átbogarászni a kódot (sietős a dolgom), de én a következőképpen állnék neki:
    Egy párhuzamos rendezőalgoritmussal (a legjobb talán a sample sort) rendezném a szavakat ABC sorrendben. Előtte persze eltávolítod a nem betűket (vessző, pont stb) (vagy szóközzé alakítod őket), aztán felvágod a szóközök mentén.
    Maga a preprocessing O(n) idő alatt megvan (ha ezt is párhuzamosítod, akkor O(n / k)), a rendezés utána ha jól emlékszem O(n*log(n) / k) (ahol a "k" a szálak száma).

    Ezután szintén párhuzamosan végigfutsz ezen a rendezett listán (Pl első szál nullánál kezd, második szál 1000-nél, stb - ezt gondolom úgyis érted) és pl egy thread-safe hashmapben számolod az egyes szavak előfordulását.
    A hashmap-et esetleg úgy is meg lehet csinálni, hogy jelölje mindig külön, hogy melyik az aktuálisan legmagasabb értékű tagja.
    Ez az átfutás O(n / k) idő alatt megvan.

    Így az egész gyönyörűen párhuzamosítható, szinte minimális lockkal.
    (Ha nem tárolja külön a hashmap a legmagasabb értékű tagot, akkor szinte kizárt a lock, ha igen, akkor az elején lesz pár várakozás, aztán egyre kevesebb.)


    Szerk.:
    Most látom, hogy több szövegfájlról van szó. Ha csak így kell párhuzamosítani, akkor sokkal egyszerűbb a feladat:
    Ha van N szövegfájlod, indítasz N szálat:
    Mindegyik szál rendezi a saját dokumentumának a szavait, végigfut rajta és egy fent leírt Thread-Safe hashmapben számolja a gyakoriságokat.
    Mutasd a teljes hozzászólást!
  • Az OpenMP 4.0 már támogat user defined reduction-t :)

    Még nem használtam, meg szerintem nem is sok fordító támogatja még (GCC 4.9 igen azt tudom).
    Azzal elvileg nagyon egyszerűen meglehet oldani :)

    Majd ha otthon leszek és lesz kis szabadidőm lehet kipróbálom. user defined reduction nélkül már nem lesz olyan szép a kód :(
    Mutasd a teljes hozzászólást!

  • Az lenne a kérésem, hogy valaki tudna-e egy ilyen progit írni? A lényeg a párhuzamosításon van, vagyis a bevitt fájlok párhuzamos feldolgozásán OpenMP segítségével.

    Hogy a kérdésre is válaszoljak, igen én pl. tudok ilyen programot írni 

    Most C vagy C++? C++ a téma, de a kódod az színtiszta C első pillantásra C style stringek, printf-ek, FILE*...
    Mutasd a teljes hozzászólást!
  • Nem többszálúság hanem párhuzamosság kell, a kettő nem ugyanaz, vagy csak részben.
    Az ajánlott könyv is a párhuzamosság irányába mutatna.

    Egyébként a megoldásod ok, csak nem több szálra kellene ezt szétpakolni, hanem több magra de van ehhez külön gyűjteménye már az MS-nek.

    Még azt nem vágtam le, hogy minek sorba-rendezni a szavakat??? 
    Eleve a tokenizációt is on time csinálnám, minél kisebb egységekre lehet felosztani a feladatokat, annál hatékonyabb tudd lenni a párhuzamosítás.

    Mondjuk szerintem a fájl beolvasást, nem érdemes párhuzamossá tenni, legalábbis valószínűleg nem sokat segít, bár függ a fájlok mérettől is.

    Szóval szerintem a fájlokat, be kell olvasni a memóriába külön külön területre, és azokon futtatni párhuzamosan a tokenizációt, a tokeneket lehetne külön
    map-be, vagy ha tetszik hash map-be pakolni (thread safe módon persze.)

    Így nincs előfeldolgozás stb....
    Mutasd a teljes hozzászólást!
  • Egyébként a megoldásod ok, csak nem több szálra kellene ezt szétpakolni, hanem több magra de van ehhez külön gyűjteménye már az MS-nek.

    Hát pedig de.

    Egyébként meg olvasd el értően a hozzászólásom "szerk" utáni részét. Ugyanazt írtam le, amit te.
    Mutasd a teljes hozzászólást!
  • A multi threading és a párhuzamos feldlgozás nagyon nem egyezik.

    Erről sdzerintem kár vitázni. A ferladat nem multithreading, hanem párhuzamos feldolgozás.
    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd