Elixir big comprehension-list optimisation - takes too long

The reason this is taking so long is because you are traversing the list so many times (178,001 which is 31,684,178,000 elements to run through).

When you have that comprehension, you are basically doing the same as

Enum.map(all_words, fn a ->
  Enum.map(all_words, fn b ->
    ...
  end)
end)

So for each element in the list, you are actually traversing the entire list again.

What you may be able to do is reduce the list into a map with the key being the length of the word, and the values in a list. So you may end up with something like

%{
  3 => ["and", "bat"],
  5 => ["apple"]
}

Then you could just merge the numbers that equal 10. This should shrink your runtime a bit. There are probably ways to do this though.

This is how I mean it:

defmodule Glue do
  @list ~w[moto camera foo giraffe stupid thing word brat wurst]

  def pair(list \\ @list), do: list |> Enum.filter(&(String.length(&1) >= 3)) |> pair([])

  def pair([], acc), do: acc |> Enum.into([])
  def pair(list = [word|tail], acc) do
    len = 10 - String.length(word)

    acc = list
    |> Enum.filter(&(String.length(&1) === len))
    |> Enum.flat_map(fn
      other when other === word -> [other <> other]
      other -> [word <> other, other <> word]
    end)
    |> Stream.concat(acc)

    pair(tail, acc)
  end
end

IO.inspect(Glue.pair())

This is just a draft though, and still might have some room for optimisations, but at least it should be of O(n * log n) instead of O(n²).

Here is how I have generated 178_000 random “words” (just ~r/[a-zA-Z]{1,11}/) with random length from 1 to 11:

file = File.open!("words.txt", [:append])
list = Enum.to_list(?a..?z) ++ Enum.to_list(?A..?Z)

1..178_000 |> Flow.from_enumerable() |> Flow.each(fn _ ->
  length = Enum.random(1..11)
  data = Enum.map(1..length, fn _ -> Enum.random(list) end)
  IO.binwrite(file, data ++ '\n')
end) |> Flow.run()

File.close(file)

From this random input I have received 35_349_451 combinations in average 209 seconds.

Note: This time is much too big as I’m on my “standard” PC usage with web browser, code editor and video player.

Here is my example code:

defmodule Example do
  require Integer

  @target_length 10

  def sample(path) do
    path
    |> File.stream!()
    |> Flow.from_enumerable()
    |> Flow.reduce(fn -> %{} end, &group/2)
    |> Enum.into(%{})
    |> do_sample()
  end

  defp group(line, acc) do
    word = String.trim(line)
    length = String.length(word)
    if length > @target_length, do: acc, else: Map.update(acc, length, [word], &[word | &1])
  end

  defp do_sample(acc) do
    target_words = Map.get(acc, @target_length) || []
    lengths = Map.keys(acc) -- [5, 10]
    keys = for a <- lengths, b = Enum.find(lengths, &(a + &1 == 10)), not is_nil(b), do: {a, b}
    keys_flow = keys |> Flow.from_enumerable() |> Flow.flat_map(&combine(&1, acc))
    target_words ++ combine_half(acc) ++ Enum.to_list(keys_flow)
  end

  defp combine_half(acc) when Integer.is_even(@target_length) do
    half_length = round(@target_length / 2)
    list = Map.get(acc, half_length) || []
    combine(list)
  end

  defp combine_half(_acc), do: []

  defp combine([]), do: []

  defp combine([head | tail]) do
    tail_flow = tail |> Flow.from_enumerable() |> Flow.map(&(head <> &1))
    Enum.to_list(tail_flow) ++ combine(tail)
  end

  defp combine({a, b}, acc) do
    flow1 = acc |> Map.get(a) |> Flow.from_enumerable()
    flow2 = acc |> Map.get(b) |> Flow.from_enumerable()
    flow1 |> Flow.flat_map(&do_combine(&1, flow2)) |> Enum.to_list()
  end

  defp do_combine(word, flow), do: flow |> Flow.map(&(word <> &1)) |> Enum.to_list()
end

Example.sample("words.txt")

I got previous clause warning, but it’s only because @target_length module attribute is set at compile time. Feel free to modify it as you wish. For sure I believe that it’s definitely possible to write better code - it’s just my typical “5 min” example as I don’t have much time now.

Let me know what do you think about it.