t-rex wrote:Вопрос тока что имено надо, "undo" поиска вперёд или настоящий поиск назад?
Ты имеешь в виду сначала найти все вхождения от начала до точки курсора, сохранить в список и потом последовательно выдавать по шифт-ф7 ничего больше не делая если условия не изменяются?
t-rex wrote:Вопрос тока что имено надо, "undo" поиска вперёд или настоящий поиск назад?
Ты имеешь в виду сначала найти все вхождения от начала до точки курсора, сохранить в список и потом последовательно выдавать по шифт-ф7 ничего больше не делая если условия не изменяются?
Что то я тебя потерял.
Как мы тут выяснили определить поиск назад можно по разному:
1. Находить последнее что нашел бы поиск вперёд (как бы прокрутка фильма назад)
2. Именно искать назад (как будто бы в реверсированой строке), максимальное совпадение (т.е. делать тоже самое что делал бы поиск вперёд).
t-rex wrote:
2. Именно искать назад (как будто бы в реверсированой строке), максимальное совпадение (т.е. делать тоже самое что делал бы поиск вперёд).
+1 за это
t-rex wrote:
1. Находить последнее что нашел бы поиск вперёд (как бы прокрутка фильма назад)
t-rex wrote:искать назад (как будто бы в реверсированой строке), максимальное совпадение
А можно практический пример, когда такое может понадобиться?
Если мне не надо бегать туда-сюда, а точно знать, что поведение поиска назад точно такое же как и поиска вперед, а именно жадное. Например вырезать в логе последнюю запись со всеми предшедствующими ей переводами строк, а не только с самым последним предшедствующим переводом строки (пример с потолка).
HaRT wrote:Подумаю. Но нельзя ли какой-нибудь примерчик, где половинное деление не приведёт к правильному результату?
Дело же не правильном или не правильном, а том что выйгрыша никакого нет и в том что чтоб работало надо псевдо половинное деление - т.е. ты ну ни как не можешь разделить строку на две части и искать в каждой по отдельности потому что часть искомого может быть в обоих половинках.
А насчёт поведения поиска назад, в поведение 2 можно получить поведение 1 как и сказал Тимур контролируя жадность.
А насчёт метода 1, мне вот тоже интересен пример когда он нужен - и не забудьте что пример должен быть с re с переменой длиной.
Про корректность: при поиске назад не требуется искать в каждой половине. Алгоритм такой: взяли среднюю позицию, ищем от неё вперёд. Если нашли, то следующее начало поиска будет серединой правой части, если не нашли — значит левой. У меня есть ощущение, что я даже готов представить строгое доказательство корректности такого подхода. Но есть ли смысл тратить на него силы в условиях, когда до строгих рассуждений не снисходят?
Про эффективность: при сдвиге по одному символу назад делается в среднем N/2 поисков, при половинном же делении — logN. Разумеется, это не идентичные поиски, но для проигрыша логарифма нужны уж очень экзотичные входные данные. На достаточно же длинных “обычных” строках различие получится ощутимое.
Про жадность: я принципиально считаю, что поиск назад — это парная функция к поиску вперёд, и они должны быть согласованы. Т.е. чтобы найти “то же самое” в обратном направлении не должно требоваться менять строку поиска.
Про пример: уже который раз пишу: бегать по длинному файлу взад-вперёд, глядя, что вокруг найденных вхождений. Есть сомнения, что в таком применении могут понадобиться RE переменной длины?
=Tim Sobolev= wrote:точно знать, что поведение поиска назад точно такое же как и поиска вперед, а именно жадное
-- т.е. точно знать что регулярка будет вести себя точно так же как при поиске вперед, а не вспоминать, каким должно быть последнее вхождение при поиске вперед этой же строки.
=Tim Sobolev=
Для регулярных выражений не определено понятие поиска назад, они умеют разбирать строку только вперёд (за исключением look-behind).
Вообще складывается впечатление, что обсуждение свелось к двум разным фичам, которые нужны разным людям:
1. Обратный поиск: находить все те и только те вхождения, что и прямой поиск, но в обратном порядке. 2. Поиск назад: искать по регулярному выражению от конца строки к её началу.
Если нет возражений против таких определений, давайте обсудим, почему бы не заложить в Фар обе эти фичи?
PS
Впрочем, поскольку S&R реализует обратный поиск, я не против того, чтобы в Фаре был поиск назад, разумеется, при условии, что S&R будет работать и в Фаре 1.8.