Аудит алгоритмов: как реализация Boyer-Moore с 190K звёзд на GitHub оказалась brute-force

[funca]

Хорошая находка и лишнее подтверждение, что авторитеты тоже ошибаются.

Интересно, почему только issue без PR?

[StudyQA]

Спасибо! PR не отправил намеренно: хотел сначала зафиксировать баг как есть, чтобы мейнтейнеры сами решили, какой фикс им ближе :) Там есть несколько вариантов: с одной стороны, можно переписать на while-цикл с корректным сдвигом. А с другой, например, можно взять каноническую реализацию Rytter (1980) или вообще заменить на Horspool, который проще и на практике не медленнее. Если issue не закроют в ближайшее время, отправлю PR с Horspool-вариантом.

[Genius_Russian_Coders]

Классный разбор. Присвоение переменной цикла в Python — недооценённая ловушка: for молча её перезаписывает на каждой итерации. Я ловил ровно то же самое при портировании Z-алгоритма — все тесты зелёные, а сложность O(n²). Property-based testing такие вещи вскрывает мгновенно.

[CitizenOfDreams]

Присвоение переменной цикла в Python — недооценённая ловушка: for молча её перезаписывает на каждой итерации.

Я не программист, но по-моему, изменение переменной цикла внутри цикла for - это грязный хак. Если ты пишешь "for i in range (5)", то нормальный человек, который потом будет разбираться в твоем коде, предположит, что ты хотел получить ровно пять циклов со значениями i=0, 1, 2, 3, 4.

А для переменной, которая может произвольно меняться в любой момент, есть цикл while.

[randomsimplenumber]

Переписали с Си на Питон похоже. Но странно, обычно в учебниках алгоритмы на паскале-подобном псевдоязыке, без сионистских хаков.

[CitizenOfDreams]

Переписали с Си на Питон похоже.

На Си я бы точно так же назвал это грязным хаком. Я бы так написал разве что на старом Бейсике, в котором нет WHILE - потому что иначе пришлось бы рисовать цикл вручную на GOTO, что еще хуже.

[wl2776]

Переписали с Си на Питон похоже. 

Вряд ли, реализации очень сильно отличаются.

https://github.com/TheAlgorithms/C/blob/e5dad3fa8def3726ec850ca66a7f51521f8ad393/searching/pattern_search/boyer_moore_search.c

https://github.com/TheAlgorithms/Python/blob/master/strings/boyer_moore_search.py

[Dimmirslr]

Иногда завести подробный багрепорт полезнее. Пулл-реквесты могут мариновать месяцами, а ишью привлекает внимание комьюнити к проблеме

[A-Dobrii]

Срочно требую обвинить в этом неросети, антропик и Гугл!

До неросетей люди ошибок не делали!

[kvd264]

А после стали не делать ещё больше!

[LinkToOS]

В Python переприсвоение переменной for-цикла не влияет на следующую итерацию.

Вы не уточнили - в C и Java такая реализация работает корректно, или приводит к ошибкам? То есть здесь описан случай неаккуратного переложения кода на несовместимый язык, или вариант кода с изменением i в теле цикла заведомо недопустим, независимо от языка программирования?

[wl2776]

Вы не уточнили - в C и Java такая реализация работает корректно, или приводит к ошибкам?

Если цикл не range-based из современных стандартов, и типы простые (`int`, `float` и т.п.), то да, такая реализация работает корректно.

Запись `for (int i = 0; i < max_value; i++)` это по сути компактная запись `while`.

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

Для range-based for loops из современного С++ изменение переменной внутри цикла тоже в ряде случаев приемлемая и корректная операция. Пример:

    std::vector<int> vec = {1, 2, 3};

    for (int& val : vec) {
        val *= 2;
    }

[vep]

Существующие статические анализаторы кода для python какую штуку не подсвечивают?

[osmanpasha]

Призываем @PvsTeam!

[wl2776]

Подсвечивают. Но в исходнике стоит комментарий, который эту проверку отключает.

[Dimmirslr]

Количество звездочек на гитхабе вообще ничего не говорит о реальном качестве кода под капотом...