"durchschnittliche Länge der Sequenzen in einer Fasta-Datei": Können Sie diesen Erlang-Code verbessern?

Question

Ich versuche, die mittlere Länge von fasta sequences mit Erlang zu erhalten. Eine fasta Datei sieht wie folgt aus

>title1 
ATGACTAGCTAGCAGCGATCGACCGTCGTACGC 
ATCGATCGCATCGATGCTACGATCGATCATATA 
ATGACTAGCTAGCAGCGATCGACCGTCGTACGC 
ATCGATCGCATCGATGCTACGATCTCGTACGC 
>title2 
ATCGATCGCATCGATGCTACGATCTCGTACGC 
ATGACTAGCTAGCAGCGATCGACCGTCGTACGC 
ATCGATCGCATCGATGCTACGATCGATCATATA 
ATGACTAGCTAGCAGCGATCGACCGTCGTACGC 
>title3 
ATCGATCGCATCGAT(...) 

Ich habe versucht, diese Frage answser den folgenden Erlang Code verwendet:

-module(golf). 
-export([test/0]). 

line([],{Sequences,Total}) -> {Sequences,Total}; 
line(">" ++ Rest,{Sequences,Total}) -> {Sequences+1,Total}; 
line(L,{Sequences,Total}) -> {Sequences,Total+string:len(string:strip(L))}. 

scanLines(S,Sequences,Total)-> 
     case io:get_line(S,'') of 
      eof -> {Sequences,Total}; 
      {error,_} ->{Sequences,Total}; 
      Line -> {S2,T2}=line(Line,{Sequences,Total}), scanLines(S,S2,T2) 
     end . 

test()-> 
    {Sequences,Total}=scanLines(standard_io,0,0), 
    io:format("~p\n",[Total/(1.0*Sequences)]), 
    halt(). 

Compilation/Execution:

erlc golf.erl 
erl -noshell -s golf test < sequence.fasta 
563.16 

dieser Code scheint Für eine kleine Fasta-Datei funktioniert es gut, aber es dauert Stunden, um einen größeren zu analysieren (> 100Mo). Warum ? Ich bin ein Erlang-Neuling, kannst du bitte diesen Code verbessern?

Answer 1

Wenn Sie wirklich schnelle IO brauchen, dann müssen Sie ein bisschen mehr Tricks als üblich tun.

-module(g). 
-export([s/0]). 
s()-> 
    P = open_port({fd, 0, 1}, [in, binary, {line, 256}]), 
    r(P, 0, 0), 
    halt(). 
r(P, C, L) -> 
    receive 
    {P, {data, {eol, <<$>:8, _/binary>>}}} -> 
     r(P, C+1, L); 
    {P, {data, {eol, Line}}} -> 
     r(P, C, L + size(Line)); 
    {'EXIT', P, normal} -> 
     io:format("~p~n",[L/C]) 
    end. 

Es ist schnellste IO, wie ich weiß, aber -noshell -noinput beachten. Compile gerade wie erlc +native +"{hipe, [o3]}" g.erl aber mit -smp disable

erl -smp disable -noinput -mode minimal -boot start_clean -s erl_compile compile_cmdline @cwd /home/hynek/Download @option native @option '{hipe, [o3]}' @files g.erl 

und laufen:

time erl -smp disable -noshell -mode minimal -boot start_clean -noinput -s g s < uniprot_sprot.fasta 
352.6697028442464 

real 0m3.241s 
user 0m3.060s 
sys  0m0.124s 

Mit -smp enable aber nativer es dauert:

$ erlc +native +"{hipe, [o3]}" g.erl 
$ time erl -noshell -mode minimal -boot start_clean -noinput -s g s<uniprot_sprot.fasta 
352.6697028442464 

real 0m5.103s 
user 0m4.944s 
sys  0m0.112s 

Byte-Code, sondern mit -smp disable (fast gleichauf mit nativer weil die meiste Arbeit im Hafen gemacht wird!):

$ erlc g.erl 
$ time erl -smp disable -noshell -mode minimal -boot start_clean -noinput -s g s<uniprot_sprot.fasta 
352.6697028442464 

real 0m3.565s 
user 0m3.436s 
sys  0m0.104s 

Nur der Vollständigkeit halber Bytecode mit smp:

$ time erl -noshell -mode minimal -boot start_clean -noinput -s g s<uniprot_sprot.fasta 
352.6697028442464 

real 0m5.433s 
user 0m5.236s 
sys  0m0.128s 

Zum Vergleich sarnoldversion mir falsche Antwort gibt und mehr auf der gleichen HW nimmt:

$ erl -smp disable -noinput -mode minimal -boot start_clean -s erl_compile compile_cmdline @cwd /home/hynek/Download @option native @option '{hipe, [o3]}' @files golf.erl 
./golf.erl:5: Warning: variable 'Rest' is unused 
$ time erl -smp disable -noshell -mode minimal -s golf test 
359.04679841439776 

real 0m17.569s 
user 0m16.749s 
sys  0m0.664s 

EDIT: Ich habe sah bei den Eigenschaften von uniprot_sprot.fasta und ich bin ein bisschen überrascht. Es ist 3824397 Zeilen und 232MB. Das bedeutet, dass die Version -smp disabled 1,18 Millionen Textzeilen pro Sekunde verarbeiten kann (71MB/s in leitungsorientiertem IO).

Answer 2

Auch ich lerne Erlang, danke für die Spaßfrage.

Ich verstehe das Arbeiten mit Erlang-Zeichenfolgen, da Listen von Zeichen sehr langsam sein können; Wenn Sie work with binaries stattdessen können Sie einige Leistungssteigerungen sehen. Ich weiß nicht, wie Sie Strings mit willkürlicher Länge mit Binärdateien verwenden würden, aber wenn Sie es lösen können, sollte es helfen.

Auch wenn es Ihnen nichts ausmacht, direkt mit einer Datei statt standard_io zu arbeiten, könnten Sie vielleicht die Dinge beschleunigen, indem Sie file:open(..., [raw, read_ahead]) verwenden. raw bedeutet, dass die Datei im Dateisystem des lokalen Knotens liegen muss, und read_ahead gibt an, dass Erlang Datei-IO mit einem Puffer ausführen soll. (Denken Sie daran, Cs stdio Einrichtungen mit und ohne Pufferung zu verwenden.)

Ich würde erwarten, dass die read_ahead den größten Unterschied macht, aber alles mit Erlang enthält den Ausdruck "Benchmark vor dem Raten".

EDIT

file:open("uniprot_sprot.fasta", [read, read_ahead]) Mit bekommt 1m31s auf dem vollen uniprot_sprot.fasta-Datensatz. (Durchschnitt 359.04679841439776.)

Mit file:open(.., [read, read_ahead]) und file:read_line(S), bekomme ich 0m34s.

Mit file:open(.., [read, read_ahead, raw]) und file:read_line(S), bekomme ich 0m9s. Ja, neun Sekunden.

Hier ist, wo ich jetzt stehe; wenn Sie herausfinden können, wie Binärdateien zu verwenden, anstatt von Listen, könnte es noch mehr Verbesserungen sehen:

-module(golf). 
-export([test/0]). 

line([],{Sequences,Total}) -> {Sequences,Total}; 
line(">" ++ Rest,{Sequences,Total}) -> {Sequences+1,Total}; 
line(L,{Sequences,Total}) -> {Sequences,Total+string:len(string:strip(L))}. 

scanLines(S,Sequences,Total)-> 
     case file:read_line(S) of 
      eof -> {Sequences,Total}; 
      {error,_} ->{Sequences,Total}; 
      {ok, Line} -> {S2,T2}=line(Line,{Sequences,Total}), scanLines(S,S2,T2) 
     end . 

test()-> 
    F = file:open("/home/sarnold/tmp/uniprot_sprot.fasta", [read, read_ahead, raw]), 
    case F of 
    { ok, File } -> 
     {Sequences,Total}=scanLines(File,0,0), 
     io:format("~p\n",[Total/(1.0*Sequences)]); 
    { error, Reason } -> 
      io:format("~s", Reason) 
    end, 
    halt(). 

Answer 3

Es sieht aus wie Ihre große Performance-Probleme haben durch Öffnen der Datei im Raw-Modus gelöst worden, aber hier ist ein paar Gedanken wenn Sie diesen Code weiter optimieren müssen.

Lernen und verwenden Sie fprof.

Sie verwenden hauptsächlich string:strip/1, um den abschließenden Zeilenumbruch zu entfernen. Da erlang-Werte unveränderlich sind, müssen Sie eine vollständige Kopie der Liste (mit der gesamten zugeordneten Speicherzuweisung) erstellen, nur um das letzte Zeichen zu entfernen. Wenn Sie wissen, dass die Datei wohlgeformt ist, ziehen Sie einfach eins von Ihrer Zählung ab, sonst würde ich versuchen, eine Längenfunktion zu schreiben, die die Anzahl der relevanten Zeichen zählt und irrelevante ignoriert.

Ich bin vorsichtig Ratschläge, die besagt, dass Binärdateien besser als Listen sind, aber angesichts wie wenig Verarbeitung Sie es wahrscheinlich hier der Fall ist. Die ersten Schritte bestehen darin, die Datei im Binärmodus zu öffnen und erlang:size/1 zu verwenden, um die Länge zu finden.

Es hat keinen Einfluss auf die Leistung (signifikant), aber die Multiplikation mit 1.0 in Total/(1.0*Sequences) ist nur in Sprachen mit defekter Division erforderlich. Erlang Division funktioniert korrekt.

Answer 4

Der Aufruf string:len(string:strip(L)) durchquert die Liste mindestens zweimal (Ich bin mir der Zeichenfolge nicht bewusst: Streifenimplementierung). Stattdessen könnten Sie eine einfache Funktion schreiben die Zeilenlänge w/0 die Räume zu zählen:

stripped_len(L) -> 
    stripped_len(L, 0). 

stripped_len([$ |L], Len) -> 
    stripped_len(L, Len); 

stripped_len([_C|L], Len) -> 
    stripped_len(L, Len + 1); 

stripped_len([], Len) -> 
    Len. 

Das gleiche Verfahren kann auch auf Binärdateien angewendet werden.

Answer 5

Haben Sie Elixir (elixir-lang.org) versucht, das auf Erlang läuft und eine ähnliche Syntax wie Ruby hat. Elixir löst String Probleme auf folgende Weise:

Elixir Strings sind UTF-8-Binärdateien, mit all den rohen Geschwindigkeit und Speicher Einsparungen bringt. Elixir hat ein String-Modul mit Unicode Funktionalität eingebaut und ist ein großartiges Beispiel für das Schreiben von Code, schreibt Code. String.Unicode liest verschiedene Unicode-Datenbank-Dumps wie als UnicodeData.txt, um Unicode-Funktionen für das String-Modul zu generieren, das direkt aus diesen Daten aufgebaut ist!(http://devintorr.es/blog/2013/01/22/the-excitement-of-elixir/)

Fragen Sie sich nur, ob Elixier schneller wäre?