Improving my code

Richard A. O'Keefe <>
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