Improving my code
Richard A. O'Keefe
ok@REDACTED
Fri Aug 12 04:55:55 CEST 2005
update_history(History, Name, Value) ->
update_history(History, Name, Value, []).
update_history([], _Name, _Value, Acc) ->
Acc;
update_history([{Name, Max, Values}|Rest], Name, Value, Acc) ->
NewVs = trunclist([Value] ++ Values, Max),
update_history(Rest, Name, Value, Acc ++ [{Name, Num, NewVs}]);
Whenever you see a "++" in your code, you should flinch.
You should feel as comfortable about it as you would a smouldering
ember on a new carpet.
To process a list of N elements this way will ALWAYS cost you O(N**2)
time. You really don't need to do that.
update_history([H|Rest], Name, Value, Acc) ->
update_history(Rest, Name, Value, Acc ++ [H]).
Your trunclist function has the same problem.
Tail recursion is good, but NOT at the price of turning
an O(N) operation into an O(N**2) one.
A simple O(N) version is:
update_history([{Name,Max,Values}|Rest], Name, Value) ->
[{Name,Max,[Value | take(Max-1, Values)], Max)}|Rest];
update_history([Item|Rest], Name, Value) ->
[Item | update_history(Rest, Name, Value)];
update_history([], _, _) -> [].
take(N, [X|Xs]) when N > 0 -> [X | take(N-1,Xs)];
take(_, _) -> [].
More information about the erlang-questions
mailing list