Приглашаю вас обсудить данный вопрос.
И так, условия задачи:
- Нужна коллекция элементов для описания, например, системы частиц (это может быть все что угодно). Такая штука в которой в среднем 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(); } } }
Данный подход позволяет исключить сборку мусора и равномерно распределить нагрузку на процессор. Для каждого наследника от базового класса нужно добавить метод заполняющий поля данного класса, что делает процесс инициализации нового члена коллекции похожим на инициализацию структуры.
Давайте пообщаемся на эту тему.
Так же буду рад ссылкам на статьи с подобными темами и изысканиями.
получилось чтото типа реализации вектора в stl?
ОтветитьУдалитьКак трудно читать код(цвет и фон)!
ОтветитьУдалитьНе понял отправил или нет комментарий?
Первое что пришло в голову при прочтении условия - Пул объектов.
ОтветитьУдалить> Изменения в коллекции не должны влиять на
> сборку мусора.
Подходит. Ненужные объекты просто лежат в пуле.
> Нельзя использовать структуры! Только
> ссылочные типы.
Подходит.
> Запрещено создавать и удалять классы,
> за исключением первой инициализации.
Ну это связано с прошлым пунктом.
> Физическое количество элементов в
> коллекции должно быть постоянным.
Создаем пул с фиксированным числом объектов. Освобождаемые не удаляем, а просто используем повторно, заполняя новыми данными.
В код вдаваться не стал.
Пул в чистом виде не подойдет из-за скрытого требования: добавление и удаление должно быть быстрым. Все равно нужна коллекция активных элементов, а удаление из List медленное.
ОтветитьУдалитьЯ бы предложил такой подход. Активные элементы хранятся в HashSet, неактивные - в пуле (наример, Stack). Индексы на самом деле не нужны (все равно они меняются), будет достаточно foreach.
Плюсы - простота кода, отсутствие базового класса для элементов, выполняются все условия.
Минусы - небольшой оверхед на вычисления в HashSet и, если элементы переопределяют GetHashCode/Equals, то нельзя добавить одинаковые элементы.
PS. Не понял, при чем тут структуры?
Используйте стандартные средства форматирования кода (и желательно нормальный фон). Попытался прочитать код - дохлый номер, читать невозможно.
ОтветитьУдалитьRoman, небольшое замечание: Пул != List. Никто не мешает использовать другие типы списоков для его реализации. Для данной задачи главная цель пула - не терять ссылки на объекты, чтобы сборщик мусора не удалил их.
ОтветитьУдалитьДля системы частиц подойдет скорее List..
ОтветитьУдалитьКруговой буфер не подойдет?
ОтветитьУдалитьА доступ по индексу нужен или нет?
ОтветитьУдалитьда Саш и он там есть
ОтветитьУдалитьЯ задал вопрос потому, что в твоей реализации индекс нельзя нигде запомнить ввиду реализации метода Remove - его надо брать из самого элемента. Или я не понимаю каких-то ньюансов?
ОтветитьУдалитьда индексная привязка запрещена. можно запомнить ссылку. но нужно иметь возможность перебирать по индексам в пределах Count. т.е. для for в функционале потомков от базовой коллекции.
ОтветитьУдалитьХм... есть ощущение, что для задачи достаточно двунаправленного списка с используемыми элементами + стэк для пула. Доступа по индексу не будет, вернее, он будет очень медленным - O(Count). Но зато операции вставки и удаления будут мгновенными, ровно как и перебор всех элементов. И расширить пул тоже дешево. Кроме того, многопоточную версию такой коллекции легко сделать LockFree (ну это при необходимости, естественно).
ОтветитьУдалитьбез примера не понятны нюансы. можешь набросать?
ОтветитьУдалитьАлександр, это тоже самое что я набросал недавно? пост64#:
ОтветитьУдалитьhttp://xnadev.ru/forum/viewthread.php?thread_id=1743&rowstart=60
И я протестую насчёт доступа по индексу в примере Дмитрия.
1)Если в коллекции 10 элементов.
2)Мы удаляем 5й.
3)Рокировка - И теперь 10й стал 5ым.
Если в этот момент какая-то переменная хранила индекс 10 как ссылку на 10й элемент то она потеряла эту ссылку, и теперь указывает на мусорный элемент.
Т.е. каждый раз когда мы сперва сохраняем в локальную переменную индекс в коллекции чтобы потом сослаться, мы рискуем.
Между тем необходимости ссылаться по индексу нет.
Ага, примерно. Ну только там реализация не полная, но суть та же.
ОтветитьУдалитьДим, подключи у себя в блоге Syntax Highlighter, чтоб удобнее было код постить: http://alexgorbatchev.com/SyntaxHighlighter/
Да у меня вроде и ошибки есть. И вообще получше можно сделать. Просто, чтобы было понятно о чём речь.
ОтветитьУдалитьПодход на связном списке обладает преимуществами: 1) порядок элементов сохраняется, 2) можно удалять элементы во время обхода.(В примере Дмитрия нельзя удалять элементы во время обхода.)
Хотя связный список требует больше процессора и памяти.
и зачем мне такое счастье?
ОтветитьУдалитьи в требовании к коллекции не написано, что необходимо оставить возможность работы с индексами. да они есть, но функционально нужны только для перебора в наследниках данной коллекции. наследников будет несколько совершенно разных веток. пока индексы нужны исключительно для ограничения количества перебираемых элементов и возможности сделать несколько видов перебора.
ОтветитьУдалитьНесколько видов перебора - это простой перебор и перебор с предикатом?
ОтветитьУдалитьВсякие там переборы типа: рандомный, в обратном порядке, батерфляй... - не имеют смысла т.к. порядок элементов всё равно рандомный.
Так. что доступ по индексу низачем не нужен(кроме перебора). А перебор нужен, но его можно зашить в класс и всё. А зачем public доступ по индексу, и public уаление по индексу? - это просто зло.
при удалении элемента в List индексные привязки следующих за ним сохраняются?
ОтветитьУдалитьМои изыскания:
ОтветитьУдалитьhttp://hale32bit.blogspot.com/2011/07/blog-post.html