Optimize function: find and update/replace in list of maps

josefrichter

I have this list of maps (or structs) and I get a list of newly updated maps. I want to update the maps in the old list with the values from the new list. Basically I can just replace the old ones with the new ones (in my real code it’s all structs rather than maps).

This is what I came up with:

olds = [
  %{class_id: 1, user_id: 1},
  %{class_id: 1, user_id: 2},
  %{class_id: 1, user_id: 3},
  %{class_id: 1, user_id: 4},
  %{class_id: 1, user_id: 5}
]

news = [
  %{class_id: 1, user_id: 2, new_key: 123},
  %{class_id: 1, user_id: 4, new_key: 456, another_new_key: 789}
]

# expected output
# [
#   %{class_id: 1, user_id: 1},
#   %{class_id: 1, user_id: 2, new_key: 123},
#   %{class_id: 1, user_id: 3},
#   %{class_id: 1, user_id: 4, new_key: 456, another_new_key: 789},
#   %{class_id: 1, user_id: 5}
# ]

olds |> Enum.map(fn old ->
  new_with_same_ids = news |> Enum.find(fn new -> new.class_id == old.class_id and new.user_id == old.user_id end)
  if (new_with_same_ids != nil) do
    new_with_same_ids
  else
    old
  end
end)
|> IO.inspect

This works, but not sure it’s very efficient, as it probably traverses both lists in m*n fashion I guess.

My second attempt is much simpler:

news ++ olds |> Enum.uniq_by(fn el -> {el.class_id, el.user_id} end) |> Enum.sort_by(& &1.user_id)
|> IO.inspect

But I lose the original order and have to use sort_by

Any suggestions how to do this more efficiently, please?

Thank you very much.

7 comments

#maps #list

0 3419 7

2022-01-12 11:59:15 UTC

Showing Posts 1 to 7

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

benwilson512

Author of Craft GraphQL APIs in Elixir with Absinthe

news_by_id = Map.new(news, &{&1.user_id, &1})

Enum.map(olds, fn old -> Map.get(news_by_id, old.user_id, old) end)

The thought process here is basically: You only need the news sometimes, whereas you always need the olds, and you want them in that order. So make a map of the news for efficient lookup, then traverse the olds and either use the new if it exists, or use the old. Map.get/3 is used with the 3rd arg as the default to just succinctly default to the old instead of having to write out a case do ourselves.

EDIT: if news can contain entirely new entities then you’ll need to do more.

Post #1

stefanluptak

Can news contain entries with user_id and class_id combination that is not in the olds already?
Is it possible that in the list, there will be more than one entry with the same user_id and class_id combination?
Is order of the entries in the list important?

Post #2

josefrichter

no, no, yes

In my real code these are in fact structs where user_id and class_id together constitute a composite primary key.

One twist I can think of is old containing some keys not present in new, so I’d need to update the old map with new keys, rather than just replace the whole map. But I don’t need that for now.

Post #3

stefanluptak

Ok, hard to beat @benwilson512’s solution then.

Post #4

josefrichter

thank you, that works nicely! according to benchmarks it’s the fastest one.

Post #5

ConstantBall

Piggybacking off of the solution from @benwilson512, maybe you could try this as well and see if it’s anymore performant:

olds_map = Map.new(olds, fn %{user_id: uid} = map -> {uid, map} end)

for %{user_id: uid} = map <- news, olds_map[uid], reduce: olds_map do
  olds -> Map.update!(olds, uid, &Map.merge(&1, map))
end

Post #6

benwilson512

Author of Craft GraphQL APIs in Elixir with Absinthe

Do note that if you want to preserve the order of the original list you have to do a second pass to pull the users back out of the map in the right order.

Post #7

— All posts loaded —