datei "halbieren" - zeile suchen

subject hört sich schon komisch an, aber was ich machen will ist recht
einfach:

ich habe eine ziemlich große datei die ich (derzeit) sequentiell lese
und dann mit dem inhalt der zeile etwas anstelle - was genau ist egal,
spielt für mein derzeitiges problem keine rolle ;-)

nun hab ich mir überlegt, dass es vielleicht sinn machen würde die
datei "aufzuteilen", so dass man evtl. mit mehr als einem thread oder
prozess arbeiten könnte.
ich würde also gerne (ungefähr) die hälfte der datei suchen und von
da an sequentiell bis zum ende laufen.
ich hab mir schon tail und readbackwards angeschaut - aber leider
bringt mir zumindest letzteres nichts.

da die zeilen nicht gleich lang sind kann ich doch auch bestimmt nicht
mit seek die "hälfte" suchen? oder funktioniert das vielleicht so,
dass man mit seek die "hälfte" sucht und dann einfach auf die nächste
zeile wechselt?=20

gruß
chunnell

Re: datei "halbieren" - zeile suchen

christrier wrote:

> da die zeilen nicht gleich lang sind kann ich doch auch bestimmt nicht
> mit seek die "hälfte" suchen? oder funktioniert das vielleicht so,
> dass man mit seek die "hälfte" sucht und dann einfach auf die nächste
> zeile wechselt?

Probiere einfach aus, was passiert, wenn Du in die Mitte
der Datei seekst und dann den Diamantoperator anwendest.
Ich vermute mal, dass das geht. Wenn Du die erste (nicht unbedingt
vollständige Zeile) wegwirfst, solltest Du danach
eine garantiert vollständige Zeile bekommen.

Grüße
Frank
--
Dipl.-Inform. Frank Seitz; http://www.fseitz.de/
Anwendungen für Ihr Internet und Intranet
Tel: 04103/180301; Fax: -02; Industriestr. 31, 22880 Wedel

Re: datei "halbieren" - zeile suchen

christrier schrieb:
> ich habe eine ziemlich große datei die ich (derzeit) sequentiell lese
> und dann mit dem inhalt der zeile etwas anstelle - was genau ist egal,
> spielt für mein derzeitiges problem keine rolle ;-)
>
> nun hab ich mir überlegt, dass es vielleicht sinn machen würde die
> datei "aufzuteilen", so dass man evtl. mit mehr als einem thread oder
> prozess arbeiten könnte.

Warum? Sind die gesuchten Zeilen immer an irgendeiner bestimmten Stelle?
Ansonsten wird dein Programm vermutlich langsamer, wenn du mit zwei
Threads dieselbe Datei durchsuchst.

> ich würde also gerne (ungefähr) die hälfte der datei suchen und von
> da an sequentiell bis zum ende laufen.
>
> da die zeilen nicht gleich lang sind kann ich doch auch bestimmt nicht
> mit seek die "hälfte" suchen? oder funktioniert das vielleicht so,
> dass man mit seek die "hälfte" sucht und dann einfach auf die nächste
> zeile wechselt?

Das kannst du machen. Aber du musst bitte noch einmal erklären, was du
genau machst, damit man sagen kann, ob du dann evtl. einen
Geschwindigkeitsvorteil hast. Wenn du eh die gesamte Datei durchlaufen
musst, ist ein einziger Thread vermutlich schneller.

Wolf

Re: datei "halbieren" - zeile suchen

Hallo chris

Frank und Wolf ja schon einiges dazu
gesagt, heir noch eine Anmerkung von mir ...

> ich habe eine ziemlich große datei die ich (derzeit) sequentiell lese
> und dann mit dem inhalt der zeile etwas anstelle - was genau ist egal,
> spielt für mein derzeitiges problem keine rolle ;-)

was ist denn "ziemlich gross"? 50MB? 500MB? 5000MB?

> nun hab ich mir überlegt, dass es vielleicht sinn machen würde die
> datei "aufzuteilen", so dass man evtl. mit mehr als einem thread oder
> prozess arbeiten könnte.

Wieviele unabhängige IO-Kanäle hat Dein Serversystem?
Wieviele CPU's hat Dein Serversystem?

Je einen? Dann ist jeder zusätzliche Thread
kontraproduktiv, grob betrachtet.

> ich würde also gerne (ungefähr) die hälfte der datei
> suchen und von da an sequentiell bis zum ende laufen.
> ich hab mir schon tail und readbackwards angeschaut -
> aber leider bringt mir zumindest letzteres nichts.

Erwäge doch mal, mit des sys-Funktionen
anzufangen (vgl. http://www.xav.com/perl/lib/Pod/perlfunc.html#item_sysseek)
- sysopen
- sysread
- sysseek

Auf welchem OS soll das passieren?

Grüße

M.

Re: datei "halbieren" - zeile suchen

christrier schrieb:

> da die zeilen nicht gleich lang sind kann ich doch auch bestimmt nicht
> mit seek die "hälfte" suchen? oder funktioniert das vielleicht so,
> dass man mit seek die "hälfte" sucht und dann einfach auf die nächste
> zeile wechselt?

Unter der Annahme, dass die Hälfte der Zeilen sich ungefähr in der Mitte des
Files befindet, kannst du mit stat und seek in die Mitte des Files wechseln
und dort dann ab der nächsten Zeile lesen.

Allerdings wird dein Programm möglicherweise durch die Geschwindigkeit der
Harddisk begrenzt, so dass ein zweiter Thread das Programm möglicherweise
sogar langsamer macht.

Je nach Betriebssystem könnte dich Sys::Mmap interessieren, da dadurch die
betriebssysteminterne Herumkopiererei von von der HD gelesenen Daten z.T.
umgangen wird. Wenigstens auf Linux ist Lesen von Files über mmap() in der
Regel einiges schneller als über read().

Gruss

Roman°
--
IRC Freenode, Channel: #usenet-friends
NEU: Das Web-Interface zum Channel:
---------------> http://albasani.net/cgiirc/irc.cgi <----------------

Re: datei "halbieren" - zeile suchen

Roman Racine writes:

[...]
> Je nach Betriebssystem könnte dich Sys::Mmap interessieren, da dadurch die
> betriebssysteminterne Herumkopiererei von von der HD gelesenen Daten z.T.
> umgangen wird. Wenigstens auf Linux ist Lesen von Files über mmap() in der
> Regel einiges schneller als über read().

mmap ist ein Standard-PerlIO-Layer. Man kann also schreiben:

open my $k, "<:mmap", $file or die;

Ein Test mit ktrace unter FreeBSD hat ergeben, dass tatsächlich mmap()
verwendet wird (und komischerweise für die letzten Bytes der Datei ein
normales read()).

Gruß,
Slaven

--
Slaven Rezic - slaven rezic de
babybike - routeplanner for cyclists in Berlin
handheld (e.g. Compaq iPAQ with Linux) version of bbbike
http://bbbike.sourceforge.net

Re: datei "halbieren" - zeile suchen

sorry, war paar tage nicht am rechner ;-)

insgesamt hat der server 4 prozessoren, aber ich hab keine ahnung
wieviele io-kanäle der server hat.
mir ist nur mal bei einem top aufgefallen, dass nur ein prozessor
arbeitet und die anderen nichts machen und irgendwie hat mich das
genervt ;-)
ich wollte daher die anderen prozessoren dazu bringen auch etwas zu
arbeiten - von daher die idee mit den mehreren threads (bzw. zwei
threads).

das die hd das ganze wieder ausbremst ist mir im ersten moment gar
nicht aufgefallen, aber noch mal danke für den hinweis.

ach ja, die datei hat knapp 2,2 millionen zeilen und die zweite datei
hat 70.000 zeilen. aber es werden halt nicht für alle zeilen aus der
ersten datei zeilen aus der zweiten datei gesucht - nur wenn sie einem
gewissen muster entsprechen.

da ich das nun doch nicht implementieren werde möchte ich mich
trotzdem für die anregungen von euch bedanken!=20

gruß

christopher

Re: datei "halbieren" - zeile suchen

christrier schrieb:

> sorry, war paar tage nicht am rechner ;-)
>
> insgesamt hat der server 4 prozessoren, aber ich hab keine ahnung
> wieviele io-kanäle der server hat.
> mir ist nur mal bei einem top aufgefallen, dass nur ein prozessor
> arbeitet und die anderen nichts machen und irgendwie hat mich das
> genervt ;-)
> ich wollte daher die anderen prozessoren dazu bringen auch etwas zu
> arbeiten - von daher die idee mit den mehreren threads (bzw. zwei
> threads).
>
> das die hd das ganze wieder ausbremst ist mir im ersten moment gar
> nicht aufgefallen, aber noch mal danke für den hinweis.

Ob das wirklich so ist, hängt ganz entscheidend davon ab, wie
CPU-aufwendig das ist, was Du machst.
Wenn Dein Programm allein läuft, was sind denn dann die Werte für
user, sys und wait?
Wenn user deutlich größer als sys und wait nur wenig über null, dann
lohnt sich Deine Idee vermutlich. Selbst mit einem einzigen Prozessor
könnte es sich lohnen, wenn idle nahe bei 50 liegt.
Du kannst das übrigens ausprobieren, ohne Dein Programm umzuschreiben:
Mach einfach 2 Testläufe. Beim ersten Testlauf nimmst Du die Zeit für
eine Ausführung mit der großen Datei. Dann nimmst Du die Zeit für 2
parallele Ausführungen mit je einer Hälfte der Datei (die Hälften
kannst Du mittels wc -l und head bzw. tail leicht herstellen).

Man kann den Ansatz nochmal optimieren, wenn die Reihenfolge der
Ergebnisse nicht gar so wichtig ist. Dann würde ich zwei Prozesse
machen, wobei (über ein Flag steuerbar) der eine nur die ungeraden,
der andere nur die geraden Zeilen verarbeitet. Damit erreichst Du
folgendes:
a) der erste Prozess muß nicht ständig prüfen, ob er schon über die
Hälfte hinaus ist
b) beide Prozesse arbeiten höchstwahrscheinlich gleichzeitig auf
demselben Datenblock bzw. der langsamere auf einem Datenblock, der
schon vom schnelleren Prozess real gelesen wurde. Jedenfalls kann so
die I/O nicht das Bottleneck werden.

Nachteil allerdings ist dann, wie mir gerade auffällt, daß dann jeder
Prozess das gesamte File in Zeilen zerlegen muß. Trotzdem lohnt es
sich, wenn die Verarbeitungszeit pro Zeile einigermaßen signifikant
ist gegenüber dem bloßen Suchen nach dem Zeilenende.


>
> ach ja, die datei hat knapp 2,2 millionen zeilen und die zweite datei
> hat 70.000 zeilen. aber es werden halt nicht für alle zeilen aus der
> ersten datei zeilen aus der zweiten datei gesucht - nur wenn sie einem
> gewissen muster entsprechen.
>
> da ich das nun doch nicht implementieren werde möchte ich mich
> trotzdem für die anregungen von euch bedanken!

Bei meinem Vorschlag ändert sich an der Progrmmlogik nicht so viel -
außer daß an der richtigen Stelle eine Zeile überlesen werden muß:

$flag =3D "all"; # oder odd oder even
$line =3D 0;

while (<>) {
$line++;
next if $flag eq "even" && ($line&1)
|| $flag eq "odd" && !($line&1);
# normale Verarbeitung
}

Re: datei "halbieren" - zeile suchen

ich hoffe man kann den beitrag noch lesen ...


> Ob das wirklich so ist, hängt ganz entscheidend davon ab, wie
> CPU-aufwendig das ist, was Du machst.
also die CPU hat mit dem programm schon ganz schön was zu tun! bei top
zeigt er mir cpu-auslastung von knapp 80% (auf der einen cpu) ...
die werte von user sind auch schon ziemlich hoch und idle ist er
eigentlich auch nicht.


> Mach einfach 2 Testläufe. Beim ersten Testlauf nimmst Du die Zeit für
> eine Ausführung mit der großen Datei. Dann nimmst Du die Zeit für 2
> parallele Ausführungen mit je einer Hälfte der Datei (die Hälften
> kannst Du mittels wc -l und head bzw. tail leicht herstellen).
ich hab die dateien mit split in zwei teile zerteilt und das programm
läuft, wenn es gleichzeitig läuft, jetzt nur noch 4 min 50 s im
gegensatz zu vorher 6 min 30 s.
also schon mal schneller - man kann das jetzt noch weiter spinnen und
die datei vierteln, aber dafür hab ich jetzt keine zeit mehr ;-)

aber noch mal danke für die anregungen - leider kann ich diesen thread
hier nicht mehr weiterverfolgen!=20

adieu
christopher ;-)