Очередь с одновременным приоритетом в .NET 4.0

Question

Похоже, в .NET 4.0 есть много улучшений, связанных с параллелизмом, которые могут полагаться на параллельные очереди с приоритетами.Есть ли реализация очереди с достойным приоритетом внутри фреймворка, доступная для повторного использования?

Answer 1

В msdn есть реализация как часть "Образцов для параллельного программирования с .NET Framework". См. ParallelExtensionsExtras .

Прямая ссылка на исходный код файла ConcurrentPriorityQueue.cs

Answer 2

Возможно, вам придется свернуть свой собственный. Относительно простым способом было бы иметь массив регулярных очередей с уменьшением приоритета.

Как правило, вы вставляете в очередь соответствующий приоритет. Затем, на стороне потребителя, вы должны перейти вниз по списку с наивысшего приоритета к низшему, проверяя, не является ли очередь непустой, и потребляя запись, если это так.

Answer 3

Может быть, вы можете использовать мою собственную реализацию PriorityQueue.Он реализует намного больше, чем обычные функции push / pop / peek, которые я реализовывал всякий раз, когда обнаруживал необходимость в этом.Он также имеет блокировки для параллелизма.

Комментарии к коду высоко ценятся:)

public class PriorityQueue<T> where T : class
{
    private readonly object lockObject = new object();
    private readonly SortedList<int, Queue<T>> list = new SortedList<int, Queue<T>>();

    public int Count
    {
        get
        {
            lock (this.lockObject)
            {
                return list.Sum(keyValuePair => keyValuePair.Value.Count);
            }
        }
    }

    public void Push(int priority, T item)
    {
        lock (this.lockObject)
        {
            if (!this.list.ContainsKey(priority))
                this.list.Add(priority, new Queue<T>());
            this.list[priority].Enqueue(item);
        }
    }
    public T Pop()
    {
        lock (this.lockObject)
        {
            if (this.list.Count > 0)
            {
                T obj = this.list.First().Value.Dequeue();
                if (this.list.First().Value.Count == 0)
                    this.list.Remove(this.list.First().Key);
                return obj;
            }
        }
        return null;
    }
    public T PopPriority(int priority)
    {
        lock (this.lockObject)
        {
            if (this.list.ContainsKey(priority))
            {
                T obj = this.list[priority].Dequeue();
                if (this.list[priority].Count == 0)
                    this.list.Remove(priority);
                return obj;
            }
        }
        return null;
    }
    public IEnumerable<T> PopAllPriority(int priority)
    {
        List<T> ret = new List<T>();
        lock(this.lockObject)
        {
            if (this.list.ContainsKey(priority))
            {
                while(this.list.ContainsKey(priority) && this.list[priority].Count > 0)
                    ret.Add(PopPriority(priority));
                return ret;
            }
        }
        return ret;
    }
    public T Peek()
    {
        lock (this.lockObject)
        {
            if (this.list.Count > 0)
                return this.list.First().Value.Peek();
        }
        return null;
    }
    public IEnumerable<T> PeekAll()
    {
        List<T> ret = new List<T>();
        lock (this.lockObject)
        {
            foreach (KeyValuePair<int, Queue<T>> keyValuePair in list)
                ret.AddRange(keyValuePair.Value.AsEnumerable());
        }
        return ret;
    }
    public IEnumerable<T> PopAll()
    {
        List<T> ret = new List<T>();
        lock (this.lockObject)
        {
            while (this.list.Count > 0)
                ret.Add(Pop());
        }
        return ret;
    }
}

Answer 4

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

Answer 5

Проверка Потокобезопасные коллекции в .NET Framework 4 и их характеристики производительности , но у AFAIK нет готовых к использованию очередей приоритетов.Все новые многопоточные коллекции не поддерживают порядок, но вы можете создать свои собственные поверх них.Посмотри на путь Стивена.

Answer 6

Хорошо, прошло 7 лет, но для потомков я бы хотел ответить своей реализацией.

Документация: опционально ожидаемый простой в использовании параллельный приоритет очереди

Исходные коды: github

пакет nuget

• Без блокировки,
• High Concurrent,
• универсальный в типе хранимых элементов,
• универсальный в типе приоритета, но ограниченный приоритетами, представленными перечислением .net, строго типизированным приоритетом,
• явно определенный нисходящий порядок приоритетов во время построения,
• способность обнаруживать количество элементов и количество элементов на уровне приоритета,
• способность удалять из очереди - в порядке убывания приоритетов,
• возможность отменять уровень приоритета в очереди,
• потенциальноожидаемый,
• потенциально на основе приоритетов ожидаемый,

Answer 7

Недавно я создавал конечный автомат, в котором мне требовались события с меткой времени. Вместо простого тика часов мне нужны были синхронизированные события с их собственными идентификаторами, чтобы можно было отличить одно событие от другого.

Исследование этой проблемы привело меня к идее использования очереди с приоритетами. Я мог поставить в очередь синхронизированные события вместе с их информацией в любом порядке; очередь приоритетов позаботится о правильном порядке событий. Таймер будет периодически проверять приоритетную очередь, чтобы определить, наступило ли время для события в начале очереди. Если это так, он удаляет событие из очереди и вызывает связанный с ним делегат. Этот подход был именно тем, что я искал.

Поиск здесь в CodeProject

https://www.codeproject.com/Articles/13295/A-Priority-Queue-in-C

Я обнаружил, что класс приоритетной очереди [^] уже был написан. Однако мне пришло в голову, что я могу легко написать свой собственный, используя моего старого друга, список пропусков. Это имело бы преимущество в том, что операция удаления очереди заняла бы только O (1) время, в то время как операция очереди все еще была бы log (n) в среднем. Я думал, что использование списков пропусков таким образом было достаточно новым, что заслуживает отдельной статьи.

Так что вот оно. Надеюсь, вам будет интересно.

Answer 8

Параметры:

1) Если ваша очередь никогда не станет большой, используйте кучу и заблокируйте всю структуру для каждой вставки и удаления.

2) Если ваша очередь станет большой, вы можете использовать алгоритм, подобный следующему:

http://www.research.ibm.com/people/m/michael/ipl-1996.pdf

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

3) Если вы стремитесь полностью избежать блокировок, другой алгоритм, упомянутый в ссылке выше, предлагает использовать очередь запросов FIFO (легко реализуемую без блокировок) и отдельный поток, который является единственной вещью, которая касается кучи , Вам нужно измерить, чтобы увидеть, как издержки переключения фокуса между потоками с использованием объектов синхронизации сравниваются с издержками простой прямой блокировки.

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

Надеюсь, это поможет: -)