Far 2.0 - regexp

Разработка Far.
Post Reply
User avatar
t-rex
Страшный и ужасный
Posts: 4910
Joined: Tue 15 Mar, 2005 16:17
Location: Tel-Aviv
Has thanked: 1 time
Been thanked: 8 times
Contact:

Re: Far 1.8 - regexp

Post by t-rex »

Latest post of the previous page:

HaRT
Мда, обломал ты мне всю малину :) Но зато хоть высплюсь :)
User avatar
HaRT
Moderator
Posts: 10865
Joined: Tue 30 Aug, 2005 17:21
Has thanked: 221 times
Been thanked: 358 times

Re: Far 1.8 - regexp

Post by HaRT »

t-rex wrote:
John Doe wrote:3. Делать поиск с переменным началом поиска, когда начало начинается с конца строки и -1 каждый раз до совпадения, после чего продолжить -1 до тех пор пока не меняется конечная позиция совпадения.
О логично, эквивалентный методу 2 но быстрей работать будет, отлично.
А зачем шагать назад именно по 1 символу или по 1 строке?!
Не лучше ли, не побоюсь этого слова, дихотомией? Т.е. рассматриваем диапазон строк от начала файла до текущей строки, ищем (разумеется, вперёд) от его середины. Если не нашли, ищем от середины первой половины, если нашли — от середины второй; и так далее. Если в итоге пришли всё же в изначальную строку, то проделываем аналогичную процедуру уже внутри строки.

И ещё одно соображение: всё-таки искать надо начало совпадения, меньшее текущей позиции, а не изменения конца совпадения.

PS
Для очень длинных файлов может потребоваться какое-то ограничение, насколько далеко назад мы готовы таким манером отступиться.
Last edited by HaRT on Thu 01 Jan, 1970 01:00, edited 0 times in total.
Reason: Добавлен PS
Фар есть инструмент, а не нянька. © 2009 DrKnS
User avatar
t-rex
Страшный и ужасный
Posts: 4910
Joined: Tue 15 Mar, 2005 16:17
Location: Tel-Aviv
Has thanked: 1 time
Been thanked: 8 times
Contact:

Re: Far 1.8 - regexp

Post by t-rex »

HaRT
Редактор у нас строковой, и ищется текст только по строкам.
User avatar
t-rex
Страшный и ужасный
Posts: 4910
Joined: Tue 15 Mar, 2005 16:17
Location: Tel-Aviv
Has thanked: 1 time
Been thanked: 8 times
Contact:

Re: Far 1.8 - regexp

Post by t-rex »

HaRT
Ну а вообще, я не думаю что такой метод поиска придаст ускорение, скорее даже наоборот, но что да стоит это для каждой строки с начало сделать поиск вперёд и только если нашлось делать метод 3 для получение правильной позиции.
User avatar
HaRT
Moderator
Posts: 10865
Joined: Tue 30 Aug, 2005 17:21
Has thanked: 221 times
Been thanked: 358 times

Re: Far 1.8 - regexp

Post by HaRT »

t-rex wrote:я не думаю что такой метод поиска придаст ускорение
Измерить бы, когда что, — тогда уже можно и эвристику какую-нибудь дельную сваять.
Фар есть инструмент, а не нянька. © 2009 DrKnS
User avatar
t-rex
Страшный и ужасный
Posts: 4910
Joined: Tue 15 Mar, 2005 16:17
Location: Tel-Aviv
Has thanked: 1 time
Been thanked: 8 times
Contact:

Re: Far 1.8 - regexp

Post by t-rex »

HaRT
Да не не надо измерять, количество проверенных строк в твоём случае всегда будет равно или больше чем если искать строка -1. Именно потому что ищем последнее совпадение.
User avatar
HaRT
Moderator
Posts: 10865
Joined: Tue 30 Aug, 2005 17:21
Has thanked: 221 times
Been thanked: 358 times

Re: Far 1.8 - regexp

Post by HaRT »

t-rex
А, я наконец-то понял, что ты пытаешься сказать: то, что из-за построчной природы редактора мы не можем из середины файла одним махом искать до конца, а надо всё равно проверять каждую строку по отдельности. Тогда да, дихотомией ничего не улучшить и надо шагать по одной строке назад, а уже внутри найденной строки — половинное деление.
Фар есть инструмент, а не нянька. © 2009 DrKnS
User avatar
CrOm
Posts: 1428
Joined: Tue 02 Aug, 2005 21:02
Location: Омск
Been thanked: 1 time

Re: Far 1.8 - regexp

Post by CrOm »

внутри строки смысла в твоем страшном слове тоже нет, ибо редко встречаются строки длиннее ширины экрана, а ради тех редких извращеных файлов воротить код не вижу смысла
FARFlipper, FARdroid, qPlayEx, Mr.Ripper
User avatar
HaRT
Moderator
Posts: 10865
Joined: Tue 30 Aug, 2005 17:21
Has thanked: 221 times
Been thanked: 358 times

Re: Far 1.8 - regexp

Post by HaRT »

CrOm
Во-первых, у кого редко, а у кого и не очень. Зачем заранее просаживать производительность?!
Во-вторых, я верю в то, что для t-rexа реализовать половинное деление в строке уж никак не дотягивает до “воротить”. ;)
Фар есть инструмент, а не нянька. © 2009 DrKnS
User avatar
t-rex
Страшный и ужасный
Posts: 4910
Joined: Tue 15 Mar, 2005 16:17
Location: Tel-Aviv
Has thanked: 1 time
Been thanked: 8 times
Contact:

Re: Far 1.8 - regexp

Post by t-rex »

HaRT
Да и тут деление не поможет :) Ведь длина искомой строки не известна.
User avatar
t-rex
Страшный и ужасный
Posts: 4910
Joined: Tue 15 Mar, 2005 16:17
Location: Tel-Aviv
Has thanked: 1 time
Been thanked: 8 times
Contact:

Re: Far 1.8 - regexp

Post by t-rex »

Короче, все эти "оптимизации" работают только для определённого вида ввода. А приколы типа ignore case, whole words и re убивают их напрочь.
User avatar
HaRT
Moderator
Posts: 10865
Joined: Tue 30 Aug, 2005 17:21
Has thanked: 221 times
Been thanked: 358 times

Re: Far 1.8 - regexp

Post by HaRT »

t-rex
Я мог бы попытаться обосновать, почему мне кажется, что для длинных строк половинное деление даст ускорение даже в случае с регулярными выражениями, но есть ощущение, что вне зависимости от моих доводов решение уже принято.
Что касается взаимодействия такой оптимизации с опциями поиска (назад), так просто непонятно, почему бы это вдруг они на неё влияли.
Фар есть инструмент, а не нянька. © 2009 DrKnS
User avatar
t-rex
Страшный и ужасный
Posts: 4910
Joined: Tue 15 Mar, 2005 16:17
Location: Tel-Aviv
Has thanked: 1 time
Been thanked: 8 times
Contact:

Re: Far 1.8 - regexp

Post by t-rex »

HaRT
Ты не можешь делить, ибо ты не знаешь где граница:
текст "aabb", ищем "ab".
или текст bbbbbbaaaaaaaaaaaaaabbbbbbbbbbbbbbbaaaaaa и ищем a+b+
User avatar
HaRT
Moderator
Posts: 10865
Joined: Tue 30 Aug, 2005 17:21
Has thanked: 221 times
Been thanked: 358 times

Re: Far 1.8 - regexp

Post by HaRT »

t-rex
Мы вообще об одном и том же говорим или нет?
Я пытаюсь обосновать, что половинное деление могло бы ускорить поиск (в том числе с регулярными выражениями) в длинной строке назад. При поиске назад пользователь ищет включение, у которого начало левее текущей позиции, но правее всех прочих таких включений.
Если в приведённых примерах искать от конца строки, то должно найтись так: “aABb” (после двух делений), “bbbbbbaaaaaaaaaaaaaABBBBBBBBBBBBBBBaaaaaa” (после шести делений). И половинное деление этому не помеха, ведь всё равно logN = o(N).
Фар есть инструмент, а не нянька. © 2009 DrKnS
User avatar
t-rex
Страшный и ужасный
Posts: 4910
Joined: Tue 15 Mar, 2005 16:17
Location: Tel-Aviv
Has thanked: 1 time
Been thanked: 8 times
Contact:

Re: Far 1.8 - regexp

Post by t-rex »

HaRT
При поиске назад должно найтись
bbbbbbaaaaaaaaaaaaaabbbbbbbbbbbbbbbaaaaaa
User avatar
t-rex
Страшный и ужасный
Posts: 4910
Joined: Tue 15 Mar, 2005 16:17
Location: Tel-Aviv
Has thanked: 1 time
Been thanked: 8 times
Contact:

Re: Far 1.8 - regexp

Post by t-rex »

Т.е. как я понимаю поиск назад это тоже самое что поиск вперёд когда точка конца это откуда начинаем поиск и как при поиске вперёд должно найтись наилучшее совпадение конец которого ближе всего к концу текста.
Post Reply

Return to “Development”