среда, 13 июля 2011 г.

Компромисс в выборе между классом и структурой

На тему навела вот эта статья "NET 4.0: Class vs Struct или в чём различия между Классом и Структурой" . Давно уже собирался собрать для себя набор иерархии универсальных коллекций, которые не попадают под сборку мусора. Тема в очередной раз стала интересна после моего известного эксперимента с Windows Phone 7. Очень сомневаюсь, что моя статья будет полезна для бизнес-приложений.  Меня больше интересует данная тема для использования в XNA/DirectX и как область применения - игры.

Приглашаю вас обсудить данный вопрос.

И так, условия задачи:
- Нужна коллекция элементов для описания, например, системы частиц (это может быть все что угодно). Такая штука в которой в среднем 60 раз в секунду добавляются и удаляются сотни элементов.
- Изменения в коллекции не должны влиять на сборку мусора.
- Нельзя использовать структуры! Только ссылочные типы.
- Запрещено создавать и удалять классы, за исключением первой инициализации.
- Физическое количество элементов в коллекции должно быть постоянным. Т.к. изменение длинны массива достаточно накладная операция, а количество элементов должно постоянно плавать, то подойдет подобие кеша. Ограничение - разработчику желательно четко знать максимально возможное количество элементов в такой коллекции. А это значит игра должна быть грамотно спроектирована. Хотя лазейку я оставлю.


Набросал вот такой черновик.

Базовый класс для элемента коллекции:

public class TElementConstLength
    {
        private  int indexInCollection = -1;
        internal int IndexInCollection { get { return indexInCollection; } }
        internal void SetIndexInCollection(int i)
        {
            indexInCollection = i;
        }
    }


Базовый класс для коллекции:

public class TCollectionConstLength<T> where T : TElementConstLength, new()
    {
        private T[] elements;

        private int count = 0;
        /// <summary>
        /// Количество живых элементов
        /// </summary>
        public  int Count { get { return count; } }

        private int end = -1;

        /// <summary>
        /// Инициализация колекции
        /// </summary>
        /// <param name="length">Длинна коллекции</param>
        public TCollectionConstLength(int length)
        {
            elements = new T[length];
        }

        /// <summary>
        /// Доступ к элементу по индексу
        /// </summary>
        /// <param name="index">Индекс</param>
        /// <returns>Элемент</returns>
        public T this[int index]
        {
            get { return elements[index]; }
        }

        /// <summary>
        /// Выделение места под новый элемент
        /// </summary>
        /// <returns>Новый элемент</returns>
        public virtual T GetNew() // = Add
        {
            // если список полон, для режима отладки
            if(end == elements.Length - 1)
                Array.Resize(ref elements, elements.Length + 1);
            // 
            end++;
            count++;
            // если не инициализирован элемент
            if(elements[end] == null)
            {
                elements[end] = new T();
                elements[end].SetIndexInCollection(end);
            }
            //
            return elements[end];
        }

        /// <summary>
        /// Очистка списка
        /// </summary>
        public void Clear()
        {
            end = -1;
            count = 0;
        }

        /// <summary>
        /// Удаление элемента по индексу
        /// </summary>
        /// <param name="index">Индекс</param>
        public virtual void Remove(int index)
        {
            // выход за пределы
            if(index < 0 || index > end)
                return;
            if(index < end)
            {
                // рокировка элементов
                T temp = elements[end];
                elements[end] = elements[index];
                elements[index] = temp;
                // рокировка индексов
                int i = elements[end].IndexInCollection;
                elements[end].SetIndexInCollection(elements[index].IndexInCollection);
                elements[index].SetIndexInCollection(i);
            }
            // уменьшаем список
            end--;
            count--;
        }

        /// <summary>
        /// Удаление элемента
        /// </summary>
        /// <param name="e">Элемент</param>
        public virtual void Remove(T e)
        {
            // проверка на соответствие ссылок (защита от тупости)
            if(e != elements[e.IndexInCollection])
                return;
            Remove(e.IndexInCollection);
        }
    }

Вот пример для тестов:

using System;

namespace CollectionConstLength
{

    public class ElementTest : TElementConstLength
    {
        private string name;
        public string Name { get { return name; } set { name = value; } }
        public ElementTest() { }
    }

    class Program
    {

        static TCollectionConstLength<ElementTest> item;

        static void Main(string[] args)
        {

            item = new TCollectionConstLength<ElementTest>(5);
            ElementTest et;
            for(int i = 0; i < 5; i++)
            {
                et = item.GetNew();
                et.Name = i.ToString();
            }
            //
            Print();
            //
            item.Remove(item[1]);
            Print();
            //
            Console.ReadKey();
        }

        static void Print()
        {
            Console.WriteLine("//--------------------------------");
            for(int i = 0; i < item.Count; i++)
            {
                Console.WriteLine(
                    string.Format("index - {0}; name - \"{1}\";", 
                        item[i].IndexInCollection, 
                        item[i].Name));
            }
            Console.WriteLine("//--------------------------------");
        }
    }
}


Пример наращивания функционала через наследование:

- Расширенный класс элемента:

public class TUpdate : TElementConstLength
    {
        public virtual void Update() { }
    }

- Расширенный класс коллекции

public class TUpdateCollection<T> : TCollectionConstLength<T> where T : TUpdate, new()
    {
        public TUpdateCollection(int l) : base(l) { }
        public virtual void Update()
        {
            for(int i = 0; i < base.Count; i++)
            {
                base[i].Update();
            }
        }
    }


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

Давайте пообщаемся на эту тему.
Так же буду рад ссылкам на статьи с подобными темами и изысканиями.

22 комментария:

  1. получилось чтото типа реализации вектора в stl?

    ОтветитьУдалить
  2. Как трудно читать код(цвет и фон)!

    Не понял отправил или нет комментарий?

    ОтветитьУдалить
  3. Первое что пришло в голову при прочтении условия - Пул объектов.

    > Изменения в коллекции не должны влиять на
    > сборку мусора.

    Подходит. Ненужные объекты просто лежат в пуле.

    > Нельзя использовать структуры! Только
    > ссылочные типы.

    Подходит.

    > Запрещено создавать и удалять классы,
    > за исключением первой инициализации.

    Ну это связано с прошлым пунктом.

    > Физическое количество элементов в
    > коллекции должно быть постоянным.

    Создаем пул с фиксированным числом объектов. Освобождаемые не удаляем, а просто используем повторно, заполняя новыми данными.

    В код вдаваться не стал.

    ОтветитьУдалить
  4. Пул в чистом виде не подойдет из-за скрытого требования: добавление и удаление должно быть быстрым. Все равно нужна коллекция активных элементов, а удаление из List медленное.

    Я бы предложил такой подход. Активные элементы хранятся в HashSet, неактивные - в пуле (наример, Stack). Индексы на самом деле не нужны (все равно они меняются), будет достаточно foreach.

    Плюсы - простота кода, отсутствие базового класса для элементов, выполняются все условия.

    Минусы - небольшой оверхед на вычисления в HashSet и, если элементы переопределяют GetHashCode/Equals, то нельзя добавить одинаковые элементы.

    PS. Не понял, при чем тут структуры?

    ОтветитьУдалить
  5. Используйте стандартные средства форматирования кода (и желательно нормальный фон). Попытался прочитать код - дохлый номер, читать невозможно.

    ОтветитьУдалить
  6. Roman, небольшое замечание: Пул != List. Никто не мешает использовать другие типы списоков для его реализации. Для данной задачи главная цель пула - не терять ссылки на объекты, чтобы сборщик мусора не удалил их.

    ОтветитьУдалить
  7. Для системы частиц подойдет скорее List..

    ОтветитьУдалить
  8. Круговой буфер не подойдет?

    ОтветитьУдалить
  9. А доступ по индексу нужен или нет?

    ОтветитьУдалить
  10. Я задал вопрос потому, что в твоей реализации индекс нельзя нигде запомнить ввиду реализации метода Remove - его надо брать из самого элемента. Или я не понимаю каких-то ньюансов?

    ОтветитьУдалить
  11. да индексная привязка запрещена. можно запомнить ссылку. но нужно иметь возможность перебирать по индексам в пределах Count. т.е. для for в функционале потомков от базовой коллекции.

    ОтветитьУдалить
  12. Хм... есть ощущение, что для задачи достаточно двунаправленного списка с используемыми элементами + стэк для пула. Доступа по индексу не будет, вернее, он будет очень медленным - O(Count). Но зато операции вставки и удаления будут мгновенными, ровно как и перебор всех элементов. И расширить пул тоже дешево. Кроме того, многопоточную версию такой коллекции легко сделать LockFree (ну это при необходимости, естественно).

    ОтветитьУдалить
  13. без примера не понятны нюансы. можешь набросать?

    ОтветитьУдалить
  14. Александр, это тоже самое что я набросал недавно? пост64#:

    http://xnadev.ru/forum/viewthread.php?thread_id=1743&rowstart=60

    И я протестую насчёт доступа по индексу в примере Дмитрия.
    1)Если в коллекции 10 элементов.
    2)Мы удаляем 5й.
    3)Рокировка - И теперь 10й стал 5ым.

    Если в этот момент какая-то переменная хранила индекс 10 как ссылку на 10й элемент то она потеряла эту ссылку, и теперь указывает на мусорный элемент.

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

    Между тем необходимости ссылаться по индексу нет.

    ОтветитьУдалить
  15. Ага, примерно. Ну только там реализация не полная, но суть та же.

    Дим, подключи у себя в блоге Syntax Highlighter, чтоб удобнее было код постить: http://alexgorbatchev.com/SyntaxHighlighter/

    ОтветитьУдалить
  16. Да у меня вроде и ошибки есть. И вообще получше можно сделать. Просто, чтобы было понятно о чём речь.
    Подход на связном списке обладает преимуществами: 1) порядок элементов сохраняется, 2) можно удалять элементы во время обхода.(В примере Дмитрия нельзя удалять элементы во время обхода.)
    Хотя связный список требует больше процессора и памяти.

    ОтветитьУдалить
  17. и в требовании к коллекции не написано, что необходимо оставить возможность работы с индексами. да они есть, но функционально нужны только для перебора в наследниках данной коллекции. наследников будет несколько совершенно разных веток. пока индексы нужны исключительно для ограничения количества перебираемых элементов и возможности сделать несколько видов перебора.

    ОтветитьУдалить
  18. Несколько видов перебора - это простой перебор и перебор с предикатом?

    Всякие там переборы типа: рандомный, в обратном порядке, батерфляй... - не имеют смысла т.к. порядок элементов всё равно рандомный.

    Так. что доступ по индексу низачем не нужен(кроме перебора). А перебор нужен, но его можно зашить в класс и всё. А зачем public доступ по индексу, и public уаление по индексу? - это просто зло.

    ОтветитьУдалить
  19. при удалении элемента в List индексные привязки следующих за ним сохраняются?

    ОтветитьУдалить
  20. Мои изыскания:

    http://hale32bit.blogspot.com/2011/07/blog-post.html

    ОтветитьУдалить