Comment lire efficacement des milliers de lignes de STDIN à Erlang?

Question

Je suis tombé sur un problème en lisant des milliers de lignes de STDIN. Cela aurait été un cas de bord imaginaire jusqu'à ce que j'ai découvert que certains tests pour this problem nécessitent la lecture de milliers de lignes de STDIN. Au début, je pensais que mes algorithmes n'étaient pas optimaux, et c'est seulement par hasard que j'ai découvert que seules les lignes de lecture sans calculs pouvaient faire passer la moitié du temps de test.

Voici le code partiel que les temps sur:

process_queries(0, _) -> ok; 
process_queries(N, A) -> 
    case io:fread("", "~s~d~d") of 
     {ok, _} -> process_queries(N - 1, A) 
     %{ok, ["Q", L, R]} -> process_queries(N - 1, apply_q(L, R, A)); 
     %{ok, ["U", Idx, Val]} -> process_queries(N - 1, apply_u(Idx, Val, A)) 
    end 
. 

J'ai délibérément laissé des commentaires pour montrer que tous ont été désactivés les calculs. Donc, ce code a expiré N=7984.

Existe-t-il une meilleure façon de lire et de traiter des milliers de lignes à partir de STDIN dans Erlang?

• io:get_line obtient seulement une ligne à la fois.
• io:get_chars vous oblige à connaître le nombre de caractères à obtenir.

Answer 1

Je suggérerais de changer stdio en binaire, puis en utilisant io:get_line. Le format de vos données est assez simple à analyser en séparant les espaces et en convertissant deux valeurs en entiers. Le code suivant est ~ 10 fois plus rapide que votre code pour moi dans un benchmark simple. J'ai utilisé escript pour comparer, ce qui signifie qu'il est fort probable que la différence soit réellement plus de 10 fois depuis que l'esquisse analyse et compile le code à la volée.

process_queries_2(0, _) -> ok; 
process_queries_2(N, A) -> 
    Line = io:get_line(""), 
    [X, Y0, Z0, _] = binary:split(Line, [<<$\s>>, <<$\n>>], [global]), 
    Y = binary_to_integer(Y0), 
    Z = binary_to_integer(Z0), 
    % use X, Y, Z 
    process_queries_2(N - 1, A). 

Voici le code que je l'habitude de référence:

main(["1"]) -> 
    ok = io:setopts(standard_io, [binary]), 
    process_queries(10000, {}); 
main(["2"]) -> 
    ok = io:setopts(standard_io, [binary]), 
    process_queries_2(10000, {}).% 

$ time yes 'Q 100 200' | escript a.erl 1 
yes 'Q 100 200' 4.64s user 0.11s system 93% cpu 5.063 total 
escript a.erl 1 4.67s user 1.44s system 120% cpu 5.062 total 
$ time yes 'Q 100 200' | escript a.erl 2 
yes 'Q 100 200' 0.36s user 0.01s system 77% cpu 0.466 total 
escript a.erl 2 0.40s user 0.10s system 106% cpu 0.464 total 

La raison de l'accélération est que Erlang Les chaînes sont des listes chaînées, qui sont très inefficaces pour le temps CPU et mémoire l'utilisation par rapport aux binaires, qui est un morceau séquentiel de la mémoire.

Answer 2

Il existe un extrait de ma solution. Il y a quelques astuces pour le faire vraiment efficace.

read_command(CP) -> 
    {ok, Line} = file:read_line(standard_io), 
    [C, A, B] = binary:split(Line, CP, [global, trim_all]), 
    {case C of <<"Q">> -> 'Q'; <<"U">> -> 'U' end, 
    binary_to_integer(A), 
    binary_to_integer(B)}. 

read_commands(N, CP) -> 
    [ read_command(CP) || _ <- lists:seq(1, N) ]. 

execute(Array, L) -> 
    lists:foldl(fun({'Q', F, T}, A) -> 
         {Val, A2} = query(A, F, T), 
         file:write(standard_io, [integer_to_binary(Val), $\n]), 
         A2; 
        ({'U', I, V}, A) -> 
         update(A, I, V) 
       end, Array, L). 

read_int_line(CP) -> 
    {ok, Line} = file:read_line(standard_io), 
    [binary_to_integer(X) || X <- binary:split(Line, CP, [global, trim_all])]. 

main() -> 
    ok = io:setopts([binary]), 
    CP = binary:compile_pattern([<<" ">>, <<$\n>>]), 
    [N] = read_int_line(CP), 
    L = read_int_line(CP), 
    N = length(L), 
    [K] = read_int_line(CP), 
    execute(init(L), read_commands(K, CP)). 

Vous devez écrire votre propre init/1, update/3 et query/3 bien sûr.