Jak szybko przeczytać konkretną linię w pliku tekstowym, bez wczytywania całego pliku?

Czołem.

Bez kodu będzie za to spróbuję wyjaśnić gdzie leży problem i może ktoś mi podpowie jak skutecznie go rozwiązać.
Mam setki plików tekstowych w znanym formacie. Konkretnie są to pliki zawierające informacje o numerycznym modelu terenu. Taka siatka z oczkiem co 1 m gdzie w węzłach tej siatki podane są wartości nad poziom morza. Pliki te pokrywają swoim zasięgiem (przestrzennym) jakiś fragment np gminy.

Użytkownik ma do dyspozycji środowisko w którym rysuje coś, np przebieg dróg, sieci miejskich itp. Rysunek jest pierwotnie płaski, czyli bez składowej wysokości. W pewnym momencie użytkownik może zaznaczyć wiele punktów tej swojej struktury, dla których należy odczytać hurtem rzędne z wyżej wspomnianych plików. Może to zrobić później, nie w momencie rysowania swojego obrazka.

Struktura plików tekstowych jest taka, że łatwo mogę określić w której linii pliku i w której kolumnie tej linii znajduje się potrzebna mi liczba. Problemem jest jednak szybkie dotarcie do tej linii. Obecnie za pomocą ReadLn w pętli przeskakuję do oczekiwanej linii i później już leci. Niestety, ta część kodu zajmuje mi zdecydowanie najwięcej czasu i dla kilku tysięcy punktów potrafi skutecznie zadławić aplikację na kilka minut. Chciałbym skrócić ten czas ile się da ale nie kosztem wczytywania całego pliku do strumienia. To może być jeszcze bardziej czasochłonne. Owszem, jednorazowe wczytanie całego pliku i później wielokrotne przeszukiwanie go wydaje się być bardzo skuteczne do momentu, w którym okazuje się, że punkty leżą na obszarach opisanych dziesiątkami różnych plików i wtedy zaczyna się sieczka, która w skrajnie niekorzystnym przypadku może prowadzić do sytuacji, gdzie co punkt to czytanie całej sekcji, która może mieć od kilkudziesięciu do kilkuset MB. Na SSD to jeszcze z bólem ale przejdzie natomiast na starszych maszynach już nie bardzo a że moimi klientami są póki co posiadacze maszyn z HDD więc wicie, rozumicie...

Myślałem nad wcześniejszym sortowaniem punktów tak by były ustawione grupami w każdej sekcji i wtedy każdą sekcję w całości czytam raz ale to będzie wymagać głębokiej rzeźby w obecnym kodzie. Zanim to popełnię chciałem zapytać o jakieś skuteczniejsze pomysły. Najlepiej gdyby udało się załatwić to przez coś na kształt ReadLn(f, nr_linii, string_z_linią) no ale nie sądzę by to było w zasięgu.

Wyznaczanie linijki w pliku można optymalizować, ale nie przykryje to faktu, że taka struktura pliku jest po prostu nieodpowiednia do zadania. Zamiast tego raczej powinieneś pomyśleć nad zmianą trzymanego formatu (ew. konwersją). Może możesz użyć po prostu sqlite? Coś takiego powinno dać sensowną wydajność.

@szatkus: te pliki pokrywają (prawie) całą Polskę i są do ściągnięcia m.in. z geoportalu.
@enedil: to nie jest mój format tylko ArcInfo ASCII Grid - taki standard w GIS

Zbuduj sobie DOM z tych punktów — dzięki temu przeskok do dowolnego punktu potrwa w mikrosekundę.

A najlepiej to pobierz sobie te dokumenty, hurtem przekonwertuj na postać binarną i takie pliki amorficzne dostarczaj z aplikacją. W razie potrzeby aktualizacji tych plików, dorzuć do aplikacji konwerter. Plik binarny, w którym każdy punkt znajduje się w znanej lokalizacji (znany offset), zapewni ultra-szybki dostęp do dowolnych punktów.

enedil napisał(a):

Wyznaczanie linijki w pliku można optymalizować, ale nie przykryje to faktu, że taka struktura pliku jest po prostu nieodpowiednia do zadania. Zamiast tego raczej powinieneś pomyśleć nad zmianą trzymanego formatu (ew. konwersją). Może możesz użyć po prostu sqlite? Coś takiego powinno dać sensowną wydajność.

@Rhode nie protestuj na uwagę @enedil bo to prawda.

To, ze format pliku tekstowego sprawdza się w dystrybucji danych, to nie znaczy, że ma cokolwiek wspólnego z wydajną pracą dla danych "tu i teraz".

Tak jak nikt nie tworzy programu, który w czasie rzeczywistym będzie stale korzystał z kursów NBP (choć przecież są de facto standardem), tylko je odkopiowuje do sensowych struktur własnych.
Do rządu wysyłasz XMLe, choć ani po twojej stronie program nie pracuje na XMLach, ani po ich (są to bazy danych)
To się po prostu tak projektuje.

UPDATE2: plik do dystrybucji danych, nie wyobrażam sobie w otwartym społeczeństwie inaczej niż tekstowy
Plik "do pracy" nie wyobrażam sobie inaczej niż binarny, ze sprytną strukturą, tu się rzekło indeksami, i podobnymi

relacyjną bazą danych o najlepszej tradycji do danych geograficznych to chyba jest Postgres

Dodam, istnieją bazy key-valuhttps://4programmers.net/e i podobne, o kosmicznej wydajności, przy niewielkim CPU i RAM, bez interpretera języka SQL. W latach młodych 1990tych coś takiego było i Turbo Pascal.

EDIT: gdybym sam miał to robić, bym chyba wybrał jakiś multi-map (tak jak to się nazywa w normalnych językach), z dostępem po X,Y, numerze punktu itd ...
Zależnie od rzeczywistego rozmiaru angażowanych danych, z backendem plikowym, lub (nadmierny optymizm???) wyłącznie w RAM

szatkus napisał(a):

No i ostatnio zdarzyło mi się coś napisać w Pascalu i z tego co pamiętam to ReadLn okazał się strasznie wolny (miałem nawet implementację w Pythonie, która była znacznie szybsza). TFileStream jest sporo szybszy.

W kontekście plików tekstowych, w których każda linia może mieć różną długość, strumień niewiele pomoże.

Jedyne co w takim przypadku może być zoptymalizowane to samo ładowanie danych z pliku, bo ono jest wąskim gardłem. Tak więc szybciej na pewno będzie wczytać cały blok danych z pliku i go odpowiednio obrobić (podzielić na linie/pakiety danych), niż czytać linijkami bezpośrednio z pliku (co oznacza de facto bajt po bajcie, a więc najwolniej jak się da). Tak jest to zoptymalizowane w przypadku TStringList.LoadFromFile — wczytywanie odbywa się w kilobajtowych paczkach i te paczki są dzielone na linie (przynajmniej we Free Pascalu).

Sam bym się na pewno w dane tekstowe nie bawił, a przerobił te wszystkie pliki na binarne. Kwestia jest tylko taka, jak często te pliki mają być aktualizowane i czy taką aktualizację może wykonać sam użytkownik.

Kilka lat temu mieliśmy podobny problem jednak struktura pliku była stała każda linia miała n byte więc czytaliśmy bezpośrednio adres z dysku gdzie linia * n byte w linii dawała adres poczatku linii, którą mieliśmy odczytać.

Najlepiej to nie rozwiązywać problemów, które już rozwiązano i wrzucić to sobie do bazy danych np sqlite.

Nikt normalny nie będzie skakał po tych plikach i przeszukiwał, raczej napisz narzędzie importujące ich zawartość do bazy, a aplikacja ma korzystać z bazy. W razie potrzeby odświeżysz bazę nowymi danymi z plików i tyle.

Może przyda się to Szybki sposob na zliczanie danych w plikach

Nie, ten wątek nie przyda się, bo jest w nim taki bajzel, że szkoda czasu na jego czytanie. :D

To co należy zrobić to albo wczytać całą zawartość pliku(ów) do pamięci (jeśli danych nie jest za dużo) i wrzucenie ich do kontenera, który pozwala wygodnie skakać po paczkach danych, albo przerobić te pliki na takie, które pozwolą na wygodny odczyt dowolnej paczki, bez konieczności ładowania całej zawartości do pamięci. Mogą to być pliki binarne o stałym rozmiarze paczek i znanych offsetach (oraz danych natywnych, nie w formie tekstu) lub zwykła baza danych.

Od biedy można te pliki po prostu edytować i dorzucić białe znaki na końcu każdej linii, tak aby wszystkie linijki miały identyczną długość bajtową. W takim przypadku da się łatwo skakać po linijkach (wystarczy prosta arytmetyka), jednak ciągła konwersja tekstu na dane natywne, będzie obniżać wydajność.

Jednak w dalszym ciągu nie wiemy ile jest tych plików, nie wiemy też ile w każdym pliku jest paczek danych, a także nie wiemy ile plików jest wykorzystywanych podczas edycji/renderowania rysunku. Może ich być kilkadziesiąt, a może być ich dziesiątki tysięcy — nie znamy łącznej wagi plików. Dane w pamięci mogą zajmować 100MB, a mogą też zajmować 10GB.

Jak się nie zna konkretów to można co najwyżej zgadywać.