3
\$\begingroup\$

This question is really similar to an existing one in Ruby. So the task is also the same: Day 8: Dictionaries and Maps!

The problem is that on Hackerrank my solution only passes the first and last testcases. All the other ones between them are timing out (>12s!). I tried to use map instead of dict and also read the queries first into a list and process them separately as was suggested in the discussion. I have a feeling it goes to infinite recursion because I'm doing the line read/strip wrong.

-module(solution).
-export([main/0]).

main() ->
    { ok, [N]} = io:fread("", "~d"),
    Dict = read_dictionary(N, dict:new()),
    queries(Dict).

read_dictionary(0, D) -> D;
read_dictionary(N, D) ->
    Name = stripped_next_line(),
    Number = stripped_next_line(),
    read_dictionary(N-1, dict:store(Name, Number, D)).

queries(Dict) ->
    queries(Dict, io:get_line("")).
queries(_, eof) -> true;
queries(Dict, Name) ->
    find_number_of(strip_line(Name), Dict),
    Next = io:get_line(""),
    queries(Dict, Next).

find_number_of(Name, Dict) ->
    out(dict:find(Name, Dict), Name).

out({ok, Number}, Name) -> io:format("~s=~s~n", [Name, Number]);
out(error, _) -> io:format("Not found~n").

strip_line(Line) -> string:strip(Line, both, $\n).
stripped_next_line() -> strip_line(io:get_line("")).
\$\endgroup\$
2
\$\begingroup\$

There are two things you can do differently that would help:

  • read all the input at once, and then process it
  • store values such that they can be output directly, without formatting

The code below first reads all the input in chunks of 4096 characters, accumulating a list of chunks. It then reverses the list, flattens the list into a large string, and splits the entire string on newlines. After that, it converts the first element of the resulting list to an integer N, and then processes N names and numbers from the remainder of the list by storing them in a map. The value stored isn't just the phone number, but the required output string "<name>=<number>\n". Once all the entries have been processed, the rest of the input is queries, which are then processed one-by-one against the map. Query processing uses maps:get/3 with the string "Not found" used as the default for lookups that fail. This allows the return value from maps:get/3 to be unconditionally output directly to stdout.

-module(solution).
-export([main/0]).

main() ->
    queries(store(read_all())).

read_all() ->
    read_all([], io:get_chars("", 4096)).
read_all(In, eof) ->
    [H|T] = string:tokens(lists:flatten(lists:reverse(In)), "\n"),
    {list_to_integer(H), T};
read_all(In, Data) ->
    read_all([Data|In], io:get_chars("", 4096)).

store(Data) ->
    store(Data, #{}).
store({0, Queries}, M) ->
    {Queries, M};
store({N, [Name,Number|T]}, M) ->
    store({N-1, T}, maps:put(Name, lists:flatten([Name,"=",Number,"\n"]), M)).

queries({[], _}) ->
    ok;
queries({[Query|Queries], M}) ->
    io:put_chars(maps:get(Query, M, "Not found\n")),
    queries({Queries, M}).

I created an input file containing 9000 entries to be stored and used it to measure this solution to be about 150 times faster than solutions that read the input line by line, as measured by running the solution on the command line in a bash shell like this:

time erl -noshell -s solution main -s init stop < input

and subtracting out the overhead of starting and stopping the Erlang VM, measured like this:

time erl -noinput -s init stop

On my machine, this overhead is ~1.20s. The original solution for input with 9000 entries and 3 lookups takes ~6.25s, while the solution I've posted here runs in ~1.23s, which means it imposes hardly any overhead over that of the VM startup and shutdown.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

To run within the Hackerrank time limits for this task it is already sufficient to use

read_pairs(N) ->
  Fmt = unicode:characters_to_list(lists:duplicate(N, "~s ~d")),
  {ok, L} = io:fread("", Fmt),
  L.

to read the known number of pairs and

read_list() -> 
  InputSize = 10000000, % found by trial and error
  Data = io:get_chars("", InputSize),
  string:lexemes(Data, [$\r, $\n]).

to read the list of unknown many queries.

Otherwise you do not have to do anything special:

-module(solution).
-export([main/0]).

main() ->
  {ok, [N]} = io:fread("", "~d"),
  Pairs = read_pairs(N),
  Map = dict(Pairs), 
  Queries = read_list(),
  lists:foreach(fun(Name) ->
    case maps:is_key(Name, Map) of
      true ->
        Number = maps:get(Name, Map),
        io:format("~s=~p~n", [Name, Number]);
      false ->
        io:format("Not found~n")
    end
  end, Queries),
  true.


dict(L) ->
  dict(L, maps:new()).

dict([], Map) ->
  Map;
dict([Name, Number|T], Map) ->
  Map2 = maps:put(Name, Number, Map),
  dict(T, Map2).

The strategy behind read_pairs/1 is to use one large format string \$\text{(~s ~d)}^N\$ for the first section of the input.

It illustrates that using formatted I/O is not slow per se, but that it has some constant impact per io:fread/2 call (expensive setup? slow memory handling?).

The strategy behind read_list/0 is to slurp in all input and then parse it. We do not know how many characters are waiting, so we just add a large enough constant. This is indeed ugly, but works and works fast.

The implementation of dict/1 is straight forward, nothing fancy.

I use hash maps via the functions from the maps module which I personally prefer over the native syntax. I also like to check first if the key exists before fetching it as is shown in main/0 function.

We do not need to exit early, so we can use lists:foreach/1 to iterate over the queries.

Individual io:format/2 calls do not harm performance, so whatever slowness is going on with io:fread/2 it is not acting here, which is interesting as both functions deal with format strings.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.