Apa cara tercepat untuk menghitung jumlah setiap karakter dalam file?

Saya ingin menghitung karakter C's G's N's dan "-" dalam sebuah file, atau setiap huruf jika diperlukan, apakah ada perintah Unix cepat untuk melakukan ini?

Jika Anda menginginkan kecepatan nyata:

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;

Adalah pseudo-one-liner yang sangat cepat.

Sebuah tes sederhana menunjukkan bahwa pada Core i7 CPU 870 @ 2.93GHz saya menghitung lebih dari 600MB / 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

Tidak seperti solusi yang melibatkan penyortiran, yang ini berjalan dalam memori konstan (4K), yang sangat berguna, jika file Anda jauh lebih besar daripada ram Anda.

Dan, tentu saja dengan sedikit minyak siku, kita dapat mencukur 0,7 detik:

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;

Jaring lebih dari 1,1GB / detik finishing di:

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

Sebagai perbandingan, saya menguji beberapa solusi lain pada halaman ini yang tampaknya memiliki semacam janji kecepatan.

The sed/ awksolusi membuat usaha gagah berani, namun meninggal setelah 30 detik. Dengan regex yang sederhana, saya berharap ini menjadi bug in sed (GNU sed versi 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

Metode perl juga tampak menjanjikan, tetapi saya menyerah setelah menjalankannya selama 7 menit

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

Akan melakukan trik sebagai liner satu. Namun diperlukan sedikit penjelasan.

grep -o foo.text -e A -e T -e C -e G -e N -e -greps file foo.text untuk huruf a dan g dan karakter -untuk setiap karakter yang ingin Anda cari. Ini juga mencetak satu karakter satu garis.

sortmengurutkannya secara berurutan. Ini mengatur panggung untuk alat selanjutnya

uniq -cmenghitung duplikat kemunculan berurutan dari sembarang baris. Dalam hal ini, karena kami memiliki daftar karakter yang diurutkan, kami mendapatkan jumlah yang rapi kapan karakter yang kami ambil pada langkah pertama

Jika foo.txt berisi string, GATTACA-inilah yang akan saya dapatkan dari serangkaian perintah ini

[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

Coba yang ini, terinspirasi oleh jawaban @ Journeyman.

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

Kuncinya adalah mengetahui tentang opsi -o untuk grep . Ini membagi kecocokan, sehingga setiap baris output sesuai dengan satu contoh pola, daripada seluruh baris untuk setiap baris yang cocok. Dengan pengetahuan ini, yang kita butuhkan hanyalah pola untuk digunakan, dan cara menghitung garis. Dengan menggunakan regex, kita dapat membuat pola disjungtif yang akan cocok dengan karakter yang Anda sebutkan:

A|T|C|G|N|-

Ini berarti "cocok dengan A atau T atau C atau G atau N atau -". Manual ini menjelaskan berbagai sintaks ekspresi reguler yang dapat Anda gunakan .

Sekarang kita memiliki output yang terlihat seperti ini:

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

Langkah terakhir kami adalah menggabungkan dan menghitung semua baris yang sama, yang dapat diselesaikan dengan a sort | uniq -c, seperti dalam jawaban @ Journeyman. Sortir tersebut memberi kami output seperti ini:

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

Yang, ketika disalurkan melalui uniq -c, akhirnya menyerupai apa yang kita inginkan:

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

Tambahan: Jika Anda ingin total jumlah A, C, G, N, T, dan - karakter dalam file, Anda dapat menyalurkan output grep melalui wc -lbukan sort | uniq -c. Ada banyak hal berbeda yang dapat Anda hitung dengan hanya sedikit modifikasi pada pendekatan ini.

Satu liner menghitung semua huruf menggunakan Python:

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

... menghasilkan keluaran ramah YAML seperti ini:

{'\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}

Sangat menarik untuk melihat bagaimana sebagian besar kali Python dapat dengan mudah mengalahkan bahkan bash dalam hal kejelasan kode.

Mirip dengan awkmetode Guru :

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

Setelah menggunakan UNIX selama beberapa tahun, Anda menjadi sangat mahir menghubungkan beberapa operasi kecil untuk menyelesaikan berbagai tugas penyaringan dan penghitungan. Setiap orang memiliki gaya mereka sendiri - beberapa suka awkdan sed, beberapa suka cutdan tr. Inilah cara saya akan melakukannya:

Untuk memproses nama file tertentu:

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

atau sebagai filter:

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

Ini berfungsi seperti ini:

1. od -a memisahkan file menjadi karakter ASCII.
2. cut -b 9-menghilangkan odmenempatkan awalan .
3. tr " " \\n mengkonversi spasi antara karakter ke baris baru sehingga ada satu karakter per baris.
4. egrep -v "^$" menghilangkan semua baris kosong tambahan yang dibuat ini.
5. sort mengumpulkan contoh masing-masing karakter bersama-sama.
6. uniq -c menghitung jumlah pengulangan dari setiap baris.

Saya memberinya makan "Halo, dunia!" diikuti oleh baris baru dan dapatkan ini:

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

Bagian sedyang didasarkan pada jawaban @ Guru , inilah pendekatan lain yang digunakan uniq, mirip dengan solusi David Schwartz.

$ 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

Anda dapat menggabungkan grepdan wcmelakukan ini:

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

grepmencari file yang diberikan untuk teks yang ditentukan, dan -oopsi mengatakannya untuk hanya mencetak kecocokan yang sebenarnya (mis. karakter yang Anda cari), daripada default yang mencetak setiap baris di mana teks pencarian itu ditemukan pada.

wcmencetak byte, kata dan jumlah baris untuk setiap file, atau dalam hal ini, output dari grepperintah. The -wpilihan mengatakan itu untuk menghitung kata, dengan setiap kata menjadi terjadinya karakter pencarian Anda. Tentu saja, -lopsi (yang menghitung garis) akan berfungsi juga, karena grepmencetak setiap kemunculan karakter pencarian Anda pada baris yang terpisah.

Untuk melakukan ini untuk sejumlah karakter sekaligus, letakkan karakter dalam array dan loop di atasnya:

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

Contoh: untuk file yang berisi string TGC-GTCCNATGCGNNTCACANN-, hasilnya adalah:

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

Untuk informasi lebih lanjut, lihat man grepdan man wc.

Kelemahan dari pendekatan ini, seperti yang dicatat pengguna Journeyman Geek di bawah ini dalam komentar, adalah yang grepharus dijalankan satu kali untuk setiap karakter. Bergantung pada seberapa besar file Anda, ini dapat menyebabkan hit kinerja yang nyata. Di sisi lain, ketika dilakukan dengan cara ini sedikit lebih mudah untuk dengan cepat melihat karakter mana yang sedang dicari, dan untuk menambah / menghapusnya, karena mereka berada di baris terpisah dari sisa kode.

Menggunakan garis urutan dari 22hgp10a.txt perbedaan waktu antara grep dan awk di sistem saya membuat menggunakan awk cara untuk pergi ...

[Sunting]: Setelah melihat solusi yang disusun Dave lupa awk juga, karena selesai dalam ~ 0,1 detik pada file ini untuk penghitungan peka huruf besar-kecil.

# 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

Versi case sensitif dari ghostdog selesai dalam ~ 14 detik.

Sed dijelaskan dalam jawaban yang diterima untuk pertanyaan ini .
Benchmarking adalah seperti pada jawaban yang diterima untuk pertanyaan ini .
Jawaban yang diterima oleh ghostdog74 adalah untuk pertanyaan ini .

Saya pikir setiap implementasi yang layak menghindari semacam itu. Tetapi karena itu juga ide yang buruk untuk membaca semuanya 4 kali, saya pikir seseorang dapat entah bagaimana menghasilkan aliran yang melewati 4 filter, satu untuk setiap karakter, yang disaring dan di mana panjang aliran juga entah bagaimana dihitung.

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

Jumlah kumulatif kemudian dalam tmp [0-6] .txt .. jadi pekerjaan masih berlangsung

Hanya ada 13 pipa dalam pendekatan ini, yang mengkonversi ke memori kurang dari 1 Mb.
Tentu saja solusi favorit saya adalah:

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

Saya tidak tahu tentang uniqatau tentang grep -o, tetapi karena komentar saya di @JourneymanGeek dan @ crazy2be memiliki dukungan seperti itu, mungkin saya harus mengubahnya menjadi anwser sendiri:

Jika Anda tahu hanya ada karakter "baik" (yang ingin Anda hitung) di file Anda, Anda bisa menggunakannya

grep . -o YourFile | sort | uniq -c

Jika hanya beberapa karakter harus dihitung dan yang lainnya tidak (mis. Pemisah)

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

Yang pertama menggunakan wildcard ekspresi reguler ., yang cocok dengan karakter tunggal apa pun. Yang kedua menggunakan 'set karakter yang diterima', tanpa urutan tertentu, kecuali yang -harus datang terakhir ( A-Cditafsirkan sebagai 'karakter apa saja antara Adan C). Diperlukan harga dalam kasus itu agar shell Anda tidak mencoba memperluasnya untuk memeriksa file satu karakter jika ada (dan menghasilkan kesalahan "tidak cocok" jika tidak ada).

Perhatikan bahwa "sort" juga memiliki -uflag nique sehingga hanya melaporkan sesuatu sekali, tetapi tidak ada flag pendamping untuk menghitung duplikat, jadi uniqmemang wajib.

Yang konyol:

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

• truntuk menghapus ( -d) semua karakter kecuali ( -c) ATCGN-
• iconv untuk mengkonversi ke ucs2 (UTF16 terbatas pada 2 byte) untuk menambahkan 0 byte setelah setiap byte,
• lain truntuk menerjemahkan karakter NUL itu ke NL. Sekarang setiap karakter ada di jalurnya sendiri
• sort | uniq -cuntuk menghitung setiap baris uniq

Itu alternatif untuk -oopsi grep non-standar (GNU) .

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 output bukan yang terbaik ...

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

Teori Operasi:

• $ ({command | command} 2> tmp) mengalihkan stderr aliran ke file sementara.
• dd mengeluarkan stdin ke stdout dan menampilkan jumlah byte yang diteruskan ke stderr
• tr -d menyaring satu karakter pada satu waktu
• grep dan urutkan filter output dari dd ke descending order
• awk menghitung perbedaannya
• sort hanya digunakan pada tahap post-processing untuk menangani ketidakpastian keluar dari instance dd

Kecepatan tampaknya 60MBps +

File sampel:

$ cat file
aix
unix
linux

Perintah:

$ 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

Menggabungkan beberapa lainnya

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

Tambahkan | sort -nruntuk melihat hasil dalam urutan frekuensi.

Jawaban singkat:

Jika keadaan memungkinkan, bandingkan ukuran file set karakter rendah ke satu tanpa karakter untuk mendapatkan offset dan hitung saja byte.

Ah, tapi detail yang kusut:

Itu semua adalah karakter Ascii. Satu byte per. File tentu saja memiliki metadata ekstra yang ditambahkan untuk berbagai hal yang digunakan oleh OS dan aplikasi yang membuatnya. Dalam kebanyakan kasus saya akan mengharapkan ini untuk mengambil jumlah ruang yang sama terlepas dari metadata tapi saya akan mencoba untuk mempertahankan keadaan yang sama ketika Anda pertama kali menguji pendekatan dan kemudian memverifikasi bahwa Anda memiliki offset konstan sebelum tidak khawatir tentang hal itu. Gotcha lainnya adalah bahwa jeda baris biasanya melibatkan dua karakter spasi ascii white dan setiap tab atau spasi akan masing-masing. Jika Anda dapat yakin ini akan hadir dan tidak ada cara untuk tahu berapa banyak sebelumnya, saya akan berhenti membaca sekarang.

Ini mungkin tampak seperti banyak kendala, tetapi jika Anda dapat dengan mudah membuat mereka, ini menurut saya sebagai pendekatan yang paling mudah / berkinerja terbaik jika Anda memiliki banyak hal untuk dilihat (yang tampaknya mungkin jika itu adalah DNA). Memeriksa satu ton file untuk panjang dan mengurangi konstanta akan lebih cepat daripada menjalankan grep (atau serupa) pada setiap file.

Jika:

• Ini adalah string sederhana yang tidak terputus dalam file teks murni
• Mereka berada dalam tipe file identik yang dibuat oleh editor teks vanilla non-format yang sama seperti Scite (paste tidak apa-apa selama Anda memeriksa spasi / pengembalian) atau beberapa program dasar yang ditulis seseorang

Dan Dua Hal Yang Mungkin Bukan Masalah Tetapi Saya Akan Mengujinya terlebih dahulu

• Nama file memiliki panjang yang sama
• File-file berada di direktori yang sama

Coba Cari Offset Dengan Melakukan Hal Berikut:

Bandingkan file kosong dengan satu dengan beberapa karakter yang mudah dihitung manusia untuk satu dengan beberapa karakter lebih banyak. Jika mengurangi file kosong dari kedua file lainnya memberi Anda jumlah byte yang cocok dengan jumlah karakter, Anda sudah selesai. Periksa panjang file dan kurangi jumlah kosong itu. Jika Anda ingin mencoba mencari file multi-line, sebagian besar editor melampirkan dua karakter satu-byte khusus untuk jeda baris karena satu cenderung diabaikan oleh Microsoft tetapi Anda harus setidaknya memahami untuk chars white-space dalam hal ini Anda mungkin juga melakukan semuanya dengan grep.

Cara Haskell :

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

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

kerjanya seperti ini:

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

kompilasi dan penggunaan:

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

mungkin tidak bagus untuk file besar.

Perl hack cepat:

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

• -n: Ulangi jalur input tetapi jangan cetak apa pun untuknya
• -l: Strip atau tambahkan jeda baris secara otomatis
• while: beralihlah ke semua kemunculan simbol yang Anda minta di baris saat ini
• END: Pada akhirnya, hasil cetak
• %a: Hash tempat nilai disimpan

Karakter yang tidak muncul sama sekali tidak akan dimasukkan dalam hasil.