unordered_map тормозит?
От: f95.2  
Дата: 21.04.20 20:31
Оценка:
Добрый вечер.
Я, конечно, слышал (краем уха) жалобы, что из-за текущих ограничений в c++ нельзя реализовать быстрый map на хеш-таблицах.
(хотя не разбирался толком, что это за ограничения и как они мешают )

Но не думал, что всё настолько плохо. Или я чего-то не понимаю?

Вот есть простенькая задачка с литкода: https://leetcode.com/problems/two-sum/
Мое решение на c++:
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        map.reserve(nums.size());

        for (int i = 0; i < nums.size(); ++i) {
            int other_part = target - nums[i];

            auto position_iter = map.find(other_part);
            if (position_iter != map.end()) {
                return vector<int>{position_iter->second, i};
            } else {
                 map.emplace(nums[i], i);
            }
        }

        return vector<int>{};
    }
};


И на java:
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap map = new HashMap<Integer, Integer>();

        for (int i = 0; i < nums.length; ++i) {
            int other_part = target - nums[i];

            Integer position = (Integer) map.get(other_part);
            if (position != null) {
                return new int[]{position, i};
            } else {
                map.put(nums[i], i);
            }
        }

        return new int[]{0, 0};
    }
}


Решение на java отрабатывает за 1-2ms, а на плюсах — за 8...

Почему так может быть? Я что-то где-то неоптимально делаю? Может, на разных машинах тестируются?
Или unordered_map действительно настолько плох, что проигрывает java'вскому HashMap, которому даже boxing-unboxing не мешает?
Re: unordered_map тормозит?
От: ned Австралия  
Дата: 22.04.20 01:00
Оценка:
Здравствуйте, f95.2, Вы писали:

F2>Решение на java отрабатывает за 1-2ms, а на плюсах — за 8...


Да там как повезёт. Верить нельзя. Вот сейчас запустил твоё решение:

Details
Runtime: 4 ms, faster than 99.84% of C++ online submissions for Two Sum.
Memory Usage: 8 MB, less than 100.00% of C++ online submissions for Two Sum.

Re: unordered_map тормозит?
От: LaptevVV Россия  
Дата: 22.04.20 05:24
Оценка:
F2>Я, конечно, слышал (краем уха) жалобы, что из-за текущих ограничений в c++ нельзя реализовать быстрый map на хеш-таблицах.
F2>(хотя не разбирался толком, что это за ограничения и как они мешают )
F2>Но не думал, что всё настолько плохо. Или я чего-то не понимаю?
Может зависеть от реализации.
Мне как-то пришлось делать обход графа в ширину.
Сделал на Студии, потом перенес проект в Code::Blocks на gcc.
И с удивлением обнаружил, что на gcc работает в 5 раз быстрее.
А во всех других проектах было лучше всего процентов на несколько. А тут в 5 раз.
Проверил-перепроверил — нет у меня никаких моих ошибок.
Обратился на РСДН.
Через пару дней один товарищ написал, что проблема в реализации стандартной библиотеки.
Я использовал дек для очереди.
А он в Студии реализован был очень плохо.
Переписал обход из ширины в глубину с вектором — все встало на свои места.

Мораль — надо анализировать производительность своего инструмента и сравнивать с другими.
Если скорость критична — надо либо инструмент менять, либо алгоритм переписывать с использованием других контейнеров.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re: unordered_map тормозит?
От: Alexander G Украина  
Дата: 22.04.20 15:00
Оценка:
Здравствуйте, f95.2, Вы писали:

F2>Я, конечно, слышал (краем уха) жалобы, что из-за текущих ограничений в c++ нельзя реализовать быстрый map на хеш-таблицах.

F2>(хотя не разбирался толком, что это за ограничения и как они мешают )

Из-за требований к итераторам мапы (не инвалидировать итераторы и поинтеры даже при перехешировании), коллизии решаются так, что в каждой корзине связный список с каждым элементом на куче.
Разумеется, это неэффективно.
Русский военный корабль идёт ко дну!
Re[2]: unordered_map тормозит?
От: andyp  
Дата: 22.04.20 20:28
Оценка:
Здравствуйте, Alexander G, Вы писали:

AG>Здравствуйте, f95.2, Вы писали:


F2>>Я, конечно, слышал (краем уха) жалобы, что из-за текущих ограничений в c++ нельзя реализовать быстрый map на хеш-таблицах.

F2>>(хотя не разбирался толком, что это за ограничения и как они мешают )

AG>Из-за требований к итераторам мапы (не инвалидировать итераторы и поинтеры даже при перехешировании), коллизии решаются так, что в каждой корзине связный список с каждым элементом на куче.

AG>Разумеется, это неэффективно.

Стандарт обратное говорит. Вот ссылка на пост на stackoverflow. Там сведены все ссылки на стандарт для всех контейнеров по вопросам, что и когда перестает быть валидным.
https://stackoverflow.com/questions/6438086/iterator-invalidation-rules
Re[2]: unordered_map тормозит?
От: T4r4sB Россия  
Дата: 22.04.20 20:44
Оценка:
Здравствуйте, Alexander G, Вы писали:


AG>Из-за требований к итераторам мапы (не инвалидировать итераторы и поинтеры даже при перехешировании), коллизии решаются так, что в каждой корзине связный список с каждым элементом на куче.


Там элементы в одном связном списке храняццо
Re: unordered_map тормозит?
От: andyp  
Дата: 22.04.20 21:23
Оценка: +1
Здравствуйте, f95.2, Вы писали:

F2>Почему так может быть?


Ну например из-за того, что разное начальное количество корзин в мапках или разный max_load_factor. Я к тому, что разное количество раз rehashing может быть.
Re: unordered_map тормозит?
От: a7d3  
Дата: 26.04.20 09:07
Оценка:
Здравствуйте, f95.2, Вы писали:

F2>Добрый вечер.

F2>Я, конечно, слышал (краем уха) жалобы, что из-за текущих ограничений в c++ нельзя реализовать быстрый map на хеш-таблицах.
F2>(хотя не разбирался толком, что это за ограничения и как они мешают )

F2>Но не думал, что всё настолько плохо. Или я чего-то не понимаю?


Как тут уже говорилось одним комментатором — надо смотреть на параметры, с которыми создаётся хэш-таблица.
Задаваемое число bucket'ов и какой именно load factor.

unordered_map относится к тому виду хэш-таблиц, которые с separate chaining. А значит при возникновении коллизии будет проход по связанному списку, что ни разу не cache friendly, как и любой другой последовательный проход по связанному списку.
Ну и перехэширование тоже может сказываться.

В общем, любой профилировщик покажет на чём затык, а они щас чуть ли не встроенные во всякие CLion, KDevelop, QtCreator и тот же VS Code.
Re: unordered_map тормозит?
От: sergii.p  
Дата: 28.04.20 17:42
Оценка:
Здравствуйте, f95.2, Вы писали:

F2>Решение на java отрабатывает за 1-2ms, а на плюсах — за 8...


на сколько я знаю, java использует "честный" хэш (грубо говоря, число 10 равновероятно преобразуется в число в диапазоне от 0 до 2^32), а в C++ — std::hash<int>{}(10) вернёт 10. Это может негативно сказываться на "диких" последовательностях типа: 1, 2, 3, 4, 10, 11, 101, 102, 1001, 1002. Но по факту конечно это такую разницу дать не может.
Если предположить, что организован хэш в java и C++ примерно одинаково, то скорее всего, дело в аллоцировании памяти. А тут, как мне кажется, имеется классическая ошибка оценки скорости работы java приложения. Да, выделяется память в java быстрее. Но узкое место тут как раз — освобождение памяти. Если бы мы дождались отработки сборщика мусора, тут и увидели бы истинную картину. А это можно сделать только под нагрузкой. В простеньких проектах сборщик мусора вызывается уже после окончания работы приложения, когда замеры сделаны и фанаты явы радостно потирают руки.
Отредактировано 28.04.2020 17:46 sergii.p . Предыдущая версия .
Re[2]: unordered_map тормозит?
От: dkotov  
Дата: 10.11.20 08:24
Оценка:
Здравствуйте, sergii.p, Вы писали:

SP>Здравствуйте, f95.2, Вы писали:


F2>>Решение на java отрабатывает за 1-2ms, а на плюсах — за 8...


SP>на сколько я знаю, java использует "честный" хэш (грубо говоря, число 10 равновероятно преобразуется в число в диапазоне от 0 до 2^32), а в C++ — std::hash<int>{}(10) вернёт 10. Это может негативно сказываться на "диких" последовательностях типа: 1, 2, 3, 4, 10, 11, 101, 102, 1001, 1002. Но по факту конечно это такую разницу дать не может.


MS под капотом использует "Fnv1A", а вот GCC "как есть".
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Re: unordered_map тормозит?
От: -prus-  
Дата: 13.11.20 12:03
Оценка: 10 (1)
Здравствуйте, f95.2, Вы писали:

F2>Почему так может быть? Я что-то где-то неоптимально делаю? Может, на разных машинах тестируются?

F2>Или unordered_map действительно настолько плох, что проигрывает java'вскому HashMap, которому даже boxing-unboxing не мешает?

Вдруг пригодится:
Hashmaps Benchmarks Overview
flat_hash_map (A very fast hashtable)
С уважением,
Евгений
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.