Какие издержки используются в Hashtable? - PullRequest
Новая
       3

Какие издержки используются в Hashtable?

1 голос
/ 04 марта 2010

Я понимаю, что, поскольку распределение выполняется во время выполнения, должны выполняться некоторые операции по ведению домашнего хозяйства. Но кроме того, что накладные расходы? Кроме того, было бы разумно создать массив хеш-таблицы Vs, когда вам нужно сохранить количество раз, когда целочисленный элемент появляется в бесконечном потоке чисел?

Ответы [ 3 ]

3 голосов
/ 04 марта 2010

Теоретически, это зависит от количества уникальных чисел в потоке чисел.Но любой реальный сценарий из жизни, который я могу себе представить, будет смехотворно медленнее.Чем больше уникальных чисел вы обработаете, тем медленнее будет решение массива.

HashTable обычно поддерживает одинаковую скорость доступа, независимо от того, насколько большим он становится.Для «бесконечного потока» я не представляю, как HashTable не будет лучшим решением.Как вы собираетесь искать в массиве?

1 голос
/ 04 марта 2010

Hashtables довольно быстро. В качестве эксперимента я получаю примерно 50-кратное замедление между необработанным массивом и хэш-картой c ++ (скомпилируйте с переключателем #if в обоих направлениях и попробуйте сами). 

#include <ext/hash_map>
using namespace __gnu_cxx;

int main() {
#if 0
  hash_map<int,int> table;
  for (int i = 0; i < 256; i++) table[i] = 0;
#else
  int table[256];
#endif

  for (int i = 0; i < 100000000; i++) {
    table[i&0xff]++;
  }
}
1 голос
/ 04 марта 2010

Как следует из комментария Нейла, накладные расходы в реализациях хэш-таблицы сильно зависят от конкретной реализации хэш-таблицы. Однако, как правило, возникают издержки хранения от неиспользуемых хэшей, а также затраты на хранение и время от коллизий хешей. Разумеется, на вычисление хеш-значений также накладываются временные издержки.

В ответ на ваш второй вопрос, это очень сильно зависит от деталей вашего потока цифр и других аспектов вашей программы. Некоторые вопросы для рассмотрения:

  • Набор возможных чисел большой или маленький? (Какого размера массив вам нужно создать?)

  • Ожидаете ли вы, что из числа возможных чисел будет использовано большинство из них или только несколько? Если вы ожидаете, что будет использоваться большинство возможных чисел в диапазоне, то использование хеш-таблицы не сэкономит вам много места.

  • Знаете ли вы диапазон возможных чисел, прежде чем начать? Или это неизвестно? Хеш-таблицы гораздо проще справляются с неизвестными диапазонами.

  • Насколько важно экономить место на диске в этой программе? Вы можете легко позволить себе выделить массив необходимого размера? Если вы можете легко выделить массив, зачем использовать хеш-таблицу?

  • Насколько важна скорость выполнения в этой программе? Массивы обычно будут быстрее.

...