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:

=Tim Sobolev=
Для регулярных выражений не определено понятие поиска назад, они умеют разбирать строку только вперёд (за исключением look-behind).

Вообще складывается впечатление, что обсуждение свелось к двум разным фичам, которые нужны разным людям:

1. Обратный поиск: находить все те и только те вхождения, что и прямой поиск, но в обратном порядке.
2. Поиск назад: искать по регулярному выражению от конца строки к её началу.

Если нет возражений против таких определений, давайте обсудим, почему бы не заложить в Фар обе эти фичи?

PS
Впрочем, поскольку S&R реализует обратный поиск, я не против того, чтобы в Фаре был поиск назад, разумеется, при условии, что S&R будет работать и в Фаре 1.8.
Фар есть инструмент, а не нянька. © 2009 DrKnS
User avatar
John Doe
Бюрократ
Posts: 13075
Joined: Wed 27 Apr, 2005 20:42
Has thanked: 42 times
Been thanked: 319 times

Re: Far 1.8 - regexp

Post by John Doe »

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

Code: Select all

aBBCd abbcd
abBCd abbcd
abbcd aBBCd
abbcd abBCd
...
Не следует забывать что в S&R есть и такая опция

Code: Select all

Do not process overlapping occurrences...
  [x] ...during replacement and counting
  [x] ...when continuing searching
и получаем другую картину

Code: Select all

aBBCd abbcd
abbcd aBBCd
https://t.me/FarManager — Telegram чат
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:Про корректность: при поиске назад не требуется искать в каждой половине. Алгоритм такой: взяли среднюю позицию, ищем от неё вперёд. Если нашли, то следующее начало поиска будет серединой правой части, если не нашли — значит левой. У меня есть ощущение, что я даже готов представить строгое доказательство корректности такого подхода. Но есть ли смысл тратить на него силы в условиях, когда до строгих рассуждений не снисходят?
Это коректный алгоритм, но это уже ни как не полноценное деление на 2 ибо происходит overlapping между "половинами", и так как поиск re это не константа а зависит от длины текста в котором ищют то как ни крути но logN тут нету, и у алгоритма с -1 тоже даже не близко к N/2. Если посчитать я довольно уверен что выйдет совершенно одинаковый o(n) ибо поиск строки невозможно оптимизировать. Тока вот твой алгоритм будет ещё и больше памяти кушать (даже если без рекурсии) и будет менее читаем и трудней к написанию и ноль выйгрыша.
HaRT wrote:Вообще складывается впечатление, что обсуждение свелось к двум разным фичам, которые нужны разным людям:
Уже давно сложилось и я уже даже в общем решил для этого глобальную опцию делать.
Хотя мне все ровно не понятно зачем нужен 1 вид поиска назад, так при том же поиске вперёд ты же обычно не ищес со следующего символа, а с конца того что нашлось, или я не прав?
HaRT wrote:я ... при условии
Не наглей.
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 »

Что то я смотрю S&R вообще назад всегда с конца строки ищет назад, пофиг где курсор стоит. Это конечно чтоб полностью делать "undo" поиска вперёд но очень как то неожиданно.
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 »

Т.е. даже не с конца а вообще как то непонятно, такое ощущение что он делает Match а не Search начиная с позиции курсора (и до конца строки) каждый раз сдвигая -1 влево.
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:так как поиск re это не константа а зависит от длины текста в котором ищют то как ни крути но logN тут нету, и у алгоритма с -1 тоже даже не близко к N/2. Если посчитать я довольно уверен что выйдет совершенно одинаковый o(n) ибо поиск строки невозможно оптимизировать
Вообще-то я писал про количество поисков, а не про количество элементарных операций (типа циклов процессора). Сдаётся мне, что если посчитать элементарные операции, то на “нормальных” данных в одном случае получится O(N*logN), а в другом O(N*N).
t-rex wrote:я уже даже в общем решил для этого глобальную опцию делать
Вот за это спасибо!
t-rex wrote:Не наглей
А кто наглел? В S&R мощная функциональность, и терять её совсем не хочется. Или планируется реализовать всё то же самое в самом Фаре?
Фар есть инструмент, а не нянька. © 2009 DrKnS
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:он делает Match а не Search начиная с позиции курсора
Что понимается под Match и под Search?
По мне S&R ведёт себя вполне интуитивно: чётко отрабатывает обратный поиск по заданному RE.
Фар есть инструмент, а не нянька. © 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:Вообще-то я писал про количество поисков, а не про количество элементарных операций (типа циклов процессора). Сдаётся мне, что если посчитать элементарные операции, то на “нормальных” данных в одном случае получится O(N*logN), а в другом O(N*N).
В этом то и твоя логическая ошибка, количество поисков не является единственным фактором ибо o(n) поиска не константа. Тут "простой" формулой не обойтись.
HaRT wrote:А кто наглел? В S&R мощная функциональность, и терять её совсем не хочется. Или планируется реализовать то же самое в самом Фаре?
Ты наглел, ставя какие то кому то условия.
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:Ты наглел, ставя какие то кому то условия
Значит я просто недостаточно чётко выразился. Имелось в виду, что если S&R будет работать и в Фаре 1.8, то лично мне не будет так уж важно, будет ли поддержан обратный поиск самим Фаром.
Фар есть инструмент, а не нянька. © 2009 DrKnS
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:Хотя мне все ровно не понятно зачем нужен 1 вид поиска назад, так при том же поиске вперёд ты же обычно не ищес со следующего символа, а с конца того что нашлось, или я не прав?
Почему бы тогда при обычном поиске без регекспов не искать так же? Строка: 1234567890. Ищем с конца 6543 и находим. Или я что-то не понимаю в варианте 2?
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:Я этого и не утверждал. Я даже специально оговорился о разнице:
Нету никакой разницы, у всех один и тот же o(N) в этом то и весь прикол.
HaRT wrote:Значит я просто недостаточно чётко выразился
Да не всё чётко, опять всё те же условия.
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 »

Andrey Budko wrote:Почему бы тогда при обычном поиске без регекспов не искать так же? Строка: 1234567890. Ищем с конца 6543 и находим. Или я что-то не понимаю в варианте 2?
Вариант 2 не ищет наоборот :)

Вот пример, строка 1234567890, курсор в конце, ищем .*
Метод 1. находится 0
Метод 2. находится 1234567890
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:Вариант 2 не ищет наоборот
ну слава богу :crazy:
User avatar
John Doe
Бюрократ
Posts: 13075
Joined: Wed 27 Apr, 2005 20:42
Has thanked: 42 times
Been thanked: 319 times

Re: Far 1.8 - regexp

Post by John Doe »

t-rex wrote:Хотя мне все ровно не понятно зачем нужен 1 вид поиска назад, так при том же поиске вперёд ты же обычно не ищес со следующего символа, а с конца того что нашлось, или я не прав?
Видимо те кто высказываются за 1 вид поиска именно так и ищут:

Code: Select all

Do not process overlapping occurrences...
  [ ] ...when continuing searching
При этом поиск продолжается как раз со следуещего символа.
https://t.me/FarManager — Telegram чат
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 »

John Doe
Ну у меня лично эта опция отключена, не люблю не предсказуемости, я обычно просто сам курсор в конец передвигаю. Поэтому и не могу понять зачем нужен метод 1. Но раз кому то нужен, то видимо нужен.
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: у всех один и тот же o(N)
Эх, кто б меня научил искать в строке за o(N) хотя бы без RE. :P
t-rex wrote:те же условия
Условия-то те же, да я их никому не ставлю. Просто описываю соотношение ценностей в своём сознании.
John Doe wrote:именно так и ищут
Я — так.
Фар есть инструмент, а не нянька. © 2009 DrKnS
Post Reply

Return to “Development”