Есть ли столь же эффективный способ
обработать все возможные пары, если
Список используется вместо
массив
A List<T> - это просто модная обертка вокруг T[], которая иногда изменяет размер, когда превышает объем вашего списка.
Ваш алгоритм уже оптимален. Если вы хотите использовать его с List<T>, просто измените объявление с void MyMethod (MyThing[] myArray) на void MyMethod (List<MyThing> myArray).
Есть ли лучшая коллекция для этого
конкретное использование, чем список <>? Я не
нужна сортировка, я только создаю новый
коллекции, очистить существующие
коллекции, добавить в коллекцию,
перечислить коллекцию или процесс
спаривания, как указано выше. Какую бы коллекцию
Я использую, мне может понадобиться от 100 до 10000
их, поэтому они не могут быть слишком дорогими, чтобы
создать / сохранить.
Сначала давайте попытаемся понять некоторые вещи о структурах данных:
Внутри List<T> хранится массив размера N; Когда вы добавляете элементы в массив, если вы превышаете размер внутреннего массива, то в List будет добавлен новый массив размером N * 2, скопируйте элементы и добавьте новый элемент. Изменение размера имеет наихудший случай O (n); однако удвоение массива при каждом изменении размера означает, что вам нужно добавить в два раза больше элементов, чем раньше, чтобы вызвать наихудший вариант поведения. У списков есть свойство, которое дает им амортизированных O (1) вставок, что означает, что вы можете выполнить n операций за O (n) время.
Обычно LinkedList имеет очень быструю вставку. Насколько мне известно, он не использует базовый массив, а скорее имеет набор узлов, содержащих указатели Next и Previous, которые указывают на смежные элементы в коллекции. С положительной стороны, вставка в наихудшем случае - это O (1), но иногда связанные списки могут иметь теоретически меньшую, чем оптимальная производительность, из-за плохого местоположения ссылки (то есть смежные элементы в списке не соседствуют в памяти).
Я лично никогда не видел сценарий, в котором перебор массива был бы заметно медленнее, чем связанный список. Прежде чем вы начнете задумываться о локальности ссылок, я бы определенно рассмотрел список, связанный с хо-хумом, перед любым другим предложением.
Итак, с учетом сказанного, если вы действительно хотите получить коллекцию динамического размера с хорошей привязкой, но также поддерживает быструю вставку, то попробуйте VList . Он имеет оба свойства, которые вы ищете, и его очень легко написать:
public class VList<T> : IEnumerable<T>
{
VListNode<T> RootNode;
public int Count { get; private set; }
public VList() : this(4) { }
public VList(int size)
{
RootNode = new VListNode<T>(4, null);
}
public void Add(T element)
{
if (RootNode.Count == RootNode.MaxSize)
RootNode = new VListNode<T>(RootNode.MaxSize * 2, RootNode);
RootNode.Add(element);
Count++;
}
public void Clear()
{
RootNode = new VListNode<T>(4, null);
}
public IEnumerator<T> GetEnumerator()
{
VListNode<T> node = RootNode;
while (node != null)
{
foreach (T t in node)
yield return t;
node = node.Next;
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
public class VListNode<T> : IEnumerable<T>
{
readonly T[] Elements;
public VListNode<T> Next { get; private set; }
public int Count { get; private set; }
public int MaxSize { get; private set; }
public VListNode(int size, VListNode<T> next)
{
MaxSize = size;
Elements = new T[size];
Next = next;
}
public void Add(T element)
{
Elements[Count] = element;
Count++;
}
public IEnumerator<T> GetEnumerator()
{
// iterate in reverse to return elements in LIFO order.
for (int i = Count - 1; i >= 0; i--)
yield return Elements[i];
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}
Простая реализация, описанная выше, должна поддерживать Add in O (1), сохраняя при этом хорошую ссылку.