Функция, вырезающая строку между двумя разделителями

← →
Piter © (2005-08-19 21:28) [0]

Ищу функцию, в которую передается 3 параметра: исходная строка и два разделителя.
Результатом является строка, находящяяся между этими двумя разделителями в исходной строке.

Ну хотелось бы как можно быстрее :)

прототип:

function CutString(Src, BeginSeparator, EndSeparatpr: string): string

Примеры работы:

CutString("abcdefg", "ab", "ef") = "cd"

CutString("bbvatzq", "a", "b") = ""

← →
Джо © (2005-08-19 21:30) [1]

А что там сложного? Обычный Pos + Copy. Или, если на то пошло, for := 1 to Length...

← →
Piter © (2005-08-19 21:34) [2]

Еще пример:

CutString("bbvatzq", "b", "a") = "bv"

← →
Piter © (2005-08-19 21:35) [3]

Джо © (19.08.05 21:30) [1]

требуется быстрый вариант, наверняка есть уже готовые функции... не хочу изобретать медленный велосипед.

← →
Piter © (2005-08-19 21:41) [4]

Явот где-то нашел в своих архивах функцию эту:

function CuteString(BeginSeparator:string; EndSeparator:string; s:string):string; var i, i2:integer; substr:string; begin result:=""; if BeginSeparator="" then i:=1 else i:= PosJOH_MMX_a(BeginSeparator, s); if i<>0 then begin inc(i, Length(BeginSeparator)); substr:=copy(s,i,length(s)-i+1); if EndSeparator="" then i2:=length(substr)+1 else i2:=PosJOH_MMX_a(EndSeparator,SubStr); inc(i2,i-1); if i2>i then Result:=Copy(s,i,i2-i); end; end;

она рабочая... только мне ее сейчас даже анализировать влом :)

Возможно, есть достаточно стандартные решения?

← →
Leonid Troyanovsky © (2005-08-19 21:59) [5]

> Piter © (19.08.05 21:41) [4]

> она рабочая... только мне ее сейчас даже анализировать влом
> :)

Т.е., ты подозреваешь, что нас в уикенд делать оное не ломает?
Тем более, что мы даже не знаем кто такой PosJOH_MMX_a.

--
Regards, LVT.

← →
Piter © (2005-08-19 22:16) [6]

Leonid Troyanovsky © (19.08.05 21:59) [5]
Т.е., ты подозреваешь, что нас в уикенд делать оное не ломает?

да я же говорю о том, что есть стандартное решение. Может у кого есть - поделится тогда

А функцию я делал сам - поэтому уверен, что можно куда лучше :)

Тем более, что мы даже не знаем кто такой PosJOH_MMX_a.

ну это аналог POS, только более быстрый, взял с какого-то сайта, где проводились соревнования по этому делу.

← →
GuAV © (2005-08-19 23:07) [7]

Piter © (19.08.05 21:41) [4]

> substr:=copy(s,i,length(s)-i+1);

> i2:=PosJOH_MMX_a(EndSeparator,SubStr);

ИМХО это плохо тем, что создаётся лишняя строка. Причём для EndSeparator = "" она уже результат, фигли ты ещё делаешь, а для EndSeparator <> "" неоправданные затраты, лучше искать конец через PosEx. Попробуй переделать PosJOH_MMX_a в PosEx ;)

Кстати, в ММХ уже другой победитель :)
http://dennishomepage.gugs-cats.dk/PosChallenge.htm

← →
Piter © (2005-08-19 23:16) [8]

GuAV © (19.08.05 23:07) [7]
переделать PosJOH_MMX_a в PosEx

ну вот, только я переделал и захотел запостить, а ты уже предложил :)

Итак, мой вариант теперь таков:

function CuteString(BeginSeparator:string; EndSeparator:string; var s:string):string; var i, i2:integer; begin Result := ""; if BeginSeparator = "" then i := 1 else i := PosEx_Sha_IA32_3_a(BeginSeparator, s); if i > 0 then begin inc(i, Length(BeginSeparator) ); if EndSeparator = "" then i2 := Length(s) + 1 else i2 := PosEx_Sha_IA32_3_a( EndSeparator, s, i); if i2 > i then Result := Copy(s, i, i2 - i); end; end;

← →
Piter © (2005-08-19 23:16) [9]

Piter © (19.08.05 23:16) [8]
PosEx_Sha_IA32_3_a

это самый быстрый пока аналог PosEx

← →
OldNaum © (2005-08-20 03:00) [10]

GuAV © (19.08.05 23:07) [7]
Спасибо за сайтец. Очень интересная "кладовая" ) Никогда не забуду длиннющие топики, где Вы, Defunct (если не ошибаюсь) и многие другие "ускоряли" Pos.

← →
Piter © (2005-08-20 12:00) [11]

А у кого по сабжу соображения будут? :)

← →
Anatoly Podgoretsky © (2005-08-20 12:50) [12]

Есть соображение, что его можно написать.

← →
Piter © (2005-08-22 03:53) [13]

Anatoly Podgoretsky © (20.08.05 12:50) [12]

кого написать?

← →
Defunct © (2005-08-22 03:57) [14]

> кого написать?

Миша ты же не тормоз?
Его - т.е. сабж.

← →
Piter © (2005-08-22 13:24) [15]

Функцию? Это понятно, что ее можно написать, а что дальше?

Можно ОС написать. И программу управления ядерными ракетами - тоже можно написать.

Не понимаю - как это относится к теме ветке?

← →
Piter © (2005-08-22 13:25) [16]

Я же не спрашивал - можно ли написать такую функцию.
Я просил наиболее оптимальный вариант.

Хотя бы оптимальнее моего в [8]

← →
Anatoly Podgoretsky © (2005-08-22 13:39) [17]

Piter © (22.08.05 13:24) [15]
Не к теме ветки, а в первую очередь к сообщению номер 11, если соображения не нужны то зачем же спрашиваешь, по крайней мере предупреждай, что вопрос риторический.

← →
Leonid Troyanovsky © (2005-08-22 14:10) [18]

> Piter © (22.08.05 13:25) [16]
> Я же не спрашивал - можно ли написать такую функцию.
> Я просил наиболее оптимальный вариант.
>
> Хотя бы оптимальнее моего в [8]

Вот тебе еще вариант (сделан на коленке).
Теперь можешь и сравнивать.

function CutString(const Src, BeginSeparator, EndSeparator: string): string; var p, p1, p2, pe : PChar; begin p := PChar(src); p1 := nil; p2 := nil; pe := p + Length(Src); while (p <= pe) and not Assigned(p2) do begin if StrLComp(p, PChar(BeginSeparator), Length(BeginSeparator)) = 0 then begin p1 := p + Length(BeginSeparator); p := p1; while p <= pe do begin if StrLComp(p, PChar(EndSeparator), Length(EndSeparator)) = 0 then begin p2 := p; Break; end else inc(p); end; end else inc(p); end; if Assigned(p2) then SetString(Result, p1, p2-p1); end;

--
Regards, LVT.

← →
afanasic (2005-08-22 14:26) [19]

А что мы будем делать в таком варианте:
CutString("cbcabdaca","b","a") = ???
Какое значние правильное:
"c",
"cabd" или
"cabdac"?

← →
afanasic (2005-08-22 14:27) [20]

Ибо алгоритмы будут существенно различаться...

← →
Piter © (2005-08-22 14:51) [21]

Anatoly Podgoretsky © (22.08.05 13:39) [17]
если соображения не нужны то зачем же спрашиваешь

а-а-а... ясно. То есть, на вопрос "Как написать функцию..." ответ "Можно написать" и является соображением? :)
Ок, ок, я не понял :)))

afanasic (22.08.05 14:26) [19]
А что мы будем делать в таком варианте:
CutString("cbcabdaca","b","a") = ???

= "c"

← →
Anatoly Podgoretsky © (2005-08-22 15:04) [22]

Piter © (22.08.05 14:51) [21]
В 11 был задан совсем другой вопрос, соображения по "сабжу", а не "как написать функцию". Правильно формулировать вопросы это твоя задача. Предъявлять по этому поводу предензии по крайней мере некрасиво.

← →
Alx2 © (2005-08-22 15:09) [23]

>Piter © (19.08.05 21:28)

Как велика (в среднем) строчка-аргумент?

← →
afanasic (2005-08-22 15:09) [24]

Тогда, учитывая и такую подставу:
CutString("abcd","abc","bcd"), очень просто и достаточно быстро, причем вместо Pos можно использовать любую функцию, которая быстрее:

function CutString(St, BegSt, EndSt: String): String; var k1,k2,n: Integer; begin Result := ""; // поищем первую строку k1 := Pos(BegSt,St); // если есть, то будем искать вторую после первой if k1 > 0 then begin Delete(St,1,k1-1); k2 := Pos(EndSt,St); if k2 > 0 then begin n := Length(BegSt); Result := Copy(st,n+1,k2-n-1); end; end; end;

← →
Anatoly Podgoretsky © (2005-08-22 15:15) [25]

afanasic (22.08.05 15:09) [24]
Надо избежать использования Delete это очень медленная операция.

← →
afanasic (2005-08-22 15:19) [26]

Вместо Delete(...)
St := Copy(St,k1,Length(st)-k1+1);

← →
Anatoly Podgoretsky © (2005-08-22 15:23) [27]

Алгоритм долже быть примерно таким
Найти начало и записать его в переменную K
Если K>0 (здесь постановка отсутствует) тогда или выход или установка К=1

Далее если М = 0 (здесь постановка отсутствует), или выход или установка М=конец строкитогда концом считать последнюю позицию или выход из фукнции, поскольку условие не выполнилось, оставим это автору.

Если K и M равно 0 (постановка отсутствует) то выход или копирование с установкой других значений.

Кроме этого ответить на вопросы от других участников, какой должен быть вариант и уточнив постановку написать за пару минут функцию.

← →
Anatoly Podgoretsky © (2005-08-22 15:28) [28]

afanasic (22.08.05 15:19) [26]
Шило на мыло, не надо ни удалять ни копировать. Надо найти начало и конец и работать уже с этим. Операции изменения строки очень медленные. Это выделение памяти (возможно освобождение старой), копирование информации. А в конце концов окажется, что от исходной строки в пару сотен килобай нужно только один/два символа. Автор заостряет вопрос как сделать это оптимально, а не как вообще сделать.

← →
Piter © (2005-08-22 15:53) [29]

Leonid Troyanovsky © (22.08.05 14:10) [18]

сравнил :(
Твой вариант в 20 раз медленнее.

Если не возражаешь против такого теста:

procedure TForm1.Button1Click(Sender: TObject); const cSizeString = 300000; // массив для тестирования будет состоять из 300 тысяч строк var arr, ArrBeginSeparator, ArrEndSeparator: array of string; i, CountSymbol: integer; Time1, Time2: cardinal; function GenerateString(Size: integer): string; var i: integer; begin SetLength(Result, Size); Randomize; for i := 1 to Length(Result) do Result[i] := Chr (Random( ord("z") - ord("a") ) + ord("a") ); // символы генерятся от a до z end; begin SetLength(arr, cSizeString); SetLength(ArrBeginSeparator, cSizeString); SetLength(ArrEndSeparator, cSizeString); Randomize ; for i := 0 to High(arr) do begin CountSymbol := Random(1000) + 5; // длина строк от 5 до 1000 символов arr[i] := GenerateString(CountSymbol); CountSymbol := Random(30) + 3; // длина разделителей от 3 до 30 символов ArrBeginSeparator[i] := GenerateString(CountSymbol); CountSymbol := Random(30) + 3; // длина разделителей от 3 до 30 символов ArrEndSeparator[i] := GenerateString(CountSymbol); end; Time1 := GetTickCount; for i := 0 to High(arr) do CuteStringMy(arr[i], ArrBeginSeparator[i], ArrEndSeparator[i]); Time1 := GetTickCount - TIme1; Time2 := GetTickCount; for i := 0 to High(arr) do CuteStringLVT(arr[i], ArrBeginSeparator[i], ArrEndSeparator[i]); Time2 := GetTickCount - TIme2; showmessage(IntToStr(Time1) + #13#10 + IntToStr(Time2)); end;

Готовый проект - http://piter.pechora.org/temp/test_cute_string_Piter_vs_LVT.zip

Пробовал тестировать на 1 миллионе строк - не хватило вирт. памяти :)

← →
Piter © (2005-08-22 15:56) [30]

afanasic (22.08.05 15:09) [24]
Delete(St,1,k1-1);

даже тестировать не имеет смысла. Будет ОЧЕНЬ долго...

← →
Piter © (2005-08-22 16:03) [31]

Anatoly Podgoretsky © (22.08.05 15:23) [27]
Найти начало и записать его в переменную K
Если K>0 (здесь постановка отсутствует

Вероятно, имелось в виду K<1.
Если K < 1 - то результат пустая строка, кроме случая когда BeginSeparator = "", тогда K = 1

Далее если М = 0 (здесь постановка отсутствует

Если M = 0 - то результат функции - пустая строка, кроме случаев EndSeparator = "", тогда M равен последнему символу во входящей строке

Anatoly Podgoretsky © (22.08.05 15:23) [27]
написать за пару минут функцию.

напишите

← →
Игорь Шевченко © (2005-08-22 16:04) [32]

А можно вопрос? Где и когда эта функция будет вызываться ?
А то получится, как у Конецкого, что смысла ускорять ее будет ровно столько же, сколько в определении длины шага у старого мерина, которого ведут на живодерню.

← →
Piter © (2005-08-22 16:07) [33]

Piter © (22.08.05 15:53) [29]
Пробовал тестировать на 1 миллионе строк - не хватило вирт. памяти :)

при этом обе функции демонстрирует, в общем, хорошее время.

На 300 тысяч строках все происходит не более 10-ти секунд

← →
Piter © (2005-08-22 16:09) [34]

Игорь Шевченко © (22.08.05 16:04) [32]
А можно вопрос? Где и когда эта функция будет вызываться ?

Текущее время уже абсолютно приемлимо.
Теперь просто интересно - можно ли быстрее :)

То есть, можно то точно, но вот интересно посмотреть на реализацию.

А вообще - такая функция уже использовалась в двух проектах, теперь просто хочется выбрать один раз и навсегда самую быструю :)

← →
Игорь Шевченко © (2005-08-22 16:29) [35]

Piter © (22.08.05 16:09) [34]

Я к чему спрашиваю - в несильно критичных местах я бы предпочел ясность и удобочитаемость кода в ущерб быстродействию.

← →
Leonid Troyanovsky © (2005-08-22 16:36) [36]

> Piter © (22.08.05 15:53) [29]
> Leonid Troyanovsky © (22.08.05 14:10) [18]
>
> сравнил :(
> Твой вариант в 20 раз медленнее.

20 это серьезно :)
Правда, пока непонятно, за счет, собс-но, чего.

По-поводу самого тестирования есть замечание,
т.е., на самом деле, на месте оптимизатора я
удалил бы оба цикла, бо ничего полезного они делают.

С другой стороны, такие вещи следует делать
примерно так: делаем цикл n раз, 2*n раз, 3*n раз
и строим зависимость T - n. Обычно это прямая
(не из нуля). Сравниваем только скорость (угол наклона).

Замечу, что еще одним подводным камнем может быть
порядок, т.е. после работы одного блока может
произойти, скажем, сброс страниц в своп.

Т.е., надо давать поработать и одной и другой функции,
возможно, в случайном порядке.

--
Regards, LVT.

> Leonid Troyanovsky © (22.08.05 16:36) [36]

> примерно так: делаем цикл n раз, 2*n раз, 3*n раз
> и строим зависимость T - n. Обычно это прямая

Фу-ты. Зависимость T от раз (1, 2, 3, ..)
Sorry.

--
Regards, LVT.

Игорь Шевченко © (22.08.05 16:29) [35]
в несильно критичных местах я бы предпочел ясность и удобочитаемость кода в ущерб быстродействию

ну не знаю. Это ведь функция сама в себе, оттестированная, черный ящик. Какая разница что там внутри? Известен алгоритм работы - а что еще надо?

Leonid Troyanovsky © (22.08.05 16:36) [36]
т.е., на самом деле, на месте оптимизатора я
удалил бы оба цикла, бо ничего полезного они делают

понятное дело, но причем же здесь это :)
Оптимизатор не вдается в подробности - что там делает функция CuteString и нужен ли возвращаемый результат. Главное, что функции исполняются.

А насчет из корректности - вроде обе функции верные значения возвращают, поэтому это я не тестировал.

Leonid Troyanovsky © (22.08.05 16:36) [36]
С другой стороны, такие вещи следует делать
примерно так: делаем цикл n раз, 2*n раз, 3*n раз
и строим зависимость T - n

ломало :)

Замечу, что еще одним подводным камнем может быть
порядок, т.е. после работы одного блока может
произойти, скажем, сброс страниц в своп

нет, тут я пробовал несколько раз и в разном порядке - ничего не меняется.

Piter © (22.08.05 16:03) [31]
Anatoly Podgoretsky © (22.08.05 15:23) [27]
Найти начало и записать его в переменную K
Если K>0 (здесь постановка отсутствует

Вероятно, имелось в виду K<1.

Да именно так.

напишите

Еще чего, нет такого желания просто так делать, будет конкретная задача, то естественно напишу, а просто так тратить время не могу, есть более насущные задачи. Тем более при отсутствии точной постановки задачи.

Ок, ок, не хотите - как хотите.

Одна мысля только - если вы, Анатолий, такой занятой, то не понимаю, чего вы участвуете в десятке форумов, в ФИДО и еще черт знаем в чем :)))

Уверен, это отнимает много часов КАЖДЫЙ день :)

Piter © (22.08.05 21:27) [41]
Занятой или нет не важно, я могу заняться и посторонней проблемой если она представит для меня интерес, ну например новихной. Данная проблема мне не интересна. Максимус что могу, так это пару замечаний или предложений, если сочту нужным.

А в форумах участвую по многим причинам, главная из которых развлечение, но и отлов интересных сообщений, которые могут пригодится, не могу же я все проверять самостоятельно, вот и использую совместный опыт. Хоть КПД и низок, но всегда что то есть очень полезное. Ну а время, не секрет, начиная с 6:30 до 24:00. Интернет постоянный, не лимитированый, быстрый. Компьютеры постоянно включены. Сервер вообще никогда не выключается.

Вот пишу в последнее время очень мало.

← →
ev (2005-08-22 22:03) [43]

можно еще так :)

str:=TStringList.Create;
str.Delimiter:="|";
str.DelimitedText:="asd|ddd|s|dd";

> Leonid Troyanovsky © (22.08.05 16:36) [36]

> 20 это серьезно :)
> Правда, пока непонятно, за счет, собс-но, чего.

Эа счет использования Паскаля и основного цикла,
в котором многократно вызываются внешние процедуры
Length и StrLComp.

Вместо SetString часто эффективнее использовать
комбинацию SetLength + Move.

> Sha © (23.08.05 08:43) [44]

> > 20 это серьезно :)
> > Правда, пока непонятно, за счет, собс-но, чего.

> Эа счет использования Паскаля и основного цикла,
> в котором многократно вызываются внешние процедуры
> Length и StrLComp.

Ну, Piter тоже пользовал не асм.
И если процедуры были внутренние, оно б сильно не изменилось.

Значит, вывод сделаем следующий:
за счет вызова процедур (сам вызов и операции с регистрами).
Т.е., ускориться можно, например, вписав вместо StrLComp
пару собс-ных циклов.

> Вместо SetString часто эффективнее использовать
> комбинацию SetLength + Move.

Трудно согласиться, бо противоречит первому утверждению.

--
Regards, LVT.

> Leonid Troyanovsky © (23.08.05 15:24) [45]
> Ну, Piter тоже пользовал не асм.

У него как раз все циклы на асме во внешней PosEx.

> И если процедуры были внутренние, оно б сильно не изменилось.

Естественно, это позволило только не передавать параметры.
Речь о том, чтобы свести количество вызовов любых процедур
к минимуму. У Piter"а их всего 3, а у тебя ~Length(Src)*2

> > Вместо SetString часто эффективнее использовать
> > комбинацию SetLength + Move.
> Трудно согласиться, бо противоречит первому утверждению.

Если не ошибаюсь, SetString всегда приводит к выделению новой
строки. А так как строка-результат функции всегда уникальна,
то обычно более чем в половине случаев комбинация
SetLength + Move приводит к обрезанию старого результата,
что увеличивает эффективность при коротких результатах.

> Sha © (23.08.05 16:54) [46]

> то обычно более чем в половине случаев комбинация
> SetLength + Move приводит к обрезанию старого результата,

Старого, это какого?

--
Regards, LVT.

> Jeer © (23.08.05 17:18) [48]

> Надо понимать, предыдущего:)

Неее. Оно нам негоже, бо недокументировано.

--
Regards, LVT.

> Jeer © (23.08.05 17:18) [48]
> Leonid Troyanovsky © (23.08.05 17:04) [47]
>
> Надо понимать, предыдущего:)

Да, и, вообще, если строка-результат всегда уникальна,
то как может случиться, что она содержит результат
предыдущего вызова.

--
Regards, LVT.

> Leonid Troyanovsky ©
> Старого, это какого?

Того, что осталься от предыдущего вызова.

> Неее. Оно нам негоже, бо недокументировано.

Документировано в исходниках.
Память под строку-результат выделяет вызывающая функция.
Если делается несколько вызовов, старый результат
замещается новым.

> Да, и, вообще, если строка-результат всегда уникальна,

Уникальность строки означает, что ее счетчик ссылок равен 1.

> то как может случиться, что она содержит результат
> предыдущего вызова.

Как описано выше :)

--
Best regards,
Aleksandr

Функция, вырезающая строку между двумя разделителями Найти похожие ветки