[Алгоритмы] Структура данных для пула объектов

[Anton Riot]

Сообщение от shmaser

…последний элемент ставят вместо удаляемого и хранят реальную длину массива в отдельной переменной.

зачем отдельной, длину можно устанавливать, изменяя поле length.

[expl]

Видел много реализаций пула объектов через массив, есть ли какие-либо преимущества/недостатки реализации в виде самописного односвязного списка? Кто-то вообще так делает?

Я так делал кое-где, потому что доступ к массиву медленный (про вектор не уверен), а по полю объекта - быстрый.
На всякий случай:

public class MyObjectPool {
    private static var _head:MyObject = null;
    public static function getObject():MyObject {// Берём с головы, если есть
        if (head == null)
            return new MyObject();
        MyObject result = _head;
        _head = _head.next;
        return result;
    }
    public static function pushObject(MyObject object):void {// Кладём в голову
        object.next = _head;
        _head = object;
    }
}

Впринципе, код простой, можно даже заинлайнить, сэкономив на вызове функций.
Но тут есть ограничения:
- надо чтобы поле next принадлежало оъектам, которые ложим в пул
- соответственно next может использоваться только для покладания только в один пул в один момент времени, если кто-то будет пытатся построить связный список используя этот next для чего-то другого - после поклажи в пул всё посыпется
- если не делать поле next, а делать отдельные ноды, например так ложить в пул:

var node:PoolNode = new PoolNode(object);
node.next = _head;
_head = node;

То вы проиграете в десятки раз пулу на массиве/векторе из-за выделений памяти под ноды и последующей их сборке GC

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

Этож ПУЛ, какая может быть переалокация? Сверху кинули, сверху первый сняли.
Не, переалокация есть на изменение размера вектора, но она случается редко и _амортизированное_ время поклажи и снятия с конца всё равно O(1), как бы это странно не звучало.
Не среднее статистическое! А гарантированное общее амортизированное. В середину же мы не лезем.

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

Это пул, там не надо в середине ничего искать, array.push(object), array.pop() и всё.

По поводу удаления из неупорядоченного массива - да есть такая практика, применяется при случайной выборке элементов, чтобы они не повторялись, т.е. взяли случайный индекс, запомнили, дырку заткнули элементом с конца.
Только не надо разводить бухгалтерию с отделным хранением длины, просто array.length-- и всё! У нас нет настоящих массивов, у нас есть 2 реализации списка: Array - реализованный неведомыми алгоритмами и Vector - это почти как List в C#. Они за вас лишний раз ничё без надобности не переалоцируют - не переживайте.

Т.е. имеем преимущества как списков так и массивов (рассматриваются только неупорядоченные данные).

Дык чтобы удалить надо свой индекс всё равно найти, сложность та же что если бы мы сдвигали все справа - O(N), О чуток поменьше только.
Это когда случайный элемент выбираем - мы индекс указываем, а не элемент - там действительно O(1).
Это _произвольный_ элемент _двусвязного_ списка удаляется за O(1), но для этого надо иметь ссылку на узел (или сам объект должен являться узлом), иначе придётся искать "чьего узла объект" перебором со всеми вытекающими.

[Akopalipsis]

Короче практически всё в ООП в той или иной мере является композицией

Согласен, просто когда прочёл в вики о списке, первое что пришло в голову - композиция, но только в рамках одного ( возможно нескольких ) класса с ссылками.

[alexcon314]

1 ..Оператор квадратной скобки для доступа к Vector/Array достаточно медленный, а с использованием связного списка доставать элементы можно будет по ссылкам...
Vector в плане производительности пошустрее массива. Ну, не мега, но все же.
Ссылка - это хорошо, но храниться она будет в свойстве объекта типа какой-нибудь PollRecord как я понимаю, а значит к ней тоже надо получать доступ - с помощью оператора "." (точка). Получается упремся в "." против "[ ]" вроде как. Проверьте. На векторе.
2. Опять же, не знаю, что лучше, но вариант со списком более логичен и универсален. Вариант с замещением удяляемого на хвост - частность, но если дело только в этом... пахнет второй волной рефракторинга, вобщем.

[expl]

1. Связный список не имеет нативной реализации в AS 3. Потому и примеров нету. Самописный? Попробовать можно, почему нет? Но вряд ли это будет быстрее вектора.

Если не создавать ноды, а использовать сами оъекты и делать односвязный список - то может даже будет.

В AS3 одно- и двусвязные- списки имеют смысл только если узлами являются сами хранимые объекты (соответственно один объект не может лежать в 2-х списках). Потому что выделение памяти и последующая сборка узлов очень много тратят ресурсов.
Или надо делать пул узлов внутри списка (видел такие конструкции в одном проекте, может даже имели смысл)

Да и сами связные списки не такие уж применимые как кажется на первый взгляд:
- Тут удаление за O(1) из середины!
- Отлично, давай удалим из list объект object
- Ээ, а как узнать какому узлу принадлежит objet? Пройтись за O(n)? Но в чём тогда преимущества?
- Ну можно запомнить узел в object при добавлении
- но тогда ведь надо будет влезть в object, и нельзя будет добавлять их в 2 списка, зачем вооще эти списки придумали?
- чтобы во время итерации вставлять после текущего узла быстро или удалять
- где такое применяется?
- на вскидку не вспомню

Кстати, если нужно просто хранилище объектов неупорядоченное с O(1) вставкой и удалением - используйте Dictionary.

[alexcon314]

Речь шла о сравнении самописного списка и вектора (массив в проигрыше) применительно к организации пула, когда нам нужно просто отдать объект с вершины/поместить его в вершину и все. Этим и следует ограничиться .

[dimarik]

Односвязный список в качестве пула должно быть OK. Сложность чтения начального элемента для него O(1). По сути, вы и вектора и массивы для пула пользуете в виде unshift (или push) и shift (или pop).

[Dukobpa3]

Односвязный список в качестве пула должно быть OK.

Вопрос мотивации.

Превращать вектор в итератор может и есть смысл, но как верно замечено:

для пула пользуете в виде unshift (или push) и shift (или pop).

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

Ябпоглядел на удобный стек или очередь на основе списка.

[Babylon]

Мне тоже интересно чем стек от пула отличается?

[dimarik]

Может кто-то проведет тест?

Добавлено через 21 минуту

Сообщение от Dukobpa3

Но в целом эта структура довольно таки специфичная. Использовать пришлось может раза два за всю практику.

Да, достаточно специфичная. Не то что синглетоны. Я обратился к связным спискам для построения списка обхода дерева дисплей объектов для рендеринга. По сути в движках, основанных на stage3d, которые я видел, этот обход делается тривиально. Post order. Имея на руках дерево, как образец, и строя по некоторым условиям свои пути обхода с помощью linked list можно серьезно экономить на производительности. Не все объекты рендерятся, некоторые из них лишь предоставляют новую матрицу трансформации, это т.н. "контейнеры". Они входят в состав "дисплей листа", но никогда не рендерятся. Они влияют лишь на трансформацию своих детей. Так зачем их включать в список обхода? Достаточно разок подсчитать матрицы реально рендерящихся детей через матрицы контейнеров и вот вам готовый линкед лист по листьям дерева, которые отображаются на экране. Поверьте, сбор матриц каждый кадр со всего дерева и сбор матриц каждый кадр с листьев, — это две большие разницы.