prog
offline
Опыт:
32,865Активность: |
а DioD то прав - метод с хранением списков свободных ячеек гораздо эффективнее чем перебор
хотя для задач с небольшим кол-вом элементов, как у автора, вполне применим кустарный метод с использованием перебора циклом и сохранением минимального индекса свободной ячейки, кол-ва свободных ячеек между минимальным индексом свободной ячейки и последней занятой ячейкой и, желательно, индекс последней свободной ячейки в промежутке между первой свободной и последней занятой
в простом виде алгоритм такой:
при запросе на новую свободную ячейку возвращается индекс первой свободной ячейки и осуществляется перебор от следующей ячейки с целью нахождения следующей свободной
при запросе на освобождение ячейки проверяется не меньше ли индекс освобожденной ячейки чем индекс первой свободной ячейки и если это так, то индекс освобожденной ячейки записывается как новый индекс первой свободной ячейки
в более сложном варианте еще выполняется проверка на то не является ли выданная ячейка последней (в диапазоне от первой свободной до последней занятой) и в этом случае перебор начинается со следующей за последней занятой
в некоторых случаях бывает удобно перебирать ячейки от последней свободной в сторону убывания
сам я давно почти отказался от таких методов (иногда целесообразнее небольшой перебор чем несколько лишних килобайт памяти) в пользу методов с сохранением списков свободных ячеек |
08.10.2010, 12:27 | #21
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
DioD
offline
Опыт:
45,134Активность: |
слишком много проверок, в варианте со списком:
генератор уникальных в него встроен блок рециркуляции
список занятых ячеек, ссылками, при удалении двигаем последний элемент на место удаляемого
того будет 1 проверка, является ли удаляемый элемент последним, и ничего не надо, при желании можно сделать без дополнительных переменных на одном массиве. |
08.10.2010, 17:54 | #22
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|