Эффективность кода: в теории и на практике

19 апреля 2020

На днях я вспомнил, что у меня есть аккаунт на HackerRank, и решил вспомнить старое, порешать там задачки.

Для разминки решил взять не сложную: Simple Text Editor

Описание задачи смотрите по ссылке, не буду его тут дублировать. Но суть в том, что нужно хранить некий стейт, выполнять к нему запросы на чтение и на модификацию. Дело не сложное, думал, что быстро управлюсь.

Решение №1

Начнем с простого решения, не задумываясь об эффективности. В первую очередь нужно сосредоточиться на самой задаче. А уж потом думать об оптимизациях, если это понадобится. Для задач на HackerRank, как правило, это таки понадобится. А в реальной жизни может быть и нет.

Итак, поскольку у нас есть операция undo, то очевидный подход -- хранить историю всех модификаций, и уметь применять и откатывать каждую модификацию.

У нас есть две модифицирующих операции:

  @type operation :: {:append, String.t} | {:delete, String.t}
  

Историю можно хранить простым списком:

  @type operation_history :: [operation]
  

И весь стейт, который нам нужен, это текущее состояние строки в редакторе, и история операций:

  @type t :: {operation_history, String.t}
  

Делаем АПИ в функциональном стиле из чистых функций. Их понадобится пять штук:

• new/0 -- создать новый редактор (стейт);
• get/2 -- получить символ в указанной позиции;
• append/2 -- добавить строку;
• delete/2 -- удалить строку;
• undo/1 -- отменить предыдущую операцию.

Функция new/0 просто создает пустой стейт:

  @spec new() :: t
  def new() do
    {[], ""}
  end
  

Функция get/2 достаточно тривиальна:

  @spec get(integer, t) :: String.t
  def get(pos, {_, str}) do
    String.at(str, pos - 1)
  end
  

Функция append/2 модифицирует строку и сохраняет в истории операцию append:

  @spec append(String.t, t) :: t
  def append(new_str, {operations, str}) do
    new_operation = {:append, new_str}
    {[new_operation | operations], str <> new_str}
  end
  

Функция delete/2 аналогичная:

  @spec delete(integer, t) :: t
  def delete(len, {operations, str}) do
    {str, deleted_str} = delete_tail(str, len)
    new_operation = {:delete, deleted_str}
    {[new_operation | operations], str}
  end
  

Вместе с операцией delete сохраняется удаленный кусок строки. Так будет проще потом отменить эту операцию.

Само удаление хвоста строки хоть и достаточно просто, но все-таки вынесено в отдельную функцию:

  @spec delete_tail(String.t, integer) :: {String.t, String.t}
  defp delete_tail(str, tail_len) do
    String.split_at(str, String.length(str) - tail_len)
  end
  

Функция undo/1 немного сложнее и интереснее всех предыдущих функций:

  @spec undo(t) :: t
  def undo({operations, str}) do
    [operation | operations] = operations
    case operation do
      {:append, appended_str} ->
        {str, _} = delete_tail(str, String.length(appended_str))
        {operations, str}
      {:delete, deleted_str} ->
        str = str <> deleted_str
        {operations, str}
    end
  end
  

Она берет из истории последнюю операцию и отменяет её действие.

В целом реализация достаточно простая и занимает немного строк кода:

defmodule SimpleTextEditor do
  @moduledoc """
  https://www.hackerrank.com/challenges/simple-text-editor/problem
  """

  @type operation :: {:append, String.t} | {:delete, String.t}
  @type operation_history :: [operation]
  @type t :: {operation_history, String.t}


  @spec new() :: t
  def new() do
    {[], ""}
  end


  @spec get(integer, t) :: String.t
  def get(pos, {_, str}) do
    String.at(str, pos - 1)
  end


  @spec append(String.t, t) :: t
  def append(new_str, {operations, str}) do
    new_operation = {:append, new_str}
    {[new_operation | operations], str <> new_str}
  end


  @spec delete(integer, t) :: t
  def delete(len, {operations, str}) do
    {str, deleted_str} = delete_tail(str, len)
    new_operation = {:delete, deleted_str}
    {[new_operation | operations], str}
  end


  @spec undo(t) :: t
  def undo({operations, str}) do
    [operation | operations] = operations
    case operation do
      {:append, appended_str} ->
        {str, _} = delete_tail(str, String.length(appended_str))
        {operations, str}
      {:delete, deleted_str} ->
        str = str <> deleted_str
        {operations, str}
    end
  end

  @spec delete_tail(String.t, integer) :: {String.t, String.t}
  defp delete_tail(str, tail_len) do
    String.split_at(str, String.length(str) - tail_len)
  end

end
  

Правда этого мало, нужно еще взаимодействие с HackerRank -- чтение запросов и вывод ответов:

defmodule Runner do
  alias SimpleTextEditor, as: Editor


  def run() do
    num_operations = IO.gets("") |> String.trim |> int_arg
    do_operation(Editor.new(), num_operations)
  end


  defp do_operation(editor, 0), do: :done
  defp do_operation(editor, counter) do
    case IO.gets("") |> String.split([" ", "\n"]) do
      ["1", str | _] -> Editor.append(str, editor)
      ["2", len | _] -> Editor.delete(int_arg(len), editor)
      ["3", pos | _] ->
        char = Editor.get(int_arg(pos), editor)
        IO.puts(char)
        editor
      ["4" | _] -> Editor.undo(editor)
    end
    |> do_operation(counter - 1)
  end

  defp int_arg(str) do
    Integer.parse(str) |> elem(0)
  end

end

Runner.run
  

Тут тоже всё не сложно: читаем количество операций, потом в рекурсивной функции обрабатываем каждую операцию. Реализован только happy path, так как HackerRank дает корректные данные и не требует обработки ошибок.

Что ж, запускаем наше первое решение. 16 тестов, 10 прошли успешно, 6 не прошли по лимиту времени.

Ну это ожидаемый результат. Как видно, пришла пора задуматься об оптимизации.

Решение №2

Попробуем сделать две вещи. Во-первых, будем работать с головой строки, а не с хвостом. И для этого строку будем хранить в развернутом виде. Во-вторых, будем хранить в стейте длину строки, чтобы не вычислять ее, всякий раз, когда она нужна.

Откровенно говоря, эти две оптимизации справедливы только для List, а у нас String, то есть binary. Для binary, вроде бы, не должно быть принципиальной разницы, модифицируется голова или хвост. И длина, вроде бы, должна вычисляться за константное время. Или нет?

Ну вот сейчас и посмотрим.

Теперь каждая операция хранит не только строку, но и ее длину:

  @type operation :: {:append, integer, String.t} | {:delete, integer, String.t}
  

И длина текущей строки в редакторе тоже хранится в стейте:

  @type t :: {operation_history, integer, String.t}
  

Функции new/0 и get/2 принципиально не меняются.

Функция append/2 разворачивает строку, добавляет ее в начало, и сохраняет в стейте длины строк:

  @spec append(String.t, t) :: t
  def append(new_str, {operations, len, str}) do
    new_len = byte_size(new_str)
    new_str = String.reverse(new_str)
    new_operation = {:append, new_len, new_str}
    {[new_operation | operations], new_len + len, new_str <> str}
  end
  

Функция delete/2 удаляет начало строки, и тоже сохраняет длины строк:

  @spec delete(integer, t) :: t
  def delete(del_len, {operations, len, str}) do
    <<del_str::binary-size(del_len), str::binary>> = str
    new_operation = {:delete, del_len, del_str}
    {[new_operation | operations], len - del_len, str}
  end
  

Для удаления я использовал pattern matching на binary вместо String.split_at в надежде, что это может быть эффективнее.

Ну и функция undo делает все то же, но с учетом новой структуры стейта:

  @spec undo(t) :: t
  def undo({operations, len, str}) do
    [operation | operations] = operations
    case operation do
      {:append, app_len, _app_str} ->
        <<_::binary-size(app_len), str::binary>> = str
        {operations, len - app_len, str}
      {:delete, del_len, del_str} ->
        {operations, del_len + len, del_str <> str}
    end
  end
  

Все в целом получилось так:

defmodule OptimizedTextEditor do
  @moduledoc """
  https://www.hackerrank.com/challenges/simple-text-editor/problem
  """

  @type operation :: {:append, integer, String.t} | {:delete, integer, String.t}
  @type operation_history :: [operation]
  @type t :: {operation_history, integer, String.t}


  @spec new() :: t
  def new() do
    {[], 0, ""}
  end


  @spec get(integer, t) :: String.t
  def get(pos, {_, len, str}) do
    String.at(str, len - pos)
  end


  @spec append(String.t, t) :: t
  def append(new_str, {operations, len, str}) do
    new_len = byte_size(new_str)
    new_str = String.reverse(new_str)
    new_operation = {:append, new_len, new_str}
    {[new_operation | operations], new_len + len, new_str <> str}
  end


  @spec delete(integer, t) :: t
  def delete(del_len, {operations, len, str}) do
    <<del_str::binary-size(del_len), str::binary>> = str
    # {del_str, str} = String.split_at(str, del_len)
    new_operation = {:delete, del_len, del_str}
    {[new_operation | operations], len - del_len, str}
  end


  @spec undo(t) :: t
  def undo({operations, len, str}) do
    [operation | operations] = operations
    case operation do
      {:append, app_len, _app_str} ->
        <<_::binary-size(app_len), str::binary>> = str
        # {_, str} = String.split_at(str, app_len)
        {operations, len - app_len, str}
      {:delete, del_len, del_str} ->
        {operations, del_len + len, del_str <> str}
    end
  end

end
  

В Runner нужно только заменить реализацию Editor, остальное остается, как было:

defmodule Runner do
  alias OptimizedTextEditor, as: Editor
  

Запускаем. Результат тот же -- 10 тестов проходят успешно, 6 не проходят по лимиту времени. Гм, ну ясно. binary -- это не List. Для него эти оптимизации не помогают. Нужно придумать что-то другое.

Решение №3

Хорошо, давайте зайдем с другого боку. Не будем хранить историю операций, а будем хранить историю изменений текущей строки. Это увеличит потребление памяти. Зато undo не потребует никаких действий.

И реализация очень простая. Нужно всего лишь хранить стек изменений сроки:

defmodule JustStackTextEditor do
  @moduledoc """
  https://www.hackerrank.com/challenges/simple-text-editor/problem
  """

  @type t :: [{integer, String.t}]


  @spec new() :: t
  def new(), do: []


  def get(pos, [{len, str} | _]) do
    String.at(str, len - pos)
  end


  @spec append(String.t, t) :: t
  def append(new_str, []) do
    new_len = byte_size(new_str)
    new_str = String.reverse(new_str)
    [{new_len, new_str}]
  end


  def append(new_str, [{len, str} | _] = stack) do
    new_len = byte_size(new_str)
    new_str = String.reverse(new_str)
    [{new_len + len, new_str <> str} | stack]
  end


  @spec delete(integer, t) :: t
  def delete(del_len, [{len, str} | _] = stack) do
    <<_::binary-size(del_len), str::binary>> = str
    [{len - del_len, str} | stack]
  end


  @spec undo(t) :: t
  def undo([_ | stack]), do: stack

end
  

Видно, что от идеи хранить строку в перевернутом виде и её длину я не отказался. Иначе все было бы еще проще.

Подменяем реализацию:

defmodule Runner do
  alias JustStackTextEditor, as: Editor
  

Запускаем. 11 тестов проходят успешно, 5 не проходят по лимиту времени. Опять не то. Как же так? Что делать?

Решение №3 с модификацией

А черт его знает, что делать. Может, там String.at тормозит? Кто их знает, этих эликсирщиков, как у них там String.at реализован? Вдруг сделали O(n). А у нас тут binary, и это за константное время можно извлечь.

Попробуем pattern matching:

  @spec get(integer, t) :: String.t
  def get(pos, [{len, str} | _]) when pos == len do
    <<char::binary-size(1), _::binary>> = str
    char
  end

  def get(1, [{len, str} | _]) do
    pos = len - 1
    <<_::binary-size(pos), char::binary-size(1)>> = str
    char
  end

  def get(pos, [{len, str} | _]) do
    pos = len - pos
    <<_::binary-size(pos), char::binary-size(1), _::binary>> = str
    char
  end
  

Тут уж наша простая функция get/1 стала не такой простой. Но, наверняка, усилия того стоили. Сейчас должно быть быстрее.

Запускаем. То же самое -- 5 тестов не проходят по лимиту времени.

Ну ладно, ясно, что String.at реализован нормально, за константное время. Эликсирщики не дураки, это я дурак.

Бенчмарки

Что ж, пора прекращать действовать наугад и подойти, наконец, к задаче как инженер. Нужно профилировать код и искать узкое место целенаправленно.

К счастью, HackerRank позволяет скачать свои тестовые данные. Что я и делаю. А дальше нужно написать бенчмарк, который прогонит мою реализацию на этих данных.

Бенчмарк берет произвольную функцию, вызывает ее 10 раз (по-хорошему стоило бы на порядок больше, но тогда придется долго ждать результатов), и показывает среднее время выполнения функции:

  defp profile_fun(f, label) do
    num_runs = 10
    times = Enum.map(1..num_runs,
         fn count ->
           {time, _res} = :timer.tc(f)
           {count, time}
         end)
    total_time = Enum.reduce(times, 0, fn {_, t}, acc -> t + acc  end)
    avg_time = total_time / num_runs
    IO.puts("profile #{label}, avg time #{avg_time} times: #{inspect(times)}")
  end
  

Теперь мы загрузим тестовые данные, обернем работу с редактором в анонимную функцию, и передадим эту функцию в бенчмарк:

  def profile() do
    file = "./hr/simple-text-editor-input-7.txt"
    {:ok, content} = File.read(file)
    [first_line | lines] = String.split(content, "\n", trim: true)
    profile_fun(
      fn ->
        Enum.reduce(lines, {Editor.new, ""}, &profile_operation/2)
      end,
      "SimpleTextEditor")
  end

  defp profile_operation(operation, editor) do
    case String.split(operation, [" "]) do
      ["1", str] ->
        Editor.append(str, editor)
      ["2", len] ->
        Editor.delete(int_arg(len), editor)
      ["3", pos] ->
        char = Editor.get(int_arg(pos), editor)
        IO.puts(char)
        editor
      ["4"] ->
        Editor.undo(editor)
    end
  end
  

Теперь сравним наши три реализации:

profile SimpleTextEditor, avg time 3,842,529.4 times: [{1, 3560961}, {2, 3443607}, ...
profile OptimizedTextEditor, avg time 3,326,230.4 times: [{1, 3097741}, {2, 3125766}, ...
profile JustStackTextEditor, avg time 3,949,343.8 times: [{1, 3199777}, {2, 3625935}, ...
  

Интересно, что все три дают примерно одинаковое время. Это значит, что все наши теоретические рассуждения об эффективности кода ничего не стоят. А еще, это наводит на мысль, что дело не в реализации Editor, а в реализации Runner.

Что ж такого может быть в Runner?

Внезапная догадка, а что если здесь:

        char = Editor.get(int_arg(pos), editor)
        IO.puts(char)
        editor
  

закомментировать IO.puts?

Комментируем, прогоняем бенчмарк, и:

profile JustStackTextEditor, avg time 1416788.3 times: [{1, 1046831}, {2, 1361710}, ...
  

Ускорение больше чем в 2 раза!

Ага! Вот уж эти эликсирщики. Напихали всяких string interpolation в свой IO.puts, и он тормозит. Уж, конечно, с правильными эрланговскими функциями такого не случится.

Заменяю IO.puts на :io.format. Гм, результат тот же.

Заменяю :io.format на :io.put_chars. Результат тот же.

Похоже я второй раз облажался обвиняя эликсирщиков в некомпетентности :)

Правильное решение

А давайте попробуем буферизированный вывод. Вместо того, чтобы вызывать IO.puts 100500 раз с одним символом, давайте попробуем накопить все эти символы, и вызвать IO.puts один раз в конце.

Немного усложняется код, так как мы передаем в рекурсии не только стейт редактора, но и буфер для накопления вывода:

  def profile() do
    file = "./hr/simple-text-editor-input-7.txt"
    {:ok, content} = File.read(file)
    [first_line | lines] = String.split(content, "\n", trim: true)
    profile_fun(
      fn ->
        {_editor, output} = Enum.reduce(lines, {Editor.new, ""}, &profile_operation/2)
        IO.puts(output)
      end,
      "SimpleTextEditor")
  end

  defp profile_operation(operation, {editor, output}) do
    case String.split(operation, [" "]) do
      ["1", str] ->
        {Editor.append(str, editor), output}
      ["2", len] ->
        {Editor.delete(int_arg(len), editor), output}
      ["3", pos] ->
        char = Editor.get(int_arg(pos), editor)
        {editor, output <> char <> "\n"}
      ["4"] ->
        {Editor.undo(editor), output}
    end
  end
  

Результат:

profile SimpleTextEditor, avg time 1,397,909.9 times: [{1, 1305942}, {2, 1338951}, ...
profile OptimizedTextEditor, avg time 925,032.5 times: [{1, 977133}, {2, 843107}, ...
profile JustStackTextEditor, avg time 1,599,463.3 times: [{1, 1220573}, {2, 1368548}, ...
  

Совсем другое дело. И, кстати, оказывается, что OptimizedTextEditor все-таки работает быстрее. Раньше это маскировалось тормозами в IO, а сейчас стало явно.

Вносим такую же доработку в Runner:

  def run() do
    num_operations = IO.gets("") |> String.trim |> int_arg
    {_editor, output} = do_operation({Editor.new(), ""}, num_operations)
    IO.puts(output)
  end

  defp do_operation({editor, output}, 0), do: {editor, output}
  defp do_operation({editor, output}, counter) do
    case IO.gets("") |> String.split([" ", "\n"]) do
      ["1", str | _] ->
        {Editor.append(str, editor), output}
      ["2", len | _] ->
        {Editor.delete(int_arg(len), editor), output}
      ["3", pos | _] ->
        char = Editor.get(int_arg(pos), editor)
        {editor, output <> char <> "\n"}
      ["4" | _] ->
        {Editor.undo(editor), output}
    end
    |> do_operation(counter - 1)
  end
  

И HackerRank, наконец, принимает решение. 16 из 16 тестов проходят успешно.

Заодно проверяем, есть ли разница между: String.at(str, len - pos) и <<_::binary-size(pos), char::binary-size(1), _::binary>> = str Нет разницы. Вероятно, String.at именно так и реализован.

Итого

Теоретические рассуждения о производительности оказались частично верны, но это не помогло найти узкое место. Помог запуск бенчмарков на подходящих данных.

Оптимизация производительности на основе теоретических рассуждений, без бенчмарков и перф-тестов -- это ерунда. (При этом сделать правильные бенчмарки и перф-тесты само по себе может быть нетривиальным. Но это тема для отдельного разговора.)

comments powered by Disqus