Информация об изменениях

Сообщение Задолбал Dick Seek со своей "невнимательностью" от 24.11.2025 16:51

Изменено 24.11.2025 23:12 VladD2

Задолбал Dick Seek со своей "невнимательностью"
А точнее — неспособностью анализировать алгоритмы. Вот, из последнего:
Анализируем функцию
  функция 
        private static void FoundKey(string source, int index, LinkedList<string> keys, ref string foundKey)
        {
            char ch = source[index];


            var node = keys.First;
            while (node != null)
            {
                var key = node.Value;

                var endOfKeyReached = index + 1 == key.Length;
                var lastCharsEquals = key[index] == ch;

                if (endOfKeyReached && lastCharsEquals)
                    foundKey = key;

                if (false == lastCharsEquals
                    || endOfKeyReached)
                {
                    keys.Remove(node);
                }

                node = node.Next;
            }
        }

Спрашиваю про проблемы производительности.

Q:
Насколько эта функция эффективна в плане скорости и потребления памяти? Можно ли эффективнее?

  получаю вот такой ответ

Проблемы текущей реализации:
1. Сложность O(n²) в худшем случае
Для каждого символа строки (source) вы проходите по всем ключам (keys)

Если ключи длинные, это становится очень медленно

2. Неэффективная структура данных
LinkedList — медленный доступ, нет быстрого поиска

Удаление из середины списка — O(n) операций

3. Избыточные проверки
csharp
var endOfKeyReached = index + 1 == key.Length;
var lastCharsEquals = key[index] == ch;
Вы проверяете ВСЕ ключи на каждом символе, даже те, которые уже не могут совпасть.


И это сразу

фэйл!

Потому что в процессе выполнения алгоритма не будет продвижения по source дальше чем длинна самого длинного ключа, т.о. сложность составляет O(L × n), где L — длина самого длинного ключа, n — количество ключей

Обоснование:
Алгоритм проверяет только первые L символов source — именно поэтому длинна source в этой формуле не участвует.
После позиции L-1 все ключи либо найдены, либо отсеяны — дальнейшие символы source не обрабатываются

Удаление из середины списка — O(n) операций

Двойной фэйл!

Remove(LinkedListNode<T>) имеет сложность O(1) — он его перепутал с методом bool Remove(T value), который действительно имеет сложность O(n)

Спрашиваю, изменится ли ситуация, если удаление из середины будет O(1).
Далее, напоминаю, что ключи таки удаляются:

Q:
Пункт 1 — неверно: заведомо несовпадающие ключи удаляются. Посмотри на эти строки
                if (false == lastCharsEquals
                    || endOfKeyReached)
                {
                    keys.Remove(node);
                }

Подумай ещё раз.


A:

Вы абсолютно правы! Я был невнимателен. Давайте переанализируем.


  и снова фэйл!

Вы абсолютно правы! Я был невнимателен. Давайте переанализируем.
## Текущий алгоритм работает умнее, чем я initially предположил:

// Ключ НЕ совпал по текущему символу ИЛИ ключ полностью найден
if (false == lastCharsEquals || endOfKeyReached)
{
    keys.Remove(node);  // Удаляем невалидные ключи сразу!
}



**Фактически алгоритм делает:**
1. Проверяет текущий символ для каждого активного ключа
2. Если символ не совпадает — ключ удаляется
3. Если ключ полностью найден — он тоже удаляется
4. Только ключи, которые всё ещё могут совпасть, остаются в списке

## Эффективность с O(1) удалением:

С O(1) удалением из LinkedList этот алгоритм становится **довольно эффективным**!

**Сложность:** O(m × k), где:
— m — длина строки `source`
— k — среднее количество **активных** ключей (тех, что ещё могут совпасть)

В худшем случае (все ключи активны до конца) — O(m × n), но на практике k быстро уменьшается.

## Преимущества текущего подхода:

1. **Автоматическая фильтрация** — невалидные ключи удаляются сразу
2. **Минимальная память** — хранятся только строки, нет дополнительных структур
3. **Простота** — легко понять и поддерживать

## Единственные возможные улучшения:

private static void FoundKeyOptimized(string source, int index, LinkedList<string> keys, ref string foundKey)
{
    char ch = source[index];
    var node = keys.First;
    
    while (node != null)
    {
        var key = node.Value;
        var nextNode = node.Next; // Сохраняем ДО возможного удаления
        
        // Более читаемая проверка
        bool charMatches = key[index] == ch;
        bool isComplete = index + 1 == key.Length;
        
        if (isComplete && charMatches)
        {
            foundKey = key;
            keys.Remove(node);
        }
        else if (!charMatches)
        {
            keys.Remove(node);
        }
        // Если charMatches И НЕ isComplete - ключ остается для след. итерации
        
        node = nextNode;
    }
}


**Вывод:** С O(1) удалением ваш алгоритм уже достаточно эффективен для большинства практических случаев! Основной недостаток — сложность понимания логики, а не производительность.

Извините за первоначальную невнимательность — ваш код умнее, чем я его оценил.


....Извините за первоначальную невнимательность — ваш код умнее, чем я его оценил.


Тащемта, снова косяк с анализом алгоритма!

**Сложность:** O(m × k), где:
— m — длина строки `source`
— k — среднее количество **активных** ключей (тех, что ещё могут совпасть)

Это неправильно. Я чуть выше писал как правильно.


Ну и ещё — вот на эту ошибку в коде мне можно было бы и указать.
                    keys.Remove(node);
                }

                node = node.Next;

Ошибка в том, что после того как ноду удалили из списка, из неё нельзя доставать node.Next — это особенности реализации (она инвалидируется — node.Next после этого null).



Вот здесь эта переписка: https://chat.deepseek.com/share/2s21f9ixhbecpg4ixj

ЗЫ: задолбал с умным видом хрень нести
Задолбал Dick Seek со своей "невнимательностью"
А точнее — неспособностью анализировать алгоритмы. Вот, из последнего:
Анализируем функцию
  функция 
        private static void FoundKey(string source, int index, LinkedList<string> keys, ref string foundKey)
        {
            char ch = source[index];


            var node = keys.First;
            while (node != null)
            {
                var key = node.Value;

                var endOfKeyReached = index + 1 == key.Length;
                var lastCharsEquals = key[index] == ch;

                if (endOfKeyReached && lastCharsEquals)
                    foundKey = key;

                if (false == lastCharsEquals
                    || endOfKeyReached)
                {
                    keys.Remove(node);
                }

                node = node.Next;
            }
        }

Спрашиваю про проблемы производительности.

Q:
Насколько эта функция эффективна в плане скорости и потребления памяти? Можно ли эффективнее?

  получаю вот такой ответ

Проблемы текущей реализации:
1. Сложность O(n²) в худшем случае
Для каждого символа строки (source) вы проходите по всем ключам (keys)

Если ключи длинные, это становится очень медленно

2. Неэффективная структура данных
LinkedList — медленный доступ, нет быстрого поиска

Удаление из середины списка — O(n) операций

3. Избыточные проверки

var endOfKeyReached = index + 1 == key.Length;
var lastCharsEquals = key[index] == ch;

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


И это сразу

фэйл!

Потому что в процессе выполнения алгоритма не будет продвижения по source дальше чем длинна самого длинного ключа, т.о. сложность составляет O(L × n), где L — длина самого длинного ключа, n — количество ключей

Обоснование:
Алгоритм проверяет только первые L символов source — именно поэтому длинна source в этой формуле не участвует.
После позиции L-1 все ключи либо найдены, либо отсеяны — дальнейшие символы source не обрабатываются

Удаление из середины списка — O(n) операций

Двойной фэйл!

Remove(LinkedListNode<T>) имеет сложность O(1) — он его перепутал с методом bool Remove(T value), который действительно имеет сложность O(n)

Спрашиваю, изменится ли ситуация, если удаление из середины будет O(1).
Далее, напоминаю, что ключи таки удаляются:

Q:
Пункт 1 — неверно: заведомо несовпадающие ключи удаляются. Посмотри на эти строки
                if (false == lastCharsEquals
                    || endOfKeyReached)
                {
                    keys.Remove(node);
                }

Подумай ещё раз.


A:

Вы абсолютно правы! Я был невнимателен. Давайте переанализируем.


  и снова фэйл!

Вы абсолютно правы! Я был невнимателен. Давайте переанализируем.
## Текущий алгоритм работает умнее, чем я initially предположил:

// Ключ НЕ совпал по текущему символу ИЛИ ключ полностью найден
if (false == lastCharsEquals || endOfKeyReached)
{
    keys.Remove(node);  // Удаляем невалидные ключи сразу!
}



**Фактически алгоритм делает:**
1. Проверяет текущий символ для каждого активного ключа
2. Если символ не совпадает — ключ удаляется
3. Если ключ полностью найден — он тоже удаляется
4. Только ключи, которые всё ещё могут совпасть, остаются в списке

## Эффективность с O(1) удалением:

С O(1) удалением из LinkedList этот алгоритм становится **довольно эффективным**!

**Сложность:** O(m × k), где:
— m — длина строки `source`
— k — среднее количество **активных** ключей (тех, что ещё могут совпасть)

В худшем случае (все ключи активны до конца) — O(m × n), но на практике k быстро уменьшается.

## Преимущества текущего подхода:

1. **Автоматическая фильтрация** — невалидные ключи удаляются сразу
2. **Минимальная память** — хранятся только строки, нет дополнительных структур
3. **Простота** — легко понять и поддерживать

## Единственные возможные улучшения:

private static void FoundKeyOptimized(string source, int index, LinkedList<string> keys, ref string foundKey)
{
    char ch = source[index];
    var node = keys.First;
    
    while (node != null)
    {
        var key = node.Value;
        var nextNode = node.Next; // Сохраняем ДО возможного удаления
        
        // Более читаемая проверка
        bool charMatches = key[index] == ch;
        bool isComplete = index + 1 == key.Length;
        
        if (isComplete && charMatches)
        {
            foundKey = key;
            keys.Remove(node);
        }
        else if (!charMatches)
        {
            keys.Remove(node);
        }
        // Если charMatches И НЕ isComplete - ключ остается для след. итерации
        
        node = nextNode;
    }
}


**Вывод:** С O(1) удалением ваш алгоритм уже достаточно эффективен для большинства практических случаев! Основной недостаток — сложность понимания логики, а не производительность.

Извините за первоначальную невнимательность — ваш код умнее, чем я его оценил.


....Извините за первоначальную невнимательность — ваш код умнее, чем я его оценил.


Тащемта, снова косяк с анализом алгоритма!

**Сложность:** O(m × k), где:
— m — длина строки `source`
— k — среднее количество **активных** ключей (тех, что ещё могут совпасть)

Это неправильно. Я чуть выше писал как правильно.


Ну и ещё — вот на эту ошибку в коде мне можно было бы и указать.
                    keys.Remove(node);
                }

                node = node.Next;

Ошибка в том, что после того как ноду удалили из списка, из неё нельзя доставать node.Next — это особенности реализации (она инвалидируется — node.Next после этого null).



Вот здесь эта переписка: https://chat.deepseek.com/share/2s21f9ixhbecpg4ixj

ЗЫ: задолбал с умным видом хрень нести