Far 2.0 - regexp

Разработка Far.
User avatar
HaRT
Moderator
Posts: 9695
Joined: Tue 30 Aug, 2005 17:21
Location: Санкт-Петербург
Has thanked: 124 times
Been thanked: 254 times

Re: Far 1.8 - regexp

Post by HaRT »

Latest post of the previous page:

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

Re: Far 1.8 - regexp

Post by t-rex »

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

Re: Far 1.8 - regexp

Post by HaRT »

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

Re: Far 1.8 - regexp

Post by t-rex »

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

Re: Far 1.8 - regexp

Post by t-rex »

Т.е. как я понимаю поиск назад это тоже самое что поиск вперёд когда точка конца это откуда начинаем поиск и как при поиске вперёд должно найтись наилучшее совпадение конец которого ближе всего к концу текста.
User avatar
t-rex
Страшный и ужасный
Posts: 4907
Joined: Tue 15 Mar, 2005 16:17
Location: Tel-Aviv
Has thanked: 1 time
Been thanked: 6 times
Contact:

Re: Far 1.8 - regexp

Post by t-rex »

Но даже само определение что такое поиск назад ни как не меняют ситуацию что для поиска именно строк o(n) ни как не может быть logN, потому что невозможно использовать половинчатое деление так как нельзя определять промежуточные границы для поиска, а также потому что совпадений может быть больше одного.
User avatar
HaRT
Moderator
Posts: 9695
Joined: Tue 30 Aug, 2005 17:21
Location: Санкт-Петербург
Has thanked: 124 times
Been thanked: 254 times

Re: Far 1.8 - regexp

Post by HaRT »

t-rex
Честно говоря, словесное определение ниасилил (я один такой тупой?).
Но налицо разное понимание того, что должен делать поиск назад. В твоём представлении по /b+c/ в “abbcd” должно найтись “aBBCd”, в моём (и плагина S&R) — “abBCd”.

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

Re: Far 1.8 - regexp

Post by t-rex »

HaRT
Как ищет S&R я прекрасно знаю, но мне что то такой поиск совершенно не логичен, какой от него смысл?
HaRT wrote:Насчёт поиска по многим строкам согласен, но прошу заметить, что я говорю о половинном делении при поиске назад в длинной строке, что явно и написал.
Да я тоже про поиск в строке, как ни крутись а искать нужно во всех возможных подстроках.
User avatar
HaRT
Moderator
Posts: 9695
Joined: Tue 30 Aug, 2005 17:21
Location: Санкт-Петербург
Has thanked: 124 times
Been thanked: 254 times

Re: Far 1.8 - regexp

Post by HaRT »

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

Re: Far 1.8 - regexp

Post by t-rex »

HaRT wrote:Это я уже написал:

HaRT wrote:включение, у которого начало левее текущей позиции, но правее всех прочих таких включений
Это описание, но смысла зачем это надо и почему поиск назад должен отличатся от поиска вперёд я не понимаю.
HaRT wrote:Вот с этим-то я и не согласен.
Даже если понимать поиск назад по-твоему, это совершенно не мешает применить половинное деление.
Оно ничего не даст, потому что как не дели а искать надо искать во всех возможных под строках. Подумай над этим немного.
User avatar
Centaur
Posts: 1083
Joined: Tue 05 Apr, 2005 20:09
Location: Novosibirsk, Russia
Been thanked: 2 times

Re: Far 1.8 - regexp

Post by Centaur »

+1 за то, что поиск назад должен находить те и только те же самые вхождения, что и поиск вперёд, только в обратном порядке.
User avatar
t-rex
Страшный и ужасный
Posts: 4907
Joined: Tue 15 Mar, 2005 16:17
Location: Tel-Aviv
Has thanked: 1 time
Been thanked: 6 times
Contact:

Re: Far 1.8 - regexp

Post by t-rex »

HaRT
Хотя да, есть один смысл, найти самое последнее совпадение которое нашел бы поиск вперёд. Мда, ситуация запутывается :)
Denis
Posts: 1433
Joined: Tue 05 Apr, 2005 18:12
Has thanked: 9 times
Been thanked: 4 times

Re: Far 1.8 - regexp

Post by Denis »

t-rex
Такое невозможно без реверса re.
User avatar
Andrey Budko
Posts: 1203
Joined: Fri 01 Apr, 2005 14:03
Contact:

Re: Far 1.8 - regexp

Post by Andrey Budko »

HaRT wrote:Но налицо разное понимание того, что должен делать поиск назад. В твоём представлении по /b+c/ в “abbcd” должно найтись “aBBCd”, в моём (и плагина S&R) — “abBCd”
Харт хочет сказать (наверное), что поиск вперед, а потом назад должен возвращать теже самые элементы. Чтобы можно было по тем же логам вперед назад ходить. В сечреплейсе, вроде, как раз так.

Берем файл с содержимым "abbcd abbcd" и ищем вперед /b+c/ Последдовательно находим:

Code: Select all

aBBCd abbcd
abBCd abbcd
abbcd aBBCd
abbcd abBCd
Курсор находится в конце файла, ничего не меняем и делаем поиск назад. Последовательнонаходим

Code: Select all

abbcd abBCd
abbcd aBBCd
abBCd abbcd
aBBCd abbcd
В точности те же строки, что при поиске вперед, но наоборот.
User avatar
t-rex
Страшный и ужасный
Posts: 4907
Joined: Tue 15 Mar, 2005 16:17
Location: Tel-Aviv
Has thanked: 1 time
Been thanked: 6 times
Contact:

Re: Far 1.8 - regexp

Post by t-rex »

Denis
Что именно невозможно по твоему мнению? А так, всё очень даже возможно.

Andrey Budko
Да я это уже понял. Вопрос тока что имено надо, "undo" поиска вперёд или настоящий поиск назад?
User avatar
Andrey Budko
Posts: 1203
Joined: Fri 01 Apr, 2005 14:03
Contact:

Re: Far 1.8 - regexp

Post by Andrey Budko »

t-rex wrote:Вопрос тока что имено надо, "undo" поиска вперёд или настоящий поиск назад?
Ты имеешь в виду сначала найти все вхождения от начала до точки курсора, сохранить в список и потом последовательно выдавать по шифт-ф7 ничего больше не делая если условия не изменяются?
Post Reply

Return to “Development”