Сравните это

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

Дикость

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

Не имея под рукой интересных проблем, что б их описать, решил прибегнуть к помощи небезызвестного (и уже упоминавшегося в канале) сервиса Leetcode. Выбрал задачу Wildcard Matching, уровня hard, их тех, что раньше пробовал решить, но не сумел.

Итак, вот оригинальная формулировка:

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Ограничения:

0 <= s.length, p.length <= 2000
s contains only lowercase English letters.
p contains only lowercase English letters, '?' or '*'.

Сразу заметим пару моментов: во-первых, строка и образец могут быть достаточно длинны, что б сделать совсем наивные решения неэффективными, во-вторых, строка не может содержать '?' или '*', а в образце – не бывает экранирования, в-третьих, строка должна полностью соответствовать образцу.

Первая приходящая в голову мысль: давайте будем итерироваться по строке и образцу "одновременно", ведь пока мы не встретили "звездочку" – всё абсолютно очевидно. Действительно, представим себе ту же задачу, но символов '*' – нет. Получим следующий набросок решения:

 bool isMatch(string s, string p) {
        auto sIndex = 0;
        auto pIndex = 0;

        auto sLen = s.length();
        auto pLen = p.length();
        int starIndex = -1;
        int matchedIndex = 0;

        while (sIndex < sLen)
        {
            // simply match then we increment the both indexes
            if (pIndex < pLen && (p[pIndex] == '?' || p[pIndex] == s[sIndex]))
            {          
                pIndex++;
                sIndex++;
                continue;
            }

            return false;
        }

        //still possible to have an unfinished pattern here
        //it matches if and only if the pattern is over 
        return pIndex == pLen;
    }

Продолжение следует.

#today #c_plus_plus #leetcode #algo #ToBeContinued

Дикость продолжается

Кратко объясню идеи сниппета из прошлого поста:
Идём по строке и образцу, если оба символа совпадает, просто наращиваем оба индекса, если в образце стоит знак вопроса - делаем тоже самое, т.к. он совпадает с любым другим символом, при первом же не совпадении – рапортуем о неудаче. Всё предельно просто.

Ну теперь попробуем вернуть "звёздочки": по определению '*' соответствует нулю либо любому иному количеству символов...то есть – она не соответствует ничему – весь вопрос в том, чему соответствует символы за ней...Что если мы попробуем матчить остаток строки остатку шаблона, а если не сможем – просто нарастим индекс в строке? Вот примерно такой набросочек:

class Solution {
public:
    bool isMatch(string s, string p) {
        auto sIndex = 0;
        auto pIndex = 0;

        if (p.empty())
        {
            return s.empty();
        }

        return isMatchImpl(s, p, sIndex, pIndex);
    }

    bool isMatchImpl(const string& s, string& p, int sIndex, int pIndex)
    {
        while (sIndex < s.size() && pIndex < p.size())
        {
            if (p[pIndex] == '?')
            {
                ++sIndex, ++pIndex;
                continue;
            }

            if (p[pIndex] == '*')
            {
                while (pIndex < p.size() - 1 && p[pIndex + 1] == '*')
                {
                    ++pIndex;
                }

                return matchStar(s, p, sIndex, ++pIndex);
            }

            if (p[pIndex] == s[sIndex])
            {
                ++sIndex, ++pIndex;
                continue;
            }

            return false;
        }

        if (sIndex < s.size() && (pIndex = p.size()))
        {
            return false;
        }

        if (sIndex == s.size())
        {
            while(pIndex < p.size())
            {
                if (p[pIndex] != '*')
                {
                    return false;
                }

                ++pIndex;
            }

            return true;
        }

        return true;
    }

    bool matchStar(const string& s, string& p, int sIndex, int pIndexAtStop)
    {
        // there is nothing after the star
        if (pIndexAtStop >= p.size())
        {
            return true;
        }

        auto stopCh = p[pIndexAtStop];

        cout << "stopchar = " << stopCh << endl;

        while (sIndex < s.size())
        {
            if (s[sIndex] == stopCh || stopCh == '?')
            {
                auto matched = isMatchImpl(s, p, sIndex + 1, pIndexAtStop + 1);

                if (matched)
                {
                    return true;
                }
            }

            ++sIndex;
        }

        return false;

    }
}

Это почти работает, в следующий раз – объясню в чём загвоздка и завершу этот маленький цикл.

#today #c_plus_plus #leetcode #algo #ToBeContinued

Закончим эту дикость

Не секрет, что для алгоритмов есть понятие корректности и сложности выполнения. С корректностью – всё нормально, с пространственной сложностью – всё сносно, она линейна от длины образца (тратим стек на каждую звездочку), со временной сложностью – плоховато...Позвольте мне не заниматься тут этими вычислениями – достаточно заметить, что платформа выдает Time Limit Exceeded на паттернах типа этого: "b**bb**a**bba*b**a*bbb**aba***babbb*aa****aabb*bbb***a".

Что же делать? На самом деле у нас очень много лишних действий...Предположим у нас есть часть выражение p1 даже с несколькими '*' и мы нашли, что оно матчит часть строки s1 (т.е. по сути части между звездочками в паттерне матчатся), и пусть в остатке шаблона p2 тоже есть "звездочки", тут важно понять, что вне зависимости от дальнейших сравнений – нет смысла заново сравнивать уже совпавшую часть шаблона p1. Действительно, при новом сравнении мы получили бы s1', уходящую правее, чем s1 – но в этом нет никакого смысла, т.к. звездочки в p2 итак могут "съесть" эти символы.

А вот и код:

class Solution {
public:
    bool isMatch(string s, string p) {
        auto sIndex = 0;
        auto pIndex = 0;

        auto sLen = s.length();
        auto pLen = p.length();
        int starIndex = -1;
        int matchedIndex = 0;

        while (sIndex < sLen)
        {
            // simply match then we increment the both indexes
            if (pIndex < pLen && (p[pIndex] == '?' || p[pIndex] == s[sIndex]))
            {          
                pIndex++;
                sIndex++;
            }
            // if it's a star then memorize its position, memorize the string position and go further to the next pattern index
            // note that here we can "consume" several stars going in the row
            else if (pIndex < pLen && p[pIndex] == '*') 
            {
                starIndex = pIndex;
                matchedIndex = sIndex;
                pIndex++;
            }
            // it's a mismatch but there is a star somewhere before it
            // then let's get back to the next index after the star in the pattern
            // and the star has eaten another symbol in the string
            else if (starIndex != -1)
             {
                pIndex = starIndex + 1;
                matchedIndex++;
                sIndex = matchedIndex;
            }
            //either mismatch or the pattern is over when the string is not
            else
            {
                return false;
            }
        }

        //still possible to have an unfinished pattern here
        // advance it while it's a star
        while (pIndex < pLen && p[pIndex] == '*') {
            pIndex++;
        }

        //it matches if and only if the pattern is over 
        return pIndex == pLen;
    }

};

#today #c_plus_plus #leetcode #algo