Добрый вечер.
Я, конечно, слышал (краем уха) жалобы, что из-за текущих ограничений в c++ нельзя реализовать быстрый map на хеш-таблицах.
(хотя не разбирался толком, что это за ограничения и как они мешают )
Но не думал, что всё настолько плохо. Или я чего-то не понимаю?
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 не мешает?
Здравствуйте, 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.
F2>Я, конечно, слышал (краем уха) жалобы, что из-за текущих ограничений в c++ нельзя реализовать быстрый map на хеш-таблицах. F2>(хотя не разбирался толком, что это за ограничения и как они мешают ) F2>Но не думал, что всё настолько плохо. Или я чего-то не понимаю?
Может зависеть от реализации.
Мне как-то пришлось делать обход графа в ширину.
Сделал на Студии, потом перенес проект в Code::Blocks на gcc.
И с удивлением обнаружил, что на gcc работает в 5 раз быстрее.
А во всех других проектах было лучше всего процентов на несколько. А тут в 5 раз.
Проверил-перепроверил — нет у меня никаких моих ошибок.
Обратился на РСДН.
Через пару дней один товарищ написал, что проблема в реализации стандартной библиотеки.
Я использовал дек для очереди.
А он в Студии реализован был очень плохо.
Переписал обход из ширины в глубину с вектором — все встало на свои места.
Мораль — надо анализировать производительность своего инструмента и сравнивать с другими.
Если скорость критична — надо либо инструмент менять, либо алгоритм переписывать с использованием других контейнеров.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, f95.2, Вы писали:
F2>Я, конечно, слышал (краем уха) жалобы, что из-за текущих ограничений в c++ нельзя реализовать быстрый map на хеш-таблицах. F2>(хотя не разбирался толком, что это за ограничения и как они мешают )
Из-за требований к итераторам мапы (не инвалидировать итераторы и поинтеры даже при перехешировании), коллизии решаются так, что в каждой корзине связный список с каждым элементом на куче.
Разумеется, это неэффективно.
Здравствуйте, Alexander G, Вы писали:
AG>Здравствуйте, f95.2, Вы писали:
F2>>Я, конечно, слышал (краем уха) жалобы, что из-за текущих ограничений в c++ нельзя реализовать быстрый map на хеш-таблицах. F2>>(хотя не разбирался толком, что это за ограничения и как они мешают )
AG>Из-за требований к итераторам мапы (не инвалидировать итераторы и поинтеры даже при перехешировании), коллизии решаются так, что в каждой корзине связный список с каждым элементом на куче. AG>Разумеется, это неэффективно.
AG>Из-за требований к итераторам мапы (не инвалидировать итераторы и поинтеры даже при перехешировании), коллизии решаются так, что в каждой корзине связный список с каждым элементом на куче.
Здравствуйте, f95.2, Вы писали:
F2>Почему так может быть?
Ну например из-за того, что разное начальное количество корзин в мапках или разный max_load_factor. Я к тому, что разное количество раз rehashing может быть.
Здравствуйте, f95.2, Вы писали:
F2>Добрый вечер. F2>Я, конечно, слышал (краем уха) жалобы, что из-за текущих ограничений в c++ нельзя реализовать быстрый map на хеш-таблицах. F2>(хотя не разбирался толком, что это за ограничения и как они мешают )
F2>Но не думал, что всё настолько плохо. Или я чего-то не понимаю?
Как тут уже говорилось одним комментатором — надо смотреть на параметры, с которыми создаётся хэш-таблица.
Задаваемое число bucket'ов и какой именно load factor.
unordered_map относится к тому виду хэш-таблиц, которые с separate chaining. А значит при возникновении коллизии будет проход по связанному списку, что ни разу не cache friendly, как и любой другой последовательный проход по связанному списку.
Ну и перехэширование тоже может сказываться.
В общем, любой профилировщик покажет на чём затык, а они щас чуть ли не встроенные во всякие CLion, KDevelop, QtCreator и тот же VS Code.
Здравствуйте, 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 быстрее. Но узкое место тут как раз — освобождение памяти. Если бы мы дождались отработки сборщика мусора, тут и увидели бы истинную картину. А это можно сделать только под нагрузкой. В простеньких проектах сборщик мусора вызывается уже после окончания работы приложения, когда замеры сделаны и фанаты явы радостно потирают руки.
Здравствуйте, 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 "как есть".
Здравствуйте, f95.2, Вы писали:
F2>Почему так может быть? Я что-то где-то неоптимально делаю? Может, на разных машинах тестируются? F2>Или unordered_map действительно настолько плох, что проигрывает java'вскому HashMap, которому даже boxing-unboxing не мешает?