Страница 1 из 2
Поиск строки в массиве
Добавлено: 14.12.2023 10:28:10
ssnakess
Есть список (Tlist) из 100тыс записей вида
Код: Выделить всё
Type
PData = ^TData;
TData = record
id:Integer;
name:String;
family:String;
nikname:String;
end;
Подскажите, что можно использовать в лазарусе для поиска по строки в этом списке (например найти запись у которой nikname='vasya')
Простым перебором - долго ищет, что естественно.
Т.е. наверняка есть какието классы которые позволяют посчитать хеши строк и потом искать по этим хешам
Или может есть какие-то другие варианты?
Не хочется засовывать данные в базу, это как из пушки по воробьям

Re: Поиск строки в массиве
Добавлено: 14.12.2023 10:39:41
RRYTY
Используйте сортированный список.
Re: Поиск строки в массиве
Добавлено: 14.12.2023 10:46:22
iskander
Сразу возникает вопрос, строки, по которым требуется поиск, уникальны или нет?
Re: Поиск строки в массиве
Добавлено: 14.12.2023 11:27:47
sts
https://forum.lazarus.freepascal.org/in ... #msg137298
If you want to make your own BST Tree then yes. Otherwise you can use TAVLTree. It is in avl_tree unit. Just add it to your uses section and learn how to use it.
Re: Поиск строки в массиве
Добавлено: 14.12.2023 19:38:51
ssnakess
iskander писал(а):Сразу возникает вопрос, строки, по которым требуется поиск, уникальны или нет?
да, конечно уникальные
Добавлено спустя 7 минут 9 секунд:
sts писал(а):https://forum.lazarus.freepascal.org/index.php/topic,23070.msg137298.html#msg137298
If you want to make your own BST Tree then yes. Otherwise you can use TAVLTree. It is in avl_tree unit. Just add it to your uses section and learn how to use it.
Я уже смотрел в эту сторону. Но меня смущает сравнение строк как таковых.
Что-то тут не правильное
посчитать может какойнить crc32 от строки и уже по нему делать дерево.
Или я туплю и так можно Str1>Str2 и это нормально?
Re: Поиск строки в массиве
Добавлено: 14.12.2023 20:09:33
iskander
ssnakess писал(а):да, конечно уникальные
Для уникальных ключей всё достаточно просто, используем хешмэп из Generics.Collections(полагаю, айдишки тоже должны быть уникальны), данные хранятся в отдельном массиве, поскольку создаётся два индекса:
Код: Выделить всё
program test;
{$mode objfpc}{$h+}
uses
SysUtils, Generics.Collections;
type
PData = ^TData;
TData = record
id: Integer;
name,
family,
nikname: string;
end;
TNikMap = specialize TDictionary<string, PData>;
TIdMap = specialize TDictionary<Integer, PData>;
const
Data: array of TData = (
(id: 1; name: 'John'; family: 'Doe'; nikname: 'Wistle'),
(id: 3; name: 'Tom'; family: 'Brown'; nikname: 'Crow'),
(id: 7; name: 'Eva'; family: 'Smith'; nikname: 'Dolly')
);
var
IdMap: TIdMap;
NikMap: TNikMap;
I: Integer;
p: PData;
begin
NikMap := TNikMap.Create;
IdMap := TIdMap.Create;
for I := 0 to High(Data) do begin
IdMap.Add(Data[I].id, @Data[I]); // бросит исключение, если такой ключ уже существует
NikMap.Add(Data[I].nikname, @Data[I]);
end;
if NikMap.TryGetValue('Dolly', p) then
with p^ do begin
WriteLn('id: ', id);
WriteLn('name: ', name);
WriteLn('family: ', family);
WriteLn('nikname: ', nikname);
end;
if IdMap.TryGetValue(3, p) then
with p^ do begin
WriteLn('id: ', id);
WriteLn('name: ', name);
WriteLn('family: ', family);
WriteLn('nikname: ', nikname);
end;
NikMap.Free;
IdMap.Free;
end.
Re: Поиск строки в массиве
Добавлено: 15.12.2023 06:53:09
Alex2013
Зачем такие извраты ? Обычный TStringList делает тоже самое только проще и совместимее(А возможно и быстрее ).
Код: Выделить всё
program test;
{$mode objfpc}{$h+}
uses
SysUtils,Classes;
type
PData = ^TData;
TData = record
id: Integer;
name,
family,
nikname: string;
end;
const
Data: array of TData = (
(id: 1; name: 'John'; family: 'Doe'; nikname: 'Wistle'),
(id: 3; name: 'Tom'; family: 'Brown'; nikname: 'Crow'),
(id: 7; name: 'Eva'; family: 'Smith'; nikname: 'Dolly')
);
var StrList: TStringList;
I: Integer;
begin
StrList:=TStringList.Create; StrList.Sorted:=True; //True - сортировать, False - не сортировать
StrList.Duplicates:=dupIgnore; //dupAccept - сохранять дубликаты (значение по умолчанию), dupIgnore - игнорировать, dupError - вызвать сообщение об ошибке
//Используем
for I := 0 to High(Data) do StringList.addObject(Data[I].nikname, TObject(@Data[I])); //и дело в шляпе !
if StringList.Find('Dolly', i) then
with PData(StringList.Objects[i])^ do
begin
WriteLn('id: ', id);
WriteLn('name: ', name);
WriteLn('family: ', family);
WriteLn('nikname: ', nikname);
end;
StrList.Free;
end;
Re: Поиск строки в массиве
Добавлено: 15.12.2023 08:01:04
iskander
Alex2013 писал(а):Обычный TStringList делает тоже самое только проще и совместимее(А возможно и быстрее ).
Совместимее с чем?
Насчёт производительности: добавление элементов в сортированный TStringList имеет квадратичную сложность.
А поиск строковых ключей в хеш-таблице размера 10^5 элементов должен быть на порядок быстрее, чем в сортированном списке или двоичном дереве поиска.
Re: Поиск строки в массиве
Добавлено: 15.12.2023 11:13:40
ssnakess
Alex2013 писал(а):Зачем такие извраты ? Обычный TStringList делает тоже самое только проще и совместимее(А возможно и быстрее ).
Как вариант - да, можно и так, но если полей по которым искать несколько, то по каждому надо делать свой TStringList.
Но тут я согласен с
iskander писал(а):добавление элементов в сортированный TStringList имеет квадратичную сложность
добавит 100тыс строк в StringList - долгая пестня
Скорее всего этот вариант
iskander писал(а):Для уникальных ключей всё достаточно просто, используем хешмэп из Generics.Collections(полагаю, айдишки тоже должны быть уникальны), данные хранятся в отдельном массиве, поскольку создаётся два индекса:
будет быстрее, если он при добавлении элементов не создает копии строк, а добавляет ссылку.
Т.е. вот тут в строке NikMap.Add(Data
.nikname, @Data); первый аргумент будет добавлен ссылкой на строку или будет создаваться её копия?
Код: Выделить всё
for I := 0 to High(Data) do begin
IdMap.Add(Data[I].id, @Data[I]); // бросит исключение, если такой ключ уже существует
NikMap.Add(Data[I].nikname, @Data[I]);
end;
Re: Поиск строки в массиве
Добавлено: 15.12.2023 11:38:31
grot
ssnakess писал(а):Есть список ... из 100тыс записей
Зачем столько данных хранить в памяти ?
Такие объемы обычно принято держать в специализированном хранилище, правильно - в базе данных.
Да и поиск по Базе будет "быстрым" !
А в памяти надо жержать столько данных, для которых любой вид доступа будет "быстрым" !
Re: Поиск строки в массиве
Добавлено: 15.12.2023 13:26:27
RRYTY
grot писал(а):Такие объемы обычно принято держать в специализированном хранилище, правильно - в базе данных.
100 килозаписей - это копейки. Примерно с таким объемом работает SEN (чуть более 85 тысяч записей на энергии и чуть более двух тысяч - на нуклиды). И никаких баз данных там не надо. Есть еще один проект, но там данные не для публикации, - 200 килозаписей, причем добавляются ежедневно десятками. Даже мысли не возникло в БД это пихать.
Re: Поиск строки в массиве
Добавлено: 15.12.2023 14:01:18
iskander
ssnakess писал(а):в строке NikMap.Add(Data.nikname, @Data); первый аргумент будет добавлен ссылкой на строку или будет создаваться её копия?
Ссылкой, конечно.
grot писал(а):Зачем столько данных хранить в памяти ?
Так для быстрого поиска же.
grot писал(а):Такие объемы обычно принято держать в специализированном хранилище, правильно - в базе данных.
Да и поиск по Базе будет "быстрым" !
Вменяемый движок БД также будет стараться запихать в оперативку чем больше тем лучше.
А то что будет быстрее, это далеко не факт, поскольку между движком и приложением обычно ещё имется слой различных передастов, обеспечивающих доступ.
Re: Поиск строки в массиве
Добавлено: 15.12.2023 14:25:17
Sharfik
Читать тему лень, просто от себя скажу.
Сравнивать строки нафиг не надо в прямую. Сравнивай через CompareText()=0 или ShortCompareText()=0.
Сравнивать будет в разы быстрее. Но они сравнивают без учета регистра. В теории, если все равно хочется быстрее, то дели на потоки. Один поток с 1..500, второй 500..1000 и т.д. Кто первый нашел тот молодец. Остальным умереть.
Re: Поиск строки в массиве
Добавлено: 15.12.2023 21:36:52
Alex2013
iskander писал(а):Alex2013 писал(а):Обычный TStringList делает тоже самое только проще и совместимее(А возможно и быстрее ).
Совместимее с чем?
Насчёт производительности: добавление элементов в сортированный TStringList имеет квадратичную сложность.
А поиск строковых ключей в хеш-таблице размера 10^5 элементов должен быть на порядок быстрее, чем в сортированном списке или двоичном дереве поиска.
1 Никто незнает что там с дженериками дальше будет. ( я когда-то вдоволь намучился с разными версиями )
2 Это если искать в несортированном TStringList (Через indexOf ) а Find ищет в сортированном массиве что огромная разница
3 Не знаю как это сейчас но ранее что-то типа IdMap.Add работало чудовищно медленно ( примерно как добавление по одному новых элементов в динамический(так и хочется написать "демонический"

) массив )
Добавлено спустя 12 минут 38 секунд:
ssnakess писал(а):Т.е. вот тут в строке NikMap.Add(Data.nikname, @Data); первый аргумент будет добавлен ссылкой на строку или будет создаваться её копия?
В данном случае копия но это не обязательно. ( досточно подменить метод сортировки через CustomSort )
Код: Выделить всё
function mySort(L : TStringList; Item1, Item2: Integer): Integer;
begin
Result := CompareStr(L[Item1], L[Item2]);
end;
procedure TMainForm.Button1Click(Sender: TObject);
var L : TStringList;
begin
//
L := TStringList.Create;
L.Add('start');
L.Add('finish');
L.Add('end');
L.Add('begin');
L.CustomSort(@mySort);
Memo1.Lines.AddStrings(L);
L.Free;
end;
(Переделывать пример лениво, но вроде всё и так "интуитивно понятно " )
Код: Выделить всё
function mySort(L : TStringList; Item1, Item2: Integer): Integer;
begin
Result := CompareStr(PData(L.Objects[Item1])^.nikname , PData(L.Objects[Item2])^.nikname);
end;
+
Код: Выделить всё
for I := 0 to High(Data) do StringList.addObject( '', TObject(@Data[I]));
(То есть можно не использовать основной массив строк, а только ссылки на Objects )
Зы
Кстати CustomSort пересортировывает то есть можно сделать mySort01, mySort02 и т.д.
Re: Поиск строки в массиве
Добавлено: 15.12.2023 22:16:59
iskander
Alex2013 писал(а):1 Никто незнает что там с дженериками дальше будет. ( я когда-то вдоволь намучился с разными версиями )
Потрясающе веский аргумент из уст человека, прожившего уже почти четверть 21 века и по сию пору считающего хеш-таблицу извращением.
Alex2013 писал(а):2 Это если искать в несортированном TStringList (Через indexOf ) а Find ищет в сортированном массиве что огромная разница
Утверждение без доказательства можно отвергнуть без всякого объяснения.
Alex2013 писал(а):3 Не знаю как это сейчас но ранее что-то типа IdMap.Add работало чудовищно медленно
См пункт 2.
Alex2013 писал(а):Добавлено спустя 12 минут 38 секунд:
ssnakess писал(а):
Т.е. вот тут в строке NikMap.Add(Data.nikname, @Data); первый аргумент будет добавлен ссылкой на строку или будет создаваться её копия?
В данном случае копия но это не обязательно. ( досточно подменить метод сортировки через CustomSort )
Брехня. И TDictionary не использует никаких CustomSort.