Comments 65
Вот уже последние лет 10 одна [половина] человечества стремительно проваливается в пучину бесполезного повторения одного и того же с каждый раз всё худшими показателями, а вторая половина запрещает абы что.
Нууу, классика:
В статье не пропущено слово
Но ведь в любом виде деятельности люди повторяют какие-то действия для того, чтоб понемножку, раз за разом, улучшать результаты получая хороший прогресс, иногда достигая великих результатов. Спортсмены, музыканты, и даже программисты. :)
Всегда казался тот, кто написал этот монолог глав.плохишу тупым как пробка.
Неверно. Уже обсуждали это в другой теме много лет назад. Главгад говорит "точное повторение". А у спортсменов не так, там каждая попытка всегда отличается. Например, вы никогда не накачаетесь, если не будете прибавлять тягаемый вес. А гонщик всегда чуть меняет траекторию и параметры скорости/торможения, нащупывая оптимальные.
Это все придирки, я так тоже могу:
Если подходить прям буквально, про точное повторение, то так-то никто вообще 100% точных повторений не делает, а главгад говорит, что видит их везде.
Очень многие близки к точным повторениям идеального для своей кондиции результата. Например, пловцы, когда начинаешь, результат не очень, но чем ближе ты к оптимальным для себя действиям, тем лучше результат и через несколько лет регулярных занятий ты в бассейне будешь повторять одни и те-же действия своим телом. Или музыканты, когда какую-то мелодию разучивают (у меня дочь на скрипке играет, я знаю). По-началу каждый раз отличается, но чем ближе к своему пределу, тем меньше и меньше отличий.
Вас сам главгероя все время по-разному убивал и все плакался как он одно и тоже действие делает.
Спасибо за ролик, впервые смотрю. Очень круто сделано, надо сыграть в эту игру 🔥🤝
ты просто медленно нажимаешь на "пробел"
Вот уже 25 лет я вижу в статьях комментах блогах и постах рой фабрики троллей, и что, у меня иммунитет, вижу издалека.
Если жить в инфопузырях, то обитатели других инфопузырей всегда кажутся ботами и троллями.
До определенного момента можно было выявлять по низкому уровню аргументации и повторяющимся паттернам. Сейчас, думаю, чатгпт меня сможет убедить в своей правоте в любой области в которой я не разбираюсь)))
Это объективная реальность, данная нам в ощущениях, ну на habr в частности. И ощущения с интуицией нас не подводят, троллей видно издалека и их тут дофига😁 Во сколько дизлайков эти наемники намарали, хы, банда информационная. 🤣🖕
Какой процент пользователей станет пользоваться Хромом чаще или перейдет на него с ФФ, если там улучшить окошко поиска? Мизер.
А скольким новым пользователям можно будет показать рекламу, если сломать очередной раз AdBlock / uBlock / etc? Миллионам!
Так что приоритет очевиден: выгоднее ломать, чем строить
Я не эксперт по всем этим views::reverse, needle, но звучит так, будто вы хотите взять ваш "довольно объёмный файл" и начать с того, что его целиком переворачивать. Или там скрыта какая-то магия?
там поиск не так тривиален по документу, смотря как рендерится документ(как хранятся строки или слова), там отталкиваемся не от 1 вхождения слова в доке или строке, а все вхождения. Отправная точка тут как я понял, когда смотрел Алгоритм_Кнута_—_Морриса_—_Пратта. Ну тоесть или просто, проходясь по всем строкам надо получить такое что-то +- [ строка позиция "введеный набор букв" ]
перед С++ можно потренероваться на Java, вводные - рендер текста через Свинг, там где-нибудь сбоку рисуем поле и тренеруемся
тоесть при запросе cntrl-f надо сформировать список и двигать курсор ко всем словам, через взаимодействие
Проблема очевидна — браузер каждый раз при поиске предыдущего вхождения искал с самого начала файла
Это называется «алгоритм Шлемиэля»
Честно говоря грустно. Завершу эту статью кодом, который ищет подстроку в строке эффективно в одну сторону и в другую на С++
Ѣ, нет слов
https://quick-bench.com/q/_KCURn2wkxN1KcQvtSP-GbcxJmE
UPD. Допустил глупую ошибку, добавил benchmark::DoNotOptimize, ситуация не поменялась
Смысл кода в том чтобы показать одинаковый подход к поиску вперёд и назад и его реализацию, оптимизировать там можно подставлением другого Searcher
Ваш код вовсе некорректный, потому что не использует никак результат и компилятор выкидывает ваши подсчёты
И у вас специально подобран кейс с худшим вариантом
P.S. этот код сильно зависит от стандартной библиотеки, на винде ситуация вполне себе обратная. Просто кто-то оптимизировал с simd стандартную либу, молодцы
Мой посыл в том, что вы предлагаете использовать ranges::search, который работает с произвольным типом вместо нативного string::find с фиксированным типом (ну или по крайней мере мы знаем, что это от 1 до 4 байт если говорим о wchar), и если где-то ожидать сворачивание в одну SIMD инструкцию типа cmpeq, то как раз скорее от find.
И да, сворачивание в одну SIMD инструкцию сравнения целого слова является например причиной неэффективности того же КМП в большинстве случаев, но вы же ни слова об этом в статье не сказали!
вы путаете алгоритмическое эффективно и всякие машинные коды и как оно исполнилось где-то на конкретной реализации
Не знаю, что по вашему мнению я путаю, попробую переформулировать. Если искомая строка <= 32 байт и нам доступны 256-битные регистры, то скорее всего любая реализация КМП будет медленнее линейного прохода с линейным сравнением, потому что компилятор свернёт всё линейное сравнение в одну SIMD инструкцию. Компилятор скорее всего сделает подобное и с сравнениями в КМП, но у него все равно в этом сценарии будет больше сравнений, которые еще и непоследовательны по доступу к памяти, что сделает его неэффективным.
Пройтись один раз, закешировав результат поиска, и прыгать по нему как хочешь?
решение в духе хромиума. Крайне неэффективно, нужно пересчитывать каждый раз при изменении строки и тд
Все удобные мне лично интерфейсы поиска подсвечивают все вхождения (отдельное окно и/или цветовые отметки на скроллбаре и в тексте). Кэширование практически не добавляет нагрузки, дальнейший поиск работает в фоне. А самый частый кейс при поиске на лету - увеличение строки, пересчитывать не надо, достаточно пройтись по кэшу.
то что вы предлагаете это последовательное усложнение, где оно не нужно. Добавление кеша, потом специализированные алгоритмы обновления кеша
Напомню, что сейчас хром подсвечивает все вхождения, но это не мешает ему при поиске вперёд находить, а при поиске назад - бешено лагать. И нет опции перехода к вхождению по номеру
Откройте уже для себя реактивное программирование, не позоритесь.
Закройте для себя хабр, вы спорите с выдуманной реализацией
Вы ведёте себя как малолетний дебил. Захотите, чтобы окружающие относились как ко взрослому - раскурите реальную реализацию: https://github.com/hyoo-ru/mam_mol/blob/master/search/jumper/jumper.view.ts
В статье нет ничего о том, что прямо так и надо перенести в реализацию браузера, только показан способ найти не перебирая весь файл сначала предыдущее вхождение подстроки в строку.
Разумеется, в браузере будет другой код, и вероятно не тот что на тайпскрипте по вашей ссылке, скорее на С++ https://cocalc.com/github/chromium/chromium/blob/main/chrome/browser/ui/views/find_bar_view.cc
И код там ужасный, в этом собственно и проблема
фокус в том, что начало строки обычно не меняется, а значит после первой пары символов нужно будет искать не по всему документу, а по списку вхождений. Что вполне эффективно. Я уж не говорю, про то, что на фоне всей той работы которую выполняет броузер, список на 400 элементов не выглядит сколько-нибудь серьёзной проблемой.
Проблема очевидна - браузер каждый раз при поиске предыдущего вхождения искал с самого начала файла и считал количество вхождений.
Нет, причина не очевидна как раз. Ну сколько там мегабайт документ? 100? Даже на таком объёме любой вменяемый алгоритм поиска за десятки мс с начала документа поиск закончит. Скорее всего, что-то другое там происходит, сборка мусора глобальная какая-то или что.
До сих пор все оптимизации передачи джаваскрипта по сети не пошли дальше удаления пробелов из исходного текста
вроде бандлы уже давно минифицируется, а веб сервер зипует текст
как же так вышло, что до сих пор в браузерах это окошко не поддерживает даже поиск по целому слову или поиск с учётом регистра
Среди миллиардов пользователей хрома, эти фичи нужны примерно нулевому проценту пользователей, как и поиск в обратную сторону
Честно говоря грустно
Так выглядит рыночек и лучше уж он. Всякие командно-плановые начинания в итоге страдают от отсутствия мотивации вообще у всех участников, начинают в конечном итоге тырить идеи у рыночка
вроде бандлы уже давно минифицируется, а веб сервер зипует текст
минифицирование это и есть удаление пробелов, это далеко от бинарного представления
Среди миллиардов пользователей хрома, эти фичи нужны примерно нулевому проценту пользователей, как и поиск в обратную сторону
как раз среди миллиардов пользователей хрома в силу их количества найдутся миллионы, которым эта фича нужна. А стоит её поддержать - практически 0. Напомню, что есть множество запросов от пользователей на улучшение этого поиска, висят эти иссуи десятки лет
Так выглядит рыночек и лучше уж он
нет, во-первых это не рыночек, а чистейшие монополии или дуополии. Во-вторых, и рынок можно организовать не одним способом. В третьих, нынешнее состояние далеко не идеально и может быть улучшено
минифицирование это и есть удаление пробелов, это далеко от бинарного представления
Нет, удаление пробелов это только часть процесса. А архив это бинарь. Джарник, например, тоже архив.
как раз среди миллиардов пользователей хрома в силу их количества найдутся миллионы, которым эта фича нужна. А стоит её поддержать - практически 0. Напомню, что есть множество запросов от пользователей на улучшение этого поиска, висят эти иссуи десятки лет
Нет, браузер для домохозяек не должен иметь этих функций. Они не только усложняют интерфейс, но и увеличивают кодовую базу, со всеми вытекающими.
нет, во-первых это не рыночек, а чистейшие монополии или дуополии.
Тем не менее, все участники материально заинтересованы
Во-вторых, и рынок можно организовать не одним способом. В третьих, нынешнее состояние далеко не идеально и может быть улучшено
Главное этими улучшениями не уничтожить саму возможность развития
Нет, браузер для домохозяек не должен иметь этих функций
где написано, что это браузер только для домохозяек? И что за позиция такая странная? В мире есть браузер специализированный для кого-то? Нет.
Они не только усложняют интерфейс, но и увеличивают кодовую базу, со всеми вытекающими
Не буду вдаваться в то, что увеличение кодовой базы бывает разное, но что-то мне подсказывает, что в хроме есть гигантское количество кода, который вообще нахрен никому не нужен
Если мы посчитали число вхождений, значит у нас уже есть их координаты - достаточно прыгать по ним, а не искать каждый раз. Тот случай, когда критик сам не далеко от критикуемых ушел.
Посчитать все вхождения это дешевле чем все вхождения сохранить. Учитывая, что нет операции перейти к вхождению №N, хранить все вхождения гораздо дороже и более подтвержено багам, чем просто найти следующее или предыдущее быстро. Какой смысл хранить это, если считается это невероятно быстро?
Кешировать такое может прийти в голову разве что питонисту
А вы как-то учли, что у вас документ может меняться в любой момент? То есть надо найти DOM node, содержащий нужный текст, но за время поиска этот текст может уже поменяться или вообще node удалиться.
То есть проблема не в поиске по строке, а в том, что для поиска нужно держать всё время некоторый дублирующий Shadow DOM с тестовой информацией
Цивилизация хомо с одной стороны размножается и подходит к пределу по потребляемым ресурсам на планете, с другой загнивает, потому как изобрели ИИ, совершенствуют, тратят на него немалые ресурсы, в общем роют подкоп у стены дома не задумываясь о том что стена от смещения грунта может и обрушиться. Это приведет к изменению природы хомо с чисто биологической на гибридную.
дел. уже есть такой комментарий.
Плюс одна причина почему я пользуюсь Firefox
Раз уж кодом делитесь, то хотя бы пример на годболте пошарили
Хорошая идея с разворотом, да. Вот только это так просто в тривиальной упрощенной задаче, где у вас поиск строки в строке. Поиск по странице в браузере гораздо сложнее, ибо тут есть структура и поиск должен идти в порядке отображения, а не в исходном Html коде.
Плюс есть всякие приколы с utf-8, иероглифами и языками, читающимеся справа-на-лево.
Теоретически, можно заморочиться и вот этот вот код подправить. Там действительно есть разница между front() и back(). Но там придется много чего перелопачивать, при том что это не даст ускорения в 99.9% случаев, потому что этот код запускается лишь на маленьких кусочках текста внутри элементов. Поиск в одном большом текстовом файле - редкий случай.
Если вам это важно, можете предложить патч или хотя бы запостить баг-репорт в crbug.com.
Человечество занимается тем же, чем занимается Эволюция. Вся живая материя основана на механизме копирования/повторения с частичным изменением.
Чем вообще занимается человечество?