Задачи по алгоритмам: избавляемся от анаграмм

[cpud47]

Вы кажется очень лихо оценили сложность сортировки.

Теперь не могу вызвать std::swap, потому что prev укажет на слово next на следующем шаге цикла.

Просто нужно использовать words[write-1] вместо prev.

[sa2304]

https://en.cppreference.com/w/cpp/algorithm/sort.html
Complexity
Given N as last - first:
1,2) O(N·log(N)) comparisons using operator<(until C++20)std::less{}(since C++20).
3,4) O(N·log(N)) applications of the comparator comp

Упс, ошибся, когда написал :)

Видимо, слова words короткие, поэтому решение со std::sort работает не хуже подсчета букв в массиве.

[KukarekusUltra]

Для map вы неправильно посчитали асимптотику.

Там будет О(n * log (m)) где m количество букв, в данном случае 26. То есть асимптотика будет O(n)

[sa2304]

https://en.cppreference.com/w/cpp/container/map/operator_at.html
Complexity
Logarithmic in the size of the container.

Спасибо. Верно ли я понял?

m - размер контейнера, сложность map::operator[] - log(m).

n - размер массива - вход алгоритма.

• Считаем сложность map::operator[] константой O(1), когда m не зависит от n. Тогда сложность алгоритма - O(n * log(m)) все равно что O(n). Например:

  • латинский алфавит из 26 букв map<char, ...>, m = 26

  • любой символ char от 0 до 0xFF, m = sizeof(char) = 255

• Сложность map::operator[] - log(n), если бы m зависел от n. Тогда сложность алгоритма - O(n * log(n))

[Jijiki]

зашел на литкод и посмотрел задачку, и подумал щас

а что если проходиться по вектору, входному, и каждое слово тоесть побуквено кидать в своё дерево(бинарное), которое при добавлении сортирует буквы, когда дошли до конца вектора, имеем отсортированные слова, ну а там сравниваем и скипаем повторы как я понял

[Kelbon]

Leetcode сообщает "твое решение работает за 1 мс - это быстрее 90% других". Это разовое измерение. Это значит, что твой алгоритм - лучший по сложности , но в этот раз не повезло. Запусти еще раз, и тот же код способен отработать за 0 мс.

чатгпт?

words[w++] = std::move(words[r]) уничтожит строку, когда w == r, а std::swap нет. Напишите в комментариях, почему так. 

это не так

C++ предлагает и std::array, но не обнуляет массив. Элементы vector<int> stat(26) равны нулю, а array<int, 26> stat - нет

что-то мне подсказывает, что есть способ инициализировать массив...

А если уж по задаче, то я думаю лучше посчитать хеш не зависящий от порядка и сравнить его перед тем как проверять

[sa2304]

Я привел пример кода, в котором в векторе остаются пустые строки после words[i] = std::move(words[i]). Я проверил пример на Leetcode и другом компиляторе онлайн. Причина мне неясна, поэтому я попросил объяснить в комментариях. А Вы потрудились запустить пример и проверить или спорите без аргументов?=)

что-то мне подсказывает, что есть способ инициализировать массив...

Вы очень догадливы, способ есть =)

я думаю лучше посчитать хеш не зависящий от порядка и сравнить его перед тем как проверять

Так напишите код и проверьте. Такую функцию нужно придумать или найти. Круто блеснуть знаниями и показать "секретное" решение, но сперва напишите, тогда хвастайтесь =)

[Kelbon]

пустые строки после words[i] = std::move(words[i])

это зависит от реализации, если вы говорите о std string. Просто формально не всегда это "уничтожит строку". Почему так - потому что кто-то решил оптимизировать строку и убрать лишнюю проверку

Вы очень догадливы, способ есть =)

так вот вы вместо того чтобы написать = {} выбрали использовать std vector

Так напишите код и проверьте.

[trnc]

is_anagram как-то сложновато. Выше же сами писали про хэш, который не зависит от порядка. Сам когда-то на том же LeetCode решал похожую задачу на анаграммы и там хватило даже вот такого:

    static constexpr int BASE = 131;
    static constexpr long long MOD = 1e9 + 7;

    long long int compute_key(string_view word) {
        array<int, 26> freq{};
        for (char c : word) {
            freq[c - 'a']++;
        }
      
        long long key  = 0;
        for (int count : freq) {
            key = (key * BASE + count) % MOD;
        }
        return key;
    }

Хотя наверняка при тестировании на больших массивах данных будут коллизии.

[Kelbon]

Принципиально не пишу код, где возможны коллизии ради микрооптимизации

[trnc]

Во-первых, микрооптимизации или нет может сказать benchmark, разве вы его проводили? Я лично не умею заранее определять степень оптимальности глядя на код. Во-вторых, хэш функции, которые не учитывают порядок, предложили именно вы, только по факту сделали sum, у которого "ad" и "bc" дают один и тот же результат, догадываюсь, что когда вы это поняли на тестовых данных, просто добавили код который ещё разок бежит по строке и считает символы. Оптимальненько :)

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

[Kelbon]

Нет, всё именно как и задумывалось

 хэш функции, которые не учитывают порядок
 "ad" и "bc" дают один и тот же результат, догадываюсь, что когда вы это поняли на тестовых данных, просто добавили код

именно это и делает сумма всех символов в строке. Именно этого я и добивался, убрал проверки на анаграмму для точно не подходящих строк

ещё разок бежит по строке и считает символы.

это оптимально, потому что тут выбор либо возможность коллизии (некорректный ответ), либо проверка

[sa2304]

Я выбрал vector, но коротко упомянул, что массив в C++ реализует и array, но по умолчанию array не обнуляет элементы. Этим он похож на массив Си.

C++ разрешает инициализировать переменные с помощью = {}: так мы обнулим array или другие примитивные типы языка Си - int, double и прочие.

Статья - о легкой задаче, а не богатстве C++. Желающий найдет ответ "Почему так?" в документации по vector и array.
https://en.cppreference.com/w/cpp/container/vector.html
https://en.cppreference.com/w/cpp/container/array.html

Я пишу так, чтобы текст увлекал, а не отталкивал. Иной автор так боится погрешить против истины, что никак не поставит точку в предложении.

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

Спасибо за Ваши дополнения :)