Коллекция. Содержит Big-O - PullRequest
Новая
       7

Коллекция. Содержит Big-O

0 голосов
/ 30 января 2012

Мне нужно оптимизировать функцию, которая отображает количество аварийных сигналов для системы, которая становится невыносимо медленной, когда она достигает 20 000 аварийных сигналов. (Тревога состоит из тревоги и условия, то есть фактически это 40 000 объектов). Этот номер обновляется каждые 5 секунд.

Теперь, не берите в голову, что единственное, что нужно, это целое число и что предыдущий программист достиг этого путем:

  1. Загрузка каждого аварийного сигнала и состояния из базы данных при каждом вызове (подтвержденном и неподтвержденном)
  2. Перебирайте каждую тревогу, чтобы найти неподтвержденные тревоги (с некоторым пользовательским расширением Linq)
  3. Отправьте этот список неподтвержденных аварийных сигналов и соответствующий список условий в приложение Silverlight
  4. Сравнить список неподтвержденных сигналов тревоги с кэшированным списком неподтвержденных сигналов тревоги
  5. Повторите 4. для условий
  6. Привязать метки к Alarms.Count и Conditions.Count

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

SELECT COUNT(*) as UnAckAlarms
FROM Alarms
WHERE AckTime IS NULL

Но нет, мне было интересно, шаг 4. Там я нашел это: 

foreach (var alarm in loadResult.Entities)
{
    if (!ActiveAlarms.Contains(alarm.AlarmId))
    {
        ActiveAlarms.Add(new AlarmInfo
        (...)

Тревога - это объект, без хэша, насколько я знаю, и поэтому я удивился ... Является ли bigO для Collection .Contains() O (n)? И в этом случае, не будет ли в приведенном выше коде O (n ^ 2)? И если я оптимизирую этот код для O (n) или даже O (1) путем замены всей коллекции, получу ли я увеличение скорости на 0,99%? (40000/400000 ^ 2) Или я должен просто заменить все оператором SQL и переписать основные части приложения?

edit: Итак, некоторые результаты: До оптимизации: 60+ секунд для общего получения После удаления ненужных циклов и пользовательских добавлений: 8 секунд. Время загрузки с сервера составляло ~ 7 секунд, поэтому: После оптимизации на стороне сервера: 0,3 секунды.

Это примерно на 200% больше скорости. :)

Ответы [ 2 ]

3 голосов
/ 30 января 2012

Если предположить, что ActiveAlarms имеет тип Collection или List и не реализован с использованием хэша, то Contains() имеет значение O (n), а приведенный выше код действительно имеет значение O (n ^2).

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

Точное увеличение скорости непредсказуемо.Измерь и выясни, я бы сказал!

Удачи!

1 голос
/ 30 января 2012

Я бы переместил все это в sql.Создайте набор триггеров, которые добавляют / вычитают из промежуточного итога всякий раз, когда тревога добавляется / удаляется / подтверждается / и т.д.Работающий цикл просто для подсчета вещей не нужен вообще

...