Вопрос: Каков самый быстрый способ подсчета количества каждого символа в файле?


Я хочу считать символы A's's's's's's's's и «-» в файле, или каждую букву, если необходимо, есть ли быстрая команда Unix для этого?


120


Источник


Подсчет баз в цепях ДНК? - Indrek
Мне нравится этот вопрос, так много разных подходов и инструментов, используемых для решения одной и той же проблемы. - Journeyman Geek♦
Хех, это пограничный код-гольф - Earlz
если кто-то заинтересован в версии 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 870 @ 2,93 ГГц он составляет чуть более 600 МБ / с:

$ 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,1 ГБ / с заканчиваются в:

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[$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
Эпический изгиб требований вопроса - я одобряю; 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: Проблема заключается в том, что он генерирует много данных, которые затем перенаправляются для сортировки. Было бы дешевле позволить программе анализировать каждый символ. См. Ответ Дейва для ответа O (N) на O (N) памяти. - Martin Ueding
@Pitto Родные Windows-сборки coreutils широко доступны - просто спросите Google или somesuch - OrangeDog


Попробуйте этот, вдохновленный ответом @ Journeyman.

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

Ключ - знать о опция -o для grep, Это разделяет совпадение, так что каждая выходная строка соответствует одному экземпляру шаблона, а не всей строке для любой строки, которая соответствует. Учитывая эти знания, все, что нам нужно, это шаблон для использования и способ подсчета строк. Используя регулярное выражение, мы можем создать дизъюнктивный шаблон, который будет соответствовать любому из символов, которые вы упоминаете:

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



Мне действительно нужно вникать в раввилоты, которые являются ядрами и регулярным выражением. Это несколько более элегантно, чем мое; p - Journeyman Geek♦
@JourneymanGeek: регулярное выражение Learge хорошо стоит того, так как оно полезно для многих вещей. Просто поймите, что это ограничения, и не злоупотребляйте властью, пытаясь сделать что-то, выходящее за рамки возможностей regexes, например попытка разбора 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





Подобно Гуру 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 часть основана на @ Ответ Гуру, вот еще один подход, использующий uniq, подобно решению Дэвида Шварца.

$ 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


Вы можете комбинировать 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 должен выполняться один раз для каждого символа. В зависимости от того, насколько велики ваши файлы, это может привести к заметному поражению производительности. С другой стороны, когда это делается, немного проще быстро увидеть, какие символы ищутся, и добавлять / удалять их, поскольку они находятся на отдельной строке от остальной части кода.


7



им нужно будет повторить его за каждого, кто захочет ... Я бы добавил. Я мог бы поклясться, что есть более элегантное решение, но ему нужно больше пить; - Journeyman Geek♦
@JourneymanGeek Хорошая точка. Один из подходов, который приходит на ум, заключается в том, чтобы помещать символы в массив и прокручивать его. Я обновил свой пост. - Indrek
слишком сложная ИМО. Просто используйте grep -e a -e t и так далее. Если вы поместите его в массив и пропустите его, не нужно ли вам запускать цикл grep один раз за символ? - Journeyman Geek♦
@JourneymanGeek Вы, вероятно, правы. uniq -c также кажется лучшим способом получения хорошо отформатированного вывода. Я не гуру nix, выше всего это то, что мне удалось собрать из моих ограниченных знаний и некоторых справочных страниц :) - Indrek
Так же, как и я, p, и одно из моих заданий в прошлом году включало сортировку около 5000 записей в адресной книге, а uniq упростил LOT. - Journeyman Geek♦


Используя строки последовательности из 22hgp10a.txt, разница во времени между grep и awk в моей системе делает использование awk способом ...

[Edit]: После того, как скомпилированное решение 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

Нечувствительная к регистру версия ghostdog завершена за ~ 14 секунд.

Сед объясняется в принятом ответе на этот вопрос,
Бенчмаркинг - как в принятом ответе на этот вопрос,
Принятый ответ ghostdog74 заключался в том, чтобы этот вопрос,


7



Ты можешь s/cache[letters[x]]/cache[letters[x]]+cache[toupper(letters[x])] чтобы сделать его регистрозависимым, не влияя на его скорость. - Dave


Я думаю, что любая достойная реализация избегает сортировки. Но поскольку это также плохая идея читать все 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 Мб памяти.
Конечно, мое любимое решение:

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

6



Это очень приятное использование tr, - adavid


Я не знал о uniq ни о grep -o, но поскольку мои комментарии к @JourneymanGeek и @ crazy2be получили такую ​​поддержку, возможно, я должен превратить ее в своего собственного автора:

Если вы знаете, что в вашем файле есть только «хорошие» персонажи (те, которые вы хотите подсчитать), вы можете пойти

grep . -o YourFile | sort | uniq -c

Если нужно подсчитать только некоторые символы, а другие нет (т. Е. Разделители)

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

Первый использует шаблон регулярного выражения ., которые соответствуют любому одиночному символу. Второй использует «набор принятых символов» без какого-либо конкретного порядка, за исключением того, что - должно быть последним (A-C интерпретируется как «любой символ междуA а также C). В этом случае необходимо указать цитаты, чтобы ваша оболочка не пыталась расширять это, чтобы проверять односимвольные файлы, если они есть (и выдает ошибку «нет совпадения», если нет).

Обратите внимание, что «сортировка» также имеет -unique, чтобы он сообщал о событиях только один раз, но не добавлял флаг сопутствующего копирования для подсчета дубликатов, поэтому uniq действительно является обязательным.


4



- не должен появляться последним, если вы избегаете его обратным слэшем: '[A\-CTGN]' должен работать нормально. - Indrek