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

Question

Это было бы быстрее, если говорить 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); 

Answer 1

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

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

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

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

Действительно ли это является узким местом для вас?

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

Answer 2

Последний.

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

Answer 3

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

Answer 4

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