Наиболее подходящий .net Таймер для планировщика

Question

Мы определили точку доступа в нашем коде, используя CCR timers. Похоже, что если мы ставим в очередь много тысяч таймеров, что код страдает от терминального замедления.

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

Что мы сейчас находим, так это то, что экземпляр SortedList, который мы используем для управления запланированными элементами, записывается с весом абстракций из списка.

У всех таймеров .net страдает проблема увеличения использования ЦП с количеством выставленных элементов или есть более интеллектуально написанная.

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

Answer 1

Попробуйте использовать LinkedList<T>, я уверен, что вы увидите значительное улучшение производительности. Он хорошо подходит для быстрых добавлений и удалений.

Answer 2

Чтобы получить скорейший запланированный элемент, вам необходимо использовать Heap, а не SortedList.

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

Answer 3

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

Если все, о чем вы заботитесь, это следующий предмет, Priority Queue, вероятно, хорошая ставка.

Answer 4

Похоже, вам нужно использовать приоритетную очередь. Priority queues часто реализуются с кучами, но я считаю, что skip lists имеют тенденцию работать лучше. К сожалению, в BCL нет очереди приоритетов, поэтому вам придется писать свои собственные или находить их в другом месте. Этот SortedList собирается убить вашу производительность. Даже если вы решите против очереди приоритетов, вы, вероятно, можете быстро повысить скорость, перейдя в SortedDictionary.

Edit: Причина, почему я предпочел бы очередь приоритет здесь, в отличие от SortedDictionary потому, что абсорбция самого низкого ключа в SortedDictionary являются O (журнал (п)), в отличие от O (1) для приоритетной очереди.

Answer 5

Если вам абсолютно нужна функция сортировки, вы можете рассмотреть использование SortedDictionary вместо SortedList. SortedDictionary - это O (log n) для вставки и remonal, так как внутри он использует дерево.

http://msdn.microsoft.com/en-us/library/5z658b67(VS.80).aspx

Answer 6

Для быстрого исправления, которые могут (или не может) быть достаточно, чтобы переключить отсортированный словарь.

Сортированный список вызовет проблемы, поскольку его базовая структура данных представляет собой массив. Как указывал другой плакат, если вы удаляете из «верхнего» ([0]) отсортированного списка, все остальные элементы должны быть сдвинуты вниз по одному в массиве, поэтому чем больше элементов у вас есть в списке, тем больше дорого его удалить. (так что производительность O (n) или хуже).

В отличие от этого, вставка и удаление в отсортированном словаре - это O (log n), поэтому эффективность удаления должна быть значительно меньше, если у вас много элементов в списке.