Сравните это

Часть 2.

В прошлый раз, мы пришли с решением, работающим, но не очень быстрым. Что же можно легко и быстро поменять, в надежде ускорить его? Правильно – используемый для dict контейнер – попробуем вместо map, которая внутри себя красно-чёрное дерево, использовать хэш-таблицу, то есть unordered_map. Не буду приводить полный листинг тут – я только изменил map на unordered_map.

Этого уже оказалось достаточно , что б стать лучше 67 процентов других решений. . А нужен ли вообще тут настоящий ассоциативный контейнер? Очевидно, что нет: букв всего 26, в конкретном слове их может быть меньше, но больше – взять неоткуда. Более того, если глянуть на таблицу ASCII все эти буквы (сюрприз-сюрприз) идут подряд и представляют собой однобайтовые целые, иначе говоря, в Си/С++ я могу сделать такой вот трюк: ch-'a', и тогда для ‘a’ я получаю индекс равный нулю, для ‘b’ – одному и так далее. То есть: использовать простой массив длинной 26. Попробуем с простым “деревянным” Сишным массивом, опять меняем только объявление:

dict: int dict[26] = {0};

Уже лучше, чем 74 процента ответов. Сишный массив – некрасиво, в настоящей разработке лучше их вовсе избегать, а что же использовать там для массива – конечно, vector – излюбленная тема всех собесов по плюсам. Изменим наш тип на vector и сразу скажем ему, что будет ровно 26 элементов – дабы ничего не замедлилось на его любимых переалокациях. Не буду приводить полный листинг: поменял только объявление dict на это:

vector<int> dict(26);

Всё – “провалился” в 0мс, тут оставим вопрос, а что, если я нажму Submit несколько раз с тем же самым решением – кому интересно попробуйте сами.

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

ex> "Elixir" |> String.graphemes() |> Enum.frequencies()
%{"E" => 1, "i" => 2, "l" => 1, "r" => 1, "x" => 1}

И захотелось мне, сравнить его с тем, как это пишется на C++, собственно задачу я нагуглил под условия…Да, этот кусочек на Elixir делает не совсем то, что в задаче, вот эквивалентный код:

 def are_occurrences_equal(s) do
    s |> String.graphemes() |> Enum.frequencies() 
    |> Map.values() |> Enum.uniq() |> Enum.count() == 1
  end

Написан только с помощью гугл и доков – потому что Эликсир я не знаю, только пытаюсь учить время от времени. Нужны ли тут комментарии насчёт выразительности, отсутствия явных циклов, низкоуровневых трюков и прочего? К сожалению, я не знаю насколько у меня быстрое решение на Эликсире, потому что Leetcode говорит, что слишком мало решений вообще у него есть (а может только моё одно?).

#IT #c_plus_plus #Elixir #leetcode

#IT #leetcode #Elixir

Давно ничего не писал, но сегодня последний день зимы, которой почти не было, и последний рабочий день на неделе, иначе говоря — пятница.

Есть в разработке такой тренд: переходить на функциональные языки программирования, либо добавлять такие фичи в уже существующие языки. Уже никого давно не удивить лямбдами в C++ (хотя, как обычно, синтаксис их уродлив).

Иногда, в фоне, ковыряю Elixir — функциональный язык, но не настолько теоретический как, скажем, Haskell.

Вот пример взятия корней из полных квадратов, реализованный через бинарный поиск и рекурсию:

defmodule SquareRoot do
  @doc """
  Calculate the integer square root of a positive integer
  """
  @spec calculate(radicand :: pos_integer) :: pos_integer
  def calculate(0), do: 0
  def calculate(1), do: 1
  
  def calculate(radicand) when is_number(radicand) and radicand > 0, do: calculate(radicand, 0, radicand)

  defp calculate(_, left, right) when left >= right, do: nil 

  defp calculate(radicand, left, right) do
    mid = div(left + right, 2)
    sq = mid * mid
    cond do
      sq == radicand -> mid
      sq > radicand -> calculate(radicand, left, mid)
      true -> calculate(radicand, mid, right)
    end
  end
end

#today #friday #elixir