Большой O для DynamicArray против HashTable при получении их значений с использованием их индексов - PullRequest
Новая
       36

Большой O для DynamicArray против HashTable при получении их значений с использованием их индексов

0 голосов
/ 20 января 2019

В общем, я знаю, что Hashtables имеют лучшую производительность по сравнению с динамическими массивами для поиска определенного значения.Верно ли это, когда мы выбираем значение напрямую, передавая индекс?

Например: 

HashTable d=new HashTable(); //let us consider it is initialized with values 

for (int i = 0; i < largeValue ; i++)
        {
            int doNothing=d[i];
        }

против: 

DynamicArray l=new DynamicArray(); //let us consider it is initialized with values

 for (int i = 0; i < largeValue ; i++)
        {
            int doNothing=l[i];
        }

Какая из них имеет лучшую производительность?

Редактировать 1: Я редактировал вопрос на основе комментариев.

1 Ответ

0 голосов
/ 20 января 2019

Поиск в словаре будет медленнее, даже если обе операции O (1).Индексирование в предопределенную область памяти массива (из которой составлены списки данных) включает меньше операций;скорее всего, это вопрос поиска начала блока памяти и добавления смещения индекса.

Hashtable поиски, с другой стороны, амортизируются O (1).В зависимости от того, как реализована хеш-таблица, вам потребуется вычислить потенциально сложный хеш-код, индексировать в сегмент, просмотреть часть связанного списка, на который указывает сегмент, и проверить равенство, чтобы убедиться, что найденный элемент соответствуеттот, который вы после.Это намного больше работы, чем операция с индексом списка.

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

Взгляните на Словарь часть 2, реализация .NET , если вы хотите более подробно изучить работу словарей C #.

...