| View previous topic :: View next topic |
| Author |
Message |
3PO
Veteran
Joined: 26 Nov 2006
Posts: 1110
Location: Schwabenländle
|
 Posted: Thu Apr 01, 2010 9:03 am Post subject: [bash] Sortieren von Inhalten in Dateien |
 |
|
Hallo Zusammen,
ich habe mal wieder ein kleines Problen, was das filtern von Dateien angeht. 
Ich habe eine Datei, index.txt, die sieht z.B. so aus:
| Code: | Anton müller
Ärger
Berta Maier
Cäsar
Charlotte berger
Dora |
Nun habe ich eine 2te Datei, liste.txt und eine 3te Datei, out.txt.
So, nun das Problem:
Ich möchte nun liste.txt durchsuchen und nur die Zeilen, die Worte enthalten, die in der index.txt stehen sollen in die out.txt geschrieben werden.
Ein weiteres Problem ist, dass die Groß/Kleinschreibung ignoriert werden soll. D.h. das z.B. auch Zeilen die anton und berta enthalten, nach out.txt geschrieben werden sollen.
Ich stehe gerade auf dem Schlauch und finde keinen Ansatz.
Evtl. hat ja hier Jemand eine Idee? |
|
| Back to top |
|
 |
toj
n00b
Joined: 19 Sep 2005
Posts: 13
|
| Posted: Thu Apr 01, 2010 1:09 pm Post subject: |
|
|
so ungefähr könntes es gehen:
| Code: | while read line; do
for word in $line ; do
if grep -iq "$word" ./index.txt ; then
echo "Treffer: $line"
fi
done
done<./liste.txt |
|
|
| Back to top |
|
|
toralf
Developer
Joined: 01 Feb 2004
Posts: 3943
Location: Hamburg
|
| Posted: Thu Apr 01, 2010 2:50 pm Post subject: |
|
|
Etwas in dieser Art | Code: | | grep -i -e $(cat index.txt | xargs | sed 's/ / -e /g') liste.txt > out.txt |
geht auch (meistens). |
|
| Back to top |
|
|
Necoro
Veteran
Joined: 18 Dec 2005
Posts: 1912
Location: Germany
|
| Posted: Thu Apr 01, 2010 3:05 pm Post subject: |
|
|
| toralf wrote: | Etwas in dieser Art | Code: | | grep -i -e $(cat index.txt | xargs | sed 's/ / -e /g') liste.txt > out.txt |
geht auch (meistens). |
Ich würde dem grep noch ein "-w" mitgeben um nur ganze Worte zu matchen
_________________
Inter Deum Et Diabolum Semper Musica Est. |
|
| Back to top |
|
|
3PO
Veteran
Joined: 26 Nov 2006
Posts: 1110
Location: Schwabenländle
|
| Posted: Thu Apr 01, 2010 3:07 pm Post subject: |
|
|
Thx @ toj & toralf,
das funktioniert soweit schon ganz gut, allerdings habe ich ein kleines Problem:
wenn nun in der liste.txt z.B. "Bergdorf" steht und und der index.txt,
| Code: | ....
berg
Dorf
.... |
steht, dann wird die Zeile trotzdem in die out.txt geschrieben.
Das sollte aber nicht sein.
Gibt es dafür auch eine Lösung? |
|
| Back to top |
|
|
toralf
Developer
Joined: 01 Feb 2004
Posts: 3943
Location: Hamburg
|
| Posted: Thu Apr 01, 2010 3:26 pm Post subject: |
|
|
| 3PO wrote: | | Gibt es dafür auch eine Lösung? |
Klar, siehe Necoro: |
|
| Back to top |
|
|
3PO
Veteran
Joined: 26 Nov 2006
Posts: 1110
Location: Schwabenländle
|
| Posted: Thu Apr 01, 2010 3:39 pm Post subject: |
|
|
grep -iew nimmt aber auch "bergdorf" wenn in der index.txt z.B. "Berg Dorf" steht.
Ich brächte halt einen Parameter der die komplette Zeile nimmt, so wie sie ist. |
|
| Back to top |
|
|
Necoro
Veteran
Joined: 18 Dec 2005
Posts: 1912
Location: Germany
|
| Posted: Thu Apr 01, 2010 3:43 pm Post subject: |
|
|
das w muss schon vor dem e stehen ...
/edit: info grep hat noch nie geschadet *dir als Bettlektüre empfehl*
_________________
Inter Deum Et Diabolum Semper Musica Est. |
|
| Back to top |
|
|
toralf
Developer
Joined: 01 Feb 2004
Posts: 3943
Location: Hamburg
|
| Posted: Thu Apr 01, 2010 4:01 pm Post subject: |
|
|
| 3PO wrote: | | grep -iew nimmt aber auch "bergdorf" wenn in der index.txt z.B. "Berg Dorf" steht. |
Natürlich, und vermutlich auch jedes andere Wort, in dem ein "w" oder "W" vorkommt ... |
|
| Back to top |
|
|
3PO
Veteran
Joined: 26 Nov 2006
Posts: 1110
Location: Schwabenländle
|
| Posted: Thu Apr 01, 2010 4:15 pm Post subject: |
|
|
| Necoro wrote: | das w muss schon vor dem e stehen ...
/edit: info grep hat noch nie geschadet *dir als Bettlektüre empfehl* |
info grep und man grep kenne ich natülich und habe es auch gelesen. Evtl ist ja grep auch nicht das optimale Tool für das was ich vorhabe?
Seltsam ist halt, dass wenn ich grep -i "berg dorf" liste.txt mache, dann erhalte ich das gewünschte Ergebnis.
Jetzt ist halt die Frage, wie ich das in ein Scrpit packe, damit eben ganze Zeilen genommen werden und nicht nur einzelne Worte einer Zeile? |
|
| Back to top |
|
|
ScytheMan
l33t
Joined: 30 Nov 2005
Posts: 605
|
| Posted: Thu Apr 01, 2010 5:31 pm Post subject: |
|
|
Ohne den Thread jetzt hijacken zu wollen, mit einer Diskussion was besser/schlechter ist, aber aus Interesse mal folgende Frage:
Wieso nimmt man dafür "Shelltools" und keine Skriptsprache á la Python, Ruby oder Perl?
Zu miese Performance? Nicht geekig genug? |
|
| Back to top |
|
|
3PO
Veteran
Joined: 26 Nov 2006
Posts: 1110
Location: Schwabenländle
|
| Posted: Thu Apr 01, 2010 6:52 pm Post subject: |
|
|
| ScytheMan wrote: | | [...] Wieso nimmt man dafür "Shelltools" und keine Skriptsprache á la Python, Ruby oder Perl? ... |
"Man" nimmt kein Python, Ruby oder Perl, weil "man" eben kein Python, Ruby oder Perl kann.
Außderdem ist ist das ja nur ein Teil eines Scriptes und der Rest geht ja schon. |
|
| Back to top |
|
|
ScytheMan
l33t
Joined: 30 Nov 2005
Posts: 605
|
| Posted: Thu Apr 01, 2010 8:27 pm Post subject: |
|
|
| 3PO wrote: | | ScytheMan wrote: | | [...] Wieso nimmt man dafür "Shelltools" und keine Skriptsprache á la Python, Ruby oder Perl? ... |
"Man" nimmt kein Python, Ruby oder Perl, weil "man" eben kein Python, Ruby oder Perl kann.
Außderdem ist ist das ja nur ein Teil eines Scriptes und der Rest geht ja schon. |
Ok, das ist eine Erklärung. Hoffe du hast das "man" nicht in den falschen Hals gekriegt, war nicht abwertend oder so gemeint. Hab es unpersönlich belassen, weil ja nicht nur du gepostet hattest sondern auch andre 
Generell bin ich trotzdem noch an meiner Frage interessiert: Wie sieht die Performance Shell vs. "Skriptsprache" aus? |
|
| Back to top |
|
|
Necoro
Veteran
Joined: 18 Dec 2005
Posts: 1912
Location: Germany
|
| Posted: Thu Apr 01, 2010 8:31 pm Post subject: |
|
|
| ScytheMan wrote: | | Generell bin ich trotzdem noch an meiner Frage interessiert: Wie sieht die Performance Shell vs. "Skriptsprache" aus? |
Ich ignorier jetzt mal die Frage nach der Performance, sondern gehe nur auf die Schwierigkeit des Codens ein...
Also in Perl kann ich mir vorstellen, dass die Aufgabe sehr schnell gelöst ist ... in Python wirds schon schwieriger. Am Ende halte ich das zu Skripten denn doch für einfacher (ist ja nur n Einzeiler) ... und bei komplizierterem kann man denn awk verwenden.
_________________
Inter Deum Et Diabolum Semper Musica Est. |
|
| Back to top |
|
|
mv
Watchman
Joined: 20 Apr 2005
Posts: 6780
|
| Posted: Sun Apr 04, 2010 2:28 pm Post subject: |
|
|
| ScytheMan wrote: | Wieso nimmt man dafür "Shelltools" und keine Skriptsprache á la Python, Ruby oder Perl?
Zu miese Performance? |
Nein, ganz im Gegenteil: Die Shell-Lösungen für ein nicht ganz triviales Problem wie dieses hier haben eine grausame Performance. Quadratische Laufzeit  (falls index.txt Kilobytes lange ist, kann man alle bisherigen Shell-Lösungen in der Pfeife rauchen; die einzige effiziente Lösung mit dem Aufbauen eines komplexen grep-Ausdrucks wird dann an der maximalen Kommandozeilenlänge scheitern). So etwas sollte man höchstens dann in Shell skripten, wenn es wegen der Kompatibilität unbedingt erforderlich ist. Ansonsten ist die Aufgabe in typisches Problem, für das Perl geschaffen wurde.
| Code: | #! /usr/bin/env perl
use strict;
use warnings;
my($index,$liste,$output,@A);
open($index, "<", "index.txt") or die "cannot read index.txt";
while(<$index>) { chomp; s/(\W)/\\$1/g; push (@A, qr/\b$_\b/i) }
close($index);
open($liste, "<", "liste.txt") or die "cannot read liste.txt";
open($output, ">", "output.txt") && select($output)
or die "cannot write to output.txt";
while(<$liste>) {
for my $match (@A) {
if(/$match/) { print; last }
}
} |
Zugegeben: Ist länger als die obigen Lösungen, enthält aber auch Vieles was eigentlich nicht notwendig ist (use strict/warnings, Fehlerabfragen).
Im Gegensatz zu den vorherigen Lösungen ist es die einzige, die mit Sonderzeichen in "index.txt" korrekt umgeht. Außerdem skaliert es vernünftig, und bei Bedarf kann man an der quadratischen Laufzeit basteln, indem man ein assoziatives Array statt eines "normalen" Arrays aus regular expressions benutzt. |
|
| Back to top |
|
|
toj
n00b
Joined: 19 Sep 2005
Posts: 13
|
| Posted: Mon Apr 05, 2010 9:35 am Post subject: |
|
|
| Code: | | grep -i -e $(cat index.txt | xargs | sed 's/ / -e /g') liste.txt > out.txt |
finde ich ziemlich elegant im Vergleich zu meinem Vorschlag; wegen des nur einmaligen grep Aufrufs wird das auch wesentlich schneller sein.
@mv: Wo siehst du denn eine Laufzeit O(n^2)? Das Problem ist ein lineares (O(n)),[/quote] und zwar unabhängig von der verwendeten Sprache. |
|
| Back to top |
|
|
mv
Watchman
Joined: 20 Apr 2005
Posts: 6780
|
| Posted: Mon Apr 05, 2010 5:26 pm Post subject: |
|
|
| toj wrote: | | @mv: Wo siehst du denn eine Laufzeit O(n^2)? |
Für jede Zeile in liste.txt (sagen wir: Länge n) wird jede Zeile in index.txt (sagen wir: ebenfalls Länge n) einmal überprüft. Macht n*n Überprüfungen. Außer bei der Perl-Lösung und der Lösung mit dem einzelnen grep-Aufruf (bei dem es aber dafür wie erwähnt die Probleme mit der Kommandozeilenbegrenzung gibt), findet die Überprüfung nicht einmal im Speicher sondern nur auf Disk (bestenfalls im Kernel Disk-Cache) statt.
Immerhin wäre es möglich, die Laufzeit auf O(n*log n) zu drücken (oder falls man genügend Speicher und genügend gute Hashes voraussetzt sogar auf O(n)). |
|
| Back to top |
|
|
mv
Watchman
Joined: 20 Apr 2005
Posts: 6780
|
| Posted: Mon Apr 05, 2010 5:52 pm Post subject: |
|
|
Um klarzumachen, was ich mit linearer Laufzeit meine, hier ist die Perl-Version dafür: | Code: | #! /usr/bin/env perl
use strict;
use warnings;
open(INDEX, "<", "index.txt") or die "cannot read index.txt";
my %A=(); while(<INDEX>) { chomp; $A{lc $_}=1; }
close INDEX;
open(LISTE, "<", "liste.txt") or die "cannot read liste.txt";
open(OUTPUT, ">", "output.txt") && select(OUTPUT)
or die "cannot write to output.txt";
while(<LISTE>) {
for my $i (split) {
if(exists $A{lc $i}) { print; last }
}
} |
Etwas vergleichbar Effizientes ist mit Shell-Mitteln kaum zu machen.
OK: Einige Shells wie zsh oder neuerdings auch Bash können ebenfalls Hashes und haben vielleicht auch interne Kommandos um so etwas wie "lowercase" zu liefern; trotzdem ist eine Shell einfach nicht die richtige Sprache für so etwas (und dürfte auch weitaus ineffizienter sein). |
|
| Back to top |
|
|
toj
n00b
Joined: 19 Sep 2005
Posts: 13
|
| Posted: Tue Apr 06, 2010 12:09 am Post subject: |
|
|
| mv wrote: | | toj wrote: | | @mv: Wo siehst du denn eine Laufzeit O(n^2)? |
Für jede Zeile in liste.txt (sagen wir: Länge n) wird jede Zeile in index.txt (sagen wir: ebenfalls Länge n) einmal überprüft. Macht n*n Überprüfungen. |
Das ist falsch. Die Größe des Problems wird ausschließlich durch die Länge der Liste beschrieben (für jedes Element entscheide ob Topf A oder B). Da die Entscheidung nicht abhängig von der Größe des Problems ist, ist der Index in diesem Zusammenhang irrelevant. Für die konkrete Laufzeit ist der Index natürlich nicht irrelevant: Je nachdem wie schnell die Entscheidung getroffen wird (wie gut der Index bzw. der Algorithmus der Entscheidung ist) desto besser oder schlechter ist die Geschwindigkeit des Programms. Nur: Wenn einmal festgelegt, bleibt die Art der Entscheidung immer die gleiche, egal wie groß oder klein das Problem wird.
Aber was mir eigentlich wichtiger ist: Die Laufzeitkomplexität eines Algorithmus ist nicht abhängig von einer Programmiersprache. Mit jeder kann man mehr oder weniger geschickt vorgehen, einige eignen sich für ein konkrete Problem besser oder weniger gut als andere ... aber der Algorithmus ist im Vergleichsfall der selbe. |
|
| Back to top |
|
|
mv
Watchman
Joined: 20 Apr 2005
Posts: 6780
|
| Posted: Tue Apr 06, 2010 12:15 pm Post subject: |
|
|
| toj wrote: | | mv wrote: | | toj wrote: | | @mv: Wo siehst du denn eine Laufzeit O(n^2)? |
Für jede Zeile in liste.txt (sagen wir: Länge n) wird jede Zeile in index.txt (sagen wir: ebenfalls Länge n) einmal überprüft. Macht n*n Überprüfungen. |
Das ist falsch. Die Größe des Problems wird ausschließlich durch die Länge der Liste beschrieben |
Nope. Bei der Messung von Laufzeit von Algorithmen nimmt man selbstverständlich die gesamten Daten (hier: Liste+Index) und darf nicht einfach annehmen, dass bei Wachsen der Daten ausschließlich die Liste wächst und nicht der Index. Ansonsten wäre Index kein Teil der Daten, sondern fest, und könnte damit als Teil des Algorithmus aufgefasst werden - das würde ein anderes Problem lösen
| Quote: | | Aber was mir eigentlich wichtiger ist: Die Laufzeitkomplexität eines Algorithmus ist nicht abhängig von einer Programmiersprache |
Das ist so pauschal nicht richtig; die Laufzeitkomplexität hängt i.d.R. davon ab, welche Operationen man in konstanter Zeit durchführen kann. Wenn man beispielsweise in einer Sprache arbeitet, die keinen "random access" auf Arrays erlaubt, bei der also ein Zugriff auf ein Array linear mit der Arraylänge wächst (wie bei POSIX Shell), ist man halt prinzipiellen Einschränkungen unterworfen. Mal abgesehen davon, dass im Fall riesiger Konstanten (wie ebenfalls bei Shell, wo man ev. Dinge in Files erledigen muss, die bei anderen Sprachen im Speicher ablaufen) nicht nur die Komplexität alleine das Entscheidende ist. |
|
| Back to top |
|
|
|
Deutsches Forum (German) 
