Здравствуйте, Аноним, Вы писали:
А>Кэп подсказывал что SortedDictionary должен быстрее осуществлять поиск элемента по ключу, т.к. по нему осуществляется сортировка. А>Получается что обычный Dictionary раз в 10 быстрее как на добавление , так и на поиск по ключу. В чем преимущество SortedDictionary тогда ?
Dictionary — хеш-таблица со средним временем поиска O(1), SortedDictionary — красно-черное дерево со средним временем поиска O(log N).
Обобщенно рассуждая, я бы сказал, что SortedDictionary медленнее потому, что оно накладывает более сильное ограничение на множество — требует упорядоченности.
А>В чем преимущество SortedDictionary тогда ?
Кэп подсказывает нам, что преимущество SortedDictionary в том, что оно сортированное.
Здравствуйте, Аноним, Вы писали:
А>Кэп подсказывал что SortedDictionary должен быстрее осуществлять поиск элемента по ключу, т.к. по нему осуществляется сортировка.
У вас какой-то неправильный кэп. Поиск в хэш-таблице всегда быстрее, чем в отсортированной коллекции.
А>Получается что обычный Dictionary раз в 10 быстрее как на добавление , так и на поиск по ключу. В чем преимущество SortedDictionary тогда ?
Преимущество в том, что он хранит ключи в отсортированном порядке и если часто нужно будет выводить значения в этом порядке, то это дбудет гораздо быстрее, чем сортировать их каждый раз.
Здравствуйте, Kerbadun, Вы писали:
А>>В чем преимущество SortedDictionary тогда ?
K>Кэп подсказывает нам, что преимущество SortedDictionary в том, что оно сортированное. K>
Это конечно здорово , только зачем нам сортировка ради сортировки ?
Обычно сортировка используется чтобы потом можно было элемент найти быстрее, а тут на порядок медленее.
Переформулирую — в чем тогда преимущество Red-Black-Tree перед хеш таблицей
Здравствуйте, Аноним, Вы писали:
А>Это конечно здорово , только зачем нам сортировка ради сортировки ? А>Обычно сортировка используется чтобы потом можно было элемент найти быстрее, а тут на порядок медленее.
Сортировка используется еще и тогда, когда по каким-то причинам нужны данных в отсортированном виде. (c) Кэп.
Здравствуйте, Lloyd, Вы писали:
L>Преимущество в том, что он хранит ключи в отсортированном порядке и если часто нужно будет выводить значения в этом порядке, то это дбудет гораздо быстрее, чем сортировать их каждый раз.
Преимущество в том, что вставка в SortedDictionary всегда занимает (асимптотически) одно и то же время — O(log n).
В (Hash)Dictionary вставка в основном производится за константное время, но в некоторые моменты происходит перестройка хэш-таблицы за линейное время (когда отношение количества элементов к количеству бакетов превышает порог).
Здравствуйте, Аноним, Вы писали:
А>Это конечно здорово , только зачем нам сортировка ради сортировки ? А>Обычно сортировка используется чтобы потом можно было элемент найти быстрее, а тут на порядок медленее. А>Переформулирую — в чем тогда преимущество Red-Black-Tree перед хеш таблицей
1) Оно всегда в отсортированном состоянии, даже после добавления элементов, и можно его в этом отсортированном состоянии куда-нибудь вывести, распечатать, скопировать, обработать без дополнительных затрат;
2) У хеш-таблиц среднее время поиска O(1), но худшее O(N) — при плохой хеш-функции или определенном сочетании элементов множества, в то время как у красно-черного дерева — время поиска гарантированно не больше 2 * log N.
3) Хеш-таблица позволяет искать данные лишь при равенстве ключей, в то время как дерево позволяет искать ближайшие значения и диапазоны значений по неравенствам;
4) Хеш-таблица требует вычисления хеша, что не всегда возможно или имеет смысл, например, для поиска попадания значения в диапазон;
5) Рост хеш-таблицы (изменение размера) при неблагоприятных сценариях может происходить очень медленно, в то время как скорость добавления элемента в дерево ограничена тем же O(log N).
Здравствуйте, stele, Вы писали:
S>А что помешало использовать для измерения интервала специально для этого предназначенный Stopwatch, а не песочные часы DateTime.Now?
Ваш пост несомненно отвечает на все вопросы, сформулированные автором.
Здравствуйте, stele, Вы писали:
S>А что помешало использовать для измерения интервала специально для этого предназначенный Stopwatch, а не песочные часы DateTime.Now?
Да смысл в стопвочах, лишний uses тащить еще вызовы start(); stop(); прописывать — datetime лишен этих недостатков.
var s = DateTime.Now;
...
Console.WriteLine( " ... {0}", DateTime.Now - s);
vs
uses System.Diagnosting;
var s = new Stopwatch();
s.Start();
...
s.Stop();
Console.WriteLine( " ... {0}", s.Elapsed );
Здравствуйте, stele, Вы писали:
S>А ты поробуй, результат тебя порадует.
Попробовал .. вместо 0.9 — 0.87 ..т.е. гдето 3% разница.
Ты хотел сказать что оно точнее ? Возможно. Но в данном случае для сравнения порядков такая точность не нужна.
В любом случае спасибо что обратил внимание
Здравствуйте, Аноним, Вы писали:
S>>>Лишняя-то лишь одна получается
H>>Вообще разницы нет
H>>var s = System.Diagnostics.Stopwatch.StartNew();
H>>...
H>>Console.WriteLine( " ... {0}", s.Elapsed);
А>Ок. Убедили !
Не в том вы видите красоту, не в количестве строк правда. Юзинг надо отдельно описывать. И .Stop() перед .Elapsed вызывать.
А>Но меня вот последнее время заботит вопрос как от лишних строк избавится здесь : http://www.rsdn.ru/forum/dotnet/4107202.1.aspx
А за вызов .ToList() только ради того, что бы получить доступ к .ForEach() надо канделябром Индекс текущей записи в .Select нужно узнавать не посредством вшешнего счётчика, а с помощью соответствующей перегрузки
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, _FRED_, Вы писали:
_FR>И .Stop() перед .Elapsed вызывать.
Это имеет смысл если
а) между точкой где нужно остановить таймер и точкой использования Elapsed выполняется некий код, который может повлиять на замер. В данном случае имхо можно пренебречь... А вот если бы строка форматирования доставалась из ресурса — тогда Stop бы не помешал.
б) Elapsed используется повторно. Тогда у неостановленного таймера показания Elapsed могут отличаться.
Т.е. в данном конкретном случае Stop можно и не вызывать