"średnia długość sekwencji w pliku fasta": Czy możesz poprawić ten kod Erlanga?

Question

Próbuję uzyskać średnią długość fasta sequences przy użyciu Erlang. Plik FASTA wygląda to

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

Próbowałem answser to pytanie za pomocą poniższego Erlang kod:

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

kompilacja/wykonanie:

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

ten kod wydaje działa dobrze dla małego pliku fasta, ale parsowanie zajmuje więcej godzin (> 100Mo). Czemu ? Jestem nowicjuszem z Erlangu, czy możesz poprawić ten kod?

Answer 1

Jeśli potrzebujesz naprawdę szybkiego IO, musisz zrobić trochę więcej sztuczek niż zwykle.

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

Jest to najszybszy IO, jak wiem, ale Uwaga -noshell -noinput. kompilacji podobnie jak erlc +native +"{hipe, [o3]}" g.erl ale z -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 

i uruchom:

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 

Z -smp enable ale rodzimy zajmuje: kod

$ 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 ale z -smp disable (prawie na równi z rodzimymi ponieważ większość pracy odbywa się w porcie!):

$ 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 

Tylko dla kompletności kodu bajtowego z 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 

Dla porównania sarnoldversion daje mi błędną odpowiedź i zajmuje więcej na tym samym HW:

$ 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: Szukałem o cechach uniprot_sprot.fasta i jestem trochę zaskoczony. Jest to 3824397 wierszy i 232 MB. Oznacza to, że wersja -smp disabled może obsłużyć 1,18 miliona linii tekstu na sekundę (71 MB/sw zorientowanym liniowo IO).

Answer 2

Ja też uczę się Erlanga, dzięki za zabawne pytanie.

Rozumiem, że pracuję z ciągami Erlanga, ponieważ listy postaci mogą być bardzo wolne; jeśli możesz work with binaries zamiast tego powinieneś zobaczyć wzrost wydajności. Nie wiem, w jaki sposób używałbyś łańcuchów o dowolnej długości z plikami binarnymi, ale jeśli potrafisz to rozwiązać, to powinno ci to pomóc.

Ponadto, jeśli nie masz nic przeciwko pracy bezpośrednio z plikiem, a nie standard_io, być może możesz przyspieszyć działanie przy użyciu file:open(..., [raw, read_ahead]). raw oznacza, że ​​plik musi znajdować się w systemie plików węzła lokalnego, a read_ahead określa, że ​​Erlang powinien wykonać plik IO z buforem. (Pomyśl o użyciu stdio C z buforowaniem i bez niego.)

Spodziewałbym się, że, aby uzyskać największą różnicę, ale wszystko z Erlangiem zawiera wyrażenie "benchmark before guessing".

EDIT

Korzystanie file:open("uniprot_sprot.fasta", [read, read_ahead]) dostaje 1m31s na pełnym uniprot_sprot.fasta zbiorze. (Średnio 359.04679841439776.)

Używając file:open(.., [read, read_ahead]) i file:read_line(S), otrzymuję 0m34s.

Używanie file:open(.., [read, read_ahead, raw]) i file:read_line(S), otrzymuję 0m9s. Tak, dziewięć sekund.

Oto, gdzie stoję teraz; czy można dowiedzieć się, jak korzystać z plików binarnych zamiast list, może to zobaczyć jeszcze lepszy:

-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

To wygląda jak wielkie problemy z wydajnością zostały rozwiązane przez otwarcie pliku w trybie surowym, ale oto kilka myśli jeśli chcesz zoptymalizować ten kod dalej.

Ucz się i używaj fprof.

Używasz głównie string:strip/1, aby usunąć końcowy znak nowej linii. Ponieważ wartości erlang są niezmienne, musisz wykonać kompletną kopię listy (ze wszystkimi powiązanymi przypisaniami pamięci), aby usunąć ostatni znak. Jeśli wiesz, że plik jest dobrze sformułowany, po prostu odejmij jedną od swojej liczby, inaczej spróbowałbym napisać funkcję długości, która zlicza liczbę odpowiednich znaków i ignoruje nieistotne.

Jestem ostrożny, jeśli chodzi o porady, które mówią, że pliki binarne są lepsze niż listy, ale biorąc pod uwagę, jak mało jest przetwarzania, prawdopodobnie tak jest w tym przypadku. Pierwszym krokiem jest otwarcie pliku w trybie binarnym i użycie numeru erlang:size/1 w celu znalezienia długości.

Nie wpłynie to na wydajność (znacząco), ale mnożenie przez 1.0 w Total/(1.0*Sequences) jest konieczne tylko w językach z uszkodzonym podziałem. Oddział Erlang działa poprawnie.

Answer 4

Połączenie string:len(string:strip(L)) przechodzi co najmniej dwukrotnie listę (nie jestem świadomy ciągu znaków: implementacja paska). Zamiast tego można napisać prostą funkcję policzyć długość linii w/0 przestrzeniach:

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. 

Tę samą metodę można zastosować do plików binarnych, jak również.

Answer 5

Czy wypróbowałeś Elixir (elixir-lang.org), który działa na górze Erlang i ma składnię podobną do Ruby. Eliksir rozwiązuje problemów ciąg w następujący sposób:

Elixir ciągi są binarne UTF8, ze wszystkimi surowego prędkości i pamięci oszczędności, które przynosi. Elixir ma moduł String z wbudowaną funkcją Unicode i jest doskonałym przykładem pisania kodu, który zapisuje kod . String.Unicode czyta różne zrzuty baz danych Unicode, takie jak jako UnicodeData.txt, aby dynamicznie generować funkcje Unicode dla Moduł String zbudowany prosto z tych danych!(http://devintorr.es/blog/2013/01/22/the-excitement-of-elixir/)

Zastanawiasz się tylko, czy Eliksir będzie szybszy?