Что такое unordered map — пояснять не нужно (кому нужно, закройте дверь с той стороны). У ей внутре неонка хэш-таблица, неважно, какого названия в конкретном месте, какого именно хэша и какого аккредитива addressing. Порядок ключей — не определён, может меняться в зависимости от фазы Луны и погоды на Сатурне, хотя обычно он более предсказуем — где делят хэш на простое число (замучивая процессор тяжёлой операцией деления, как в GCC STL), где доставая младшие биты. Но в любом случае он не фиксирован.
Есть два варианта, как допилить до фиксированного порядка. В одном используется какое-то сравнение ключей по их значению; получаем STLʼный <map> (внутре, обычно, ксенонка красно-чёрное дерево или что-то похожее). Но обидно людям, что O(log N) на одну операцию, всупереч хэшовому O(1), хоть и конкретно амортизированному. Поэтому некий сумрачный гений родил другой вариант: неважно, какие ключи по смыслу, главное, в каком порядке поступили. Не знаю, первой ли была Java, но LinkedHashMap там по жизни. Зато в JavaScript оно везде. Когда из меня хотели сделать вебостроителя (я успешно отбрыкался), я запомнил, что во всех его не-песочных реализациях соблюдается порядок перебора по порядку вставки. В ES6 это ещё и формализовали для Map, хотя и без него порядок соблюдается. (И на кой им ещё один Map такой же, как изначальный map? Будем считать, что тут так принято.)
Здравствуйте, 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 .
Здравствуйте, smeeld, Вы писали:
S>Дык, и я о том же:
НЕТ
S>sort -> introsort_loop -> partial_sort -> heap_sort. Так это устроено. heap_sort вызывается в partial_sort, которая вызывается в introsort_loop когда размер массива, куска на которые разбиваемся в introsort_loop становится меньше некоторого значения. То есть, тут типичный quick sort, реализованный в цикле introsort_loop, и heap sort, которому передаётся управление тогда, когда размер разбиваемого куска станет достаточно малым.
*Откуда* утверждение про размер??? Читаем C++ по фоновому:
__depth_limit это не размер, это параметр, который уменьшается на 1 с каждым рекурсивным вызовом функции самой себя. И если рекурсия зашла слишком глубоко (а размер при этом, наоборот, больше, чем ожидался!) — то тут и включается __partial_sort.
S> То есть, алгоритм quick sort дробит на куски, а куски сортируются heap sort-ом. Где тут какое-то insertion, не понятно.
В __introsort_loop первая строка тела:
while (__last - __first > int(_S_threshold))
то есть если мы попали на начало итерации цикла, а разница позиций уже меньше _S_threshold, никакая сортировка на этом этапе выполняться не будет. И вот это то, что insertion sort дорабатывает в самом конце.
Здравствуйте, Zhendos, Вы писали:
N>> И знаете, я их понимаю. Потому что когда в тесте надо сравнивать
Z>А я не очень, в чем проблема написать универсальную функцию сравнения двух dictionary/map?
Потому что оно прошло через отдельного участника, который уже экспортнул в текст, а проверяется вся цепочка.
Здравствуйте, smeeld, Вы писали:
S> heap_sort вызывается в partial_sort, которая вызывается в introsort_loop когда размер массива, куска на которые разбиваемся в introsort_loop становится меньше некоторого значения.
Неверно. Нет такого.
Выше уже была приведена ссылка с кодом: http://rsdn.org/forum/flame.comp/7349517.1
Видно, что heap_sort как раз не вызывается при нормальном сценарии (а вызывается только если лимит глубины исчерпан, но это редкая ситуация, и ожидается, что при сортировке она вероятно не произойдёт).
Рандомизировали не от веселья, а вероятно потому, что можно устроить DoS с помощью Hash Collision Complexity Attack, упорядоченный словарь выдаёт атакующему информацию о хэширующей функции.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, netch80, Вы писали:
N>>Именно что есть говорить именно потому, что в документации ничего не обещалось. N>>Но вы и не пытались подумать.
PD>О чем подумать-то ? Зачем в JS они так сделали ? Я же ответил — видимо, посчитали что для задач, решаемых там так лучше.
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 полез, это уже его проблемы.
Здравствуйте, 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-ом) становится меньше некоторго значения.
Здравствуйте, Ватакуси, Вы писали:
В>Это жалоба или хвасталка? В>В чём, собственно, проблема?
В>Запоминать порядок вставки нужно, пусть и редко. Кому это мешает?
Вот это вам кажется, что оно "редко" нужно. А ширнармассы кодеров хотят этого всегда, и разработчики под них прогибаются.
В этом и проблема.
Зато штатного аналога <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, это не так сильно ударит по производительности) и не быть хипстером
Здравствуйте, netch80, Вы писали:
N>Здравствуйте, smeeld, Вы писали:
N>Не так.
N>Во-первых, их три: quick, heap и insertion. Как раз insertion используется для мелких кусков, но вызывается не на каждый мелкий кусок, а в финальном проходе сразу по всему массиву. То есть они тут экономят на кэше кода за счёт возможного второго некэшированного прохода по всем данным (зато последовательного). За счёт предварительного разделения через quicksort расстояние перемещения в этом проходе ограничено тем самым пределом размера.
Что за insertion тут у Вас? Тут introsort_loop- который воплощает quick sort, и partial_sort, который есть heap sort
Здравствуйте, smeeld, Вы писали:
N>>Во-первых, их три: quick, heap и insertion. Как раз insertion используется для мелких кусков, но вызывается не на каждый мелкий кусок, а в финальном проходе сразу по всему массиву. То есть они тут экономят на кэше кода за счёт возможного второго некэшированного прохода по всем данным (зато последовательного). За счёт предварительного разделения через quicksort расстояние перемещения в этом проходе ограничено тем самым пределом размера.
S>Что за insertion тут у Вас? Тут introsort_loop- который воплощает quick sort, и partial_sort, который есть heap sort
Я привёл код ко второму утверждению, а не к первому. К первому вот этот кусок имеет отношение — реализация всей std::sort() (если непонятно, я вслед за контекстом говорю именно о ней, а не о std::partial_sort, которая вообще никак раньше не вспоминалась):
Здравствуйте, netch80, Вы писали:
N>Здравствуйте, smeeld, Вы писали:
N>>>Во-первых, их три: quick, heap и insertion. Как раз insertion используется для мелких кусков, но вызывается не на каждый мелкий кусок, а в финальном проходе сразу по всему массиву. То есть они тут экономят на кэше кода за счёт возможного второго некэшированного прохода по всем данным (зато последовательного). За счёт предварительного разделения через quicksort расстояние перемещения в этом проходе ограничено тем самым пределом размера.
S>>Что за insertion тут у Вас? Тут introsort_loop- который воплощает quick sort, и partial_sort, который есть heap sort
N>Я привёл код ко второму утверждению, а не к первому. К первому вот этот кусок имеет отношение — реализация всей std::sort() (если непонятно, я вслед за контекстом говорю именно о ней, а не о std::partial_sort, которая вообще никак раньше не вспоминалась):
N>
sort -> introsort_loop -> partial_sort -> heap_sort. Так это устроено. heap_sort вызывается в partial_sort, которая вызывается в introsort_loop когда размер массива, куска на которые разбиваемся в introsort_loop становится меньше некоторого значения. То есть, тут типичный quick sort, реализованный в цикле introsort_loop, и heap sort, которому передаётся управление тогда, когда размер разбиваемого куска станет достаточно малым. То есть, алгоритм quick sort дробит на куски, а куски сортируются heap sort-ом. Где тут какое-то insertion, не понятно.
W>Видно, что heap_sort как раз не вызывается при нормальном сценарии (а вызывается только если лимит глубины исчерпан, но это редкая ситуация, и ожидается, что при сортировке она вероятно не произойдёт).
Это всегда происходит, когда исходный массив "большой".
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, smeeld, Вы писали:
S>> heap_sort вызывается в partial_sort, которая вызывается в introsort_loop когда размер массива, куска на которые разбиваемся в introsort_loop становится меньше некоторого значения. W>Неверно. Нет такого. W>Выше уже была приведена ссылка с кодом: http://rsdn.org/forum/flame.comp/7349517.1
W>Видно, что heap_sort как раз не вызывается при нормальном сценарии (а вызывается только если лимит глубины исчерпан, но это редкая ситуация, и ожидается, что при сортировке она вероятно не произойдёт).
В смысле, тот самый счётчик глубины отражает размер куска.
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, smeeld, Вы писали:
S>> heap_sort вызывается в partial_sort, которая вызывается в introsort_loop когда размер массива, куска на которые разбиваемся в introsort_loop становится меньше некоторого значения. W>Неверно. Нет такого. W>Выше уже была приведена ссылка с кодом: http://rsdn.org/forum/flame.comp/7349517.1
W>Видно, что heap_sort как раз не вызывается при нормальном сценарии (а вызывается только если лимит глубины исчерпан, но это редкая ситуация, и ожидается, что при сортировке она вероятно не произойдёт).
В смысле 2: если бы не было счётчика глубины, то мы в дроблении доходили бы до размера кусков в один-два элемента, которые бы свопились. С счётчиком мы доходим до размера куска, определяемого величиной счётчика (чем больше счётчик тем меньше возможен размер куска) после чего на куске запускается heap sort.
W>>Видно, что heap_sort как раз не вызывается при нормальном сценарии (а вызывается только если лимит глубины исчерпан, но это редкая ситуация, и ожидается, что при сортировке она вероятно не произойдёт).
S>В смысле, тот самый счётчик глубины отражает размер куска.
Он отражает его _наоборот_.
Достижение случая __depth_limit == 0 возможно, если падение длины куска сильно меньше, чем хотелось.
В идеале (каждое деление строго пополам) это невозможно, потому что начальное значение __depth_limit равно log2(size)*2, а при идеальном делении глубина рекурсии не превысит log2(size).
Достижение __depth_limit == 0 возможно только если все деления "по дороге" оказались в среднем (геометрическом) хуже, чем 2.41:1 (2.41 = sqrt(2)/(1-sqrt(2))).
Здравствуйте, smeeld, Вы писали:
W>>Видно, что heap_sort как раз не вызывается при нормальном сценарии (а вызывается только если лимит глубины исчерпан, но это редкая ситуация, и ожидается, что при сортировке она вероятно не произойдёт).
S>Это всегда происходит, когда исходный массив "большой".
Нет. Это происходит только при цепочке достаточно неоптимальных разбиений. Если все разбиения достаточно неплохи, то оно никогда в heapsort не скатывается.
Здравствуйте, smeeld, Вы писали:
N>>*Откуда* утверждение про размер??? Читаем C++ по фоновому:
S>Выше про отражение счётчиком минимального размера куска, на которые можем разбиваться в рекурсии intrsort_loop
Вы писали:
>> heap_sort вызывается в partial_sort, которая вызывается в introsort_loop когда размер массива, куска на которые разбиваемся в introsort_loop становится меньше некоторого значения.
Так вот — нет никакого правила "partial_sort вызывается, когда размер куска становится меньше некоторого значения".
При этом вообще ничего не вызывается в цикле до финального прохода insertion.
Здравствуйте, smeeld, Вы писали:
N>>Он отражает его _наоборот_.
S>Да, и в треде об этом написал, хотя, это уже и не важно как именно он отражает.
Важно, если мы говорим о том, при каких условиях и с какими размерами зовётся heapsort.
Она никогда не будет вызвана при размерах не более _S_threshold. Только при бо́льших, а в типичном случае — заметно бо́льших.
Иначе и смысла нет.
В>>Это жалоба или хвасталка? В>>В чём, собственно, проблема?
В>>Запоминать порядок вставки нужно, пусть и редко. Кому это мешает?
N>Вот это вам кажется, что оно "редко" нужно. А ширнармассы кодеров хотят этого всегда, и разработчики под них прогибаются. N>В этом и проблема.
OrderedDict встречается очень редко и в сторонних библиотеках и в тех местах, где я работал.
Есть ещё SortedDict, но это вообще экзотика.
N>Зато штатного аналога <map> нет ни в JS, ни в Python. И это вторая проблема.
Ни разу не видел, где бы он (аналог) понадобился бы. Можно пример?
Зато пока в C++ не ввели unordered_map было скучно на огромных объёмах данных.
N>Можно подключить внешнюю библиотеку, но хипстеры берут сразу sqlite.
Может лучше сразу redis?
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.
Эта цитата из pypy.
А в CPython пишут, что мол это "implementation details", которые вполне могут и поменяться в будущем.
Здравствуйте, Ватакуси, Вы писали:
N>>А вот читаем по ссылке отсюда:
N>>
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.
В>Эта цитата из pypy.
С каких это пор официальная документация CPython стала "цитата из pypy"??
В>А в CPython пишут, что мол это "implementation details", которые вполне могут и поменяться в будущем.
Если речь именно про порядок перебора, то в 3.7 его стандартизовали:
the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec.
Ну и вряд ли будут в будущем менять реализацию на менее эффективную, ящетаю (tm)
В>>Эта цитата из pypy.
N>С каких это пор официальная документация CPython стала "цитата из pypy"?? https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html
В>>А в CPython пишут, что мол это "implementation details", которые вполне могут и поменяться в будущем.
N>Если речь именно про порядок перебора, то в 3.7 его стандартизовали:
Твоя ссылка вела на 3.6, а там написано именно то, что я и сказал.
N>
the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec.
Здравствуйте, Ватакуси, Вы писали:
В>>>А в CPython пишут, что мол это "implementation details", которые вполне могут и поменяться в будущем. N>>Если речь именно про порядок перебора, то в 3.7 его стандартизовали: В>Твоя ссылка вела на 3.6, а там написано именно то, что я и сказал.
Что в 3.7 его закрепили формально, я написал в первом письме темы.
N>>
the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec.
N>>Ну и вряд ли будут в будущем менять реализацию на менее эффективную, ящетаю (tm) В>Меняли и не раз уже.
Я бы только ещё добавил, что
1) начиная с 3.6 эта рандомизация всё равно есть для собственно распределения в хэше по корзинам, но за счёт insertion order это перестало быть открыто видно;
2) в некоторых местах используются альтернативные подходы — в Java 8 переполненные корзины получают, по сути, вложенный TreeMap.
Здравствуйте, vsb, Вы писали:
vsb>Лучше скажите, зачем в C++ назвали unordered map, а не hashmap?
Почему вы вообще эти два понятия смешиваете? Первое про контракт, второе про реализацию. Соотв. абстрактный интерфейс надо называть первым, а конкретный класс-реализацию вторым.
Здравствуйте, Ватакуси, Вы писали:
В>>>Запоминать порядок вставки нужно, пусть и редко. Кому это мешает? N>>Вот это вам кажется, что оно "редко" нужно. А ширнармассы кодеров хотят этого всегда, и разработчики под них прогибаются. N>>В этом и проблема. В>OrderedDict встречается очень редко и в сторонних библиотеках и в тех местах, где я работал.
Ну теперь будет чаще.
Ну очень многим нравится, что нет странных шатаний порядка там, где они не ожидают, и можно визуально сравнить, например, два jsonʼовых выхлопа.
N>>Зато штатного аналога <map> нет ни в JS, ни в Python. И это вторая проблема. В>Ни разу не видел, где бы он (аналог) понадобился бы. Можно пример?
NDA. Но один из примеров можно описать так: некий набор сущностей имеет упорядочение по временны́м меткам, и нужно иметь возможность быстро выцепить последовательность сущностей в обе стороны от конкретной метки.
В>Зато пока в C++ не ввели unordered_map было скучно на огромных объёмах данных.
Теперь мне уже непонятно. Разница в log(N) настолько критична?
N>>Можно подключить внешнюю библиотеку, но хипстеры берут сразу sqlite. В>Может лучше сразу redis?
Здравствуйте, netch80, Вы писали:
>Поэтому некий сумрачный гений родил другой вариант: неважно, какие ключи по смыслу, главное, в каком порядке поступили.
Если в задаче именно это главное, то тебе не нужен TreeMap , а и впрямь нужен LinkedHashMap. TreeMap попросту не для этого — он для того, чтобы, потеряв (по сравнению с HashMap) в производительности, получить упорядоченность именно по самим ключам, а не по порядку их поступления. Это дает ряд дополнительных возможностей, например, быстро получить наименьшее (наибольшее) значение ключа, или несколько наименьших (наибольших) или вообще кусок мэпа "от-до", да и просто обеспечение того, что при проходе по мэпу мы будем иметь ключи в порядке Comparator, а не в порядке фаз Луны или погоды на Сатурне.
В общем, это просто разные вещи, у каждой свое назначение.
Здравствуйте, Pavel Dvorkin, Вы писали:
>>Поэтому некий сумрачный гений родил другой вариант: неважно, какие ключи по смыслу, главное, в каком порядке поступили. PD>Если в задаче именно это главное, то тебе не нужен TreeMap , а и впрямь нужен LinkedHashMap.
[...]
Скажите, пожалуйста, почему происходит такое. Вот я запускаю nodejs и вижу:
> a = {}
{}
> a.foo = 1
1
> a.bar = 2
2
> a
{ foo: 1, bar: 2 }
> delete a.foo
true
> a
{ bar: 2 }
> a.foo = 1
1
> a
{ bar: 2, foo: 1 }
То же самое в Firefox, в Chrome. Какую задачу они они этим решают?
PD>В общем, это просто разные вещи, у каждой свое назначение.
Так вот — какое именно назначение у JS object, что он ведёт себя так?
Здравствуйте, netch80, Вы писали:
N>Скажите, пожалуйста, почему происходит такое. Вот я запускаю nodejs и вижу:
<skipped>
А собственно говоря, что происходит-то ? Я вообще не вижу, что происходит. Ну оказываются они в другом порядке напечатаны, и что из этого следует ? Там по документации (я не специалист в node) что-то вообще обещается в плане прохода по сету ? (В HashSet вообще ничего не обещается) Если нет, то вообще говорить не о чем. А если да, значит, там LinkedHashSet
N>Какую задачу они они этим решают?
Не знаю. Видимо, они посчитали, что LinkedHashSet (назовем так) лучше. Но что из этого следует в плане того, о чем я писал ?
Здравствуйте, Pavel Dvorkin, Вы писали:
N>>Какую задачу они они этим решают? PD>Не знаю.
Таки зря я вычеркнул из предыдущего комментария пассаж про бессмысленное кэпство. Глядишь, сэкономил бы пару килобайт RSDNʼу.
PD>Там по документации (я не специалист в node) что-то вообще обещается в плане прохода по сету ? (В HashSet вообще ничего не обещается) Если нет, то вообще говорить не о чем.
Именно что есть говорить именно потому, что в документации ничего не обещалось.
Но вы и не пытались подумать.
Здравствуйте, Ikemefula, Вы писали:
N>>То же самое в Firefox, в Chrome. N>>Какую задачу они они этим решают?
I>Это старая особенность и сейчас это обратная совместимость.
Ну вот ты думаешь, что это обратная совместимость.
А я предполагаю, наблюдая новые тенденции, что это какой-то фактор, который действует и сейчас.
I>Какую задачу решали — возможно удобство девелоперов, для работы с джсонон. Много воды утекло и вряд ли сохранились те, кто это делал.
Вот именно — удобство девелоперов. Но это очевидный вариант (для того, кто хоть раз сравнивал глазами выдачу двух простыней параметров хотя бы в один экран).
I>https://bugs.chromium.org/p/v8/issues/detail?id=164
Да, интересно. Что у nodejs между ключами, которые целое число (пусть даже в текстовом виде), порядок числовой, а не по истории вставки — я замечал, но не счёл нужным это выносить на обобщение.
Для тех, которые слова, типа foo, bar — сохраняется порядок вставки.
NodeJS вроде на том же варианте V8, что и хром? Тогда и на него это действует. Но это уже за пределами обсуждаемого.
Этот тикет хрома от 2011. Что порядок вставки сохраняется в основных движках — мне утверждали в 2015. В тикете говорят, что это ломали во всех браузерах.
>> In web development, we have learned NOT to rely on standards,
>> Let's get real! This discussion is all about high-and-mighty "good coders" finally getting a chance to take a shit on the heads of the "bad coders".
>> For the record, the ECMAScript 2015 language specification clearly defines object property iteration order:
Оп-паньки! Раньше я знал только про Map, но не Object.
vsb>А namespace на что? Непонятно. Если кто-то в std полез, это уже его проблемы.
Вроде бы у STLport есть реализация hash_map, т.е. она предоставляла все что дает std по стандарту, плюс еще некоторые штуку вроде hash_map в std. STLport могла много где использоваться где родная STL была более убогая.
