Поиск строки в массиве

[ssnakess]

Есть список (Tlist) из 100тыс записей вида

Код: Выделить всё

Type
        PData = ^TData;
        TData = record
          id:Integer;
          name:String;
          family:String;
          nikname:String;
       end;


Подскажите, что можно использовать в лазарусе для поиска по строки в этом списке (например найти запись у которой nikname='vasya')
Простым перебором - долго ищет, что естественно.
Т.е. наверняка есть какието классы которые позволяют посчитать хеши строк и потом искать по этим хешам
Или может есть какие-то другие варианты?
Не хочется засовывать данные в базу, это как из пушки по воробьям

[RRYTY]

Используйте сортированный список.

[iskander]

Сразу возникает вопрос, строки, по которым требуется поиск, уникальны или нет?

[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.

[ssnakess]

Сразу возникает вопрос, строки, по которым требуется поиск, уникальны или нет?

да, конечно уникальные

Добавлено спустя 7 минут 9 секунд:

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 и это нормально?

[iskander]

да, конечно уникальные

Для уникальных ключей всё достаточно просто, используем хешмэп из 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.


[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;


[iskander]

Обычный TStringList делает тоже самое только проще и совместимее(А возможно и быстрее ).

Совместимее с чем?
Насчёт производительности: добавление элементов в сортированный TStringList имеет квадратичную сложность.
А поиск строковых ключей в хеш-таблице размера 10^5 элементов должен быть на порядок быстрее, чем в сортированном списке или двоичном дереве поиска.

[ssnakess]

Зачем такие извраты ? Обычный TStringList делает тоже самое только проще и совместимее(А возможно и быстрее ).

Как вариант - да, можно и так, но если полей по которым искать несколько, то по каждому надо делать свой TStringList.
Но тут я согласен с

добавление элементов в сортированный TStringList имеет квадратичную сложность

добавит 100тыс строк в StringList - долгая пестня

Скорее всего этот вариант

Для уникальных ключей всё достаточно просто, используем хешмэп из Generics.Collections(полагаю, айдишки тоже должны быть уникальны), данные хранятся в отдельном массиве, поскольку создаётся два индекса:

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

Т.е. вот тут в строке NikMap.Add(Data[I].nikname, @Data[I]); первый аргумент будет добавлен ссылкой на строку или будет создаваться её копия?

Код: Выделить всё

  for I := 0 to High(Data) do begin
    IdMap.Add(Data[I].id, @Data[I]);      // бросит исключение, если такой ключ уже существует
    NikMap.Add(Data[I].nikname, @Data[I]);
  end;


[grot]

Есть список ... из 100тыс записей

Зачем столько данных хранить в памяти ?
Такие объемы обычно принято держать в специализированном хранилище, правильно - в базе данных.
Да и поиск по Базе будет "быстрым" !

А в памяти надо жержать столько данных, для которых любой вид доступа будет "быстрым" !

[RRYTY]

Такие объемы обычно принято держать в специализированном хранилище, правильно - в базе данных.

100 килозаписей - это копейки. Примерно с таким объемом работает SEN (чуть более 85 тысяч записей на энергии и чуть более двух тысяч - на нуклиды). И никаких баз данных там не надо. Есть еще один проект, но там данные не для публикации, - 200 килозаписей, причем добавляются ежедневно десятками. Даже мысли не возникло в БД это пихать.

[iskander]

в строке NikMap.Add(Data[I].nikname, @Data[I]); первый аргумент будет добавлен ссылкой на строку или будет создаваться её копия?

Ссылкой, конечно.

Зачем столько данных хранить в памяти ?

Так для быстрого поиска же.

Такие объемы обычно принято держать в специализированном хранилище, правильно - в базе данных.
Да и поиск по Базе будет "быстрым" !

Вменяемый движок БД также будет стараться запихать в оперативку чем больше тем лучше.
А то что будет быстрее, это далеко не факт, поскольку между движком и приложением обычно ещё имется слой различных передастов, обеспечивающих доступ.

[Sharfik]

Читать тему лень, просто от себя скажу.
Сравнивать строки нафиг не надо в прямую. Сравнивай через CompareText()=0 или ShortCompareText()=0.
Сравнивать будет в разы быстрее. Но они сравнивают без учета регистра. В теории, если все равно хочется быстрее, то дели на потоки. Один поток с 1..500, второй 500..1000 и т.д. Кто первый нашел тот молодец. Остальным умереть.

[Alex2013]

Обычный TStringList делает тоже самое только проще и совместимее(А возможно и быстрее ).

Совместимее с чем?
Насчёт производительности: добавление элементов в сортированный TStringList имеет квадратичную сложность.
А поиск строковых ключей в хеш-таблице размера 10^5 элементов должен быть на порядок быстрее, чем в сортированном списке или двоичном дереве поиска.

1 Никто незнает что там с дженериками дальше будет. ( я когда-то вдоволь намучился с разными версиями )
2 Это если искать в несортированном TStringList (Через indexOf ) а Find ищет в сортированном массиве что огромная разница
3 Не знаю как это сейчас но ранее что-то типа IdMap.Add работало чудовищно медленно ( примерно как добавление по одному новых элементов в динамический(так и хочется написать "демонический" ) массив )

Добавлено спустя 12 минут 38 секунд:

Т.е. вот тут в строке NikMap.Add(Data[I].nikname, @Data[I]); первый аргумент будет добавлен ссылкой на строку или будет создаваться её копия?

В данном случае копия но это не обязательно. ( досточно подменить метод сортировки через 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 и т.д.

[iskander]

1 Никто незнает что там с дженериками дальше будет. ( я когда-то вдоволь намучился с разными версиями )

Потрясающе веский аргумент из уст человека, прожившего уже почти четверть 21 века и по сию пору считающего хеш-таблицу извращением.

2 Это если искать в несортированном TStringList (Через indexOf ) а Find ищет в сортированном массиве что огромная разница

Утверждение без доказательства можно отвергнуть без всякого объяснения.

3 Не знаю как это сейчас но ранее что-то типа IdMap.Add работало чудовищно медленно

См пункт 2.

Добавлено спустя 12 минут 38 секунд:
ssnakess писал(а):
Т.е. вот тут в строке NikMap.Add(Data[I].nikname, @Data[I]); первый аргумент будет добавлен ссылкой на строку или будет создаваться её копия?

В данном случае копия но это не обязательно. ( досточно подменить метод сортировки через CustomSort )

Брехня. И TDictionary не использует никаких CustomSort.