Что такое unordered map — пояснять не нужно (кому нужно, закройте дверь с той стороны). У ей внутре неонка хэш-таблица, неважно, какого названия в конкретном месте, какого именно хэша и какого аккредитива addressing. Порядок ключей — не определён, может меняться в зависимости от фазы Луны и погоды на Сатурне, хотя обычно он более предсказуем — где делят хэш на простое число (замучивая процессор тяжёлой операцией деления, как в GCC STL), где доставая младшие биты. Но в любом случае он не фиксирован.
Есть два варианта, как допилить до фиксированного порядка. В одном используется какое-то сравнение ключей по их значению; получаем STLʼный <map> (внутре, обычно, ксенонка красно-чёрное дерево или что-то похожее). Но обидно людям, что O(log N) на одну операцию, всупереч хэшовому O(1), хоть и конкретно амортизированному. Поэтому некий сумрачный гений родил другой вариант: неважно, какие ключи по смыслу, главное, в каком порядке поступили. Не знаю, первой ли была Java, но LinkedHashMap там по жизни. Зато в JavaScript оно везде. Когда из меня хотели сделать вебостроителя (я успешно отбрыкался), я запомнил, что во всех его не-песочных реализациях соблюдается порядок перебора по порядку вставки. В ES6 это ещё и формализовали для Map, хотя и без него порядок соблюдается. (И на кой им ещё один Map такой же, как изначальный map? Будем считать, что тут так принято.)
N>когда в тесте надо сравнивать "<sip:123@abc>;session=yes;privacy=full" с "<sip:123@abc>;privacy=full;session=yes", а оно расходится
Хипстеры против программирования, счёт 0:1
Здравствуйте, Muxa, Вы писали:
N>>когда в тесте надо сравнивать "<sip:123@abc>;session=yes;privacy=full" с "<sip:123@abc>;privacy=full;session=yes", а оно расходится M> M>Хипстеры против программирования, счёт 0:1
Да. Это ж сколько работы тест привести к правильному виду, проще запилить сравнение строк.
Таков мой примар каминг-аут.
Нифига не понял. Хешмап для одних задач, линкедхешмап для других.
Лучше скажите, зачем в C++ назвали unordered map, а не hashmap? Короче же пишется. Или это типа с завязкой на будущие 100500 лет, если вдруг кто-то изобретёт алгоритм круче хешмапа? По-моему это уже какая-то абстракция головного мозга. С сортом то же самое. Нет бы назвать конкретную сортировку, quicksort, mergesort, timsort и тд.
Здравствуйте, vsb, Вы писали:
vsb>Нифига не понял. Хешмап для одних задач, линкедхешмап для других.
А какие такие задачи решает HashMap, что LinkedHashMap не справляется?
vsb>Лучше скажите, зачем в C++ назвали unordered map, а не hashmap? Короче же пишется. Или это типа с завязкой на будущие 100500 лет, если вдруг кто-то изобретёт алгоритм круче хешмапа? По-моему это уже какая-то абстракция головного мозга. С сортом то же самое. Нет бы назвать конкретную сортировку, quicksort, mergesort, timsort и тд.
Я понимаю. Только сегодня в вики увидел:
In OpenBSD 5.5, released in May 2014, arc4random was modified to use ChaCha20. The implementations of arc4random in NetBSD and Linux's libbsd also use ChaCha20.
Это же так интересно, когда в мавзолее Ленина давно лежит Брежнев, а табличку не меняют...
Здравствуйте, netch80, Вы писали:
vsb>>Нифига не понял. Хешмап для одних задач, линкедхешмап для других.
N>А какие такие задачи решает HashMap, что LinkedHashMap не справляется?
Хранение данных без расхода памяти на два лишних указателя и операции с данными без траты времени на манипуляцию с этими указателями.
Вот HashMap.Node:
final int hash;
final K key;
V value;
Node<K,V> next;
А вот LinkedHashMap.Entry (extends HashMap.Node):
Entry<K,V> before, after;
Размер первого объекта примерно 16 + 4 + 8 + 8 + 8 = 44 байта. Размер второго объекта 60 байтов. На 36% больше. Зачем лишние расходы? Может тогда вообще HashMap не использовать, выдумать какой-нибудь LinkedTreeMap, там и отсортированно можно вытянуть, вдруг пригодится, и в порядке вставки.
Здравствуйте, vsb, Вы писали:
vsb>Лучше скажите, зачем в C++ назвали unordered map, а не hashmap? Короче же пишется. Или это типа с завязкой на будущие 100500 лет, если вдруг кто-то изобретёт алгоритм круче хешмапа? По-моему это уже какая-то абстракция головного мозга. С сортом то же самое. Нет бы назвать конкретную сортировку, quicksort, mergesort, timsort и тд.
Всё именно так. За тем исключением, что внутри sort лежит 2-3 разных сортировки для разных размеров массива. Оптимизация под абстракцией.
Здравствуйте, vsb, Вы писали:
vsb>>>Нифига не понял. Хешмап для одних задач, линкедхешмап для других. N>>А какие такие задачи решает HashMap, что LinkedHashMap не справляется? vsb>Хранение данных без расхода памяти на два лишних указателя и операции с данными без траты времени на манипуляцию с этими указателями.
Так в том и дело, что в последние лет 5 появились реализации, в которых те затраты на упорядочение настолько снижены, что мало кого волнуют.
И вообще, с каких это пор "без расхода... на два лишних" это проблема? Расход это затрата, а проблемой он становится не сам по себе, а тогда, когда из-за него что-то куда-то не влезает.
Но тогда надо думать на всех уровнях, а не на одной мапе.
vsb>Размер первого объекта примерно 16 + 4 + 8 + 8 + 8 = 44 байта. Размер второго объекта 60 байтов. На 36% больше. Зачем лишние расходы?
Это такая реализация. Java не лучшее средство для экономии памяти, но даже для неё, думаю, возможно сделать не так радикально.
vsb> Может тогда вообще HashMap не использовать, выдумать какой-нибудь LinkedTreeMap, там и отсортированно можно вытянуть, вдруг пригодится, и в порядке вставки.
Можно. Но у TreeMap и так есть порядок, зачем ещё один?
Здравствуйте, vsb, Вы писали:
vsb>Лучше скажите, зачем в C++ назвали unordered map, а не hashmap? Короче же пишется. Или это типа с завязкой на будущие 100500 лет, если вдруг кто-то изобретёт алгоритм круче хешмапа? По-моему это уже какая-то абстракция головного мозга.
To avoid name clashes with non-standard libraries that developed their own hash table implementations, the prefix “unordered” was used instead of “hash”.
Здравствуйте, netch80, Вы писали:
N>Так в том и дело, что в последние лет 5 появились реализации, в которых те затраты на упорядочение настолько снижены, что мало кого волнуют.
Ну я пока таких не видел. А что за реализации? Какие-нибудь XOR-трюки над указателями? По факту в Java сделано так, поэтому если мы говорим про Java, то накладные расходы у LinkedHashMap есть и просто так использовать LinkedHashMap там, где достаточно HashMap это означает тратить память впустую. Кому-то может и пофиг, я считаю это неприемлемым.
N>Можно. Но у TreeMap и так есть порядок, зачем ещё один?
Для всех тех случаев, когда используют LinkedHashMap, т.е. людям важен порядок вставки.
Здравствуйте, koodeer, Вы писали:
vsb>>Лучше скажите, зачем в C++ назвали unordered map, а не hashmap? Короче же пишется. Или это типа с завязкой на будущие 100500 лет, если вдруг кто-то изобретёт алгоритм круче хешмапа? По-моему это уже какая-то абстракция головного мозга.
K>В Wiki пишут:
K>
To avoid name clashes with non-standard libraries that developed their own hash table implementations, the prefix “unordered” was used instead of “hash”.
А namespace на что? Непонятно. Если кто-то в std полез, это уже его проблемы.
Здравствуйте, Zhendos, Вы писали:
N>> И знаете, я их понимаю. Потому что когда в тесте надо сравнивать
Z>А я не очень, в чем проблема написать универсальную функцию сравнения двух dictionary/map?
Потому что оно прошло через отдельного участника, который уже экспортнул в текст, а проверяется вся цепочка.
Здравствуйте, netch80, Вы писали:
N>Есть два варианта, как допилить до фиксированного порядка. В одном используется какое-то сравнение ключей по их значению; получаем STLʼный <map> (внутре, обычно, ксенонка красно-чёрное дерево или что-то похожее). Но обидно людям, что O(log N) на одну операцию, всупереч хэшовому O(1), хоть и конкретно амортизированному. Поэтому некий сумрачный гений родил другой вариант: неважно, какие ключи по смыслу, главное, в каком порядке поступили. Не знаю, первой ли была Java, но LinkedHashMap там по жизни. Зато в JavaScript оно везде. Когда из меня хотели сделать вебостроителя (я успешно отбрыкался), я запомнил, что во всех его не-песочных реализациях соблюдается порядок перебора по порядку вставки. В ES6 это ещё и формализовали для Map, хотя и без него порядок соблюдается. (И на кой им ещё один Map такой же, как изначальный map? Будем считать, что тут так принято.)
не ясно что нужно: шашечки, или ехать? Если сравнивать по порядку поступления, то можно использовать std::list<std::pair> (а можно и std::vector); если нужна скорость поиска — std::unordered_map. Упомянутый всуе LinkedHashMap использует под капотом оба контейнера (и места занимает соответственно).
А вообще, думаю сравнивать в тестах по порядку вставки — идея так себе. Нужно соблюдать порядок в двух местах. Поменялся порядок формирования элементов — тесты отвалились. Поэтому, как уже было упомянуто, можно реализовать сравнение коллекций (благо, в случае std::unordered_map, это не так сильно ударит по производительности) и не быть хипстером
Здравствуйте, Nuzhny, Вы писали:
N>Здравствуйте, vsb, Вы писали:
vsb>>Лучше скажите, зачем в C++ назвали unordered map, а не hashmap? Короче же пишется. Или это типа с завязкой на будущие 100500 лет, если вдруг кто-то изобретёт алгоритм круче хешмапа? По-моему это уже какая-то абстракция головного мозга. С сортом то же самое. Нет бы назвать конкретную сортировку, quicksort, mergesort, timsort и тд.
N>Всё именно так. За тем исключением, что внутри sort лежит 2-3 разных сортировки для разных размеров массива. Оптимизация под абстракцией.
Здравствуйте, Nuzhny, Вы писали:
N>Всё именно так. За тем исключением, что внутри sort лежит 2-3 разных сортировки для разных размеров массива. Оптимизация под абстракцией.
Конкретно в гнусной реализации их две, quick sort и heap sort. Второй включается для сортировки кусков, размер которых (куски, на которые разбивается quick sort-ом) становится меньше некоторго значения.
Здравствуйте, smeeld, Вы писали:
N>>Всё именно так. За тем исключением, что внутри sort лежит 2-3 разных сортировки для разных размеров массива. Оптимизация под абстракцией.
S>Конкретно в гнусной реализации их две, quick sort и heap sort. Второй включается для сортировки кусков, размер которых (куски, на которые разбивается quick sort-ом) становится меньше некоторго значения.
Не так.
Во-первых, их три: quick, heap и insertion. Как раз insertion используется для мелких кусков, но вызывается не на каждый мелкий кусок, а в финальном проходе сразу по всему массиву. То есть они тут экономят на кэше кода за счёт возможного второго некэшированного прохода по всем данным (зато последовательного). За счёт предварительного разделения через quicksort расстояние перемещения в этом проходе ограничено тем самым пределом размера.
Во-вторых, heap используется в случае, когда бюджет рекурсии исчерпан:
/// This is a helper function for the sort routine.template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
while (__last - __first > int(_S_threshold))
{
if (__depth_limit == 0)
{
std::__partial_sort(__first, __last, __last, __comp);
return;
}
--__depth_limit;
_RandomAccessIterator __cut =
std::__unguarded_partition_pivot(__first, __last, __comp);
std::__introsort_loop(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
}
вот этот самый __depth_limit инициализируется в std::__lg(__last — __first) * 2 .
Здравствуйте, Ватакуси, Вы писали:
В>Это жалоба или хвасталка? В>В чём, собственно, проблема?
В>Запоминать порядок вставки нужно, пусть и редко. Кому это мешает?
Вот это вам кажется, что оно "редко" нужно. А ширнармассы кодеров хотят этого всегда, и разработчики под них прогибаются.
В этом и проблема.
Зато штатного аналога <map> нет ни в JS, ни в Python. И это вторая проблема.
Можно подключить внешнюю библиотеку, но хипстеры берут сразу sqlite.
Здравствуйте, sergii.p, Вы писали:
SP>не ясно что нужно: шашечки, или ехать? Если сравнивать по порядку поступления, то можно использовать std::list<std::pair> (а можно и std::vector); если нужна скорость поиска — std::unordered_map. Упомянутый всуе LinkedHashMap использует под капотом оба контейнера (и места занимает соответственно).
One surprising part is that the new design, besides being more memory efficient, is ordered by design: it preserves the insertion order. This is not forbidden by the Python language, which allows any order. It makes the collections.OrderedDict subclass much faster than before: it is now a thin subclass of dict.
Старый дизайн тоже был не худшим. Так что они и на месте сэкономили.
SP>А вообще, думаю сравнивать в тестах по порядку вставки — идея так себе. Нужно соблюдать порядок в двух местах. Поменялся порядок формирования элементов — тесты отвалились. Поэтому, как уже было упомянуто, можно реализовать сравнение коллекций (благо, в случае std::unordered_map, это не так сильно ударит по производительности) и не быть хипстером
