Optimizing an "almost-increasing" array problem

Ya know what else has to iterate over the whole list? List.delete_at, especially when called with length(list). A quick benchmark:

Mix.install([:benchee])

list1 = 1..100 |> Enum.to_list()
length1 = length(list1)

list2 = 1..1000 |> Enum.to_list()
length2 = length(list2)

list3 = 1..10000 |> Enum.to_list()
length3 = length(list3)

Benchee.run(
  %{
    "100 elements" => fn -> List.delete_at(list1, length1) end,
    "1000 elements" => fn -> List.delete_at(list2, length2) end,
    "10000 elements" => fn -> List.delete_at(list3, length3) end
  },
  time: 10,
  memory_time: 2
)

produces the output on my machine:

Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-6820HQ CPU @ 2.70GHz
Number of Available Cores: 8
Available memory: 16 GB
Elixir 1.13.4
Erlang 25.0.2

Benchmark suite executing with the following configuration:
warmup: 2 s
time: 10 s
memory time: 2 s
reduction time: 0 ns
parallel: 1
inputs: none specified
Estimated total run time: 42 s

Benchmarking 100 elements ...
Benchmarking 1000 elements ...
Benchmarking 10000 elements ...

Name                     ips        average  deviation         median         99th %
100 elements        393.26 K        2.54 μs  ±1944.85%        1.85 μs        4.95 μs
1000 elements        80.38 K       12.44 μs   ±142.97%       10.82 μs       42.36 μs
10000 elements        6.85 K      145.95 μs    ±33.72%      143.90 μs      279.72 μs

Comparison: 
100 elements        393.26 K
1000 elements        80.38 K - 4.89x slower +9.90 μs
10000 elements        6.85 K - 57.40x slower +143.41 μs

Memory usage statistics:

Name              Memory usage
100 elements           3.18 KB
1000 elements         20.95 KB - 6.59x memory usage +17.77 KB
10000 elements       224.88 KB - 70.72x memory usage +221.70 KB

Even calling length on the input is not desirable, since it has to traverse the list all the way to the end.

Calling List.delete_at as part of a recursion is a quick way to end up in the O(N^2) Bad Place.

A different way to think about this problem is to ask the question: what are the outcomes of adding an element to the end of an already almost-increasing list?

To express this with functions, we can use Enum.reduce_while/3 because of the control flow it gives us:

Enum.reduce_while(list, initial_state, fn element, state ->
  # keep going:
  {:cont, new_state}
  # give up early:
  {:halt, final_state}
end)

The trick with reduce and friends is to pick the right shape for the “state” data.

In this problem, we have two important parts of the state:

• the last element we want to compare the new one to
• what have we seen so far?
  • almost-increasing with no errors
  • almost-increasing with one error
  • (no third case because we want to give up)

This suggests that “state” is a tuple of {status, last_element}.

Now we need an “initial” value. The empty list is almost-increasing, and we know the minimum value for elements is -105 so we can start with a value that will always be less than the first element of list:

Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
  ...
end)

(Note: there’s nothing magical about :all_increasing, it’s chosen solely for human readability)

There are two factors that decide what to do next:

• the last state
• the comparison result between last_element and element

so let’s use a case:

Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
  case {last_status, el > last_element} do

  end
end)

The first case is easy: if the list is almost-increasing and el is bigger, then the list is still almost-increasing and we should next look at element:

Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
  case {last_status, element > last_element} do
    {:all_increasing, true} ->
      {:cont, {:all_increasing, element}}
  end
end)

The next-easiest case is when we’ve already found a “bad” element and we find another one. In that case, it’s time to give up:

Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
  case {last_status, element > last_element} do
    {:all_increasing, true} ->
      {:cont, {:all_increasing, element}}

    {:one_wrong, false} ->
      {:halt, :not_increasing}
  end
end)

Almost as easy: if we’ve seen one wrong element but the current one is increasing, keep going:

Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
  case {last_status, element > last_element} do
    {:all_increasing, true} ->
      {:cont, {:all_increasing, element}}

    {:one_wrong, true} ->
       {:cont, {:one_wrong, element}} 

    {:one_wrong, false} ->
      {:halt, :not_increasing}
  end
end)

The tricky one is if the current element is “bad” but there are no previous errors. In that case, we continue noting that there’s been an error AND skip el (since it’s bad):

Enum.reduce_while(list, {:all_increasing, -106}, fn element, {last_status, last_element} ->
  case {last_status, element > last_element} do
    {:all_increasing, true} ->
      {:cont, {:all_increasing, element}}

    {:all_increasing, false} ->
       {:cont, {:one_wrong, last_element}}

    {:one_wrong, true} ->
       {:cont, {:one_wrong, element}} 

    {:one_wrong, false} ->
      {:halt, :not_increasing}
  end
end)

Without passing last_element in that case, sequences like [1,2,1,2] aren’t correctly detected.

Finally, the result of Enum.reduce_while is the last accumulator so it needs to be cleaned up into the boolean result.

Final code with some cleanup:

defmodule Sequence do
  def almost_increasing(sequence) do
    case Enum.reduce_while(sequence, {:all_increasing, -1000}, &do_almost_increasing/2) do
      {:all_increasing, _} -> true
      {:one_wrong, _} -> true
      :not_increasing -> false
    end
  end

  defp do_almost_increasing(el, {state, last_element}) do
    case {state, el > last_element} do
      {:all_increasing, true} ->
        {:cont, {:all_increasing, el}}

      {:all_increasing, false} ->
        {:cont, {:one_wrong, last_element}}

      {:one_wrong, true} ->
        {:cont, {:one_wrong, el}}

      {:one_wrong, false} ->
        {:halt, :not_increasing}
    end
  end
end