Затраты на перечисление по сравнению с индексаторами в производительности строк

Question

Мне было поручено ускорить обработку текста / нормализацию нашего кода, и было несколько разделов, которые имели несколько настраиваемых списков «если увидишь, замени на это», и они были реализованы с большими стеками регулярные выражения. Это выглядело как хорошее место для начала - и это было.

Я реализовал простой Tr ie, загруженный с записями конфигурации, а затем имел функцию

Match (string raw, int idx = 0)

, которая просматривала необработанные вход, просматривая Tr ie на совпадения.

Мой первый черновик функции соответствия использовал a для l oop и индексатор (т.е.

TrieNode node = Root;
for (; idx < raw.Length; idx++)
{
    TrieNode next;
    if (node.TryGetValue(raw[idx], out next))
    ...

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

Я хотел очистить и обобщить Tr ie, возможно, сделать его настраиваемым для символов или слов в качестве токенов, и после всех обобщений я заменил выше с

foreach (var c in idx > 0 ? raw.Skip(idx) : raw)
{
    ...

и был удивлен, увидев, сколько накладных расходов вызвало изменение в итерации. Я ожидал, что будут некоторые издержки, но метод foreach был примерно в 100 раз медленнее (4300 мс на цикл из 100 статей). против 40 мс с for для l oop) - только это изменение само по себе.

Я видел много статей из разных периодов времени, в которых говорилось: «Конечно, Linq и перечислители сосут!» для «alwa». Вы используете foreach, потому что производительность достаточно близка, а foreach круче ".

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

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

Я нашел дискуссия о том, должен ли String реализовывать IReadOnlyList или нет, и кажется, что он мог бы быть лучшим из обоих миров, но его не существует.

Кто-нибудь еще удивляется, что такое количество накладных расходов?

Answer 1

Меня не удивляет, что Skip на несколько порядков медленнее, поскольку оно будет равно O (n) (существенно увеличивая целое число, пока вы не достигнете idx), по сравнению с O (1) для прямого индексатора.

Я бы не стал обобщать это как "Linq sucks - use foreach". Вы можете функционально реализовать тот же код, что и Skip в вашем foreach, и получить примерно те же результаты. Проблема не в том, что вы используете Linq, а в том, что вы используете Skip в коллекции, которая поддерживает прямой доступ.

Если вы хотите обобщить ее, чтобы использовать либо символы, либо слова в качестве токенов может быть проще всего преобразовать raw в List<T> и поддерживать либо список символов, либо список строк - с тем, что у вас есть, не должно быть существенной разницы в производительности между этими двумя.