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

odohMei7

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.

14 comments

#lists #enum

1 3711 14

2023-12-22 18:40:25 UTC

Showing Posts 1 to 10

Show Best Posts
Show All (oldest first)
Show All (newest first)

krasenyp

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

Post #1

lud

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.

Post #2

odohMei7

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?

Post #3

odohMei7

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

Post #4

wanton7

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.

Post #5

odohMei7

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

Post #6

eksperimental

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]]

Post #7

odohMei7

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

Post #8

sabiwara

Elixir Core Team

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

Post #9

odohMei7

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?

Post #10

Load more posts (4 remaining)