Лучшая структура данных C # для случайного порядка населения?

Question

В C # у меня есть сценарий использования, где у меня есть отображение от int s до коллекций.

• int s - это плотный (но не упакованный) набор от 1 до n, где n неизвестно.
• Ячейки будут загружены в случайном порядке.
• предельная стоимость каждой ячейки должна быть идеальной (например, List<T> или T[])
• Я бы хотел заполнить ячейки по умолчанию

Какова лучшая структура для этого?

A List<T> будет работать хорошо (лучше в космосе, чем Dictionary<>) и, исходя из этого, я могу получить многое из того, что хочу, но есть ли что-то лучше? Как в лучшем коде есть код, который вы не пишете.

Answer 1

A Dictionary<int, Cell> звучит как хороший матч для меня. Или вы можете использовать List<Cell> довольно легко, и просто убедитесь, что вы расширяете его при необходимости:

public static void EnsureCount<T>(List<T> list, int count)
{
    if (list.Count > count)
    {
        return;
    }
    if (list.Capacity < count)
    {
        // Always at least double the capacity, to reduce
        // the number of expansions required
        list.Capacity = Math.Max(list.Capacity*2, count);
    }
    list.AddRange(Enumerable.Repeat(default(T), list.Capacity-list.Count));
}

Answer 2

Если вы хотите быть настоящим фанатом, один из вариантов - написать класс фасадов, который обеспечивает стратегию для множества различных картографов. Сделайте так, чтобы он использовал статически определенный массив, когда N <некоторое значение и когда нагрузка (упакованность) превышает некоторый порог. Поменяйте его на дерево или словарь, когда пройдете определенные пороги. </p>

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

Ура! * * 1005