Can you improve this? Zipping two lists, the result must be same size as the first list

Questions / Help
, ,
1

Heya.
I am inviting you to copy-paste the module below and add your own functions and measure them, or simply give other ideas about how the desired result can be produced best.

I got interested in writing a function that takes two lists where the first is always bigger than the second and make pairs a la Enum.zip but not stop when the smaller list depletes. I want it to continue, while cycling through the second list, until we have a list with the same size as the first one, containing 2-size tuples.

Example:

list0 = [1, 2, 3, 4, 5]
list1 = [:a, :b]

I want the output to be:

[{1, :a}, {2, :b}, {3, :a}, {4, :b}, {5, :a}]

I came up with these two functions (and benchmark code):

defmodule Xyz do
  def pair_with_enum_reduce(list0, list1) do
    list1_tuple = List.to_tuple(list1)
    list1_last_position = tuple_size(list1_tuple) - 1

    Enum.reduce(list0, {[], 0}, fn item, {final_list, position} ->
      mapped_item = {item, elem(list1_tuple, position)}

      position =
        case position do
          ^list1_last_position ->
            0

          _ ->
            position + 1
        end

      {[mapped_item | final_list], position}
    end)
    |> elem(0)
    |> Enum.reverse()
  end

  def pair_with_stream_cycle(list0, list1) do
    stream = Stream.cycle(list1)
    Enum.zip(list0, Enum.take(stream, length(list0)))
  end

  def bench() do
    list0 = Enum.to_list(1..2000)
    list1 = [:worker_0, :worker_1, :worker_2, :worker_3, :worker_4]

    Benchee.run(%{
      "pair_with_enum_reduce" => fn -> pair_with_enum_reduce(list0, list1) end,
      "pair_with_stream_cycle" => fn -> pair_with_stream_cycle(list0, list1) end
    })
  end
end

Benchmark results on my machine:

Name                             ips        average  deviation         median         99th %
pair_with_enum_reduce        19.80 K       50.49 μs    ±28.32%          50 μs          85 μs
pair_with_stream_cycle        7.64 K      130.89 μs    ±40.15%         108 μs      327.12 μs

Comparison:
pair_with_enum_reduce        19.80 K
pair_with_stream_cycle        7.64 K - 2.59x slower +80.39 μs

I know Stream incurs some performance penalty but was rather surprised by how much. I don’t like the size of the pair_with_enum_reduce function, nor the fact that it has to call Enum.reverse at the end but it’s still significantly faster. And I don’t like that the pair_with_stream_cycle relies on calling length on the first list. Both functions I am kind of unhappy with.

Any criticisms? And, do you think you could do better?

(Alternatively, another implementation might not care about which size list is bigger.)

3 Likes
2

Come to think of it, these can super easily be adapted to lists where you don’t know which is bigger by just prepending this code to both of them:

{list1, list0} = Enum.min_max_by([list0, list1], &length(&1))

So you basically swap them if the second is bigger than the first, and the algorithms in both functions will still work.

New benchmark results with the above code prepended at the start of both functions:

Name                             ips        average  deviation         median         99th %
pair_with_enum_reduce        18.45 K       54.19 μs    ±25.74%          54 μs          88 μs
pair_with_stream_cycle        6.69 K      149.41 μs    ±44.89%         114 μs         360 μs

Comparison:
pair_with_enum_reduce        18.45 K
pair_with_stream_cycle        6.69 K - 2.76x slower +95.22 μs
1 Like
3

Added another variation of the Stream-using function:

  def pair_with_stream_cycle_and_zip(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))

    list0
    |> Stream.zip(Stream.cycle(list1))
    |> Enum.to_list()
  end

And its performance is awful. :003:

Name                                     ips        average  deviation         median         99th %
pair_with_enum_reduce                18.59 K       53.80 μs    ±24.68%       53.99 μs       85.99 μs
pair_with_stream_cycle                6.91 K      144.65 μs    ±45.27%      110.99 μs      338.99 μs
pair_with_stream_cycle_and_zip        1.91 K      522.93 μs    ±27.79%      459.99 μs     1000.55 μs

Comparison:
pair_with_enum_reduce                18.59 K
pair_with_stream_cycle                6.91 K - 2.69x slower +90.85 μs
pair_with_stream_cycle_and_zip        1.91 K - 9.72x slower +469.13 μs
1 Like
4

The statistics on this make me wonder what’s going on with the distribution of runtimes: the average is considerably larger than the median, which suggests there are a lot of long-running outliers.

Otherwise it seems understandable why pair_with_stream_cycle is slower: it traverses list0 twice, versus traversing it once:

Enum.zip(list0, Enum.take(stream, length(list0)))
    ^ one traversal                 ^ the second traversal
2 Likes
5

True, but as you can see, going all-in on Stream is even worse…

1 Like
6

Added plain old recursion without much core API usage:

  def pair_recursively(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))
    list1_tuple = List.to_tuple(list1)
    list1_last_position = tuple_size(list1_tuple) - 1

    do_pair_recursively(list0, list1_tuple, 0, list1_last_position)
  end

  defp do_pair_recursively([item | rest], other_items, other_max_position, other_max_position) do
    [
      {item, elem(other_items, other_max_position)}
      | do_pair_recursively(rest, other_items, 0, other_max_position)
    ]
  end

  defp do_pair_recursively([item | rest], other_items, other_position, other_max_position) do
    [
      {item, elem(other_items, other_position)}
      | do_pair_recursively(rest, other_items, other_position + 1, other_max_position)
    ]
  end

  defp do_pair_recursively([], _, _, _), do: []

Unsurprisingly it’s the best performer, although the code I dislike a lot. Still, no Enum.reverse, but still there are like 3 traversals (two with Enum.min_max_by and one with List.to_tuple).

Name                             ips        average  deviation         median         99th %
pair_recursively             30.87 K       32.39 μs    ±24.38%          30 μs          52 μs
pair_with_enum_reduce        20.36 K       49.13 μs    ±24.02%          50 μs          76 μs
pair_with_stream_cycle        7.85 K      127.40 μs    ±37.04%         102 μs         260 μs
pair_with_stream_zip          2.06 K      484.80 μs    ±23.82%         432 μs         941 μs

Comparison:
pair_recursively             30.87 K
pair_with_enum_reduce        20.36 K - 1.52x slower +16.73 μs
pair_with_stream_cycle        7.85 K - 3.93x slower +95.01 μs
pair_with_stream_zip          2.06 K - 14.97x slower +452.40 μs
1 Like
7

Posting current full version of what I have locally.

Full module source 
defmodule Xyz do
  def pair_with_enum_reduce(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))

    list1_tuple = List.to_tuple(list1)
    list1_last_position = tuple_size(list1_tuple) - 1

    Enum.reduce(list0, {[], 0}, fn item, {final_list, position} ->
      mapped_item = {item, elem(list1_tuple, position)}

      position =
        case position do
          ^list1_last_position ->
            0

          _ ->
            position + 1
        end

      {[mapped_item | final_list], position}
    end)
    |> elem(0)
    |> Enum.reverse()
  end

  def pair_with_stream_cycle(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))
    stream = Stream.cycle(list1)
    Enum.zip(list0, Enum.take(stream, length(list0)))
  end

  def pair_with_stream_zip(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))

    list0
    |> Stream.zip(Stream.cycle(list1))
    |> Enum.to_list()
  end

  def pair_recursively(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))
    list1_tuple = List.to_tuple(list1)
    list1_last_position = tuple_size(list1_tuple) - 1

    do_pair_recursively(list0, list1_tuple, 0, list1_last_position)
  end

  defp do_pair_recursively([item | rest], other_items, other_max_position, other_max_position) do
    [
      {item, elem(other_items, other_max_position)}
      | do_pair_recursively(rest, other_items, 0, other_max_position)
    ]
  end

  defp do_pair_recursively([item | rest], other_items, other_position, other_max_position) do
    [
      {item, elem(other_items, other_position)}
      | do_pair_recursively(rest, other_items, other_position + 1, other_max_position)
    ]
  end

  defp do_pair_recursively([], _, _, _), do: []

  def bench() do
    list0 = Enum.to_list(1..2000)
    list1 = [:worker_0, :worker_1, :worker_2, :worker_3, :worker_4]

    Benchee.run(%{
      "pair_with_enum_reduce" => fn -> pair_with_enum_reduce(list0, list1) end,
      "pair_with_stream_cycle" => fn -> pair_with_stream_cycle(list0, list1) end,
      "pair_with_stream_zip" => fn -> pair_with_stream_zip(list0, list1) end,
      "pair_recursively" => fn -> pair_recursively(list0, list1) end
    })
  end
end
1 Like
8

How about this:

  def pair_with_body_recursion(list0, list1) do                                                     
    pair_recursion(list0, list1, list1)                                                             
  end                                                                                               
                                                                                                    
  defp pair_recursion([], _, _), do: []                                                             
  defp pair_recursion(l0, [], l1), do: pair_recursion(l0, l1, l1)                                   
  defp pair_recursion([h0 | t0], [h1 | t1], l1) do                                                  
    [{h0, h1} | pair_recursion(t0, t1, l1)]                                                         
  end
3 Likes
9

Seems like this is encountering a specifically-optimized path in Enum.zip when both arguments are lists:

3 Likes
10

I was wondering about mixing the [head | tail] = list pattern and reset the list when it was depleted but it wasn’t clear in my head yet, and you definitely beat me to it (by a big margin).

Hats off to you, your solution is so far both the shortest and fastest. :bowing_man:

Name                               ips        average  deviation         median         99th %
pair_with_body_recursion       42.92 K       23.30 μs    ±33.11%          20 μs          46 μs
pair_recursively               29.97 K       33.37 μs    ±26.55%          32 μs          56 μs
pair_with_enum_reduce          19.97 K       50.07 μs    ±24.80%          50 μs          79 μs
pair_with_stream_cycle          7.92 K      126.23 μs    ±36.73%         103 μs         264 μs
pair_with_stream_zip            2.03 K      491.43 μs    ±26.30%         433 μs      981.39 μs

Comparison:
pair_with_body_recursion       42.92 K
pair_recursively               29.97 K - 1.43x slower +10.07 μs
pair_with_enum_reduce          19.97 K - 2.15x slower +26.77 μs
pair_with_stream_cycle          7.92 K - 5.42x slower +102.93 μs
pair_with_stream_zip            2.03 K - 21.09x slower +468.13 μs

And here’s the latest source code:

Full source 
defmodule Xyz do
  def pair_with_enum_reduce(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))

    list1_tuple = List.to_tuple(list1)
    list1_last_position = tuple_size(list1_tuple) - 1

    Enum.reduce(list0, {[], 0}, fn item, {final_list, position} ->
      mapped_item = {item, elem(list1_tuple, position)}

      position =
        case position do
          ^list1_last_position ->
            0

          _ ->
            position + 1
        end

      {[mapped_item | final_list], position}
    end)
    |> elem(0)
    |> Enum.reverse()
  end

  def pair_with_stream_cycle(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))
    stream = Stream.cycle(list1)
    Enum.zip(list0, Enum.take(stream, length(list0)))
  end

  def pair_with_stream_zip(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))

    list0
    |> Stream.zip(Stream.cycle(list1))
    |> Enum.to_list()
  end

  def pair_recursively(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))
    list1_tuple = List.to_tuple(list1)
    list1_last_position = tuple_size(list1_tuple) - 1

    do_pair_recursively(list0, list1_tuple, 0, list1_last_position)
  end

  defp do_pair_recursively([item | rest], other_items, other_max_position, other_max_position) do
    [
      {item, elem(other_items, other_max_position)}
      | do_pair_recursively(rest, other_items, 0, other_max_position)
    ]
  end

  defp do_pair_recursively([item | rest], other_items, other_position, other_max_position) do
    [
      {item, elem(other_items, other_position)}
      | do_pair_recursively(rest, other_items, other_position + 1, other_max_position)
    ]
  end

  defp do_pair_recursively([], _, _, _), do: []

  def pair_with_body_recursion(list0, list1) do
    pair_recursion(list0, list1, list1)
  end

  defp pair_recursion([], _, _), do: []
  defp pair_recursion(l0, [], l1), do: pair_recursion(l0, l1, l1)

  defp pair_recursion([h0 | t0], [h1 | t1], l1) do
    [{h0, h1} | pair_recursion(t0, t1, l1)]
  end

  def bench() do
    list0 = Enum.to_list(1..2000)
    list1 = [:worker_0, :worker_1, :worker_2, :worker_3, :worker_4]

    Benchee.run(%{
      "pair_with_enum_reduce" => fn -> pair_with_enum_reduce(list0, list1) end,
      "pair_with_stream_cycle" => fn -> pair_with_stream_cycle(list0, list1) end,
      "pair_with_stream_zip" => fn -> pair_with_stream_zip(list0, list1) end,
      "pair_recursively" => fn -> pair_recursively(list0, list1) end,
      "pair_with_body_recursion" => fn -> pair_with_body_recursion(list0, list1) end
    })
  end
end
1 Like
11

Heh, quite nice, and it’s always obvious in hindsight, right? Nice find, thank you.

1 Like
12

On my machine tail recursion is faster:

  def pair_with_tail_recursion(list0, list1) do
    Enum.reverse(pair_tail_recursion(list0, list1, list1, []))
  end
  
  defp pair_tail_recursion([], _, _, acc), do: acc
  defp pair_tail_recursion(l0, [], l1, acc), do: pair_tail_recursion(l0, l1, l1, acc)
  defp pair_tail_recursion([h0 | t0], [h1 | t1], l1, acc) do
    pair_tail_recursion(t0, t1, l1, [{h0, h1} | acc])
  end
3 Likes
13

BTW could you post updated code that doesn’t care which list is bigger? Curious how it would look in such a final form.

1 Like
14

Yep, that’s even faster. :103:

Name                               ips        average  deviation         median         99th %
pair_with_tail_recursion       58.71 K       17.03 μs    ±50.24%          13 μs          38 μs
pair_with_body_recursion       41.06 K       24.36 μs    ±35.43%          21 μs          47 μs
pair_recursively               28.37 K       35.25 μs    ±26.58%          33 μs          59 μs
pair_with_enum_reduce          19.17 K       52.16 μs    ±26.21%          52 μs          93 μs
pair_with_stream_cycle          9.44 K      105.96 μs    ±19.78%         101 μs         173 μs
pair_with_stream_zip            2.24 K      447.00 μs    ±21.87%         418 μs         924 μs

Comparison:
pair_with_tail_recursion       58.71 K
pair_with_body_recursion       41.06 K - 1.43x slower +7.32 μs
pair_recursively               28.37 K - 2.07x slower +18.22 μs
pair_with_enum_reduce          19.17 K - 3.06x slower +35.13 μs
pair_with_stream_cycle          9.44 K - 6.22x slower +88.93 μs
pair_with_stream_zip            2.24 K - 26.24x slower +429.97 μs

Full source follows:

Full source 
defmodule Xyz do
  def pair_with_enum_reduce(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))

    list1_tuple = List.to_tuple(list1)
    list1_last_position = tuple_size(list1_tuple) - 1

    Enum.reduce(list0, {[], 0}, fn item, {final_list, position} ->
      mapped_item = {item, elem(list1_tuple, position)}

      position =
        case position do
          ^list1_last_position ->
            0

          _ ->
            position + 1
        end

      {[mapped_item | final_list], position}
    end)
    |> elem(0)
    |> Enum.reverse()
  end

  def pair_with_stream_cycle(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))
    stream = Stream.cycle(list1)
    Enum.zip(list0, Enum.take(stream, length(list0)))
  end

  def pair_with_stream_zip(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))

    list0
    |> Stream.zip(Stream.cycle(list1))
    |> Enum.to_list()
  end

  def pair_recursively(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))
    list1_tuple = List.to_tuple(list1)
    list1_last_position = tuple_size(list1_tuple) - 1

    do_pair_recursively(list0, list1_tuple, 0, list1_last_position)
  end

  defp do_pair_recursively([item | rest], other_items, other_max_position, other_max_position) do
    [
      {item, elem(other_items, other_max_position)}
      | do_pair_recursively(rest, other_items, 0, other_max_position)
    ]
  end

  defp do_pair_recursively([item | rest], other_items, other_position, other_max_position) do
    [
      {item, elem(other_items, other_position)}
      | do_pair_recursively(rest, other_items, other_position + 1, other_max_position)
    ]
  end

  defp do_pair_recursively([], _, _, _), do: []

  def pair_with_body_recursion(list0, list1) do
    pair_recursion(list0, list1, list1)
  end

  defp pair_recursion([], _, _), do: []
  defp pair_recursion(l0, [], l1), do: pair_recursion(l0, l1, l1)

  defp pair_recursion([h0 | t0], [h1 | t1], l1) do
    [{h0, h1} | pair_recursion(t0, t1, l1)]
  end

  def pair_with_tail_recursion(list0, list1) do
    Enum.reverse(pair_tail_recursion(list0, list1, list1, []))
  end

  defp pair_tail_recursion([], _, _, acc), do: acc
  defp pair_tail_recursion(l0, [], l1, acc), do: pair_tail_recursion(l0, l1, l1, acc)

  defp pair_tail_recursion([h0 | t0], [h1 | t1], l1, acc) do
    pair_tail_recursion(t0, t1, l1, [{h0, h1} | acc])
  end

  def bench() do
    list0 = Enum.to_list(1..2000)
    list1 = [:worker_0, :worker_1, :worker_2, :worker_3, :worker_4]

    Benchee.run(%{
      "pair_with_enum_reduce" => fn -> pair_with_enum_reduce(list0, list1) end,
      "pair_with_stream_cycle" => fn -> pair_with_stream_cycle(list0, list1) end,
      "pair_with_stream_zip" => fn -> pair_with_stream_zip(list0, list1) end,
      "pair_recursively" => fn -> pair_recursively(list0, list1) end,
      "pair_with_body_recursion" => fn -> pair_with_body_recursion(list0, list1) end,
      "pair_with_tail_recursion" => fn -> pair_with_tail_recursion(list0, list1) end
    })
  end
end
1 Like
15

I can’t think of a nice way to do that without involving length/1

1 Like
16

This version doesn’t care which list is shorter.
But we need to keep track of both list during execution, which is probably slower.

  def pair_with_tail_recursion_auto(list0, list1) do
    Enum.reverse(pair_tail_recursion_auto(list0, list1, list0, list1, []))
  end

  defp pair_tail_recursion_auto([], _l1, [], _c1, acc), do: acc
  defp pair_tail_recursion_auto(_l0, [], _c0, [], acc), do: acc

  defp pair_tail_recursion_auto([], l1, c0, _c1, acc),
    do: pair_tail_recursion_auto(c0, l1, c0, [], acc)

  defp pair_tail_recursion_auto(l0, [], _c0, c1, acc),
    do: pair_tail_recursion_auto(l0, c1, [], c1, acc)

  defp pair_tail_recursion_auto([h0 | t0], [h1 | t1], c0, c1, acc) do
    pair_tail_recursion_auto(t0, t1, c0, c1, [{h0, h1} | acc])
  end
3 Likes
17

That’s what I created as well, though slightly different. First using Stream.unfold, then using tail recursion. The latter being about twice as fast.

Summary 
def pair_with_unfold(list0, list1) do
    Stream.unfold({list0, list1, list1}, fn 
     {[], _, _list1} -> nil
     {[head_l0 | rest_l0], [], [head_l1 | rest_l1] = list1} -> {{head_l0, head_l1}, {rest_l0, rest_l1, list1}}
     {[head_l0 | rest_l0], [head_l1 | rest_l1], list1} -> {{head_l0, head_l1}, {rest_l0, rest_l1, list1}}
    end)
    |> Enum.to_list()
  end

  def pair_with_recursion(list0, list1) do
    pair_with_recursion(list0, list1, list1, [])
  end

  defp pair_with_recursion([], _, _list1, acc) do
    Enum.reverse(acc)
  end

  defp pair_with_recursion([head_l0 | rest_l0], [], [head_l1 | rest_l1] = list1, acc) do
    pair_with_recursion(rest_l0, rest_l1, list1, [{head_l0, head_l1} | acc])
  end

  defp pair_with_recursion([head_l0 | rest_l0], [head_l1 | rest_l1], list1, acc) do
    pair_with_recursion(rest_l0, rest_l1, list1, [{head_l0, head_l1} | acc])
  end
3 Likes
18

Replacing

defp pair_tail_recursion(l0, [], l1, acc), do: pair_tail_recursion(l0, l1, l1, acc)

with

defp pair_tail_recursion1([h0 | t0], [], [h1 | t1], acc), 
  do: pair_tail_recursion1(t0, t1, [h1 | t1], [{h0, h1} | acc])

could improve the performance by a lot depending on the sizes of the lists.

The test case with length(list0) == 2000 and length(list1) == 5 was 1.70x faster:

Name                                        ips        average  deviation         median         99th %
pair_with_tail_recursion_improved       58.66 K       17.05 μs    ±22.80%       14.99 μs       26.99 μs
pair_with_tail_recursion                34.59 K       28.91 μs    ±13.25%       29.99 μs       36.99 μs

Comparison: 
pair_with_tail_recursion_improved       58.66 K
pair_with_tail_recursion                34.59 K - 1.70x slower +11.86 μs
1 Like
19

So I added @moogle19’s code, @LostKobrakai’s code (both variants, Stream and recursion) and amended @derek-zhou’s code with @moogle19’s suggestion.

Forgot to say, I am using Elixir 1.13.2-otp-24 and Erlang 24.2.1.

Results:

Name                                    ips        average  deviation         median         99th %
pair_with_recursion                 61.13 K       16.36 μs    ±50.08%       11.99 μs       36.99 μs
pair_with_tail_recursion            59.86 K       16.71 μs    ±48.00%       12.99 μs       37.99 μs
pair_with_tail_recursion_auto       55.38 K       18.06 μs    ±54.73%       13.99 μs       38.99 μs
pair_with_body_recursion            42.12 K       23.74 μs    ±33.12%       20.99 μs       45.99 μs
pair_recursively                    30.21 K       33.10 μs    ±27.24%       30.99 μs       59.99 μs
pair_with_enum_reduce               20.40 K       49.01 μs    ±24.39%       49.99 μs       75.99 μs
pair_with_unfold                     9.84 K      101.63 μs    ±43.74%       85.99 μs      308.99 μs
pair_with_stream_cycle               9.03 K      110.80 μs    ±33.82%       98.99 μs      248.99 μs
pair_with_stream_zip                 2.27 K      441.38 μs    ±22.92%      405.99 μs      936.86 μs

Comparison:
pair_with_recursion                 61.13 K
pair_with_tail_recursion            59.86 K - 1.02x slower +0.35 μs
pair_with_tail_recursion_auto       55.38 K - 1.10x slower +1.70 μs
pair_with_body_recursion            42.12 K - 1.45x slower +7.39 μs
pair_recursively                    30.21 K - 2.02x slower +16.75 μs
pair_with_enum_reduce               20.40 K - 3.00x slower +32.66 μs
pair_with_unfold                     9.84 K - 6.21x slower +85.27 μs
pair_with_stream_cycle               9.03 K - 6.77x slower +94.44 μs
pair_with_stream_zip                 2.27 K - 26.98x slower +425.02 μs

Well, seems we have a winner: @LostKobrakai. :rocket:
2nd place goes to @derek-zhou with help from @moogle19. :heart:

Full source 
defmodule Xyz do
  def pair_with_enum_reduce(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))

    list1_tuple = List.to_tuple(list1)
    list1_last_position = tuple_size(list1_tuple) - 1

    Enum.reduce(list0, {[], 0}, fn item, {final_list, position} ->
      mapped_item = {item, elem(list1_tuple, position)}

      position =
        case position do
          ^list1_last_position ->
            0

          _ ->
            position + 1
        end

      {[mapped_item | final_list], position}
    end)
    |> elem(0)
    |> Enum.reverse()
  end

  def pair_with_stream_cycle(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))
    stream = Stream.cycle(list1)
    Enum.zip(list0, Enum.take(stream, length(list0)))
  end

  def pair_with_stream_zip(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))

    list0
    |> Stream.zip(Stream.cycle(list1))
    |> Enum.to_list()
  end

  def pair_recursively(list0, list1) do
    {list1, list0} = Enum.min_max_by([list0, list1], &length(&1))
    list1_tuple = List.to_tuple(list1)
    list1_last_position = tuple_size(list1_tuple) - 1

    do_pair_recursively(list0, list1_tuple, 0, list1_last_position)
  end

  defp do_pair_recursively([item | rest], other_items, other_max_position, other_max_position) do
    [
      {item, elem(other_items, other_max_position)}
      | do_pair_recursively(rest, other_items, 0, other_max_position)
    ]
  end

  defp do_pair_recursively([item | rest], other_items, other_position, other_max_position) do
    [
      {item, elem(other_items, other_position)}
      | do_pair_recursively(rest, other_items, other_position + 1, other_max_position)
    ]
  end

  defp do_pair_recursively([], _, _, _), do: []

  def pair_with_body_recursion(list0, list1) do
    pair_recursion(list0, list1, list1)
  end

  defp pair_recursion([], _, _), do: []
  defp pair_recursion(l0, [], l1), do: pair_recursion(l0, l1, l1)

  defp pair_recursion([h0 | t0], [h1 | t1], l1) do
    [{h0, h1} | pair_recursion(t0, t1, l1)]
  end

  def pair_with_tail_recursion(list0, list1) do
    Enum.reverse(pair_tail_recursion(list0, list1, list1, []))
  end

  defp pair_tail_recursion([], _, _, acc), do: acc
  # defp pair_tail_recursion(l0, [], l1, acc), do: pair_tail_recursion(l0, l1, l1, acc)

  defp pair_tail_recursion([h0 | t0], [], [h1 | t1], acc),
    do: pair_tail_recursion(t0, t1, [h1 | t1], [{h0, h1} | acc])

  defp pair_tail_recursion([h0 | t0], [h1 | t1], l1, acc) do
    pair_tail_recursion(t0, t1, l1, [{h0, h1} | acc])
  end

  def pair_with_tail_recursion_auto(list0, list1) do
    Enum.reverse(pair_tail_recursion_auto(list0, list1, list0, list1, []))
  end

  defp pair_tail_recursion_auto([], _l1, [], _c1, acc), do: acc
  defp pair_tail_recursion_auto(_l0, [], _c0, [], acc), do: acc

  defp pair_tail_recursion_auto([], l1, c0, _c1, acc),
    do: pair_tail_recursion_auto(c0, l1, c0, [], acc)

  defp pair_tail_recursion_auto(l0, [], _c0, c1, acc),
    do: pair_tail_recursion_auto(l0, c1, [], c1, acc)

  defp pair_tail_recursion_auto([h0 | t0], [h1 | t1], c0, c1, acc) do
    pair_tail_recursion_auto(t0, t1, c0, c1, [{h0, h1} | acc])
  end

  def pair_with_unfold(list0, list1) do
    Stream.unfold({list0, list1, list1}, fn
      {[], _, _list1} ->
        nil

      {[head_l0 | rest_l0], [], [head_l1 | rest_l1] = list1} ->
        {{head_l0, head_l1}, {rest_l0, rest_l1, list1}}

      {[head_l0 | rest_l0], [head_l1 | rest_l1], list1} ->
        {{head_l0, head_l1}, {rest_l0, rest_l1, list1}}
    end)
    |> Enum.to_list()
  end

  def pair_with_recursion(list0, list1) do
    pair_with_recursion(list0, list1, list1, [])
  end

  defp pair_with_recursion([], _, _list1, acc) do
    Enum.reverse(acc)
  end

  defp pair_with_recursion(
         [head_l0 | rest_l0],
         [],
         [head_l1 | rest_l1] = list1,
         acc
       ) do
    pair_with_recursion(rest_l0, rest_l1, list1, [{head_l0, head_l1} | acc])
  end

  defp pair_with_recursion([head_l0 | rest_l0], [head_l1 | rest_l1], list1, acc) do
    pair_with_recursion(rest_l0, rest_l1, list1, [{head_l0, head_l1} | acc])
  end

  def bench() do
    list0 = Enum.to_list(1..2000)
    list1 = [:worker_0, :worker_1, :worker_2, :worker_3, :worker_4]

    Benchee.run(%{
      "pair_with_enum_reduce" => fn -> pair_with_enum_reduce(list0, list1) end,
      "pair_with_stream_cycle" => fn -> pair_with_stream_cycle(list0, list1) end,
      "pair_with_stream_zip" => fn -> pair_with_stream_zip(list0, list1) end,
      "pair_recursively" => fn -> pair_recursively(list0, list1) end,
      "pair_with_body_recursion" => fn -> pair_with_body_recursion(list0, list1) end,
      "pair_with_tail_recursion" => fn -> pair_with_tail_recursion(list0, list1) end,
      "pair_with_tail_recursion_auto" => fn -> pair_with_tail_recursion_auto(list0, list1) end,
      "pair_with_unfold" => fn -> pair_with_unfold(list0, list1) end,
      "pair_with_recursion" => fn ->
        pair_with_recursion(list0, list1)
      end
    })
  end
end
2 Likes
20

@dimitarvp This topic is awesome!

I would like to see more of those ‘using the community to find the best solution’-topics from experienced Elixir developers (opposed to newbie questions). Great value and with a good amount of SEO it might be so that inexperienced developers find those topics first :wink:

4 Likes