CODEWITHSUNDEEP
elixir
Thomas Browne
Thomas Browne

Reputation: 24888

Elixir: find the key for the list of lowest length, in a map of lists

What is an efficient way to find the key associated with the list of minimum length, in a map of lists in Elixir. Let's say I have:

z = %{a: [1, 2, 3], b: [4, 5], c: [6, 7, 8, 9]}

I know I can do:

Enum.map z, fn {k, v} -> length(v) end

which will give me:

[3, 2, 4]

But what I really need is just the answer, namely the key associated with the minimum value 2, which of course is :b.

I will be running this on dynamic map of lists approximately every second so I'd like it to be as efficient as possible.

Upvotes: 1

Views: 1245

Answers (4)

Thomas Browne
Thomas Browne

Reputation: 24888

For anyone who wishes to repeat @Dogbert's benchmark, including the answer of Patrick Oscity:

map = for(key <- 1..1000, into: %{}, do: {key, Enum.random([[1, 2, 3], [4, 5], [6, 7, 8, 9]])})

Benchee.run(%{
  "mudasobwa" => fn ->
    Enum.reduce(map, {nil, 0}, fn
      {k, v}, {_, len} when len == 0 or len > length(v) -> {k, length(v)}
      _, acc -> acc
    end)
    |> elem(0)
  end,
  "dogbert" => fn ->
    :maps.fold(
      fn k, v, {_, min} = acc ->
        l = length(v)
        if min == 0 || l < min, do: {k, l}, else: acc
      end,
      {nil, 0},
      map
    )
    |> elem(0)
    end,
  "oscity" => fn ->
        map
        |> Enum.min_by(fn {_k, v} -> length(v) end)
        |> elem(0)
    end
})

My results on an Nvidia TX2 (64-bit ARM):

Name                ips        average  deviation         median         99th %

    oscity           252.78        3.96 ms     ±3.01%        3.92 ms        4.38 ms
    mudasobwa         80.66       12.40 ms     ±1.61%       12.37 ms       13.15 ms
    dogbert           32.90       30.39 ms     ±0.90%       30.32 ms       31.27 ms

Benchee code is here:

https://hex.pm/packages/benchee

ie just add {:benchee, "~> 0.12.1"} under deps in mix.exs.

Upvotes: 0

Patrick Oscity
Patrick Oscity

Reputation: 54674

I prefer simplicity over performance unless absolutely necessary, so here's how I would do it, if performance was less of a concern:

map
|> Enum.min_by(fn {_k, v} -> length(v) end)
|> elem(0)

Adding to the benchmark by @Dogbert reveals that this is ~1.5x slower with an avg. 90µs/iteration on my machine. That's still plenty of headroom to run it every second.

Upvotes: 5

Dogbert
Dogbert

Reputation: 222040

If you're looking for speed, :maps.fold would usually be a tiny bit faster than Enum.reduce. Here's an implementation which runs ~10% faster than @mudasobwa's implementation:

:maps.fold(
  fn k, v, {_, min} = acc ->
    l = length(v)
    if min == 0 || l < min, do: {k, l}, else: acc
  end,
  {nil, 0},
  map
)
|> elem(0)

Benchmark code:

map = for(key <- 1..1000, into: %{}, do: {key, Enum.random([[1, 2, 3], [4, 5], [6, 7, 8, 9]])})

Benchee.run(%{
  "mudasobwa" => fn ->
    Enum.reduce(map, {nil, 0}, fn
      {k, v}, {_, len} when len == 0 or len > length(v) -> {k, length(v)}
      _, acc -> acc
    end)
    |> elem(0)
  end,
  "dogbert" => fn ->
    :maps.fold(
      fn k, v, {_, min} = acc ->
        l = length(v)
        if min == 0 || l < min, do: {k, l}, else: acc
      end,
      {nil, 0},
      map
    )
    |> elem(0)
  end
})

Output:

Name                ips        average  deviation         median         99th %
dogbert         12.36 K       80.90 μs    ±25.05%          73 μs      146.20 μs
mudasobwa       11.14 K       89.81 μs    ±34.32%          80 μs         185 μs

Comparison:
dogbert         12.36 K
mudasobwa       11.14 K - 1.11x slower

Upvotes: 2

Aleksei Matiushkin
Aleksei Matiushkin

Reputation: 120990

The most efficient way to do anything in Elixir is to Enum.reduce/3:

Enum.reduce(z, {nil, 0}, fn
  {k, v}, {_, len} when len == 0 or len > length(v) -> {k, length(v)}
   _, acc -> acc
end)

#⇒ {:b, 2}

To get :b only, pattern match the result:

{key, _} = ⇑the above⇑

or (worse) pipe to |> Tuple.to_list() |> List.first.

Here we update the accumulator if:

  • we just started and the saved value is empty, or
  • the new length is less than the old one.

Upvotes: 1

Related Questions