- 1
- 2
- 3
- 4
- 5
var lst = new List<string>();
foreach (String parameterName in parameters.Keys) // parameters это Dictionary<String, Object>
{
lst.Add(parameterName + ": " + parameters[parameterName].ToString());
}-
C# / Говнокод #18452
+145
Долгий вариант перебора словаря: перебор ключей в цикле и на каждой итерации получение по ключу значения из словаря
Запостил:
vldalx,
08 Июля 2015
Follow us!
а если и дальше говорить о производительности, то простое сцепление строк, через + или string.concat работает быстрее чем string.Format
единственный плюс string.Format это читаемость
Значит поиск по ключу в хешталице - это медленно, а переливать из одной коллекции в другую - это норма?
Вот такой вариант намного эффективнее:
var lst = new List<string>();
foreach (var parameter in parameters)
{
lst.Add(parameter.Key + ": " + parameter.Value.ToString());
}
более того, в первоначальном варианте, скорость доступа по ключу к элементу словаря колеблется от того, какие строки (т.е. что они из себя представляют) используются в качестве ключа.
>> Автор этого кода видимо тоже с трудом представляет что это такое.
Куда уж нам, о Великий!
Правда, что она бывает ло-ка-ри-фми-чис-кая?
Жаль, что вы не видите, или не хотите видеть, разницу между двумя кусками кода.
Не надо так.
Тут большинство прекрасно понимает что такое сложность и в чем разница между двумя вариантами
Извиняюсь перед bormand.
Судя по минусам к коду, когда еще не было никаких комментариев, то не все всё понимают.
Добро пожаловать в реальный мир на говнокод
А вы?
Я лично вижу, что оба вариант работают за O(n), где n - размер словаря. Правда, в топике - амортизированное O(n), а в вашем варианте - гарантированное.
Все зависит от количества коллизий при инициализации словаря.
ОООО!!!
Разумеется. Возможность запоминать информацию тебя удивляет?
Строить map как вырожденное в список дерево.
Или попробовать как-то обмануть HashMap.
Они стандартные?
>Посмотрев на реализацию хэша в стд-либе и подобрав коллизии?
На чужой машине это с некоторого времени не работает, на своей - но зачем?
Ключём в словаре может быть любой тип. Эффективноть работы словаря зависит от качества хэш-функции для типа-ключа, который может быть определён пользователем.
В первых версиях jdk была кривая хэш-функция для строк, просматривавшая не всю строку. Из-за этого для некоторых входов (например, доменных имён), было дикое кол-во коллизий.
>foreach (String parameterName in parameters.Keys)
www, перелогинься.
Для строк хешкод стандартный.
> где-то сохранены
Флаг в каком-то виде всяко есть (возможно неявный, в виде какого-нибудь null'а). Иначе поиск и вставку не реализовать.
Вот так в жабе реализован обход мапы.
>openjdk
Ты опять?
Там Entry[], а Entry в добавок хранит ссылку на next. Т.е. в хешмепе параллельно хранится список ключей/значений? Оригинально.
P.S. По существу вопросы будут?
Опять выходишь на связь? Опять называешь openjdk жавой?
Так они решают проблему с коллизиями хеша - Entry с одинаковым хешем будут лежать в виде связного списка.
Ваш кэп.
P.S. Ну по коду же всё видно...
IDE НЕ ПОДСВЕЧИВАЕТ (tm)
Иди уже поучи матчасть, не позорься.
Почитай реализацию get() что ли...
Для поиска см. выше.
Для итерации - да, пробегаем все слоты. Твоя проблема возникнет только в одном случае - если навставлять миллион элементов и погрохать почти все, причем табличка должна не уметь сжиматься (жабья, как я понимаю, как раз не умеет).
Приведи пример практического сценария, когда это произойдёт.
Для этого даже образования не надо, лишь чуточку ума.
Пробегаешь по всему массиву бакетов, в каждом бакете посещаешь список пар ключ-значение. Итератору достаточно хранить указатель на текущий бакет и текущую позицию в массиве бакетов.
Конкурентные модификации хэш-таблицы в жаве запрещаются.
Который с дырками?
Да, и что, в чём проблема?
Просто скипаешь все дырки, там нулевые укатели. На каждом next() надо бежать до следующего непустого.
В том, что у тебя на мегабайт может быть одно место? И тогда хуй тебе, а не O(количество элементов)
И что? Хорошая табличка должна расти с увеличением числа записей, чтобы кол-во бакетов было всегда порядка O(n) от n записей. Поэтому в худшем случае вся итерация в сумме будет работать O(n).
Если планируется удалять много записей, нужна табичка, которая шринкается при низком load factor.
Ты понял, что за хуйню ты сморозил? В O сокращается множитель. Нет, ну O(количество записей) то останется, но множитель может быть неприятным.
А вдруг таблицы которые в языках - плохие?
> множитель может быть неприятным
Ну ты и лалка. Почитай про load factor чтоли.
Специально открыл первую статью на вики - даже там про это написано.
Раз думать тебя так и не научили.
В крестах (gcc) unordered_map тоже не шринкается. Шарповый Generic.Dictionary тоже.
Что даёт на O(N) на итерацию, где N - максимальный размеров словаря, наблюдаемый за время его существования. Если предположить, что элементы удаляются не сильно чаще, чем добавляются, то получаем эффективное O(n) с константой порядка 2-4.
Видимо, шринк - настолько редкое требование, что его никто не делает из коробки.
Пистоний словарь вроде как может ресайзиться в меньшую сторону, но в коде удаления элементов я этого не нашёл.
Те, у кого сильно специфический ворклоад, вполне могут позволить себе запилить эвристический шринк, чтобы отвязаться от N.
Да и кому надо сам напишет
Проблемы нет, просто не нужно
координаты GPS дай
Ум - он скорбь приумножает. Наверное иногда хочется отупеть как сема, вот и несу херню
>похороним
т.е. Ты настолько пидар, что если kegdan приедет тебя пиздить ты обосрешься выйти один.
У меня будет, лалка. Мне не составляет никакого труда реализовать хэш-таблицу, которая будет гарантировать O(n) итерацию.
То, что дефолтная жаба делает что-то определённым образом не означает, что что-то невозможно.
Кроме того, жабий HashMap поддерживает keySet() которая позволяет быстро обходить только ключи и лукапить значения по ключу, если уж есть сценарий с массовым удалением.
>позволяет быстро обходить только ключи
И как она это делает? Отдельно хранит ключи?
В шарповском словаре помимо бакетов есть тупо линейный список контейнеров, в котором лежит хеш, номер следующего (если есть), ключ и значения. Просто по нему пробегаешь и достаешь что хочешь.
Может я в терминологии путаюсь, но вроде как словарь в шарпе - это и есть хэш-таблица
Нет, а что это?
> Автор этого кода...
...раньше однозначно писал на js (или perl'е?). Ну просто я не помню других языков, где кроме идиомы из топика ничего не работает.
> намного эффективнее
Ну не так уж намного. В общем-то в типичной прикладнухе разницу и не заметить.
Мой суррогатный тестовый код
https://ideone.com/kXelZy
скрины профилировщика ннадо?
Ух ты, сисярп умеет в foreach по словарю?
> for (int i = 0; i < 10000; i++,key += "1")
Ключи в 10k символов - такой типичный случай? Сделай что-нибудь поумнее.
bormand в http://www.govnokod.ru/18452#comment292495 написал:
>> В общем-то в типичной прикладнухе разницу и не заметить.
3_14dar в http://www.govnokod.ru/18452#comment292502 написал:
>> Ключи в 10k символов - такой типичный случай?
kegdan в http://www.govnokod.ru/18452#comment292500 написал:
>> Мой суррогатный тестовый код
>> Ух ты, сисярп умеет в foreach по словарю?
>> Что значит суррогатный?
3_14dar в http://govnokod.ru/18452#comment292502 написал:
>> Сделай что-нибудь поумнее.
лол
Поддельный тестовый код?
Напугал ежа голой жопой. Т.е. разница только в константе и всего в 2 раза? Причём при диких ключах в ~5000 символов?
Вот когда этот код будет бутылочным горлышком - можно задуматься о профайлере. А до этого в общем-то похуй.
P.S. Но мне вариант с парами больше нравится из-за наглядности.
P.P.S. Попробуй сделать тест на рост сложности - 1к, 10к, 100к.
http://download.hdd.tomsk.ru/preview/waefahjh.jpg
все в миллисекундах
Словарь заполняется вот так