Как найти пустую ячейку массива с наименьшим индексом?
Привет. Помогите с задачей.
Исходные данные:
1. Ячейка массива считается пустой, если в ней записано число -1.
2. Ячейка не пустая, если в ней что-то записано, допустим, указатель на объект.
3. Есть массив из 16000 ячеек.
3. Я создаю объекты и последовательно заполняю массив указателями на них, начиная с 0-й ячейки: 0, 1, 2, 3, 4, 5...
Но, в один момент я решаю удалить объект в ячейке с индексом 2. Объект удаляется, а в массив вместо указателя на объект я должен записать -1 (т. е. освобождаю ячейку).
Потом я продолжаю создавать объекты. Но теперь после этого удаления созданный объект должен записаться в ту самую пустую ячейку 2 (т. к. у нее наименьший индекс и она свободна). Когда ячейка 2 снова будет занята, вновь созданные объекты продолжат заполнять массив 6, 7, 8, 9 и т. д.
Естественно, я могу удалять сразу несколько объектов до создания нового объекта.
Допустим, я удалил бы не только объект во 2-й ячейке, но и в 4-й. Тогда новые объекты занимали бы ячейки сначала 2 и 4, а потом как обычно.
Не хочу проходить циклом от начала до конца и проверять, свободна ли ячейка, т. к. у меня будет 16000 объектов минимум (следовательно и массив на 16000 ячеек).
UPD: в распоряжении только обычные массивы и циклы.
Может, завести массив вакансий, в который писать адреса удалённых? Его отн. быстро сортировать.
И переменную с индексом начала ещё неосвоенной сплошной области в хвосте.
Да и 16 тыс перебрать циклом, строго сравнивая с -1 дело недолгое..
Как вариант, хранить листом все неиспользуемые индексы (если массив может изменяться в размере во время выполнения, то последнее значение в листе может указывать на первый свободный элемент, в который ещё ничего не записывалось). И когда надо брать нужный индекс из листа / добавлять в лист свободный индекс.
WbICHA, Если уж если хранить листом (списком) все неиспользуемые индексы, то разумнее вообще отказаться от изначальной структуры массива указателей и делать сразу список указателей. Но изначально сказано четко и безаппеляционно "Есть массив из 16000 ячеек"
Впрочем одно могу сказать - попытка сначала спроектировать структуру, а потом на нее "натягивать" свою задачу - как правило всегда ущербна. Структуру и соответственно алгоритмы работы с ней надо проектировать исходя из конкретной имеющейся *прикладной) задачи. К сожалению на все (начинающие) программисты осознают это. А когда осознавать - это наверно и характеризует их переход из разряда "юниор" в разряд "миддл".
Сергей Соколов, может быть и 32000 и 48000. Они играют роль слотов в инвентарях игроков. На сервере максимум 1000 игроков. Пока сделал, что у каждого по 16 ячеек в инвентаре, увеличу скорее всего.
Лев Александров, Из вашего описания следует, что если объект никак (семантически) не связан с его индексом, то непонятно, зачем вам массив, основное преимущество которого как раз и заключается в прямом доступе к объекту по индексу.
Впрочем - это предмет дискуссии совершенного другого вопроса.
P.S. Это какой-же язык программирования настолько " специфический"?
Лев Александров, А какой это язык? Извините если лезу не в свое дело, но какой контекст у задачи, для чего вы её решаете. Признаюсь, я заинтересовался. Может, переписать проект на более гибком языке (например на Лиспе)?
Нужно хранить пустые ячейки в списке. У вас будет одна внешняя переменная - указатель на голову этого списка. Можно в качестве указателей в списке использовать сами ячейки.
При добавлении:
Если этот указатель -1 - то надо взять следующий по порядку элемент. Иначе указатель - это пустая ячейка. Ее используйте, но сначала сдвиньте указатель на список пустых элементов вперед по списку.
При удалении просто добавляйте пустую ячейку в начало списка (эта ячейка указывает на текущую голову списка; голова теперь указывает на эту ячейку).
УПД:
Это все выше, если забить на требование заполнения самой левой пустой ячейки. Зато все операции (удаление, поиск пустой ячейки) выполняются за константу и не надо константную дополнительную память.
Если обязательно заполнять самую левую ячейку - то надо писать или приоритетную очередь (через heap) или дерево отрезков (или дерево Фенвика). Тогда операции удаления и поискка будут работать за логарифм и потребуется линейная дополнительная память.
Лев Александров, Ах да, тут добавляется новый элемент не в самую левую ячейку, а в последнюю освобожденную. Но зато добавление и удаление за константу и дополнительной памяти - одна переменная.
Если вам обязательно нужно в самую левую ячейку класть, то придется реализовывать, например, дерево отрезков, или бинарную кучу. Это делается только на массивах и циклах. В этих структурах данных можно будет искать самую левую ячейку, добавлять ячейки и удалять самую левую за логарифм.
Если скорость не важна, то пишите тупой перебор - циклом пройдитесь по массиву, пока пустую ячейку не встретите.
Wataru, Тут нужен не список, а очередь. Её можно делать в виде однонаправленного списка, но хорошо бы оптимизировать, выделяя память не под каждый элемент со ссылкой на следующий, а выделять блок под несколько элементов и ссылку на следующий блок.
См.мой ответ ниже.
Лев Александров, Любый списки, очереди и много иное делается на базе массивов. Благо RAM есть массив, а в ней делается вообще всё, что делается на компьютере.
Karpion, Я описал стек, реализованный в виде списка внутри используемого массива. Чем очередь лучше стека? В принципе, все то же самое, но надо два указателя вместо одного: на начало и конец очереди. И в предложенном мной решении никакой памяти выделять не надо.
Но это все только если забить на требование выбора самой левой ячейки.
Ну, я могу предложить то же, что и Wataru : создать очередь со ссылками на пустые элементы массива. Есть даже более красивое решение:
В пустом элементе хранится не "-1", а ссылка на следующий пустой элемент. А начало списка хранится в отдельной переменной.
Соответственно, массив можно инициировать этими ссылками.
Т.е. учёт занятости элементов массива ведётся в этом же массиве, в свободных элементах. Примерно так работает классическая файловая система Unix с дисковым пространством; с той только разницей, что в кластере файловой системы можно хранить много ссылок.
И есть второй вариант:
При каждом удалении элемента производить дефрагментацию свободного места. Сдвигать весь хвост массива слишком сложно, а вот переместить на освободившееся место последний элемент массива = самое то что нужно.
Средний
