Алгоритм перноса слов в строке.

← →
panov © (2004-04-22 19:26) [0]

Посовеуйте максимально скоростной алгоритм переноса слов в строке.

Есть
1. Массив структур типа record:

TObj = record X,Y: Integer; Text: String; end

Arr: array of Obj;

2. TStringList со строками.

Необходимо сформировать из TStringList массив Arr, где каждый элемент Arr.Text будет содержать строку, содержащую количество символов не более Len, с минимальными затратами времени.

Строки из TStringList переносятся по словам.
За разделитель принимаем пробел и . - " " и ".";

← →
VictorT © (2004-04-22 19:53) [1]

> TObj = record
> X,Y: Integer;
> Text: String;
> end

А Х, Y для чего?

← →
panov © (2004-04-22 19:56) [2]

>VictorT © (22.04.04 19:53) [1]
X,Y используются для других целей.
У меня - это координаты.

← →
VictorT © (2004-04-22 19:58) [3]

Насчёт алгоритма - наверно так:
Переходим на позицию Len в исходной строке, и начиная с неё, уменьшая позицию, исчем первый встретившийся разделитель. Когда нашли, копируем кусок строки от начала до найденной позиции (назовём N) в первый елемент массива Arr. Переходим на позицию Len+N и т.д.

← →
panov © (2004-04-22 20:13) [4]

>VictorT © (22.04.04 19:58) [3]

Будет активное перераспределение памяти, наверное?

← →
VictorT © (2004-04-22 20:14) [5]

Т.е.?

← →
Anatoly Podgoretsky © (2004-04-22 20:17) [6]

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

← →
Anatoly Podgoretsky © (2004-04-22 20:19) [7]

И контроль обеих границ, а то можно залететь.

← →
Anatoly Podgoretsky © (2004-04-22 20:21) [8]

Скорость можешь повысить если откажешься от String в записи, в пользу ShortString или String[<=255]

← →
panov © (2004-04-22 20:36) [9]

>Anatoly Podgoretsky © (22.04.04 20:21) [8]
От стринг нельзя отказаться, к сожалению...

← →
Anatoly Podgoretsky © (2004-04-22 20:39) [10]

Я и не предлагаю отказываться от string, а предлагаю использовать другую string, со статической длиной. Думаю преобразование компилятор сам сделает.

TObj = record X,Y: Integer; Text: String[80]; end

← →
panov © (2004-04-22 20:43) [11]

Сейчас пытаюсь реализовать такой алгоритм:

1. Функция
function GetWrapText(const aSrc: String; const aMaxLen, aNumWrap: Integer;const aDelim: String): String;

aSrc - исходная строка
aMaxLen - мкс. длина подстроки
aNumWrap - номер строки, которую должна возвратить функция в режультате переносов
aDelim: список разделителей.

2. Выделяю массив для позиций разделителей в строке:

tmpPos: array[1..10000] of Integer;

В цикле заполняю массив, порходя по строке один раз.

3. в цикле по aNumWrap выбираю подходящие позиции для границ строки

← →
panov © (2004-04-22 20:46) [12]

Anatoly Podgoretsky © (22.04.04 20:39) [10]

Очень ценная мысль, спасибо

← →
Anatoly Podgoretsky © (2004-04-22 20:51) [13]

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

1. Вместо этого можно передавать индекс правого индекса, изначально длина строки. Тогда поиск пойдет от этой позиции.

2. Многократная передача разделителей и строки.

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

Это как один из вариантов, а то у тебя большие потери на передаче параметров и на поиске энной позиции разделения.

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

← →
panov © (2004-04-22 20:56) [14]

>Anatoly Podgoretsky © (22.04.04 20:51) [13]

1. Вместо этого можно передавать индекс правого индекса, изначально длина строки. Тогда поиск пойдет от этой позиции.

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

2. Многократная передача разделителей и строки.

Да, передача строки каждый раз - это накладные расходы. Но они разве не меньше, нежели передавать каждый раз подстроку - это копирование и перераспределение памяти.

К тому же строка передается по ссылке, как const.

← →
MBo © (2004-04-22 21:58) [15]

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

const Delims = [" ", ".", ","]; var s, snew: string; LastPos, LastDelim: Integer; i, Len, MaxLen: Integer; begin s := "Это длинная строка, наполненная всякой, блин, абракадаброй и вообще фигней"; LastDelim := 0; LastPos := 0; MaxLen := 20; Len := Length(s); for i := 1 to Len do begin if s[i] in Delims then LastDelim := i; if (i - LastPos = MaxLen) then begin SetString(snew, PChar(@s[LastPos + 1]), LastDelim - LastPos); Memo1.Lines.Add(snew); LastPos := LastDelim; end; end; if LastPos < Len then begin SetString(snew, PChar(@s[LastPos + 1]), Len - LastPos); Memo1.Lines.Add(snew); end; end;

← →
panov © (2004-04-22 22:05) [16]

>MBo © (22.04.04 21:58) [15]
Спасибо за код, сейчас потестирую...

← →
panov © (2004-04-22 22:22) [17]

>MBo © (22.04.04 21:58) [15]

Если "в лоб" использовать, то на 20000 строках выкушивает 260Мб памяти и работает около минуты...

← →
panov © (2004-04-22 22:30) [18]

Вот эта функция отрабатывает в пределах 5 сек, почти не ест памяти.
Но приемлимое время обработки - 1 - 1.5 сек... -(

function WWrap(aStr: String;aLen,aNumStr: Integer): String;
var
s: String;
nLine,nPos: Integer;
begin
s := WrapText(aStr,aLen);
Result := "";
nLine := aNumStr;
while nLine>0 do
begin
nPos := Pos(#13#10,s);
if nPos>0 then
begin
Dec(nLine);
if nLine=0 then
begin
Result := Copy(s,1,nPos-1);
end
else
begin
Delete(s,1,nPos+1);
Continue;
end;
end
else
begin
if s="" then Exit;
Dec(nLine);
if nLine>0 then
begin
Delete(s,1,aLen);
Continue;
end;
Result := Copy(s,1,aLen);
Exit;
end;
end;
end;

← →
panov © (2004-04-23 22:42) [19]

Вобчем свой алгоритм, который работал бы быстрееЮ чем DrawText с переносом, реализовать не удалось, поэтому пока остановился на
http://delphimaster.net/view/8-1082739156/

Всем спасибо.

← →
Piter © (2004-04-23 23:16) [20]

20.000 строк за 1,5 секунды? Хм, не круто ли берешь?

← →
panov © (2004-04-23 23:22) [21]

>Piter © (23.04.04 23:16) [20]
Сейчас 20000 строк обрабатывается не более 0.9 сек.

← →
panov © (2004-04-23 23:38) [22]

Все, похоже добился предела... время обработки 20000 строк 0.2-0.7 сек...

черт побери.. а что за машина?

А
function WrapText(const Line, BreakStr: string; const breakChars: TSysCharSet; MaxCol: Integer): string;
не смотрели?

RealRascal (24.04.04 00:11) [24]

а http://delphimaster.net/view/8-1082739156/ не смотрел?

ой, меня сглюкануло, сори. Пойду спать

упс...я тут, к сожелению, не постоянно...

Слегка измененый вариант MBO работает в ~10 раз быстрее, чем тебе надо. 99% времени занимает передача результата в Memo:procedure WordWrap(sl: TStrings; const s, Delim: string; MaxLen: integer); var IsDelim: array[char] of boolean; OldLine, NewLine, CurPos: integer; ch: char; begin; FillChar(IsDelim,SizeOf(IsDelim),false); IsDelim[ #0]:=true; for CurPos:=1 to Length(Delim) do IsDelim[Delim[CurPos]]:=true; OldLine:=1; NewLine:=1; CurPos:=1; if s<>"" then begin; while true do begin; ch:=s[CurPos]; inc(CurPos); if IsDelim[ch] then begin; NewLine:=CurPos; if ch=#0 then break; end; if CurPos-OldLine>=MaxLen then begin; if NewLine=OldLine then NewLine:=CurPos; sl.Add(Copy(s, OldLine, NewLine-OldLine)); OldLine:=NewLine; end; end; sl.Add(Copy(s, OldLine, NewLine-OldLine-1)); end; end; procedure TForm1.Button1Click(Sender: TObject); var i: integer; s: string; sl: TStringList; begin; s:="Это длинная строка, наполненная всякой, блин, абракадаброй и вообще фигней. "; for i:=1 to 14 do s:=s+s; //повторим 16*1024 раз sl:=TStringList.Create; try sl.Capacity:=20000; sl.BeginUpdate; WordWrap(sl,s," ,.",30); sl.EndUpdate; Memo1.Text:=sl.Text; finally sl.Free; end; end;

>Sha © (24.04.04 00:19) [28]

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

← →
Матлабист (2004-04-26 16:29) [30]

Про алгоритмы переноса текста можно почитать также в книге "Все про TeX". Глава "Как TeX разбивает абзац на строки". Там рассматривается довольно-таки общий случай... ;)

>>Sha © (24.04.04 00:19) [28]

Еще раз благодарю.
После адаптации алгоритма время обработки массива из 20000 строк сократилось до 0.05-0.10 сек. на PIV 2Гг RAM 512.
Дома протестирую на более медленном ПК.

Алгоритм перноса слов в строке. Найти похожие ветки