Как работать с большим обьемом строк.

← →
DDS (2004-02-04 10:49) [0]

Моя программа работает с большими обьемами строк.
Я использую TStringList, но таким макаром все работает медленно
и в него больше 64KB не запишешь. Как быстро манипулировать строками. Например WinAmpУ практически не составляет труда сортировать или просто загрузить плейлист на 2 тысячи файлов и осуществлять поиск по ним.

← →
Beat © (2004-02-04 10:52) [1]

Почему больше 64Кб не загрузишь???

Тормозит??? List.Sorted - ?

← →
Palladin © (2004-02-04 10:52) [2]

> в него больше 64KB не запишешь.

неправда

> все работает медленно

как определил?

← →
Reindeer Moss Eater © (2004-02-04 10:53) [3]

Где написано про ограничение в 64К у TStringList?

Например WinAmpУ практически не составляет труда сортировать или просто загрузить плейлист на 2 тысячи файлов и осуществлять поиск по ним.

Где написано, что что он делает это? (грузит 2 тысячи имен)

← →
Digitman © (2004-02-04 10:54) [4]

> в него больше 64KB не запишешь

что, прямо так и говорит, мол, отвали, не запишу больше 64KB ?

← →
Beat © (2004-02-04 10:56) [5]

Удалено модератором

← →
Reindeer Moss Eater © (2004-02-04 10:59) [6]

Удалено модератором

← →
Beat © (2004-02-04 11:00) [7]

Reindeer Moss Eater:
сортируется то весь список, но ОДИН раз после его создания - иначе никак

з.ы. все ухожу _приятно_ было пообщаться...

← →
Sergey_Masloff (2004-02-04 11:04) [8]

В TStringList можно запихать несколько сотен Mb без проблем и тормозов, так теоретически пару гигов ;-)

← →
Digitman © (2004-02-04 11:22) [9]

очевидно, следы чудес ведут к стринглисту в составе TMemo
тогда все вполне объяснимо

← →
Плохиш (2004-02-04 11:25) [10]

> Digitman © (04.02.04 11:22) [9]
> очевидно, следы чудес ведут к стринглисту в составе TMemo
> тогда все вполне объяснимо

под Вынь9x

← →
DDS (2004-02-04 16:49) [11]

Когда я в цикле перебираю все строки StringList то
это получается накладно по времени.

А насчет WinAmpА если кому-то надо могу скинуть скриншот
вот у меня MP3шек ровно 1849 это после того как я штук 500 нарезал.

А в WinAmpЕ вся эта груда строк сортируется причем и по тегам за несколько секунд. Я в словей проге только минут 5 жду пока прочту тег каждого файла. Да хотя бы грузить просто имена файлов в StringList идет долго.

← →
Тимохов © (2004-02-04 16:51) [12]

2 млн строк в TStingList сортируется много меньше чем за 1 сек - поверь.
В своей проге ты ждешь 5 секунд не из за tstringlist, а из за неточностой в своем алгоритме.

← →
Digitman © (2004-02-04 17:06) [13]

> DDS

перед заполнением списка :

- отключи автосортировку
- установи св-во Capacity равным макс.числу строк, которые планируется добавить (если это значение заранее известно тебе)

после заполнения списка перед вызовом методов поиска строк по их значению включи автосортировку

← →
Reindeer Moss Eater © (2004-02-04 17:11) [14]

Удалено модератором

← →
RealRascal © (2004-02-04 19:05) [15]

Не знаю мне кажется ничего лучше Tstringlist для работы с большим количеством строк не существует... И врядли удастся сократить время поиска написав свой алгоритм.
Ибо насколько я понимаю по (этот кусок из Classes)
function TStringList.IndexOf( const S: string): Integer; begin if not Sorted then Result := inherited IndexOf(S) else if not Find(S, Result) then Result := -1; end; function TStringList.Find( const S: string; var Index: Integer): Boolean; var L, H, I, C: Integer; begin Result := False; L := 0; H := FCount - 1; while L <= H do begin I := (L + H) shr 1; C := AnsiCompareText(FList^[I].FString, S); if C < 0 then L := I + 1 else begin H := I - 1; if C = 0 then begin Result := True; if Duplicates <> dupAccept then L := I; end; end; end; Index := L; end;

если список несортированный, то поиск ведется простым перебором, а если сортированный - то бинарным поиском. А ничего эффективнее последнего для сортированных списков нет.

← →
DDS (2004-02-04 23:24) [16]

Удалено модератором

← →
DDS (2004-02-04 23:30) [17]

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

Я дкмаю, что алгоритмы сортировки гнилые, может кто-нибудь посоветовать инфу по сортировкам строк?

Да к стати у меня в циклах идет обращение к VCLкам я от этого избавился и вроде выиграл несколько секунд, но все же долго он с ними работает.

К примеру просто перебрать все строки списка и проверить каждую на вхождение подстроки. Если 1000 строк то ждать надо.

← →
Юрий Зотов © (2004-02-04 23:57) [18]

> DDS (04.02.04 23:30) [17]

К примеру просто перебрать все строки списка и проверить каждую на вхождение подстроки. Если 1000 строк то ждать надо.

procedure TForm1.Button1Click(Sender: TObject);
var
i: integer;
T: DWORD;
begin
with TStringList.Create do
try
for i := 0 to 999999 do Add("asdladnadmasdmna");
T := GetTickCount;
for i := 0 to Count - 1 do Pos("AasasaS", Strings[i]);
Caption := IntToStr(GetTickCount - T)
finally
Free
end
end;

Результаты:
1. StringList без проблем вместил миллион строк.
2. Вызов Pos для каждой из миллиона строк - менее полсекунды.

Выводы напрашиваюся: "Дело было не в бобине..."

← →
DDS (2004-02-05 00:07) [19]

А из за частого обращения к визуальным компонентам в цикле могет отниматься много времени?

← →
Юрий Зотов © (2004-02-05 00:28) [20]

> DDS (05.02.04 00:07) [19]

Если они при этом перерисовываются (например, обновляют отображаемые данные) - то перерисовка будет отнимать не просто много, а ОЧЕНЬ много времени.

Если в цикле есть инварианты - вытащите их наружу. Если есть обращения к свойствам объектов - закэшируйте их (например, простейшая замена свойства Text на обычную строку как-то сократила время работы одной программы с 4-х часов до 6 минут).

И т. д. Понимаете, при нормальном построении кода тех проблем, о которых Вы говорите, просто не может быть. Ну никак.

← →
DDS (2004-02-05 01:15) [21]

Короче понял я, похоже, в чем пробемма.
Есть у меня такая функция:

function TForm1.GetKey(str:string):integer;
var i:integer;
begin
result:=-1;
for i:=0 to List.Count-1 do
begin
if pos(str,List[i])>0
then begin result:=i; break; end;
end;
end;

Она очень часто используется в программе
и почти всегда примерно вот в таком виде:

for i:=0 to List.Count-1 do
begin
r:=GetKey(List[i]);
if r>0 then List_1.Add(List[i]); //к примеру
end;

И никак переделать нельзя.
Короче двойной цикл по всем элементам списка,
и так как списки не маленькие, то

2000 строк в одном и 2000 в другом
2000*2000=4 000 000

(все равно, что for i:=0 to 2000 do for j:=0 to 2000 do)
Если я правильно все написал, то как же мне быстро найти строку
в списке в которой содержится нужная подстрока.

← →
dr Tr0jan © (2004-02-05 04:18) [22]

Народ, а не проще ли потоками (TStream) все сделать?

← →
Palladin © (2004-02-05 07:18) [23]

хм... ну во первых советую использовать другой алгоритм Pos, не тот что в System, помоему библиотека называется FastStrings... во вторых искать не в TStringList, а слить в одну строку с указанием индексированых диапазонов для каждой строки, таким образом Pos можно будет вызвать лишь один раз для определения номера строки, в которой найден Str...

← →
DHDD (2004-02-05 07:37) [24]

>DDS (05.02.04 01:15) [21]
Ты понимаешь, что написал? 8-0

← →
ЮЮ © (2004-02-05 07:59) [25]

>for i:=0 to List.Count-1 do
>begin
> r:=GetKey(List[i]);
> if r>0 then List_1.Add(List[i]); //к примеру
>end;

>И никак переделать нельзя.

r всегда > 0, т.к. List[k] как минимум равен List[k] для любого k
Поэтому весь цикл приводится к
List_1.Assign(List);

← →
DDS (2004-02-05 13:47) [26]

СПасибо, попробую, напишу ответ.

← →
DDS (2004-02-05 14:46) [27]

>ЮЮ
r не всегда > 0 потому, что функция GetKey возвращает -1 если ее параметр не является подстрокой другого списка. А если является то возвращает индекс строки. И функция тоже работает в цикле по всему списку.

>с указанием индексированых диапазонов для каждой строки

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

>Palladin
А где FastStrings найти, на Мастерах или на Torry есть, у тебя есть ссылка?

Тоесть надо сделать GetKey без использования цикла.Вот идея, может и бредовая но это мне в голову пришло:
Берем StringList и записываем его как Text и записываем его в какой-нибудь
RichEdit. Дальше используя встроенный RichEdit1.FindText ищем текст и потом
выражаем номер строки в RichEdit из найденногою. Это и будет номер из StringList.
Я не говорю, что делать надо точно так, например можно не использовать визуальный
компонент RichEdit, а RichEdit1.FindText взять из ComCtrls.

Получаем:
RichEdit1.PlainText:=True; RichEdit1.Text:=List.Text; RichEdit1.SelStart:=RichEdit1.FindText(Str,1,Length(RichEdit1.Text),[]); RichEdit1.SelLength:=0;

{{Из Delphi FAQ}}
Как получить номер строки memo, в которой находится курсор?
Для этого необходимо послать сообщение EM_LINEFROMCHAR.
LineNumber := Memo1.Perform(EM_LINEFROMCHAR, -1, 0);
{{Из Delphi FAQ}}

То же самое использовать для RichEdit.
Сильно не ругайтесь на все это.

>DDS (05.02.04 14:46) [27]
а еще лучше установить MS SQL Server, он быстро ищет

← →
Serginio666 (2004-02-05 15:14) [29]

DDS (05.02.04 01:15) [21]
Ищи половинным делением в сортированном TstringList или на неполное совпадение, или делай хэш таблицу например
http://rsdn.ru/Forum/Message.aspx?mid=419818&only=1

> DDS (05.02.04 14:46) [27]

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

s[1]:="abc";
s[2]:="def";
s[3]:="ghi";

строим массив индексов
indexArray:array [1..3] of integer;
заполняем его по следующему принципу
indexArray[1]:=1;
for i:=2 to 3 do indexArray[i]:=indexArray[i-1]+Length*s[i-1]+1;
добравшись до последнего индекса
SetLength(strCommon,indexArray[3]+Length(s[3]));
заполняем strCommon
for i:=1 to 3 do
begin
Move(s[i][1],strCommon[indexArray[i]],Length(s[i]));
strCommon[indexArray[i]-1]:=#13;
end;
дальше получаем позицию подстроки
nPos:=Pos(strSubStr,strCommon);
и бинарный поиск по indexArray (здесь писать не буду, сам пиши) тебе даст номер в исходном массиве строк...
faststrings ищи в инете

← →
DDS (2004-02-05 21:48) [31]

Я придумал кое-что: (FastString нашел)
Гружу список в STRING ищу подстроку а дальше перебираю символы от найденной позиции
1) влево пока не найду сивол начала строки 0Ah
2) вправо пока не найду сивол перевода строки 0Dh
Между ними моя строка. Фактически я выразил строку из списка. Получаю ее индекс через IndexOf.

List.Count ~ 2000 строк
Что придумал работает за ~40000мс
Но едрить-колотить старый вариант работает быстрее в 5 раз!!!!!!!!
Почему НОВЫЙ вариант медленнее там ведь операции простые и цикла нет.

{{{{ Старый вариант был: }}}}
procedure TForm1.GetKey(ind:integer);
var i:integer;
s:string;
begin
s:=Drugoi_List[ind]; //Подстрока
k:=-1;
for i:=0 to List.Count-1 do //Просто перебираю
begin
if pos(s,List[i])>0 //Нашел
then begin k:=i; break; end;
end;
end;

{{{{ Новый вариант: }}}}
procedure TForm1.GetKey(ind:integer);
var i,st_ln,ps:integer;
st,bx:string;
begin
tx:=List.Text; //Загружаю весь лист в STRING
tx_ln:=length(tx); //Ну и длину за одно
st:=Drugoi_List[ind]; //Подстрока
st_ln:=length(st); //И ее длина

{Ищу входждение подстроки st в строке всего списка tx}
ps:=FastPos(tx,st,tx_ln,st_ln, 1);
if ps>0 then
begin
ps:=FastPosBack(tx,ord(10),tx_ln,1, ps); //Ищу начало строки т.е. символ начала строки
bx:=copy(tx,ps,length(tx)-ps);
bx:=copy(bx,1,pos(ord(13),bx)+2); //С того самого начала по символ конца строки
k:=List.IndexOf(bx); //Ищу полученную строку в списке через IndexOf и получаю номер строки
end;
end;

{{{{ Использование: }}}}
for i:=0 to List.Count-1 do
GetKey(i,false);

Пробовал так же не каждый раз грузить весть лист в STRING а только 1ый.

← →
DDS (2004-02-06 00:10) [32]

ВСЕ!ВСЕ!ВСЕ!ВСЕ!ВСЕ!ВСЕ!ВСЕ!ВСЕ!ВСЕ!ВСЕ!ВСЕ!ВСЕ!ВСЕ!ВСЕ!ВСЕ!
СПАСИБО ВАМ ЛЮДИ ДОБРЫЕ!
Я РЕШИЛ ЗАБИТЬ НА ВСЕ ЭТО И ОСТАВИТЬ ПРЕЖНИЙ ВАРИАНТ.
РАБОТАЕТ И ЛАДНО. ВСЕМ ЕЩЕ РАЗ СПАСИБО!

Очень правильная позиция, в следующий рах когда например в программе будет постоянно выскакивать AV, также забей на ВСЕ

← →
Serginio666 (2004-02-06 12:20) [34]

Я бы тебе посоветовал поиск по вхождению в строку метод Боуера-Мура Харрисона. Я его применяю например.
http://www.1c.hippo.ru/cgi-bin/predownl.cgi?id=2019

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

← →
Serginio666 (2004-02-06 12:23) [35]

DDS (06.02.04 00:10) [32]
Прошу прощения за назойливость но позволю себе предложить Вам весьма неплохую статью
http://www.rsdn.ru/article/alg/textsearch.xml

← →
DDS (2004-02-08 01:37) [36]

Спасибо, но ссылка дохлая

Как работать с большим обьемом строк. Найти похожие ветки