سؤال ما أسرع طريقة لحساب عدد كل حرف في الملف؟


أريد أن أحسب حرف A's C's N's C's و "-" في ملف ، أو كل حرف إذا لزم الأمر ، هل هناك أمر Unix سريع للقيام بذلك؟


120


الأصل


عد القواعد في فروع الحمض النووي؟ - 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;

هو سريع شبه واحد بشكل لا يصدق سريع.

يظهر اختبار بسيط أنه في بلدي كور i7 CPU 870 @ 2.93GHz يتم حسابه عند أكثر من 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.1GB / ثانية في التشطيب:

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

على سبيل المقارنة ، اختبرت بعض الحلول الأخرى في هذه الصفحة والتي يبدو أنها تمتلك نوعًا من وعد السرعة.

ال sed/awk جعل الحل جهدا شجاعا ، لكنه توفي بعد 30 ثانية. مع مثل هذا التعابير البسيطة ، أتوقع أن يكون هذا خطأ في لغة الترميز المغناطيسي (GNU sed version 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

بدت طريقة بيرل واعدة كذلك ، لكني استسلمت بعد تشغيلها لمدة 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



دموي يونيكس السحر! :د - Pitto
إذا كان هناك فقط CTAG- الأحرف في الملفات الخاصة بك ، يصبح regexp نفسه لا طائل منه ، أليس كذلك؟ grep -o. | نوع سوف uniq -c تعمل على قدم المساواة بشكل جيد ، afaik. - sylvainulg
+1 كنت أستخدم grep لمدة 25 عامًا ولم أكن أعرف -o. - LarsH
JourneymanGeek: المشكلة في هذا هو أنه يولد الكثير من البيانات التي يتم توجيهها بعد ذلك إلى الفرز. سيكون من الأرخص السماح لبرنامج تحليل كل حرف. انظر إجابة ديف عن O (1) بدلاً من تعقيد الذاكرة O (N). - Martin Ueding
@ يبني ويندوز الأصلية من النوى الأساسية متاحة على نطاق واسع - فقط اسأل جوجل أو 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



أنا حقا بحاجة إلى الخوض في rabbitholes التي هي coreutils و regex. هذا هو أكثر أناقة إلى حد ما من الألغام لذلك ؛ p - Journeyman Geek♦
JourneymanGeek: Lange regex تستحق العناء ، لأنها مفيدة للكثير من الأشياء. ما عليك سوى فهم القيود ، وعدم إساءة استخدام السلطة من خلال محاولة القيام بأشياء خارج نطاق regexes capabilites ، مثل تحاول تحليل XHTML. - crazy2be
grep -o '[ATCGN-]' يمكن أن يكون أكثر قابلية للقراءة هنا. - sylvainulg


واحد بطانة عد جميع الرسائل باستخدام بايثون:

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

من المثير للاهتمام أن نرى كيف أن بايثون في معظم الأوقات يمكن أن تضرب بسهولة حتى من حيث وضوح الشفرة.


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
صيح. قد يكون من اللطيف إضافة تعبير ثانٍ إلى s 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 المهوس أدناه في تعليق ، هو ذلك grep يجب أن يتم تشغيله مرة واحدة لكل حرف. اعتمادًا على حجم الملفات الكبيرة ، يمكن أن يؤدي ذلك إلى حدوث أداء ملحوظ. من ناحية أخرى ، عند القيام بهذه الطريقة يكون من الأسهل قليلاً رؤية الأحرف التي يتم البحث عنها ، ولإضافتها / إزالتها ، لأنها موجودة على سطر منفصل عن بقية الشفرة.


7



سيحتاجون لتكرارها لكل charecter يريدون ... سأضيف. أستطيع أن أقسم أن هناك حلاً أكثر أناقة ولكنه يحتاج إلى مزيد من الدعس ؛ ص - Journeyman Geek♦
JourneymanGeek نقطة جيدة. أحد الأساليب التي تتبادر إلى الذهن هو وضع الأحرف في صفيف والتكرار من خلالها. لقد قمت بتحديث منصبي. - Indrek
المنظمة البحرية الدولية معقدة للغاية. مجرد استخدام grep -e aeee وهلم جرا. إذا وضعته في صفيف وحلقة خلاله ، ألن تضطر إلى المرور عبر دورة grep مرة واحدة لكل حرف؟ - Journeyman Geek♦
JourneymanGeek ربما كنت على حق. uniq -c يبدو أيضا وكأنه طريقة أفضل للحصول على إخراج منسق بشكل جيد. أنا لا * نيكس المعلم ، ما سبق هو فقط ما تمكنت من وضعها معا من معرفتي المحدودة وبعض الصفحات الرجل :) - Indrek
وكذلك فعلت أنا ؛ ف ، وواحدة من المهام التي قمت بها في الفصل الأخير شملت فرز ما يقرب من 5000 من مداخل دفتر العناوين ، وجعلها uniq أسهل بكثير. - Journeyman Geek♦


باستخدام خطوط التسلسل من 22hgp10a.t.t فرق التوقيت بين grep و awk على نظام بلدي جعل استخدام awk الطريق للذهاب ...

[عدل]: بعد أن رأى حل ديف الذي تم جمعه ننسى 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 's مكتمل في 14 ثانية ~.

وأوضح السيد في الجواب المقبول ل هذا السؤال.
المقياس كما هو الحال في الإجابة المقبولة على هذا السؤال.
الجواب المقبول من قبل ghostdog74 كان هذا السؤال.


7



يمكنك s/cache[letters[x]]/cache[letters[x]]+cache[toupper(letters[x])] ليجعلها غير حساسة دون التأثير على سرعتها. - Dave