Poruszanie się po dużym pliku tekstowym

Witajcie! W ramach zaliczenia jednego z przedmiotów mamy do napisania program, który wyszuka w pliku wybrane przez użytkownika dane. Problem polega na tym, że cały plik zajmuje 300 megabajtów! Szukamy podpowiedzi, jak można owe wyszukiwanie rozwiązać stosunkowo dobrze - to znaczy powinno się ono odbywać relatywnie szybko (by użytkownik nie czekał za długo na odpowiedź programu). Cały plik składa się z sekcji - każda z nich prezentuje się mniej więcej tak:

NAGŁÓWEK
DANE
DANE
DANE

end

Liczba linijek z danymi jest różna (i składa się z różnej ilości znaków, podobnie jak nagłówek).

Oczywiście w przypadku, gdy plik ma ponad trzy i pół miliona linii tekstu, zastosowanie metody getline() odpada. Czy znacie jakąś funkcję/bibliotekę/sprawdzone rozwiązanie, które może ułatwić pracę na tak olbrzymim pliku z danymi?

PS: Oczywiście mamy stworzyć aplikację konsolową.

Wczytuj dane dużymi buforami, aby znacząco zwiększyć prędkość wczytywania danych.

Dużymi - to znaczy jaką maksymalnie mogę określić wielkość buforu? Dzisiaj coś z tym kombinowałem, ale teraz pytanie - jak odnosić się później do konkretnego bufora, aby nie czytać wszystkich po kolei w sytuacji, gdy np. informacja jest w ostatnim wczytanym buforze?

PS: Nasunęło mi się kolejne pytanie - jak mogę indeksować te bufory? Wymyśliłem sobie zapisywanie zawartości konkretnych buforów do indeksowanej dynamicznej tablicy stringów i późniejsze sprawdzanie, czy w danym stringu jest szukana przeze mnie informacja. Chociaż nie wiem, na ile będzie to dobre rozwiązanie.

tomciozdwola napisał(a):

Oczywiście w przypadku, gdy plik ma ponad trzy i pół miliona linii tekstu, zastosowanie metody getline() odpada.

Wygenerowalem przed chwila plik o rozmiarze 314 MB, ktory posiadal 10 mln linii tekstu. Przeczytanie tego pliku za pomoca getline trwalo u mnie 1.81336 sek. Przeczytanie tego samego pliku bez uzycia strumieni (funkcja fgets z jezyka C) trwalo 0.885774 sek. Nie wydaje mi sie to jakos specjalnie dlugo. Mozna sie jeszcze pobawic funkcja read i funkcjami z WinAPI - byc moze uda sie przyspieszyc ale pytanie czy warto?

tomciozdwola napisał(a):

Dzisiaj coś z tym kombinowałem, ale teraz pytanie - jak odnosić się później do konkretnego bufora, aby nie czytać wszystkich po kolei w sytuacji, gdy np. informacja jest w ostatnim wczytanym buforze?

Bufor jest jeden. Czytasz dane z pliku po kawalku i wypelniasz na tej podstawie bufor. Bufor analizujesz w locie - po przeczytaniu kolejnej porcji danych zawartosc bufora powinna byc nadpisywana. Nie ma za bardzo sensu ladowac danych do wielu buforow, no chyba, ze chcesz czytac dane wielowatkowo, ale nie wiem na ile Ci to pomoze.

tomciozdwola napisał(a):

PS: Nasunęło mi się kolejne pytanie - jak mogę indeksować te bufory? Wymyśliłem sobie zapisywanie zawartości konkretnych buforów do indeksowanej dynamicznej tablicy stringów i późniejsze sprawdzanie, czy w danym stringu jest szukana przeze mnie informacja. Chociaż nie wiem, na ile będzie to dobre rozwiązanie.

Jezeli dobrze Cie zrozumialem, to nie wydaje mi sie to dobrym pomyslem. Zapychasz po prostu niepotrzebnie RAM, a Twoj program bedzie dzialal poprawnie do momentu az system przestanie tolerowac Twoje marnotrastwo - z 300 MB plikiem sobie pewnie poradzi ale z naprawde duzym zbiorem danych to raczej srednio. Pomijam juz fakt, ze jak bedziesz wszystko ladowal do pamieci to mozesz ten program spowolnic a nie przyspieszyc.

Powiedzmy 4 kilobajty. Albo 64.
Wielkość ma drugorzędne znaczenie, ważne że jakiś bufor przyjmujesz.

tomciozdwola napisał(a):

A wyświetlałeś wczytane dane na ekran? Powiem Ci, że gdy sam próbowałem przeczytać wszystkie informacje za pomocą getline() i wyświetlić na ekran - zajęło mi to piętnaście minut. Czy samo wyświetlanie może to powodować?

Owszem, wyswietlanie danych to najbardziej czasochlonna czynnosc w tym programie. Szczegolnie w sytuacji kiedy uzywales do tego cout'a - juz sama zmiana na printf czesto przyspiesza taki program.

Nie zmienia to jednak faktu, ze wyswietlanie wszystkich przeczytanych danych mija sie z celem - nie dosc ze nikt nie bedzie czytal 300 MB pliku to jeszcze takie wypisywanie dlugo trwa.

tomciozdwola napisał(a):

Możesz mi na PW podesłać kod tego programu? Aż nie chce mi się wierzyć, że trwało to ponad sekundę... :)

Napisalem cos takiego:

    ifstream stream("tu_sciezka_do_pliku");
    string line;
    while (!stream.eof())
    {                
        getline(stream, line);
        if (line.find("1055238") != string::npos) 
        {
            cout << line << endl;
        }
    }    
    stream.close();

Czyli wyszukalem fraze 1055238 w kazdej linii pliku tekstowego. Poniewaz program znalazl tylko jedno wystapienie takiej linii (malo danych do wyswietlenia) zajelo mu to 1.64167 sek. Zmierz u siebie i daj znac. Najlepiej wyszukaj fraze z konca pliku - bedziemy mieli pewnosc ze plik jest czytany do konca.