Szybkie wczytywanie dużych plików

Witam,
Mam do wczytania plik, którego linie można liczyć w dziesiątkach, a w przyszłości, w setkach tysięcy. Jak najszybciej wczytać linijka po linijce?

póki co mam tak:

load.open(filename);
		if(!this->file_exists())
			throw new FileNotFoundException("Plik nie istnieje");

		load.seekg(0,ios::end);
		int lenght = load.tellg();
		load.seekg(0,ios::beg);
		buf = new char[lenght];
		load.read(buf,lenght);
		
		ss<<buf;
		delete []buf; 

a potem już pobieranie z ss do obiektu klasy vector - listaRekordow

 
while(getline(ss,tmp))
		{
				if(tmp=="")
					continue;
				listaRekordow.push_back(tmp);
		}

Wczytywanie trwa szybko, jednakże może jest sposób, który jest optymalny względem tego?

pozdrawiam

Myślę, że powinieneś otworzyć strumień i pętlą while wkładać plik do vectora za pomocą getline. Po co te kopiowanie? Teoretycznie powinno przyśpieszyć późniejsze wczytywanie linia po linii, ale zastanawiam się, czy os nie zrobi tego za Ciebie. (Przynajmniej w przypadku niewielkich plików powinien)

Może chciałbyś się zainteresować http://en.wikipedia.org/wiki/Memory-mapped_file :-P

Endrju napisał(a)

Myślę, że powinieneś otworzyć strumień i pętlą while wkładać plik do vectora za pomocą getline. Po co te kopiowanie?

Wydawało mi się, że szybciej będzie wpierw wszystko wrzucić do buffer a potem do ss, który jest obiektem klasy stringstream i dopiero później getline wyciągać to do vectora. Gdzieś chyba wyczytałem, że wyciąganie danych bezpośrednio z obiektu fstream jest mocno nieoptymalne, ale nie wiem ile w tym prawdy.

Endrju napisał(a)

Może chciałbyś się zainteresować http://en.wikipedia.org/wiki/Memory-mapped_file :-P

ano zapoznam się. dzięki!

Porada jak będziesz optymalizował - mierz, mierz i mierz. Rozwiązanie ze stringstreamem wcale nie musi być szybsze niż cin, szczególnie z wyłączoną synchronizacją ze stdin. Pamiętaj też, że np. w GCC nadal szybsze są funkcje C niż strumienie, choć to też byś musiał przetestować. Możesz spróbować wczytać do dużego buforu (mieszczącego na pewno cały plik) zawartość pliku przez fread i dzielić przez strtok, używając w reszcie programu odpowiednich wskaźników do char*. Dodatkowo zmierzyłbym ile zajmuje wczytywanie danych najprostszą metodą w stosunku do całego czasu działania programu, w końcu coś z tymi danymi musisz robić, jeżeli zajmuje to 10% czasu, to przyspieszając dwukrotnie program będzie działał tylko 5 % szybciej, co może nie być wystarczające do wytłumaczenia stosowania bardziej skomplikowanego kodu.

Zdecydowanie, sprawdzenie kilku rozwiązań jest dobrym pomysłem. Wydaje mi się jednak, że nie warto cudować dla pliku, który ma 1MiB. Chociaż pewnie warto przetestować to dla własnej satysfakcji. ;-)

Skoro wiesz co trwa u Ciebie najdłużej najpierw zajmij się tym. Profiler na pewno Ci pomoże.

No właśnie, robisz pewnie knn kwadratowo, co jest bardzo nieoptymalne. Ja bym spróbował użyć jakiś linesweep, naiwny będzie i tak dla małego k o wiele bardziej optymalny. Ogólnie ja najpierw robię działający program (lub część), po tym optymalizuje algorytmicznie (często wcześniej, ale dla bardziej skomplikowanych algorytmów dobrze jest mieć implementację wzorcową), a na samym końcu właściwą optymalizację tam, gdzie tego potrzeba. Nawet używając lepszych algorytmów i tak czas wczytania danych w tym wypadku będzie pomijalny.

edit: line sweep to było złe określenie, chodziło mi bardziej o szukanie w punktach posortowanych względem jednej współrzędnej, dzięki czemu ilość odległości do porównania można bardzo ograniczyć. Innym podejściem może być podzielenie przestrzeni na ileś segmentów dla każdego wymiaru i szukanie rozpocząć od najbliższych kwadratów (dla 2d). Wszystkie te optymalizacje niestety zawodzą, jak twoja przestrzeń ma zbyt dużo wymiarów, wtedy to najszybsze może być liczenie odległości między każdą parą punktów, zainteresuj się bibliotekami do obliczeń macierzowych.

Zjarek napisał(a)

edit: line sweep to było złe określenie, chodziło mi bardziej o szukanie w punktach posortowanych względem jednej współrzędnej, dzięki czemu ilość odległości do porównania można bardzo ograniczyć.

Chwila, jeśli dobrze rozumiem, to właśnie to robię. Wpierw dostaje 25000 obiektów z pewnymi etykietami/klasyfikatorami. Ja daje mu jeszcze jeden obiekt, który jednak nie ma klasyfikatora i wszystkie dane są sortowane względem tego nowego obiektu.

if(w[i+1].element().interval(x)<w[i].element().interval(x)) 

gdzie x jest tym elementem względem którego sortowane są elementy żeby potem przypisać mu najczęściej występujący klasyfikator w k-najbliższych sąsiadach

Mam dodatkowo problem przy wczytywaniu danych do buf, gdyż po alokacji pamięci

 buf = new char[lenght];

buf przechowuje ciąg takich znaków: -51 'Í'
i nie wiem jak tego się pozbyć przed wczytaniem danych gdyż już po wczytaniu te znaki wciąż widnieją na końcu tablicy, co jest problemem przy zamienianiu chara na liczby

EDIT: w sumie, to mi nie przeszkadza... ale i tak ciekawi mnie skąd bierze się akurat taki znak i to w liczbie mnogiej?

Dlaczego to miałby być problem? Na końcu c-stringa powinieneś mieć \0 żeby takich problemów nie było.

Moim zdaniem żeby zrobić to naprawdę sprawnie, wystarczyłoby znać liczbę linii pliku albo na początku ją sprawdzić a potem podzielić całość na proporcjonalną ilość wątków i odpowiednia na nich działać żeby jednocześnie pracowały.
Wydaje mi się to być najłatwiejszym rozwiązaniem.

Mackos napisał(a)

Moim zdaniem żeby zrobić to naprawdę sprawnie, wystarczyłoby znać liczbę linii pliku albo na początku ją sprawdzić a potem podzielić całość na proporcjonalną ilość wątków i odpowiednia na nich działać żeby jednocześnie pracowały.
Wydaje mi się to być najłatwiejszym rozwiązaniem.

Pracowałem z wątkami tylko w C#. Kompletnie nie wiem jak to się robi w C++ i jakby wydaje się, że nie ma dużo materiału w internecie. Jak rozumiem boost::Thread jest najlepszym rozwiązaniem? Przydałby się jakiś dobry, prosty przykład.