題 計算文件中每個字符數的最快方法是什麼?


我想在一個文件中計算A的T的C的G的N和“ - ”字符,或者如果需要的話,每個字母是否都有一個快速的Unix命令來執行此操作?


120


起源


計算DNA鏈的鹼基? - Indrek
我喜歡這個問題,許多不同的方法和工具用於解決同樣的問題。 - Journeyman Geek♦
嘿,這是邊緣碼 - 高爾夫 - Earlz
如果somone對windows powershell版本感興趣: [System.IO.File]::ReadAllText("C:\yourfile.txt").ToCharArray() | Group-Object $_ | Sort Count -Descending - Guillaume86
好吧我覺得我找到了純粹的PS方式: Get-Content "C:\eula.3082.txt" | % { $_.ToCharArray() } | Group-Object | Sort Count -Descending - Guillaume86


答案:


如果你想要一些真正的速度:

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;

是一個令人難以置信的快速偽單行。

一個簡單的測試顯示我的Core i7 CPU 870 @ 2.93GHz 它的數量剛剛超過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

與涉及排序的解決方案不同,這個解決方案在常量(4K)內存中運行,如果您的文件遠遠大於您的內存,這非常有用。

而且,當然還有一點肘部油脂,我們可以減少0.7秒:

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;

網隊剛剛超過1.1GB / s完成:

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

為了比較,我在這個頁面上測試了一些似乎有某種速度承諾的其他解決方案。

sed/awk 解決方案做出了勇敢的努力,但在30秒後死亡。有了這麼簡單的正則表達式,我希望這是sed中的一個bug(GNU sed版本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

perl方法似乎也很有希望,但是在運行它7分鐘後我放棄了

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

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

135



+1對於一個理智的解決方案,當它有大量數據時,而不僅僅是少數幾個字節。這些文件雖然在磁盤緩存中,不是嗎? - Daniel Beck♦
巧妙的是,它在處理中具有O(N)的複雜性,在內存中具有O(1)的複雜性。管道通常在處理中具有O(N log N)(或甚至O(N ^ 2))和O(N)在存儲器中。 - Martin Ueding
不過,您正在擴展“命令行”的定義。 - gerrit
史詩彎曲問題的要求 - 我贊成; p。 superuser.com/a/486037/10165 < - 有人跑了基準,而且這個 是 最快的選擇。 - Journeyman Geek♦
+1我很欣賞我在正確的地方使用C語言。 - Jeff Ferland


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

將伎倆作為一個班輪。但是需要一點解釋。

grep -o foo.text -e A -e T -e C -e G -e N -e - greps文件foo.text用於字母a和g以及字符 - 對於您要搜索的每個字符。它還會在一行中打印一個字符。

sort 按順序排序。這為下一個工具奠定了基礎

uniq -c 計算任何行的重複連續出現次數。在這種情況下,由於我們有一個排序的字符列表,我們得到一個巧妙的計數,我們在第一步中看到的字符

如果foo.txt包含字符串 GATTACA-這是我從這組命令中得到的

[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

118



血腥的unix魔法! :d - Pitto
如果文件中只有CTAG字符,則正則表達式本身變得毫無意義,對吧? grep -o。 |排序| uniq -c同樣可以工作,afaik。 - sylvainulg
+1我已經使用grep 25年並且不知道 -o。 - LarsH
@JourneymanGeek:問題在於它會生成大量數據,然後轉發到排序。讓程序解析每個字符會更便宜。請參閱Dave對O(1)而非O(N)內存複雜性答案的回答。 - Martin Ueding
@Pitto本機Windows版本的coreutils廣泛可用 - 只要問Google或其他人 - OrangeDog


嘗試這個,受@ Journeyman的回答啟發。

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

關鍵是了解 grep的-o選項。這會將匹配分開,以便每個輸出行對應於模式的單個實例,而不是匹配任何行的整行。有了這些知識,我們所需要的只是一種使用模式,以及一種計算線條的方法。使用正則表達式,我們可以創建一個與你提到的任何字符匹配的析取模式:

A|T|C|G|N|-

這意味著“匹配A或T或C或G或N或 - ”。手冊描述 您可以使用各種正則表達式語法

現在我們的輸出看起來像這樣:

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

我們的最後一步是合併和計算所有類似的線,這可以簡單地用一個完成 sort | uniq -c,就像@Journeyman的回答一樣。排序給我們這樣的輸出:

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

通過管道輸送時 uniq -c,最後類似於我們想要的:

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

附錄:如果要總計文件中A,C,G,N,T和 - 字符的數量,可以通過管道輸出grep輸出 wc -l 代替 sort | uniq -c。只需對此方法稍作修改,就可以計算出許多不同的東西。


45



我真的需要深入研究coreutils和regex的rabbitholes。這比我的優雅一點; p - Journeyman Geek♦
@JourneymanGeek:學習正則表達式是值得的,因為它對很多東西很有用。只是理解它的局限性,不要試圖做一些超出正則表達式範圍的事情來濫用權力,比如 試圖解析XHTML。 - crazy2be
grep -o'[ATCGN-]'在這裡可能更具可讀性。 - sylvainulg


使用Python計算所有字母的一個班輪:

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

...生成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}

有趣的是,在代碼清晰度方面,Python大多數時候都可以輕鬆擊敗bash。


13





與Guru相似 awk 方法:

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

11





在使用UNIX幾年後,您可以非常熟練地將許多小操作鏈接在一起,以完成各種過濾和計數任務。每個人都有自己的風格 - 有些人喜歡 awk 和 sed,有些喜歡 cut 和 tr。這是我的方式:

要處理特定文件名:

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

或作為過濾器:

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

它的工作原理如下:

  1. od -a 將文件分隔為ASCII字符。
  2. cut -b 9- 消除了前綴 od 放。
  3. tr " " \\n 將字符之間的空格轉換為換行符,這樣每行就有一個字符。
  4. egrep -v "^$" 擺脫了所創造的所有額外空白行。
  5. sort 收集每個角色的實例。
  6. uniq -c 計算每一行的重複次數。

我餵牠“你好,世界!”然後換行,得到了這個:

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

10





sed 部分基於 @ Guru的回答,這是另一種使用方法 uniq,類似於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

9



使用 [[:alpha:]] 而不是 . 在 sed 只匹配字符而不是換行符。 - Claudius
[[:alpha:]] 如果你也試圖匹配像這樣的東西會失敗 -,這是在問題中提到的 - Izkata
正確。為sed添加第二個表達式以首先過濾掉其他所有內容然後在所需字符上顯式匹配可能更好: sed -e 's/[^ATCGN-]//g' -e 's/\([ATCGN-]\)/\1\n/g' foo | sort | uniq -c。但是,我不知道如何擺脫那裡的新線: - Claudius