diff options
| author | Matthew Sackman <matthew@rabbitmq.com> | 2011-08-17 14:56:09 +0100 |
|---|---|---|
| committer | Matthew Sackman <matthew@rabbitmq.com> | 2011-08-17 14:56:09 +0100 |
| commit | 7cf68828f0e8d83d061218436e906ca831e11e26 (patch) | |
| tree | 10da2c9d69a2ce1efdda1d01f0379786bf10984f /src | |
| parent | 30b3e146747b9b67b90bafb3d6bef2abb31c85c7 (diff) | |
| download | rabbitmq-server-git-7cf68828f0e8d83d061218436e906ca831e11e26.tar.gz | |
Get algorithmic complexity of function right.
Yes, it's 4 more lines, but:
> L = [{X,X} || X <- lists:seq(1,1000000)].
> timer:tc(erlang,apply,[fun () -> mirrored_supervisor:merge_proplists(L, L) end, []]).
{190570,[...]}
whereas with previous implementation, after eight minutes, this still hadn't completed.
Diffstat (limited to 'src')
| -rw-r--r-- | src/mirrored_supervisor.erl | 16 |
1 files changed, 10 insertions, 6 deletions
diff --git a/src/mirrored_supervisor.erl b/src/mirrored_supervisor.erl index 70a0627a3c..e4d0983388 100644 --- a/src/mirrored_supervisor.erl +++ b/src/mirrored_supervisor.erl @@ -526,9 +526,13 @@ with_exit_handler(Handler, Thunk) -> Handler() end. -add_proplists(P1, []) -> P1; -add_proplists(P1, [{K, V2} | P2]) -> - add_proplists(case proplists:get_value(K, P1) of - undefined -> [{K, V2} | P1]; - V1 -> [{K, V1 + V2} | proplists:delete(K, P1)] - end, P2). +add_proplists(P1, P2) -> + add_proplists(lists:keysort(1, P1), lists:keysort(1, P2), []). +add_proplists([], P2, Acc) -> P2 ++ Acc; +add_proplists(P1, [], Acc) -> P1 ++ Acc; +add_proplists([{K, V1} | P1], [{K, V2} | P2], Acc) -> + add_proplists(P1, P2, [{K, V1 + V2} | Acc]); +add_proplists([{K1, _} = KV | P1], [{K2, _} | _] = P2, Acc) when K1 < K2 -> + add_proplists(P1, P2, [KV | Acc]); +add_proplists(P1, [KV | P2], Acc) -> + add_proplists(P1, P2, [KV | Acc]). |