Append to list after Enum.map. How to do this efficiently?

Questions / Help
,
1

How can I efficiently append one entry to a list? Is this the best solution:

history = [{1,100}, {2,300}, {3,200}] 
current = {4,150}
chart = Enum.map(history,&Tuple.to_list(&1)) ++ [Tuple.to_list(current)]|>Jason.encode!

It does not feel good to scan the list twice, once during Enum.map and once for appending to the list which is O(length(list)) as I have read. Is there a better method to only loop through the list once (think of a long history list)?

I did not benchmark and what I have done above seems to be sufficiently performant in my use case so this is rather a theoretical question that I am interested in.

Bonus question: Is there any method to avoid the Tuple.to_list before I pipe into Jason.encode, this also feels unnecessary but unfortunately Jason.encode cannot handle tuples.

1 Like
2

I doubt there’s a way to append elements more efficiently because of immutability.

3

Any solution I could imagine would be a wrapper around Tuple.to_list anyway.

For the double scan, unless your history is very, very long, I would not try to optimize that, what you do is fine. If your really want a performance optimization here then I would just build the history in reverse order, and prepend the new entry instead of appending it.

2 Likes
4

I don’t understand this argument because why couldn’t the a function similar to Enum.map just construct the new list in a way such that there is a last element is as desired? Shouldn’t it be possible in principle without violating immutability?

5

Thank you, yes, I should just keep it as is and go on. I suffer from premature optimization because I come from C++ :smile:, was just wondering if there is a thing here that I should know about.

1 Like
6

Why don’t you keep history data in types you can just Jason.encode without conversion? If you want to micro optimize, could you keep history in reverse order? Adding something to front [0 | list] is fast but adding element to end list ++ [0] is slow.

7

It comes as list of lists Exqlite.Sqlite3 — Exqlite v0.11.0 from Exqlite but the hint with the reverse order is interesting.

8

Yes, there is a way which is optimal.
You only iterate over your list twice.

iex> Enum.reduce(history, [], fn x, acc  ->
...>   [Tuple.to_list(x) | acc]
...> end)
...> |> :lists.reverse([Tuple.to_list(current)])
[[1, 100], [2, 300], [3, 200], [4, 150]]
1 Like
9

Thank you, but I think the list reverse has to go through the entire loop a second time.

10

From a purely theoretical perspective, you could implement a variant of Enum.map/2 that appends an element at the end, such as:

  def map_append([], _fun, last), do: [last]
  def map_append([head | tail], fun, last) do
    [fun.(head) | map_append(tail, fun, last)]
  end

But as you pointed out, this is probably premature optimization and I wouldn’t recommend doing this in production code :wink:

3 Likes
11

I think this is the correct answer. But there is one more thing I want to know: Is this tail-recursive or does the repeated call fill the stack?

Because if it does not fill the stack then this would mean that one could append to a list cheaply in O(1), which is not possible as we all said above. So I think that the list starts to be constructed when the last map_append([],…) is evaluated and then it goes the call stack up to prepend, right?

1 Like
12

Just like Enum.map/2 (actually :lists.map/2), this implementation is body recursive, not tail recursive.

A tail-recursive version would need to call Enum.reverse/2 at the end, just like the example provided by @eksperimental.

Either one is probably fine in this case and the performance should be roughly equivalent when building lists, cf the Erlang efficiency guide and the article it refers to. Body recursion might even be faster / use less memory depending on the function being optimized, list size, your architecture etc…

2 Likes
13

I would like to mention that Enum.reverse in turn calls :lists.reverse if the first argument (the enumerable) is a List.

With that said, after reading the following in Programming Erlang (2nd edition) by Joe Armstrong, I felt much better about using Enum.reverse with a List as the enumerable:

…
If the order matters, then call lists:reverse/1, which is highly optimized.
…

Note: Whenever you want to reverse a list, you should call lists:reverse and nothing else. If you look in the source code for the module lists, you’ll find a definition of reverse. However, this definition is simply used for illustration. The compiler, when it finds a call to lists:reverse, calls a more efficient internal version of the function.

So, with a long list, most of the time I’ll always add elements to a list head and then call Enum.reverse at the end and trust that Joe and Erlang have my back. :slight_smile:

But as Joe points out a little later:

The best thing to do is first write your programs as clearly as possible and then, if there are performance problems, measure before making any optimizations.

5 Likes
14

Thank you for this precious additional information!

1 Like
15

To avoid the first iteration you can use Stream.map (a lazy iterator) instead of Enum.map and append using Enum.concat. Example:

[0, 1, 2]
|> Stream.map(&(&1 + 1))
|> Enum.concat([4, 5])

[1, 2, 3, 4, 5]

Good luck!

1 Like