Jaki jest najszybszy sposób na policzenie liczby każdego znaku w pliku?

Chcę policzyć litery A, litery C, litery G, litery „N” i „-” w pliku lub każdą literę, jeśli to konieczne, czy istnieje szybkie polecenie uniksowe, aby to zrobić?

Jeśli chcesz prawdziwej prędkości:

echo 'int cache[256],x,y;char buf[4096],letters[]="tacgn-"; int main(){while((x=read(0,buf,sizeof buf))>0)for(y=0;y<x;y++)cache[(unsigned char)buf[y]]++;for(x=0;x<sizeof letters-1;x++)printf("%c: %d\n",letters[x],cache[letters[x]]);}' | gcc -w -xc -; ./a.out < file; rm a.out;

Jest niesamowicie szybkim pseudo-jednym-linerem.

Prosty test pokazuje, że na moim Core i7 CPU 870 @ 2.93GHz liczy on nieco ponad 600 MB / s:

$ du -h bigdna 
1.1G    bigdna

time ./a.out < bigdna 
t: 178977308
a: 178958411
c: 178958823
g: 178947772
n: 178959673
-: 178939837

real    0m1.718s
user    0m1.539s
sys     0m0.171s

W przeciwieństwie do rozwiązań obejmujących sortowanie, ten działa w stałej pamięci (4K), co jest bardzo przydatne, jeśli plik jest znacznie większy niż ram.

I oczywiście przy odrobinie smaru łokciowego możemy zgolić 0,7 sekundy:

echo 'int cache[256],x,buf[4096],*bp,*ep;char letters[]="tacgn-"; int main(){while((ep=buf+(read(0,buf,sizeof buf)/sizeof(int)))>buf)for(bp=buf;bp<ep;bp++){cache[(*bp)&0xff]++;cache[(*bp>>8)&0xff]++;cache[(*bp>>16)&0xff]++;cache[(*bp>>24)&0xff]++;}for(x=0;x<sizeof letters-1;x++)printf("%c: %d\n",letters[x],cache[letters[x]]);}' | gcc -O2 -xc -; ./a.out < file; rm a.out;

Sieci nieco ponad 1,1 GB / s wykańczają w:

real    0m0.943s
user    0m0.798s
sys     0m0.134s

Dla porównania przetestowałem niektóre inne rozwiązania na tej stronie, które wydawały się mieć jakąś obietnicę szybkości.

Rozwiązanie sed/ awkwykonało dzielny wysiłek, ale zmarło po 30 sekundach. Przy tak prostym wyrażeniu regularnym spodziewam się, że będzie to błąd w sed (GNU sed wersja 4.2.1):

$ time sed 's/./&\n/g' bigdna | awk '!/^$/{a[$0]++}END{for (i in a)print i,a[i];}' 
sed: couldn't re-allocate memory

real    0m31.326s
user    0m21.696s
sys     0m2.111s

Metoda perla również wydawała się obiecująca, ale poddałem się po uruchomieniu jej przez 7 minut

time perl -e 'while (<>) {$c{$&}++ while /./g} print "$c{$_} $_\n" for keys %c' < bigdna 
^C

real    7m44.161s
user    4m53.941s
sys     2m35.593s

grep -o foo.text -e A -e T -e C -e G -e N -e -|sort|uniq -c

Wykona lewę jako jeden liniowiec. Potrzebne jest jednak małe wyjaśnienie.

grep -o foo.text -e A -e T -e C -e G -e N -e -greps plik foo.text dla liter a i g oraz znak -dla każdego znaku, który chcesz wyszukać. Drukuje również jeden znak w linii.

sortsortuje to w kolejności. To przygotowuje scenę dla następnego narzędzia

uniq -cliczy zduplikowane kolejne wystąpienia dowolnej linii. W tym przypadku, ponieważ mamy posortowaną listę znaków, otrzymujemy dokładną liczbę, kiedy znaki, które wyłapaliśmy w pierwszym kroku

Jeśli foo.txt zawiera ciąg, GATTACA-to właśnie otrzymam ten zestaw poleceń

[geek@atremis ~]$ grep -o foo.text -e A -e T -e C -e G -e N -e -|sort|uniq -c
      1 -
      3 A
      1 C
      1 G
      2 T

Wypróbuj ten, zainspirowany odpowiedzią @ Journeyman.

grep -o -E 'A|T|C|G|N|-' foo.txt | sort | uniq -c

Kluczem jest znajomość opcji -o dla grep . To dzieli dopasowanie, tak że każda linia wyjściowa odpowiada pojedynczej instancji wzorca, a nie całej linii dla dowolnej pasującej linii. Biorąc pod uwagę tę wiedzę, wszystko, czego potrzebujemy, to wzór do użycia i sposób na policzenie linii. Za pomocą wyrażenia regularnego możemy utworzyć rozłączny wzorzec, który będzie pasował do dowolnej z wymienionych przez Ciebie postaci:

A|T|C|G|N|-

Oznacza to „dopasuj A lub T lub C lub G lub N lub -”. Podręcznik opisuje różne składnie wyrażeń regularnych, których możesz użyć .

Teraz mamy wyjście, które wygląda mniej więcej tak:

$ grep -o -E 'A|T|C|G|N|-' foo.txt 
A
T
C
G
N
-
-
A
A
N
N
N

Naszym ostatnim krokiem jest połączenie i policzenie wszystkich podobnych wierszy, które można po prostu osiągnąć za pomocą sort | uniq -c, jak w odpowiedzi @ Journeyman. Sortowanie daje nam następujące wyniki:

$ grep -o -E 'A|T|C|G|N|-' foo.txt | sort
-
-
A
A
A
C
G
N
N
N
N
T

Które, po przepuszczeniu uniq -c, w końcu przypomina to, czego chcemy:

$ grep -o -E 'A|T|C|G|N|-' foo.txt | sort | uniq -c
      2 -
      3 A
      1 C
      1 G
      4 N
      1 T

Dodatek: Jeśli chcesz zsumować liczbę znaków A, C, G, N, T i - w pliku, możesz przesłać wyjście grep wc -lzamiast sort | uniq -c. Istnieje wiele różnych rzeczy, które można liczyć z niewielkimi modyfikacjami tego podejścia.

Jeden linijka zliczająca wszystkie litery za pomocą Pythona:

$ python -c "import collections, pprint; pprint.pprint(dict(collections.Counter(open('FILENAME_HERE', 'r').read())))"

... wytwarzając taki przyjazny wynik YAML:

{'\n': 202,
 ' ': 2153,
 '!': 4,
 '"': 62,
 '#': 12,
 '%': 9,
 "'": 10,
 '(': 84,
 ')': 84,
 '*': 1,
 ',': 39,
 '-': 5,
 '.': 121,
 '/': 12,
 '0': 5,
 '1': 7,
 '2': 1,
 '3': 1,
 ':': 65,
 ';': 3,
 '<': 1,
 '=': 41,
 '>': 12,
 '@': 6,
 'A': 3,
 'B': 2,
 'C': 1,
 'D': 3,
 'E': 25}

Interesujące jest zobaczyć, jak w większości przypadków Python może łatwo pokonać nawet bash pod względem przejrzystości kodu.

Podobne do awkmetody Guru :

perl -e 'while (<>) {$c{$&}++ while /./g} print "$c{$_} $_\n" for keys %c'

Po kilku latach korzystania z systemu UNIX bardzo dobrze biegniesz w łączeniu wielu małych operacji w celu wykonywania różnych zadań filtrowania i liczenia. Każdy ma swój styl - niektórzy lubią, awka sedniektórzy cutlub tr. Oto jak bym to zrobił:

Aby przetworzyć określoną nazwę pliku:

 od -a FILENAME_HERE | cut -b 9- | tr " " \\n | egrep -v "^$" | sort | uniq -c

lub jako filtr:

 od -a | cut -b 9- | tr " " \\n | egrep -v "^$" | sort | uniq -c

Działa to tak:

1. od -a dzieli plik na znaki ASCII.
2. cut -b 9-eliminuje umieszczanie przedrostków od.
3. tr " " \\n konwertuje spacje między znakami na znaki nowej linii, aby w linii był jeden znak.
4. egrep -v "^$" pozbywa się wszystkich dodatkowych pustych linii, które to tworzy.
5. sort zbiera wystąpienia każdej postaci razem.
6. uniq -c zlicza liczbę powtórzeń każdej linii.

Nakarmiłem to „Witaj, świecie!” następnie nowy wiersz i otrzymałem to:

  1 ,
  1 !
  1 d
  1 e
  1 H
  3 l
  1 nl
  2 o
  1 r
  1 sp
  1 w

sedCzęść jest na podstawie odpowiedzi @ Guru , oto kolejny stosując podejście uniq, podobne do rozwiązania Davida Schwartza.

$ cat foo
aix
linux
bsd
foo
$ sed 's/\(.\)/\1\n/g' foo | sort | uniq -c
4 
1 a
1 b
1 d
1 f
2 i
1 l
1 n
2 o
1 s
1 u
2 x

Możesz połączyć grepi wczrobić to:

grep -o 'character' file.txt | wc -w

grepprzeszukuje podany plik (-y) w celu -oznalezienia określonego tekstu, a opcja nakazuje mu wydrukowanie tylko rzeczywistych dopasowań (tj. szukanych znaków), a nie domyślny, który polega na drukowaniu każdej linii, w której znajdował się szukany tekst znalezione na.

wcwypisuje liczbę bajtów, słów i wierszy dla każdego pliku lub w tym przypadku dane wyjściowe greppolecenia. Ta -wopcja nakazuje policzyć słowa, przy czym każde słowo występuje w wyszukiwanym znaku. Oczywiście -lopcja (licząca linie) również działałaby, ponieważ grepdrukuje każde wystąpienie twojego znaku wyszukiwania w osobnej linii.

Aby to zrobić dla wielu znaków jednocześnie, umieść je w tablicy i zapętl:

chars=(A T C G N -)
for c in "${chars[@]}"; do echo -n $c ' ' && grep -o $c file.txt | wc -w; done

Przykład: w przypadku pliku zawierającego ciąg TGC-GTCCNATGCGNNTCACANN-wyjściowy będzie:

A  3
T  4
C  6
G  4
N  5
-  2

Aby uzyskać więcej informacji, zobacz man grepi man wc.

Wadą tego podejścia, jak zauważa użytkownik Journeyman Geek w komentarzu, jest to, że grepnależy uruchomić raz dla każdej postaci. W zależności od tego, jak duże są twoje pliki, może to spowodować zauważalny spadek wydajności. Z drugiej strony, gdy jest to zrobione w ten sposób, łatwiej jest szybko zobaczyć, które znaki są wyszukiwane, oraz dodawać / usuwać je, ponieważ znajdują się one w osobnej linii od reszty kodu.

Używając linii sekwencji z 22hgp10a.txt, różnica czasowa między grep i awk w moim systemie sprawia, że ​​używanie awk jest właściwą drogą ...

[Edytuj]: Po obejrzeniu skompilowanego rozwiązania Dave'a zapomnij również o awk, ponieważ jego ukończenie w tym pliku w ~ 0,1 sekundy zapewnia pełne liczenie wielkości liter.

# A nice large sample file.
wget http://gutenberg.readingroo.ms/etext02/22hgp10a.txt

# Omit the regular text up to the start `>chr22` indicator.
sed -ie '1,/^>chr22/d' 22hgp10a.txt

sudo test # Just get sudo setup to not ask for password...

# ghostdog74 answered a question <linked below> about character frequency which
# gave me all case sensitive [ACGNTacgnt] counts in ~10 seconds.
sudo chrt -f 99 /usr/bin/time -f "%E elapsed, %c context switches" \
awk -vFS="" '{for(i=1;i<=NF;i++)w[$i]++}END{for(i in w) print i,w[i]}' 22hgp10a.txt

# The grep version given by Journeyman Geek took a whopping 3:41.47 minutes
# and yielded the case sensitive [ACGNT] counts.
sudo chrt -f 99 /usr/bin/time -f "%E elapsed, %c context switches" \
grep -o foo.text -e A -e T -e C -e G -e N -e -|sort|uniq -c

Wersja ghostdog bez rozróżniania wielkości liter jest ukończona w ~ 14 sekund.

Sed wyjaśniono w zaakceptowanej odpowiedzi na to pytanie .
Benchmarking jest zgodny z przyjętą odpowiedzią na to pytanie .
Przyjęta odpowiedź ghostdog74 była na to pytanie .

Myślę, że jakakolwiek przyzwoita implementacja unika sortowania. Ponieważ jednak źle jest czytać wszystko 4 razy, myślę, że można w jakiś sposób wygenerować strumień, który przechodzi przez 4 filtry, po jednym dla każdego znaku, który jest odfiltrowywany, a gdzie długości strumienia są również w jakiś sposób obliczane.

time cat /dev/random | tr -d -C 'AGCTN\-' | head -c16M >dna.txt
real    0m5.797s
user    0m6.816s
sys     0m1.371s

$ time tr -d -C 'AGCTN\-' <dna.txt | tee >(wc -c >tmp0.txt) | tr -d 'A' | 
tee >(wc -c >tmp1.txt) | tr -d 'G' | tee >(wc -c >tmp2.txt) | tr -d 'C' | 
tee >(wc -c >tmp3.txt) | tr -d 'T' | tee >(wc -c >tmp4.txt) | tr -d 'N' | 
tee >(wc -c >tmp5.txt) | tr -d '\-' | wc -c >tmp6.txt && cat tmp[0-6].txt

real    0m0.742s
user    0m0.883s
sys     0m0.866s

16777216
13983005
11184107
8387205
5591177
2795114
0

Skumulowane sumy są następnie w tmp [0-6] .txt .., więc prace są nadal w toku

W tym podejściu jest tylko 13 potoków, które konwertują do mniej niż 1 Mb pamięci.
Oczywiście moim ulubionym rozwiązaniem jest:

time cat >f.c && gcc -O6 f.c && ./a.out
# then type your favourite c-program
real    0m42.130s

Nie wiedziałem uniqani o tym grep -o, ale ponieważ moje komentarze na @JourneymanGeek i @ crazy2be miały takie wsparcie, być może powinienem przekształcić je w własną odpowiedź:

Jeśli wiesz, że w pliku są tylko „dobre” znaki (te, które chcesz policzyć), możesz poszukać

grep . -o YourFile | sort | uniq -c

Jeśli tylko niektóre znaki muszą być policzone, a inne nie (tj. Separatory)

grep '[ACTGN-]' YourFile | sort | uniq -c

Pierwszy używa symboli wieloznacznych wyrażeń regularnych ., które pasują do dowolnego pojedynczego znaku. Drugi używa „zestawu akceptowanych znaków”, bez określonej kolejności, z wyjątkiem tego, że -musi ono nastąpić jako ostatnie ( A-Cjest interpretowane jako „dowolny znak pomiędzy Ai C). W takim przypadku wymagane są cudzysłowy, aby twoja powłoka nie próbowała rozwinąć tego, aby sprawdzić pliki jednoznakowe, jeśli takie istnieją (i wygenerować błąd „brak dopasowania”, jeśli nie istnieje).

Zauważ, że „sort” ma również -uflagę nique, dzięki czemu zgłasza rzeczy tylko raz, ale nie ma flagi towarzyszącej do liczenia duplikatów, więc uniqjest to rzeczywiście obowiązkowe.

Głupiutki:

tr -cd ATCGN- | iconv -f ascii -t ucs2 | tr '\0' '\n' | sort | uniq -c

• traby usunąć ( -d) wszystkie znaki oprócz ( -c) ATCGN-
• iconv przekonwertować na ucs2 (UTF16 ograniczony do 2 bajtów), aby dodać bajt 0 po każdym bajcie,
• inny, traby przetłumaczyć te znaki NUL na NL. Teraz każda postać ma swoją własną linię
• sort | uniq -cpoliczyć każdą linię uniq

Jest to alternatywa dla niestandardowej -oopcji grep.

time $( { tr -cd ACGTD- < dna.txt | dd | tr -d A | dd | tr -d C | dd | tr -d G |
dd | tr -d T | dd | tr -d D | dd | tr -d - | dd >/dev/null; } 2>tmp ) &&
grep byte < tmp | sort -r -g | awk '{ if ((s-$0)>=0) { print s-$0} s=$0 }'

Format wyjściowy nie jest najlepszy ...

real    0m0.176s
user    0m0.200s
sys     0m0.160s
2069046
2070218
2061086
2057418
2070062
2052266

Teoria operacji:

• $ ({polecenie | polecenie} 2> tmp) przekierowuje stderr strumienia do pliku tymczasowego.
• dd wyprowadza stdin na stdout i wyświetla liczbę bajtów przekazanych do stderr
• tr -d odfiltrowuje jeden znak na raz
• grep i sort filtruje wyjście dd do malejącej kolejności
• awk oblicza różnicę
• Sort jest używany tylko na etapie przetwarzania końcowego, aby obsłużyć niepewność kolejności wyjścia wystąpień dd

Szybkość wydaje się wynosić 60 MB / s

Przykładowy plik:

$ cat file
aix
unix
linux

Komenda:

$ sed 's/./&\n/g' file | awk '!/^$/{a[$0]++}END{for (i in a)print i,a[i];}'
u 2
i 3
x 3
l 1
n 2
a 1

Łącząc kilka innych

chars='abcdefghijklmnopqrstuvwxyz-'
grep -o -i "[$chars]" foo|sort | uniq -c

Dodaj, | sort -nraby zobaczyć wyniki w kolejności częstotliwości.

Krótka odpowiedź:

Jeśli pozwalają na to okoliczności, porównaj rozmiary plików o niskim zestawie znaków z zestawem bez znaków, aby uzyskać przesunięcie i po prostu policzyć bajty.

Ach, ale splątane szczegóły:

To są wszystkie postacie ascii. Jeden bajt na. Pliki zawierają oczywiście dodatkowe metadane dla różnych rzeczy używanych przez system operacyjny i aplikację, która je utworzyła. W większości przypadków spodziewałbym się, że zajmą one tyle samo miejsca bez względu na metadane, ale starałbym się zachować identyczne okoliczności, kiedy najpierw testujesz podejście, a następnie weryfikujesz, czy masz stałe przesunięcie, zanim się o to nie martwisz. Inna gotcha polega na tym, że w łamaniu linii zwykle występują dwie ascii białe znaki, a wszelkie tabulacje lub spacje byłyby po jednym. Jeśli możesz być pewien, że będą obecne i nie ma sposobu, aby wiedzieć, ile wcześniej, przestałbym czytać teraz.

Może się to wydawać wieloma ograniczeniami, ale jeśli możesz je łatwo ustalić, wydaje mi się to najłatwiejszym / najskuteczniejszym podejściem, jeśli masz mnóstwo takich ograniczeń (co wydaje się prawdopodobne, jeśli to DNA). Sprawdzanie tony plików pod względem długości i odejmowanie stałej byłoby o wiele szybsze niż uruchamianie grep (lub podobnego) na każdym z nich.

Jeśli:

• Są to proste ciągłe ciągi w czystych plikach tekstowych
• Są w identycznych typach plików utworzonych przez ten sam waniliowy, niesformatujący edytor tekstowy, jak Scite (wklejanie jest w porządku, o ile sprawdzasz spacje / zwroty) lub jakiś podstawowy program, który ktoś napisał

I dwie rzeczy, które mogą nie mieć znaczenia, ale najpierw sprawdziłbym

• Nazwy plików są równej długości
• Pliki znajdują się w tym samym katalogu

Spróbuj znaleźć przesunięcie, wykonując następujące czynności:

Porównaj pusty plik z plikiem z kilkoma łatwymi do policzenia znakami z plikiem z kilkoma innymi znakami. Jeśli odjęcie pustego pliku od obu pozostałych dwóch plików da ci liczbę bajtów pasującą do liczby znaków, to koniec. Sprawdź długości plików i odejmij tę pustą ilość. Jeśli chcesz spróbować znaleźć pliki wielowierszowe, większość redaktorów dołącza dwa specjalne znaki jednobajtowe do podziałów wierszy, ponieważ Microsoft zwykle ignoruje jeden, ale w takim przypadku musisz przynajmniej grep równie dobrze możesz to wszystko zrobić grep.

Sposób Haskell :

import Data.Ord
import Data.List
import Control.Arrow

main :: IO ()
main = interact $
  show . sortBy (comparing fst) . map (length &&& head) . group . sort

to działa tak:

112123123412345
=> sort
111112222333445
=> group
11111 2222 333 44 5
=> map (length &&& head)
(5 '1') (4 '2') (3 '3') (2 '4') (1,'5')
=> sortBy (comparing fst)
(1 '5') (2 '4') (3 '3') (4 '2') (5 '1')
=> one can add some pretty-printing here
...

kompilowanie i używanie:

$ ghc -O2 q.hs
[1 of 1] Compiling Main             ( q.hs, q.o )
Linking q ...
$ echo 112123123412345 | ./q
[(1,'\n'),(1,'5'),(2,'4'),(3,'3'),(4,'2'),(5,'1')]%       
$ cat path/to/file | ./q
...

może nie nadaje się do dużych plików.

Szybki hack Perla:

perl -nle 'while(/[ATCGN]/g){$a{$&}+=1};END{for(keys(%a)){print "$_:$a{$_}"}}'

• -n: Iteruj po liniach wejściowych, ale nie drukuj dla nich niczego
• -l: Automatyczne usuwanie lub dodawanie podziałów linii
• while: powtarzaj wszystkie wystąpienia żądanych symboli w bieżącym wierszu
• END: Na koniec wydrukuj wyniki
• %a: Hash, w którym przechowywane są wartości

Znaki, które w ogóle nie występują, nie zostaną uwzględnione w wyniku.