Пул ресурсов для структуры данных
При реализации элементарной структуры данных типа stack, queues, linked list и др.
должен ли я создавать пул ресурсов (узлов), динамически выделяя память в связке, или я должен выделять память отдельно каждый раз, когда мне нужен узел?
2 ответа:
Это целиком зависит от ваших целей. По умолчанию (то есть, если вам действительно не нужно делать иначе), просто выполните нормальное распределение для каждого следующего узла.
Пулы памяти по сравнению с простым выделением узлов:
Сделайте распределение быстрее. В зависимости от базового механизма распределения, иногда значительно быстрее.
Обычно меньше фрагментации памяти,хотя это не может быть проблемой с некоторыми распределителями.
Главный недостаток: тратить память на зарезервированные, но не используемые узлы. Это очень важно, если вы используете структуру данных без разбора (например, 1000 экземпляров), а не просто несколько экземпляров.
Из-за этого недостатка пулы памяти не подходят для общих ситуаций.
В C++ все стандартные контейнеры имеют параметр шаблона
allocator.
Это основной компромисс между временем и пространством. Выбирал исходя из того, что для вас важнее:
Если вы выделяете пул заранее,то ваши вставки элементов среды выполнения будут-в среднем-оптимизированы для скорости, т. е. постоянного времени, т. е. "В среднем" означает, что Большинство вставок будет постоянным временем, за исключением тех, которые достигают максимума и требуют расширения пула, которые являются линейным временем, O(n). Вы также рискуете потерять часть памяти, если в конечном итоге не используете целый бассейн.
Если вы делаете выделение в реальном времени каждого нового узла, вы всегда будете иметь вставку с постоянным временем, но в этом случае постоянное время немного больше, чем постоянное время выше, потому что вы не только должны поместить значение в ячейку памяти, но вы также должны сначала выделить ячейку памяти. Кроме того, этот метод не тратит впустую память, резервируя места памяти заранее.
В большинстве ситуаций, я думаю, распределение в реальном времени является достаточно эффективный с точки зрения времени, что я не вижу, почему вы используете объединенный подход, , если только ваше приложение не требует экстремальной средней скорости или Вы делаете огромное количество вставок.