Сравните это

Часть 1.

Сегодня будет длинный пост, ещё и с кодом, так получается – ничего не могу поделать с этим.

Итак, я взял простенькую задачку с Leetcode: нужно написать одну функцию, принимающую на вход строку длинной от 1 до 1000 символом, символ – буква латинского алфавита в нижнем регистре т.е. a…z, функция должна вернуть true если все буквы встречаются в строке одинаковое количество раз, т.е. “a”, “ab”, “azzabb” – примеры входных данных на которых нужно вернуть true, а “aza”, “bzcc” – примеры на которых нужно вернуть false. Что удобно на Leetcode – можно просто написать решение нажать Run, Submit – и увидеть, работает оно или нет, и если да – то оно сравнит его скорость с другими решениями.

Задача понятная, задача простая…первым шагом нужно посчитать частоты встречающихся в слове букв и сохранить их. Вторым шагом нужно проверить, что они все одинаковы, т.е. выглядит так, что нужно написать 2 цикла, первый будет сложность O(n), где n – длина строки, второй тоже O(1) – потому, что букв в английском алфавите всего 26.

Тут зададимся вопросом, что мы, собственно говоря, можем и должны всегда стараться использовать в языке C++ - правильно, STD, а конкретно – его контейнеры и алгоритмы, тут и Leetcode нам подсказывает, изначально выдавая в наброске решения входным параметром функции типа std::string, а не бестолковый const char* времён Си. Но, что собственно может std::string для решения этой задачи – а ничего…range-based for завезли в C++ 11, это немного сократит нам код и на этом всё. Давайте перейдем к листингу:

    bool areOccurrencesEqual(string s) {
        map<char, int> dict;
        for (const auto& ch: s)
        {
            auto it = dict.find(ch);

            if (dict.end() == it)
            {
                dict[ch] = 1;
            }
            else
            {
                ++it->second;
            }
        }

        int count = 0;

        for (const auto& [_, value]: dict)
        {
            if (count != value && count)
            {
                return false;
            }

            if (!count)
            {
                count = value;
            }
        }

        return true;
    }

В этом решении всё максимально прямолинейно: сделали именно, то, что написано, сначала итерируемся по всем буквам в строке считаем и запоминаем в dict, потом – идём по dict, сравниваем, что все частоты одинаковы, нужно учесть, что вначале count нулевой, и необходимо его инициализировать, встретив первое ненулевое значение.

Но вот загвоздка: работает не очень быстро, всего лишь лучше 27% других решений – мы тут явно не ради такого собрались!

#IT #c_plus_plus #leetcode #today #ToBeContinued

#IT #c_plus_plus #leetcode #today #ToBeContinued

Сравните это

Часть 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 #c_plus_plus #leetcode

#IT #leetcode #Elixir