Как может быть реализован класс, подобный .ConcurrentBag от NET<T> ?

Question

Я нахожу себя очень заинтригованным существованием ConcurrentBag<T> класс в готовящейся платформе .NET 4.0 framework:

Пакеты полезны для хранения предметов, когда порядок не имеет значения, и, в отличие от наборов, пакеты поддерживают дубликаты.

Мой вопрос заключается в следующем:как эта идея могла бы быть реализована?Большинство коллекций, с которыми я знаком, по сути, представляют собой (под капотом) некоторую форму массива, порядок в котором может не "иметь значения", но есть является порядок (вот почему, даже если в этом нет необходимости, перечисление почти всегда будет проходить через неизмененную коллекцию, будь то List, Queue, Stack, и т.д.в той же последовательности).

Если бы мне пришлось гадать, я мог бы предположить, что внутренне это могло бы быть Dictionary<T, LinkedList<T>>;но это на самом деле кажется довольно сомнительным, учитывая, что не имело бы смысла использовать просто Любой Тип T в качестве ключа.

Чего я ожидаю / надеюсь, так это того, что это на самом деле установленный тип объекта, который уже где-то "выяснили", и что кто-то, кто знает об этом установленном типе, может рассказать мне об этом.Это просто так необычно для меня - одна из тех концепций, которые легко понять в реальной жизни, но трудно перевести в класс, пригодный для использования разработчиком, - вот почему мне любопытно узнать о возможностях.

Редактировать:

Некоторые респонденты предположили, что Bag может быть формой внутренней хэш-таблицы.Это была и моя первоначальная мысль, но я предвидел две проблемы, связанные с этой идеей:

1. Хэш-таблица не так уж полезна, когда у вас нет подходящей функции хэш-кода для рассматриваемого типа.
2. Простое отслеживание "количества" объектов в коллекции - это не то же самое, что хранение объекта.

Как предположил Мета-Найт, возможно, пример сделал бы это более понятным:

public class ExpensiveObject() {
    private ExpensiveObject() {
        // very intense operations happening in here
    }

    public ExpensiveObject CreateExpensiveObject() {
        return new ExpensiveObject();
    }
}

static void Main() {
    var expensiveObjects = new ConcurrentBag<ExpensiveObject>();

    for (int i = 0; i < 5; i++) {
        expensiveObjects.Add(ExpensiveObject.CreateExpensiveObject());
    }

    // after this point in the code, I want to believe I have 5 new
    // expensive objects in my collection

    while (expensiveObjects.Count > 0) {
        ExpensiveObject expObj = null;
        bool objectTaken = expensiveObjects.TryTake(out expObj);
        if (objectTaken) {
            // here I THINK I am queueing a particular operation to be
            // executed on 5 separate threads for 5 separate objects,
            // but if ConcurrentBag is a hashtable then I've just received
            // the object 5 times and so I am working on the same object
            // from 5 threads at the same time!
            ThreadPool.QueueUserWorkItem(DoWorkOnExpensiveObject, expObj);
        } else {
            break;
        }
    }
}

static void DoWorkOnExpensiveObject(object obj) {
    ExpensiveObject expObj = obj as ExpensiveObject;
    if (expObj != null) {
        // some work to be done
    }
}

Answer 1

Если вы посмотрите на детали ConcurrentBag<T>, вы обнаружите, что внутренне это, по сути, настраиваемый связанный список.

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

Answer 2

Здесь есть хорошая информация о ConcurrentBag: http://geekswithblogs.net/BlackRabbitCoder/archive/2011/03/03/c.net-little-wonders-concurrentbag-and-blockingcollection.aspx

Способ, которым работает ConcurrentBag , заключается в использовании преимуществ нового Типа ThreadLocal (нового в System.Потоковая обработка для .NET 4.0), так что у каждого потока, использующего пакет, есть список локальный только для этого потока.

Это означает, что добавление или удаление в локальный список потоков требует очень низкой синхронизации.Проблема возникает в когда поток отправляется для использования элемента но его локальный список пуст.В этом случае сумка выполняет “кражу работы” где она будет красть элемент из другого потока, в котором есть элементы в его списке.Это требует более высокого уровня синхронизации, что добавляет немного накладных расходов к операции take.

Answer 3

Поскольку порядок не имеет значения, ConcurrentBag может использовать хэш-таблицу за кулисами, чтобы обеспечить быстрый поиск данных.Но в отличие от Хэш - набор пакет принимает дубликаты.Возможно, каждый элемент мог бы быть сопряжен со свойством Count, которому присваивается значение 1 при добавлении элемента.Если вы добавите тот же элемент во второй раз, вы могли бы просто увеличить свойство Count этого элемента.

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

Answer 4

Ну, в smalltalk (откуда взялось понятие Пакета) коллекция в основном такая же, как хэш, хотя и допускающая дублирование.Однако вместо того, чтобы хранить дублирующийся объект, он поддерживает "количество вхождений", например, повторное количество каждого объекта.Если ConcurrentBag является точной реализацией, это должно дать вам отправную точку.

Answer 5

Я считаю, что понятие "Сумка" является синонимом понятия "Мультинабор".

Существует ряд реализаций "Bag" / "Multiset" (это Java) с открытым исходным кодом, если вам интересно, как они реализованы.

Эти реализации показывают, что "Сумка" может быть реализована любым количеством способов в зависимости от ваших потребностей.Существуют примеры TreeMultiset, HashMultiset, LinkedHashMultiset, ConcurrentHashMultiset.

Коллекции Google
У Google есть ряд Реализации "мультимножества", один из которых является ConcurrentHashMultiset.

Общее достояние Apache
Apache имеет несколько реализаций "Bag".