# [bash] Sortieren von Inhalten in Dateien

## 3PO

Hallo Zusammen,

ich habe mal wieder ein kleines Problen, was das filtern von Dateien angeht.  :Smile: 

Ich habe eine Datei, index.txt, die sieht z.B. so aus:

```
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?  :Smile: 

----------

## toj

so ungefähr könntes es gehen:

```
while read line; do

      for word in $line ; do

            if grep -iq "$word" ./index.txt ; then

                  echo "Treffer: $line"

            fi

      done

done<./liste.txt
```

----------

## toralf

Etwas in dieser Art

```
grep -i -e $(cat index.txt | xargs | sed 's/ / -e /g') liste.txt > out.txt
```

geht auch (meistens).

----------

## Necoro

 *toralf wrote:*   

> Etwas in dieser Art
> 
> ```
> grep -i -e $(cat index.txt | xargs | sed 's/ / -e /g') liste.txt > out.txt
> ```
> ...

 

Ich würde dem grep noch ein "-w" mitgeben um nur ganze Worte zu matchen

----------

## 3PO

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,

```
....

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?

----------

## toralf

 *3PO wrote:*   

> Gibt es dafür auch eine Lösung?

 Klar, siehe Necoro:

```
grep -i -w ...
```

----------

## 3PO

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.

----------

## Necoro

das w muss schon vor dem e stehen ...

/edit: info grep hat noch nie geschadet  :Smile:  *dir als Bettlektüre empfehl*

----------

## toralf

 *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 ...

----------

## 3PO

 *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?

----------

## ScytheMan

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?

----------

## 3PO

 *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.

----------

## ScytheMan

 *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  :Wink: 

Generell bin ich trotzdem noch an meiner Frage interessiert: Wie sieht die Performance Shell vs. "Skriptsprache" aus?

----------

## Necoro

 *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.

----------

## mv

 *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   :Rolling Eyes:   (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.

```
#! /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.

----------

## toj

```
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.

----------

## mv

 *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)).

----------

## mv

Um klarzumachen, was ich mit linearer Laufzeit meine, hier ist die Perl-Version dafür: 

```
#! /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).

----------

## toj

 *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.

----------

## mv

 *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.

----------

