计算文件中每个字符数的最快方法是什么？

#1 楼

如果您想要一些真实的速度：

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）内存中，这非常有用，如果您的文件远比ram大。

，当然，如果再加上一点肘油脂，我们可以节省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（GNU sed版本4.2.1）中的一个错误：

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

real    7m44.161s
user    4m53.941s
sys     2m35.593s
]++}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分钟后放弃了

q4312078q

#2 楼

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 -抓住文件foo.text中的字母a和g，以及每个要搜索的字符-。它还在一行中打印一个字符。

sort对其进行排序。这为下一个工具奠定了基础。uniq -c对任何行的重复连续出现进行计数。在这种情况下，由于我们有一个排序的字符列表，因此可以清晰地计算出第一步中提取出的字符的时间

如果foo.txt包含字符串GATTACA-，这就是我d从这组命令中获取

[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

#3 楼

试试这个，灵感来自@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进行管道传输时，最终类似于我们想要的内容： >
附录：如果要总计一个文件中的A，C，G，N，T和-字符数，则可以通过wc -l而不是sort | uniq -c传递grep输出。只需对这种方法稍加修改，就可以计数很多不同的事物。

#4 楼

一个衬里使用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。

#5 楼

类似于Guru的awk方法：

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

#6 楼

使用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

它的工作原理是这样的：



od -a将文件分成ASCII字符。

cut -b 9-消除了前缀od放置。

tr " " \n将字符之间的空格转换为换行符，因此每行只有一个字符。

egrep -v "^$"消除了由此创建的所有多余空白行。 />
sort一起收集每个字符的实例。

uniq -c计算每行的重复次数。

我给它喂“你好，世界！”然后换行并得到以下内容：

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

#7 楼

sed部分基于@Guru的答案，这是另一种使用uniq的方法，类似于David Schwartz的解决方案。

$ cat foo
aix
linux
bsd
foo
$ sed 's/\(.\)/\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

#8 楼

您可以组合使用grep和wc来执行以下操作：

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

grep在给定文件中搜索指定的文本，并且-o选项告诉它仅打印实际匹配（即您要查找的字符），而不是默认值，即打印在其中找到搜索文本的每一行。

wc打印字节，单词和行数每个文件，或者在这种情况下为grep命令的输出。 -w选项告诉它对单词进行计数，每个单词都代表您的搜索字符。当然，-l选项（对行进行计数）也可以使用，因为grep会将每次出现的搜索字符打印在单独的行上。

要一次对多个字符执行此操作数组中的字符并在其上循环：

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

示例：对于包含字符串TGC-GTCCNATGCGNNTCACANN-的文件，输出将是：

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

有关更多信息，请参见man grep和man wc。


这种方法的缺点，正如用户Journeyman Geek在下面的评论中指出的那样，是grep具有每个字符运行一次。根据文件的大小，这可能会导致明显的性能下降。另一方面，以这种方式完成操作后，可以快速查看正在搜索的字符并添加/删除它们，因为它们与其余代码位于不同的行中，因此容易一些。

#9 楼

使用22hgp10a.txt中的序列线，我系统上grep和awk之间的时序差异使使用awk成为可能...

[编辑]：看到Dave的编译解决方案后，也忘记了awk，因为他在此文件中需要约0.1秒才能完成，可以进行完全区分大小写的计数。

# 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

鬼狗的不区分大小写的版本需要约14秒即可完成。
< br sed在此问题的公认答案中得到解释。
基准测试与在该问题的公认答案中相同。
ghostdog74的公认答案就是在该问题上。

#10 楼

我认为任何体面的实现都可以避免排序。但是，由于要全部读取4次也是一个坏主意，我认为可以以某种方式生成一个流，该流经过4个过滤器，每个字符一个，过滤掉，并以某种方式计算流的长度。

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

然后，累积总和存储在tmp [0-6] .txt中。因此工作仍在进行中

这种方法只有13个管道，它转换为不到1 Mb的内存。
当然，我最喜欢的解决方案是：

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

#11 楼

我既不知道uniq也不知道grep -o，但是由于我对@JourneymanGeek和@ crazy2be的评论有这样的支持，也许我应该把它变成一个自己的答案：

如果您知道有文件中仅包含“好”字符（您要计数的字符），则可以使用

grep . -o YourFile | sort | uniq -c

如果仅必须计算一些字符而不计算其他字符（即，分隔符） ）

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

第一个使用正则表达式通配符.，它匹配任何单个字符。第二个使用“可接受的字符集”，没有特定的顺序，只是-必须排在最后（A-C被解释为“ A和C之间的任何字符”）。在这种情况下，必须使用引号，以便您的shell不会尝试将其扩展为检查单个字符文件（如果有的话）（如果没有则产生“ no match”错误）。

请注意，“ sort”还具有一个-u nique标志，因此它仅报告一次，但没有伴随标志来计数重复项，因此uniq确实是必需的。

#12 楼

一个愚蠢的人：

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

tr删除（-d）除（-c）ATCGN-

iconv转换为ucs2（UTF16限制为2个字节），以便在每个字节后添加一个0字节，另一个tr将这些NUL字符转换为NL。现在每个字符都在自己的行上

sort | uniq -c来计数每条uniq行

这是非标准（GNU）-o grep选项的替代方法。

评论

---

您能否在此简要说明命令和逻辑？

–安德鲁·兰伯特（Andrew Lambert）
2012年10月10日23:09

---

#13 楼

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-
real    0m0.176s
user    0m0.200s
sys     0m0.160s
2069046
2070218
2061086
2057418
2070062
2052266
)>=0) { print s-q4312078q} s=q4312078q }'

输出格式不是最好的...

q4312078q

工作原理：


$（{command | command} 2> tmp）将流的stderr重定向到一个临时文件。tr -d过滤器一次输出一个字符
grep并排序过滤dd的输出到降序
awk计算差值
sort仅用于后处理阶段以处理出口的不确定性dd

实例的速度似乎是60MBps +

评论

---

改进：摆脱tmp？使用“粘贴”来打印涉及的信件？

– Aki Suihkonen
2012年10月11日，9：09

---

#14 楼

示例文件：

$ cat file
aix
unix
linux

命令：

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

#15 楼

结合其他几个

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

添加| sort -nr以按频率顺序查看结果。

#16 楼

简短答案：

如果情况允许，将低字符集的文件大小与无字符的文件大小进行比较，以获取偏移量并仅计算字节数。

但是杂乱的细节：

这些都是Ascii字符。每一个字节当然，文件还具有额外的元数据，用于处理OS和创建该文件的应用所使用的各种内容。在大多数情况下，无论元数据如何，我都希望它们占用相同的空间，但是当您首先测试该方法，然后在不担心它的情况下，验证您的偏移量恒定时，我会尝试保持相同的环境。另一个难题是，换行符通常包含两个ascii空格字符，并且任何制表符或空格将各为一个。如果您可以确定这些条件将存在并且无法事先知道有多少，我现在就停止阅读。

这似乎有很多限制，但是如果您可以轻松地建立它们，如果您要看一堆（如果是脱氧核糖核酸，那似乎很有可能），这将使我成为最简单/性能最佳的方法。检查一吨文件的长度并减去一个常数比在每个文件上运行grep（或类似文件）要快得多。

如果：


纯文本文件中的简单不间断字符串
它们是由相同的香草非格式文本编辑器（如Scite）创建的相同文件类型（只要您检查空格/返回，粘贴就可以了）或某人编写的一些基本程序

两件事可能不重要，但我会先进行测试


文件名长度相等
文件在同一位置目录

通过执行以下操作尝试查找偏移：

将一个空文件与一个带有几个易于计数的字符的文件与另一个与几个字符比较的文件进行比较。如果从其他两个文件中减去空文件后得到的字节数与字符数相匹配，就可以了。检查文件长度，然后减去该空量。如果要尝试找出多行文件，大多数编辑器都会为换行符附加两个特殊的一字节字符，因为一个字符会被Microsoft忽略，但是在这种情况下，您至少必须使用grep来换行您也可以使用grep来完成所有操作。

#17 楼

Haskell方式：

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

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

它的工作原理是：

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

编译和使用：

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

可能不适用于大文件。

#18 楼

快速的perl破解：

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

-n：遍历输入行但不打印任何内容

-l：自动删除或添加换行符

while：遍历当前行中所有出现的所需符号
/>
END：最后，打印结果

%a：存储值的哈希值

根本不会出现的字符包含在结果中。