Сбор с очень быстрой итерацией и хорошим добавлением и удалением скоростей

Question

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

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

Я буду хранить uint s (но может быть int с при необходимости) в коллекции.Хотя общее решение было бы хорошо, так как я уверен, что в будущем у меня возникнет такая необходимость.

Коллекция .net была бы идеальной, если бы не было чего-то более легкого и открытого источника, было бы здорово.

Существует ли класс коллекции, который бы соответствовал моим потребностям?Если нет, то как бы мне создать его?

---

Чтобы уточнить, это идентификаторы объектов, которые класс должен обрабатывать каждый кадр.Они обычно добавляются в порядке возрастания с пробелами.Там нет верхнего предела.Любой может быть удален, что может оставить пробелы.
Порядок итераций не совсем важен, но он был бы очень полезен (особенно для отладки), если бы он был в согласованном порядке.

Answer 1

У меня есть два предложения:

Во-первых, как насчет использования Reflector или ILSpy для просмотра Generic List<T>?Я предполагаю, что реализация не в CF или вы могли бы использовать его.Generic List<T> поддерживает массив и использует алгоритм удвоения, начиная с массива длиной 4, каждый вызов .Add over Capacity заставляет его удваиваться и выполнять Array.Copy в новый массив.Размер не изменится, если вы явно не установите Capacity на ноль, так что будьте осторожны с точки зрения памяти.Добавление - это одно, но каждое удаление приведет к тому, что массив будет скопирован и смещен влево после удаления индекса.

Второе предложение заключается в следующем: как насчет создания пользовательского класса, который для этого обрабатывает целочисленный массив, который использует аналогичный двойной алгоритм (или четырехкратное увеличение) для Generic List<T> (для обработки изменения размера), но начинается сскажем, размер 256. Вы можете добавить целочисленные идентификаторы объекта к этому из последовательности так быстро, как вам нравится, и это не будет удваиваться слишком часто.Вы также можете смоделировать удаление, указав (int) -1 или uint.MaxValue как «нулевой индекс», означающий отсутствие Array.Copy при удалении.Затем примените некую быструю сортировку для каждого кадра, чтобы отсортировать массив индекса объекта перед рисованием.Если вы сортируете по возрастанию, все ваши -1 появятся в начале (или uint.MaxValues ​​в конце) и могут быть проигнорированы.Вы можете периодически «собирать» индексный массив, изменяя размеры и удаляя предыдущие -1 в отдельном потоке (будьте осторожны - используйте блокировку;)

Что вы думаете?Просто подумав, что вы будете компенсировать некоторые вычисления один раз за кадр для быстрой сортировки (не дорого на xbox, по сравнению с выделением / сбором памяти при каждом удалении и некоторых добавлениях (дорого).

UPDATE - BlockArray - Listгде T - массив фиксированного размера

Еще один комментарий по этому поводу.Недавно я экспериментировал с наиболее эффективной структурой данных для динамически изменяемых списков и экспериментально обнаружил, что блоки массивов - это класс, который поддерживается списком T [], где каждый T [] был массивом блока фиксированного размера, например512, 4096, 8192 как несколько преимуществ над простым списком .

Я обнаружил, что реализация Add () (где размер неизвестен) в спискезначительно превосходил Add () для List , особенно когда общий размер стал больше.Это связано с алгоритмом удвоения List , который запрашивает новый массив в 2 раза больше старого, а memcpy - старым массивом при превышении размера.

Скорость итерации аналогична.Предварительное выделение (предварительно определенная емкость) было намного медленнее, чем List для небольших блоков (512), но лишь немного медленнее для больших блоков (8192).Удаление проблематично, так как требует копирования / сдвига влево многих блоков.

Что интересно в списке(список блоков), вы можете кэшировать / объединять блоки.Если достаточно малы, блоки T [] помещаются в кучу небольших объектов (в пользу сжатия, более быстрого выделения), могут помещаться в кэш L2, и несколько блоков могут быть предварительно выделены и объединены в пул

Answer 2

А как насчет пользовательского класса, SparseList :

• списка, который позволяет удалять элементы путем установки пропущенных значений на ноль (или для SparseValueList, специальноготакие значения, как -1 (как решение д-ра ABT), 0 (по умолчанию (T)), или int.MinValue, или uint.MaxValue,) и
• , затем ведение списка удаленных индексов (стек ).Затем, когда вам нужно добавить в список, он извлекает удаленный индекс из стека и добавляет туда значение.(Для многопоточности, возможно, ConcurrentQueue будет другой идеей.)
• перечислитель может пропускать удаленные элементы (для поддержки foreach )
• предметы могут быть удалены из коллекции во время перечисления !(Я должен сделать это много, так что это хорошо.)
• indexer предоставляет необработанный доступ к списку, который содержит нули.Так что если вы используете цикл for (;;), будьте готовы отфильтровать нули .
• call Compact () , если / когда вы хотите удалить все нули
• Если во время игры никто не называет компактный, меня беспокоит перебор огромного числа нулей.Так что для экспериментальной альтернативы компактному, смотрите SparseListCleaningEnumerator: автоматически сжимайте список каждый раз, когда он перечисляется, по крайней мере для однопоточных ситуаций: когда MoveNext удаляется от элемента, он просматривает стек, чтобы увидеть, меньше ли индекс, иесли это так, он назначает элемент нижнему индексу, удаляя его из текущей позиции, что приведет к сокращению списка.Балансировка может занять много итераций и включать несколько ходов перед оптимизацией, если только стек не заменен сортированным списком или стек не сортируется время от времени.Если последнее значение равно нулю, это не сработает, потому что индекс будет похоронен в свободном стеке индексов (замена стека чем-то отсортированным позволит избежать этого).

Я реализовал это (нееще не проверено), но я храню фактические ссылки на мои игровые объекты вместо идентификаторов, так что вам нужно как-то адаптировать это для int или Nullable.(Хорошо, чтобы убедиться, что я отвечаю на требование int / uint вашего вопроса, я также добавил SparseValueList , который немного отличается, используя default (T) вместо null. Это означает, что вы не можете использовать 0 в списке.) Возможно, вы могли быуберите управление версиями, если вы считаете, что оно вам не нужно - большинство игр может и не понадобиться.

/// <summary>
/// Specifying null as value has unspecified results.
/// CopyTo may contain nulls.
/// </summary>
/// <typeparam name="T"></typeparam>
public class SparseList<T> : IList<T>
    where T : class
{
    int version = 0;
    List<T> list = new List<T>();
    Stack<int> freeIndices = new Stack<int>();

    public int Capacity { get { return list.Capacity; } set { list.Capacity = value; } }

    public void Compact()
    {
        var sortedIndices = freeIndices.ToList();

        foreach (var i in sortedIndices.OrderBy(x => x).Reverse())
        {
            list.RemoveAt(i);
        }
        freeIndices.Clear();
        list.Capacity = list.Count;
        version++; // breaks open enumerators
    }

    public int IndexOf(T item)
    {
        return list.IndexOf(item);
    }

    /// <summary>
    /// Slow (forces a compact), not recommended
    /// </summary>
    /// <param name="index"></param>
    /// <param name="item"></param>
    public void Insert(int index, T item)
    {
        // One idea: remove index from freeIndices if it's in there.  Stack doesn't support this though.
        Compact(); // breaks the freeIndices list, so apply it before insert
        list.Insert(index, item);
        version++; // breaks open enumerators
    }

    public void RemoveAt(int index)
    {
        if (index == Count - 1) { list.RemoveAt(index); }
        else { list[index] = null; freeIndices.Push(index); }
        //version++; // Don't increment version for removals
    }

    public T this[int index]
    {
        get
        {
            return list[index];
        }
        set
        {
            if (value == null) throw new ArgumentNullException();
            list[index] = value;
        }
    }

    public void Add(T item)
    {
        if (item == null) throw new ArgumentNullException();

        if (freeIndices.Count == 0) { list.Add(item); return; }

        list[freeIndices.Pop()] = item;
        //version++; // Don't increment version for additions?  It could result in missing the new value, but shouldn't break open enumerators
    }

    public void Clear()
    {
        list.Clear();
        freeIndices.Clear();
        version++;
    }

    public bool Contains(T item)
    {
        if (item == null) return false;
        return list.Contains(item);
    }

    /// <summary>
    /// Result may contain nulls
    /// </summary>
    /// <param name="array"></param>
    /// <param name="arrayIndex"></param>
    public void CopyTo(T[] array, int arrayIndex)
    {
        list.CopyTo(array, arrayIndex);
    }
    //public void CopyNonNullTo(T[] array, int arrayIndex)
    //{
    //}

    /// <summary>
    /// Use this for iterating via for loop.
    /// </summary>
    public int Count  { get { return list.Count; } }

    /// <summary>
    /// Don't use this for for loops!  Use Count.
    /// </summary>
    public int NonNullCount
    {
        get { return list.Count - freeIndices.Count; }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    public bool Remove(T item)
    {
        int i = list.IndexOf(item);
        if (i < 0) return false;

        if (i == list.Count - 1)
        {
            // Could throw .  Could add check in 
            list.RemoveAt(i);
        }
        else
        {
            list[i] = null;
            freeIndices.Push(i);
        }
        //version++;  // Don't increment version for removals
        return true;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new SparseListEnumerator(this);
    }

    private class SparseListEnumerator : IEnumerator<T>, IRemovingEnumerator
    {
        SparseList<T> list;
        int version;
        int index = -1;

        public SparseListEnumerator(SparseList<T> list)
        {
            this.list = list;
            this.version = list.version;

            //while (Current == null && MoveNext()) ;
        }

        public T Current
        {
            get {
                if (index >= list.Count) return null; // Supports removing last items of collection without throwing on Enumerator access
                return list[index]; 
            }
        }

        public void Dispose()
        {
            list = null;
        }

        object IEnumerator.Current
        {
            get { return Current; }
        }

        public bool MoveNext()
        {
            do
            {
                if (version != list.version) { throw new InvalidOperationException("Collection modified"); }
                index++;
                return index < list.Count;
            } while (Current == null);
        }

        public void Reset()
        {
            index = -1;
            version = list.version;
        }

        /// <summary>
        /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return null.
        /// </summary>
        public void RemoveCurrent()
        {
            list.RemoveAt(index);
        }
    }

    private class SparseListCleaningEnumerator : IEnumerator<T>, IRemovingEnumerator
    {
        SparseList<T> list;
        int version;
        int index = -1;

        public SparseListCleaningEnumerator(SparseList<T> list)
        {
            this.list = list;
            this.version = list.version;

            //while (Current == null && MoveNext()) ;
        }

        public T Current
        {
            get
            {
                if (index >= list.Count) return null; // Supports removing last items of collection without throwing on Enumerator access
                return list[index];
            }
        }

        public void Dispose()
        {
            list = null;
        }

        object IEnumerator.Current
        {
            get { return Current; }
        }

        public bool MoveNext()
        {
            do
            {
                if (version != list.version) { throw new InvalidOperationException("Collection modified"); }
                if (index > 0
                    && Current != null // only works for values that are set, otherwise the index is buried in the free index stack somewhere
                    )
                {
                    int freeIndex = list.freeIndices.Peek();
                    if (freeIndex < index)
                    {
                        list.freeIndices.Pop();
                        list[freeIndex] = list[index];
                        list.RemoveAt(index);
                    }
                }
                index++;
                return index < list.Count;
            } while (Current == null);
        }

        public void Reset()
        {
            index = -1;
            version = list.version;
        }

        /// <summary>
        /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return null.
        /// </summary>
        public void RemoveCurrent()
        {
            list.RemoveAt(index);
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

/// <summary>
/// Like SparseList but Supports value types, using default(T) in place of null.
/// This means values of default(T) are not permitted as values in the collection.
/// CopyTo may contain default(T).
/// TODO: Use EqualityComparer&lt;T&gt;.Default instead of default(T).Equals()
/// </summary>
/// <typeparam name="T"></typeparam>
public class SparseValueList<T> : IList<T>
{
    int version = 0;
    List<T> list = new List<T>();
    Stack<int> freeIndices = new Stack<int>();

    public int Capacity { get { return list.Capacity; } set { list.Capacity = value; } }

    public void Compact()
    {
        var sortedIndices = freeIndices.ToList();

        foreach (var i in sortedIndices.OrderBy(x => x).Reverse())
        {
            list.RemoveAt(i);
        }
        freeIndices.Clear();
        list.Capacity = list.Count;
        version++; // breaks open enumerators
    }

    public int IndexOf(T item)
    {
        return list.IndexOf(item);
    }

    /// <summary>
    /// Slow (forces a compact), not recommended
    /// </summary>
    /// <param name="index"></param>
    /// <param name="item"></param>
    public void Insert(int index, T item)
    {
        // One idea: remove index from freeIndices if it's in there.  Stack doesn't support this though.
        Compact(); // breaks the freeIndices list, so apply it before insert
        list.Insert(index, item);
        version++; // breaks open enumerators
    }

    public void RemoveAt(int index)
    {
        if (index == Count - 1) { list.RemoveAt(index); }
        else { list[index] = default(T); freeIndices.Push(index); }
        //version++; // Don't increment version for removals
    }

    public T this[int index]
    {
        get
        {
            return list[index];
        }
        set
        {
            if (default(T).Equals(value)) throw new ArgumentNullException();
            list[index] = value;
        }
    }

    public void Add(T item)
    {
        if (default(T).Equals(item)) throw new ArgumentNullException();

        if (freeIndices.Count == 0) { list.Add(item); return; }

        list[freeIndices.Pop()] = item;
        //version++; // Don't increment version for additions?  It could result in missing the new value, but shouldn't break open enumerators
    }

    public void Clear()
    {
        list.Clear();
        freeIndices.Clear();
        version++;
    }

    public bool Contains(T item)
    {
        if (default(T).Equals(item)) return false;
        return list.Contains(item);
    }

    /// <summary>
    /// Result may contain default(T)'s
    /// </summary>
    /// <param name="array"></param>
    /// <param name="arrayIndex"></param>
    public void CopyTo(T[] array, int arrayIndex)
    {
        list.CopyTo(array, arrayIndex);
    }
    //public void CopyNonNullTo(T[] array, int arrayIndex)
    //{
    //}

    /// <summary>
    /// Use this for iterating via for loop.
    /// </summary>
    public int Count { get { return list.Count; } }

    /// <summary>
    /// Don't use this for for loops!  Use Count.
    /// </summary>
    public int NonNullCount
    {
        get { return list.Count - freeIndices.Count; }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    public bool Remove(T item)
    {
        int i = list.IndexOf(item);
        if (i < 0) return false;

        if (i == list.Count - 1)
        {
            // Could throw .  Could add check in 
            list.RemoveAt(i);
        }
        else
        {
            list[i] = default(T);
            freeIndices.Push(i);
        }
        //version++;  // Don't increment version for removals
        return true;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return new SparseValueListEnumerator(this);
    }

    private class SparseValueListEnumerator : IEnumerator<T>, IRemovingEnumerator
    {
        SparseValueList<T> list;
        int version;
        int index = -1;

        public SparseValueListEnumerator(SparseValueList<T> list)
        {
            this.list = list;
            this.version = list.version;

            //while (Current == default(T) && MoveNext()) ;
        }

        public T Current
        {
            get
            {
                if (index >= list.Count) return default(T); // Supports removing last items of collection without throwing on Enumerator access
                return list[index];
            }
        }

        public void Dispose()
        {
            list = null;
        }

        object IEnumerator.Current
        {
            get { return Current; }
        }

        public bool MoveNext()
        {
            do
            {
                if (version != list.version) { throw new InvalidOperationException("Collection modified"); }
                index++;
                return index < list.Count;
            } while (default(T).Equals(Current));
        }

        public void Reset()
        {
            index = -1;
            version = list.version;
        }

        /// <summary>
        /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return default(T).
        /// </summary>
        public void RemoveCurrent()
        {
            list.RemoveAt(index);
        }
    }

    private class SparseValueListCleaningEnumerator : IEnumerator<T>, IRemovingEnumerator
    {
        SparseValueList<T> list;
        int version;
        int index = -1;

        public SparseValueListCleaningEnumerator(SparseValueList<T> list)
        {
            this.list = list;
            this.version = list.version;

            while (default(T).Equals(Current) && MoveNext()) ;
        }

        public T Current
        {
            get
            {
                if (index >= list.Count) return default(T); // Supports removing last items of collection without throwing on Enumerator access
                return list[index];
            }
        }

        public void Dispose()
        {
            list = null;
        }

        object IEnumerator.Current
        {
            get { return Current; }
        }

        public bool MoveNext()
        {
            do
            {
                if (version != list.version) { throw new InvalidOperationException("Collection modified"); }
                if (index > 0 
                    && (!default(T).Equals(Current)) // only works for values that are set, otherwise the index might be buried in the stack somewhere
                    )
                {
                    int freeIndex = list.freeIndices.Peek();
                    if (freeIndex < index)
                    {
                        list.freeIndices.Pop();
                        list[freeIndex] = list[index];
                        list.RemoveAt(index);
                    }
                }
                index++;
                return index < list.Count;
            } while (default(T).Equals(Current));
        }

        public void Reset()
        {
            index = -1;
            version = list.version;
        }

        /// <summary>
        /// Accessing Current after RemoveCurrent may throw a NullReferenceException or return default(T).
        /// </summary>
        public void RemoveCurrent()
        {
            list.RemoveAt(index);
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Answer 3

Как насчет использования Mono's HashSet<T>?

https://github.com/mono/mono/blob/master/mcs/class/System.Core/System.Collections.Generic/HashSet.cs

Он лицензирован в соответствии с MIT X11, который является разрешающей лицензией.

---

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

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

Существует также коллекция SortedSet<T>, но я не знаю, какие у нее характеристики производительности.