Самый быстрый и самый эффективный тип коллекции в C # - PullRequest
Новая
       7

Самый быстрый и самый эффективный тип коллекции в C #

8 голосов
/ 26 марта 2011

Я создаю приложение, в котором требуется, чтобы коллекция содержала около 10 тыс. Строк.

Коллекция будет использоваться в качестве очереди.

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

РЕДАКТИРОВАТЬ на основе комментариев.

Любая существующая коллекция будет полезна.Или отличная коллекция, которая может превзойти любую существующую коллекцию, будет великолепна.

Спасибо

Ответы [ 3 ]

8 голосов
/ 26 марта 2011

Если вы ищете высокопроизводительную систему Put & Get при проверке уникальности (дублирующая проверка), но порядок не имеет значения (не очередь), используйте HashSet<T>

Если функция очереди важнее, используйте Queue<T>

Я не думаю, что есть что-то, что предлагает оба.

6 голосов
/ 26 марта 2011

Существует класс OrderedDictionary , который сохраняет порядок вставки, но позволяет искать значения по ключу.

6 голосов
/ 26 марта 2011

Вы не против потратить O (2n) памяти? Вы можете использовать Очередь <> в сочетании со Словарём <,>. Очередь будет обрабатывать операции очереди и удаления из очереди, а словарь будет обеспечивать уникальные записи. Простой класс-обертка может объединить эти два, и он даст вам O (log n) очереди и время ожидания.

Пример: 

public class SetQueue<T>
{
    private readonly Dictionary<T, bool> duplicates = new Dictionary<T, bool>();
    private readonly Queue<T> queue = new Queue<T>();

    public bool Enqueue(T item)
    {
        if (!duplicates.ContainsKey(item))
        {
            duplicates[item] = true;

            queue.Enqueue(item);

            return true;
        }

        return false;
    }

    public T Dequeue()
    {
        if (queue.Count >0)
        {
            var item = queue.Dequeue();
            if (!duplicates.ContainsKey(item))
                throw new InvalidOperationException("The dictionary should have contained an item");
            else
                duplicates.Remove(item);

            return item;
        }

        throw new InvalidOperationException("Can't dequeue on an empty queue.");
    }
}

Вставка в эту пользовательскую структуру данных проверяет, содержит ли словарь элемент. Эта операция использует метод ContainsKey, который является операцией O (log n). Если элемент уже содержался в структуре данных, метод завершается. Если элемент не содержится, то элемент будет вставлен в очередь, что является постоянной операцией O (1). Он также будет добавлен в словарь. Когда количество словаря меньше емкости, это приблизится к константе, а также к времени вставки O (1). Следовательно, общее время очереди будет O (log n).

То же самое относится и к методу удаления очереди.

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

...