Всегда ли необходимо реализовывать таблицу ha sh с динамическим распределением памяти c?

Question

Я искал в Интернете по этому поводу и спросил мои TA, и я не получил очень solid ответ. Я тестирую различные структуры данных на производительность для вставки и поиска данных. Одна из структур данных, которую я тестирую, - это таблица ha sh.

Я понимаю, что динамическое выделение памяти полезно, если вы не знаете конечный размер массива и хотите реализовать массив double для любого ряд причин. Но скажем, мы знаем количество данных. В этом случае 40000 целочисленных значений. Нужно ли динамически выделять массив в куче, или я могу получить ту же функциональность и использовать статическое создание экземпляра в стеке? Я сделал бы все то же самое, создал бы мой заголовочный файл, мой файл реализации и main (), но не выделял бы динамически память.

Answer 1

Хороший вопрос. Вы можете реализовать mallo c в системе без динамического выделения памяти c, просто поместив большую пустую таблицу внутри mallo c. c и обрабатывая ее части до тех пор, пока не закончится. Свободно вставит в это комки, так что вы никогда не закончите.

Связанный способ выделения памяти - через frame allocator (иногда распределитель пула); названный так потому, что он предоставляет доступ к N объектам размера M, а не к истинному динамическому распределителю c, где каждый объект имеет свой размер. Распределители фреймов потрясающие, потому что они быстрые и простые - редкая комбинация.

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

Answer 2

Это действительно зависит от того, что вы подразумеваете под «динамическим c выделением».

Типичная таблица ha sh содержит массив сегментов (или массив указателей на сегменты). Каждое ведро содержит коллекцию вещей, которые хэшируются на один и тот же ха sh. Таким образом, учитывая коллекцию 40000 int, которую вы хотите поместить в таблицу ha sh, вам потребуется некоторая форма динамического выделения 1020 * для каждой самой коллекции, так как вы не будете знать, сколько элементов окажется в каждой bucket.

Если под динамическим выделением c вы имеете в виду «вызовы mallo c», то вы можете управлять памятью для самой таблицы ha sh, коллекцией блоков, каждой отдельной корзиной самостоятельно, используя « размещение новых"или какая-либо другая форма управления вашей собственной памятью. Вы бы рассчитали объем памяти, необходимый для реализации таблицы ha sh, плюс набор сегментов памяти, плюс наихудший случай для памяти для максимального количества используемых интервалов, которое составляет 40000, поскольку наихудший случай равен одной записи на сегмент. если диапазон вашей функции ha sh меньше 40000

В качестве примера таблица ha sh может выглядеть как

template <typename T> class Bucket {
  int size;
  T* items;
};

template <typename T> class HashTable {
  int size;  // optional if you know your hash function's range
  Bucket<T>* buckets;
};

Так что вам нужно

max_buckets = min(hash_table_range, num_items);
bytesNeeded = sizeof(HashTable<T>)
            + num_hash_values * sizeof(Bucket<T>*)
            + max_buckets * sizeof(Bucket<T>)
            + sizeof(T) * num_items;

Вы все равно должны были бы управлять распределением сегментов (в некотором смысле это «распределение dyanmi c»), и вам нужно было бы иметь возможность перетасовывать сегменты по мере их роста, так как не было бы места вырастить их на месте, которое мне кажется, добавило бы тонну накладных расходов. Просто вы сами управляете этим распределением, так что решать, будет ли это «динамическое распределение» 1028 *.

Answer 3

Если вы знаете максимальный (или фиксированный) размер вашей таблицы ha sh, вы можете статически распределить ее.

Основная причина динамического распределения c состоит в изменении размер во время выполнения и возможность передавать владение структурой от функции к функции. Например (и это вообще не связано с таблицами sh, поэтому я просто использую обобщенную структуру c):

Item *GetItem() {
    return new Item();
}

, которая динамически распределяет элемент и передает его обратно вызывающий абонент (вместе с владельцем (ответственность за управление его временем жизни)). Наивный способ избежать динамического выделения c будет выглядеть так:

Item *GetItem() {
    Item item;
    return &item;
}

К сожалению, этот адрес не может быть использован при возврате, так как item вышел из области видимости в тот момент, так что вы можете предотвратить это. with:

Item *GetItem() {
    static Item item;
    return &item;
}

Сохраняет объект даже после возврата из функции, но имеет ограничение на существование только одной его копии. Если вы попытаетесь получить два элемента из этой функции, они будут одинаковыми, и у вас могут появиться ошибки, если вы не поймете это.

Итак, я бы сказал, что, если вам нужен только один га sh таблица, вы можете избежать динамического распределения памяти c, просто имея ее статическую c копию.

Конечно, кроме ограничения на единственную копию, у этого также есть недостаток, требующий выделения памяти. максимальное пространство, необходимое. Это не обязательно плохая идея (особенно если это фиксированный размер), но это может вызвать неэффективность.

---

В любом случае вы можете беспокоиться о производительности без необходимости. Вы также можете легко динамически распределить структуру в ее максимальном / фиксированном размере заранее (вместо того, чтобы делать много небольших выделений и перераспределений). Так как это действительно происходит только один раз за стол * га sh (с надеждой, что многие используют таблицы ха sh до освобождения), стоимость будет относительно небольшой.

И это дает вам возможность иметь более одной таблицы ha sh в программе.