Самый быстрый способ перебора стека в c #

Question

Мне кажется, что использование GetEnumerator () и приведение IEnumerator.Current стоит дорого. Есть лучшие предложения?

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

После размышлений:
Будет ли универсальный стек лучше, чтобы не требовалось приведение?

Answer 1

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

Обратите внимание, что если вы хотите прочитать данные только один раз (т. Е. Вы счастливы использовать стек), то этот может быть быстрее (избегая накладных расходов перечислителя); YMMV.

    Stack<T> stack = null;
    while (stack.Count > 0)
    {
        T value = stack.Pop();
        // process value
    }

Answer 2

Делали ли вы какие-либо тесты, или они просто инстинктивные чувства?

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

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

EDIT:

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

Answer 3

Да, использование универсального стека избавит от приведения.

Answer 4

Если вам нужна функциональность стека (в отличие от списка или другого типа коллекции), тогда да, используйте универсальный стек. Это немного ускорит процесс, так как компилятор пропустит приведение во время выполнения (потому что оно гарантировано во время компиляции).

Stack<MyClass> stacky = new Stack<MyClass>();

foreach (MyClass item in stacky)
{
    // this is as fast as you're going to get.
}

Answer 5

перечисление по универсальному IEnumerable<T> или IEnumerator<T> не создает приведение, если итерационная переменная имеет тип T, так что да, использование универсального будет быстрее в большинстве случаев, но универсальные очень тонкие проблемы, особенно при использовании с типами значений.

У Рико Мариани (архитектора производительности Microsoft) есть несколько постов с подробным описанием различий и основ

• Шесть вопросов об универсальности и производительности
• Тест производительности № 7 - Общие улучшения и затраты
• Тест производительности № 7 - Общие улучшения и затраты - Решение

Answer 6

Что касается скорости, есть несколько переменных, зависит от контекста. Например, в кодовой базе с автоматическим управлением памятью, такой как C #, вы можете получить пики распределения, которые могут повлиять на частоту кадров в чем-то вроде, скажем, игры. Хорошая оптимизация, которую вы можете сделать для этого вместо foreach - это перечислитель с циклом while:

var enumerator = stack.GetEnumerator();

while(enumerator.MoveNext ()) {
  // do stuff with enumerator value using enumerator.Current
  enumerator.Current = blah
}

Что касается тестов ЦП, это, вероятно, не быстрее, чем foreach, но foreach может иметь непреднамеренные скачки распределения, которые в конечном итоге могут "замедлить" производительность вашего приложения.

Answer 7

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