Параллельная очередность приоритетов в .NET 4.0

Ответ 1

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

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

Ответ 2

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

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

Ответ 3

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

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

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;
    }
}

Ответ 4

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

Ответ 5

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

Ответ 6

Параметры:

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

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

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

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

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

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

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

Ответ 7

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

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

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

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

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

Итак, вот оно. Надеюсь, вам понравится.

Ответ 8

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

Документация: Необязательно простую в использовании параллельную очередность приоритетов

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

пакет nuget

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