Czy można przyspieszyć ten skrypt powłoki?

Question

Mam zadanie tworzenia skryptu, który pobiera duży plik tekstowy jako dane wejściowe. Następnie musi znaleźć wszystkie słowa i liczbę wystąpień i utworzyć nowy plik z każdym wierszem wyświetlającym unikalne słowo i jego wystąpienie.

Jako przykład wziąć plik z tej zawartości:

Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor 
incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud 
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure 
dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. 
Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt 
mollit anim id est laborum. 

trzeba utworzyć plik, który wygląda tak:

1 AD 
1 ADIPISICING 
1 ALIQUA 
... 
1 ALIQUIP 
1 DO 
2 DOLOR 
2 DOLORE 
... 

W tym celu napisałem skrypt, używając tr, sort i uniq:

#!/bin/sh 
INPUT=$1 
OUTPUT=$2 
if [ -a $INPUT ] 
then 
    tr '[:space:][\-_?!.;\:]' '\n' < $INPUT | 
     tr -d '[:punct:][:special:][:digit:]' | 
     tr '[:lower:]' '[:upper:]' | 
     sort | 
     uniq -c > $OUTPUT 
fi 

Co to jest? es dzieli słowa za pomocą spacji jako ogranicznika. Jeśli słowo zawiera -_?!.;:, ponownie je rozbijam na słowa. Usuwam znaki interpunkcyjne, znaki specjalne i cyfry oraz konwertuję cały ciąg znaków na wielkie litery. Po wykonaniu tej czynności sortuję ją i przekazuję ją przez uniq, aby uzyskać żądany format.

Teraz pobrałem Biblię w formacie txt i użyłem jej jako wejścia. Timing to mam:

scripts|$ time ./text-to-word.sh text.txt b  
./text-to-word.sh text.txt b 16.17s user 0.09s system 102% cpu 15.934 total 

I zrobił to samo ze skryptu Pythona:

import re 
from collections import Counter 
from itertools import chain 
import sys 

file = open(sys.argv[1]) 

c = Counter() 

for line in file.readlines(): 
    c.update([re.sub('[^a-zA-Z]', '', l).upper() 
      for l in chain(*[re.split('[-_?!.;:]', word) 
        for word in line.split()])]) 

file2 = open('output.txt', 'w') 
for key in sorted(c): 
    file2.write(key + ' ' + str(c[key]) + '\n') 

Kiedy wykonywany skrypt uzyskałem:

scripts|$ time python text-to-word.py text.txt 
python text-to-word.py text.txt 7.23s user 0.04s system 97% cpu 7.456 total 

Jak widać zabrakło w 7.23s w porównaniu do skryptu powłoki, który działał w 16.17s. Próbowałem z większymi plikami i zawsze wydaje się, że Python triumfuje. Mam kilka pytań do powyższego senario:

1. Dlaczego skrypt Pythona jest szybszy, biorąc pod uwagę, że polecenia powłoki są napisane w języku C? Rozumiem, że skrypt powłoki może nie być optymalny.
2. Jak mogę poprawić skrypt powłoki?
3. Czy mogę ulepszyć skrypt Pythona?

Aby było jasne, nie porównuję Pythona ze skryptami powłoki. Nie próbuję rozpoczynać wojny płomieniowej lub nie potrzebuję odpowiedzi w jakimkolwiek innym języku, porównując się do bycia szybszym. Używając filozofii UNIXa do wykonywania małych poleceń w celu wykonania zadania, jak mogę przyspieszyć działanie skryptu powłoki?

Answer 1

Ważnym punktem tutaj jest prawdopodobnie międzyprocesowe we/wy. Skrypt w języku Python ma wszystkie dane w pamięci, więc żadne operacje I/O nie są wykonywane podczas przetwarzania danych.

Należy również zauważyć, że Python nie jest wolny. Większość funkcji w języku Python jest zaimplementowana w C.

Skrypt powłoki musi rozpoczynać 5 procesów, a każdy z nich musi przeczytać cały tekst z stdin i czterokrotnie napisać cały tekst do stdout.

Nie może być sposób, aby skrypt Pythona nieco szybciej: Można przeczytać cały tekst w jednym ciągu, a następnie usunąć wszystkie znaki interpunkcyjne, Split słowa, a następnie policzyć:

text = file.read() 
text = re.sub(r'[.,:;-_]', '', text) 
text = text.upper() 
words = re.split(r'\\s+', text) 
c = Counter() 
c.update(words) 

że uniknij narzutu kilku zagnieżdżonych pętli.

Co do skryptu powłoki: Powinieneś spróbować zmniejszyć liczbę procesów. Trzy procesy tr można prawdopodobnie zastąpić jednym wywołaniem dla sed.

Answer 2

Nie jest to kwestia jednego języka w stosunku do drugiego. Twoje podejście jest inne.

W Pythonie, zwiększasz licznik dla każdego słowa w miarę napotykania go, a następnie iterujesz licznik, aby wytworzyć wynik. To będzie O (n).

W bashu wszystkie swoje słowa umieszczasz pojedynczo w długiej krotce, sortując krotkę, a następnie licząc instancje. Najprawdopodobniej będzie to O (nlogn).

Answer 3

Można poprawić swój skrypt bash:

sed 's/[^a-zA-Z][^a-zA-Z]*/\'$'\n/g' <$INPUT | sort -f -u >$OUTPUT 

ale odpowiedź krótka i prawo na Twoje pytanie brzmi: Ponieważ używasz zupełnie różne algorytmy.

Answer 4

Można spróbować to:

Zważywszy plik wejściowy będzie input.txt

skryptu Bash

cat Input.txt | tr [:space:] '\n' | grep -v "^\s*$" | sort | uniq -c | sort -bnr | tr [:lower:] [:upper:] 

Answer 5

Jednym ze sposobów korzystania GNU awk:

WHINY_USERS=1 awk '{ for (i=1; i<=NF; i++) { sub("[,.]","",$i); array[toupper($i)]++ } } END { for (j in array) print array[j], j }' file.txt 

---

Pseudokod/wyjaśnienie:

## WHINY_USERS=1 enables sorting by keys. A bit of a trick. 
## Now loop through each word on each line, removing commas, full-stops, 
## adding each word in uppercase to an array. 
## Loop through the array printing vals and keys 

YMMV

Answer 6

rozwiązanie bash

#!/bin/bash 
IFS=' -_?!.;\:,' 
while read -r line; do 
    for word in $line; do 
    word=${word//[^[:alpha:]]/} 
    [ $word ] || continue 
    word=$(tr '[:lower:]' '[:upper:]' <<<"$word") 
    ((_w_$word++)) 
    done 
done <"$INPUT" 
IFS=' ' 
for wword in ${!_w_*}; do echo "${!wword} ${wword#_w_}"; done > $OUTPUT.v1 

rozwiązanie Perl golf

perl -nle '$h{uc()}++for/(\w+)/g}{print"$h{$_} $_"for sort keys%h' $INPUT > $OUTPUT.v2