List.BinarySearch vs Dictionary.TryGetValue - что быстрее

Что было бы быстрее, скажем, 500 элементов.

Или какова более быстрая структура данных / сбор данных для извлечения элементов?

        List<MyObj> myObjs = new List<MyObj>();
        int i = myObjs.BinarySearch(myObjsToFind);
        MyObj obj = myObjs[i];

Или

        Dictionary<MyObj, MyObj> myObjss = new Dictionary<MyObj, MyObj>();
        MyObj value;
        myObjss.TryGetValue(myObjsToFind, out value);
2 c#
11.12.2008 11:47:57
4 ОТВЕТА

Я предполагаю, что в вашем реальном коде вы на самом деле заполнили бы myObjs - и отсортировали его.

Вы только что попробовали это? Это будет зависеть от нескольких факторов:

  • Вам нужно отсортировать список по любой другой причине?
  • Как быстро MyObj.CompareTo (MyObj)?
  • Насколько быстро MyObj.GetHashCode ()?
  • Как быстро MyObj.Equals ()?
  • Насколько вероятно, что вы получите коллизии хешей?
  • Это на самом деле имеет для вас существенное значение?

В случае двоичного поиска потребуется около 8 или 9 сравнений с одним вызовом GetHashCode и некоторым количеством вызовов Equals (в зависимости от коллизий хешей) в случае словаря. Затем в обоих случаях используются внутренние вычисления (доступ к массивам и т. Д.).

Это действительно узкое место для вас, хотя?

Я бы ожидать словарь будет немного быстрее на 500 элементов, но не очень значительно быстрее. По мере роста коллекции разница, очевидно, будет расти.

9
11.12.2008 11:54:34

Последний.

Бинарный поиск выполняется в O (log n), а хеш-таблица будет O (1).

1
11.12.2008 11:54:35
Это не гарантирует, что это будет быстрее, хотя. Это гарантирует, что это будет быстрее, когда n достаточно велико, но могут быть задействованы огромные постоянные факторы. Предположим, что Словарь всегда занимает 1 секунду, а список занимает 1 мс * log (n). Список победит надолго. Я не говорю, что это происходит (продолжение)
Jon Skeet 11.12.2008 11:57:42
просто ваше второе утверждение не доказывает ваше первое. На самом деле я не знаю, где находится точка отсечения для списка / словаря, и это будет зависеть от стоимости других факторов (сравнение с хэш-кодом и т. Д.). Я подозреваю , что на 500 элементов словаря будет выиграть. Я не хотел бы говорить без тестирования, хотя.
Jon Skeet 11.12.2008 11:58:36
IIRC, они рекомендуют словарь для чего-либо больше, чем 10 пунктов.
Joel Coehoorn 11.12.2008 13:54:43

BinarySearch требует, чтобы список уже был отсортирован. [править: Забыл, что словарь является хеш-таблицей. Итак, поиск - это O (1)]. 2 не совсем то же самое. Первый действительно проверяет, существует ли он в списке и где он находится. Если вы хотите просто проверить существование в словаре, используйте метод содержимого.

0
11.12.2008 11:57:42

Большая нотация «О», используемая некоторыми комментаторами, является отличным руководством для использования. На практике, однако, единственный способ убедиться, какой путь быстрее в конкретной ситуации, - это рассчитать время своего собственного кода до и после изменения (как намекал Джон).

1
11.12.2008 16:13:44