Который быстрее для нахождения объекта в хеш-таблице или в отсортированном списке?
Я только что создал образец, вы можете сделать это следующим образом
Form2 form2 = new Form2();
DataGridViewRow row = this.dataGridView1.Rows[e.RowIndex];
//populate the textbox from specific value of the coordinates of column and row.
form2.label1.Text = row.Cells[0].Value.ToString();
form2.Show();
В Form2.Designer вы переходите от частного к общему
public System.Windows.Forms.Label label1;
7 ответов
Сложность алгоритма - это хорошая вещь, которую нужно знать, а хэш-таблицы, как известно, составляют O (1) , а отсортированный вектор (в вашем случае, я думаю, лучше использовать отсортированный массив, чем список) предоставит время доступа O (log n) .
Но вы должны знать, что обозначение сложности дает вам время доступа для N, идущего до бесконечности. Это означает, что если вы знаете, что ваши данные будут продолжать расти , обозначение сложности даст вам некоторую подсказку по выбору алгоритма.
Когда вы знаете, что ваши данные будут иметь довольно небольшую длину: например, имея только несколько записей в вашем массиве / хэш-таблице, вы должны взять с собой часы и измерить. Так что проведите тест.
Например, в другой задаче: сортировка массива. Для несколько записей пузырьковая сортировка, в то время как O (N ^ 2) может быть быстрее, чем .. быстрая сортировка, а это O (n log n) .
Кроме того, в соответствии с другими ответами и в зависимости от вашего элемента вы должны попытаться найти лучшую хеш-функцию для вашего экземпляра хеш-таблицы. В противном случае это может привести к резкому снижению производительности поиска в вашей хеш-таблице (как указано в ответе Хэнка Гэя).
Изменить: прочтите эту статью, чтобы понять значение нотации Big O .
Если алгоритм хеширования не чрезвычайно медленный (и / или плохой), хеш-таблица будет быстрее.
ОБНОВЛЕНИЕ: Как отметили комментаторы, вы также можете получить снижение производительности из-за слишком большого количества столкновений не потому, что ваш алгоритм хеширования плохой, а просто потому, что хеш-таблица недостаточно велика. Большинство реализаций библиотек (по крайней мере, на языках высокого уровня) автоматически увеличивают вашу хеш-таблицу за кулисами - что приведет к более медленной, чем ожидалось, производительности на вставке, которая запускает рост, - но если вы используете свою собственную, это определенно что-то рассмотреть.
вы также можете получить снижение производительности из-за слишком большого количества столкновений не потому, что ваш алгоритм хеширования плохой, а просто потому, что хеш-таблица недостаточно велика. Большинство реализаций библиотек (по крайней мере, на языках высокого уровня) автоматически увеличивают вашу хеш-таблицу за кулисами - что приведет к более медленной, чем ожидалось, производительности на вставке, которая запускает рост, - но если вы используете свою собственную, это определенно что-то рассмотреть. вы также можете получить снижение производительности из-за слишком большого количества столкновений не потому, что ваш алгоритм хеширования плохой, а просто потому, что хеш-таблица недостаточно велика. Большинство реализаций библиотек (по крайней мере, на языках высокого уровня) автоматически увеличивают вашу хеш-таблицу за кулисами - что приведет к более медленной, чем ожидалось, производительности на вставке, которая запускает рост, - но если вы используете свою собственную, это определенно что-то рассмотреть. Операция get в SortedList - это O (log n) , а та же операция ea HashTable - O (1) . Итак, обычно , HashTable будет намного быстрее. Но это зависит от ряда факторов:
- Размер списка
- Производительность алгоритма хеширования
- Количество коллизий / качество алгоритма хеширования
Предполагается, что под «отсортированным списком» вы подразумеваете «сортированную коллекцию с произвольным доступом». Список обладает тем свойством, что вы можете перемещаться по нему только элемент за элементом, что приведет к сложности O (N).
Самый быстрый способ найти элемент в отсортированной индексируемой коллекции - N-арный поиск, O ( logN), тогда как хеш-таблица без коллизий имеет сложность поиска O (1).
В некоторых случаях это зависит от размера коллекции (и, в меньшей степени, от деталей реализации). Если ваш список очень маленький, может быть, 5-10 пунктов, я думаю, что список будет быстрее. В противном случае xtofl прав.
HashTable будет более эффективным для списка, содержащего более 10 элементов. Если в списке меньше 10 элементов, накладные расходы из-за алгоритма хеширования будут больше.
Если вам нужен быстрый словарь, но при этом нужно хранить элементы в упорядоченном виде, используйте OrderedDictionary. (.Net 2.0 и более поздние версии)
Это полностью зависит от объема хранимых вами данных.
Предполагая, что у вас достаточно памяти, чтобы их использовать (так что хеш-таблица достаточно велика), хеш-таблица найдет целевые данные за фиксированный промежуток времени, но необходимость вычисления хэша приведет к некоторым (также фиксированным) накладным расходам.
Поиск в отсортированном списке не будет иметь этих накладных расходов на хеширование, но время, необходимое для выполнения работы по поиск целевых данных будет увеличиваться по мере роста списка.
Таким образом, в целом отсортированный список будет быстрее для небольших наборов данных. (Для очень маленьких наборов данных, которые часто меняются и / или редко просматриваются, отсортированный список un может быть даже быстрее, поскольку он позволяет избежать накладных расходов на выполнение сортировки.) По мере того, как набор данных становится большим, рост списка » Время поиска затмевает фиксированные накладные расходы на хеширование, и хеш-таблица становится быстрее.
Где находится эта точка останова, будет зависеть от вашей конкретной хеш-таблицы и реализаций поиска по отсортированному списку. Выполните тесты и оцените производительность ряда наборов данных стандартного размера, чтобы увидеть, какие из них будут работать лучше в вашем конкретном случае. (Или, если код уже выполняется «достаточно быстро», не делайте этого. Просто используйте то, что вам удобнее, и не беспокойтесь об оптимизации чего-то, что не требует оптимизации.)
Выполните тесты и оцените производительность ряда наборов данных стандартного размера, чтобы увидеть, какие из них будут работать лучше в вашем конкретном случае. (Или, если код уже выполняется «достаточно быстро», не делайте этого. Просто используйте то, что вам удобнее, и не беспокойтесь об оптимизации чего-то, что не требует оптимизации.) Выполните тесты и оцените производительность ряда наборов данных стандартного размера, чтобы увидеть, какие из них будут работать лучше в вашем конкретном случае. (Или, если код уже выполняется «достаточно быстро», не делайте этого. Просто используйте то, что вам удобнее, и не беспокойтесь об оптимизации чего-то, что не требует оптимизации.)