[M.A.D.M.A.N.]

Сообщение от SCrat.ORS

Результаты тестирования.

Я не знаю как ты тестил, но код, который я привел в примере, 1000 итераций на файле 66 852 700 байт (1 591 731 строк) выполняет мгновенно, за 0,00118835431432329 сек.
10000 итераций за 0,0126044552868083 сек.
Разовый поиск за 6,84213423583157E-6 сек.

[SCrat.ORS]

Bargest, Нет строки разные, поиск шёл по слову.
M.A.D.M.A.N. Я просто взял массив array of string, который динамически расширял и заносил сортированный список. Функцию поиска просто скопипастил, единственно заменил TStringArray на array of string, т.к. у меня массив использовался, если быть точным MASS : array of array [0..2] of string (да, такой вот странный) и на функцию подавал MASS[0] . Затем поставил GetTickCount и запустил цикл поиска 10000 раз по первому слову в массиве, слову в середине массива, и последнему слову в массиве, GetTickCount снимал после циклов поиска каждого слова. После чего вывел среднее арифметическое из 3 результатов, аналогично для разных длин массива.
А теперь об ошибке, - когда я передал функции массив длинной 1 700 000, он выбил Ошибку. И еще, обрати внимание, я время указывал в Миллисекундах. Опять таки, возможно, я использовал на форме, а у вас возможно в консоли. Возможно комп слабее/мощнее. Что бы было нагляднее, проведи тестирование тоже всех 4 видов... Конечно я согласен, что тупо перебор слово в первой строке найдет мгновенно, а последнее слово - чем больше массив тем дольше,.. Ясен перец Бинарный поиск в огромном массиве найдет в разы быстрее, но у меня почему-то результат обратный - наверное что-то не так сделал - не отрицаю, сам был удивлён.

[Bargest]

А теперь об ошибке, - когда я передал функции массив длинной 1 700 000, он выбил Ошибку

Раз ошибка Stack Overflow, то скорее всего делфи попыталась выделить полтора ляма строк на стеке из-за кривого объявления его типа.

[M.A.D.M.A.N.]

Сообщение от SCrat.ORS

M.A.D.M.A.N. Я просто взял массив array of string, который …

Я на стринглисте тестировал. Вообще, массивы неудобная штука для обработки списков.

Комп 4 ядра, тестировал на форме, вместо «счетчика клещей», я использовал «перформанс каунтер».

По поводу тайминга:

Код:

10^−1     деци     
10^−2     санти     
10^−3     милли     
10^−6     микро     
10^−9     нано     
10^−12     пико     
10^−15     фемто     
10^−18     атто     
10^−21     зепто     
10^−24     иокто     

=> 0,00118835431432329 сек = 1188 микросекунд.

[SCrat.ORS]

Все-таки в моём понимании массив - это array а не StringList...
А почему в бинарном поиске у меня вылезает ошибка стека при большом количестве записей - не понимаю... другие то функции ошибки не вызывают.

[M.A.D.M.A.N.]

Чем вообще обусловлен выбор array?

[SCrat.ORS]

Ну изначально вопрос встал так:
У меня есть какой-то файл, в котором содержится информация об каких-либо свойствах объектов, а именно - название, длина, ширина, который я загружаю в один array.
Так же имеется список, скажем выставленных объектов на карту (пусть так), где записано, ИД объекта, его координаты (x,y) и название объекта, которые я загружаю в другой array, и непосредственно с этим массивом работаю.
И при отрисовке объекта на карте мне надо получить его длину и ширину. И тут вызываю поиск по массиву с информацией - передаю название объекта, на выходе получаю длину и ширину (пусть в TPoint, - не суть)... поэтому и получается что использовать StringList как-то не правильно. А список выставленных объектов иногда может переваливать за несколько тысяч, а то и десятков тысяч... Идея такова.
Да и по жизни я стараюсь использовать array of myTypes для запоминания свойств объектов.
Когда реализовывал задачу, я подумал, что перебор по всем строкам массива будет очень медленным способом поиска и сделал кроме основного массива с информацией еще и stringList, где в том же порядке записал просто названия объектов, а далее при работе просто вызывал IndexOf и получал нужный мне индекс. Потом по этому индексу брал из массива информацию. Теперь, как я понял, я выбрал самый тормознутый способ.
В любом случае Пост получился довольно интересным для меня, за что всем принявшим участие в нем - огромное спасибо. Конечно хочется развить тему дальше и найти самый продуктивный способ как поиска так и хранения свойств каких-либо объектов (частенько требуется).

[M.A.D.M.A.N.]

Сообщение от SCrat.ORS

Да и по жизни я стараюсь использовать array of myTypes для запоминания свойств объектов.

Всё понятно, разговор окончен.

[Bargest]

список, скажем выставленных объектов на карту (пусть так), где записано, ИД объекта, его координаты (x,y) и название объекта

Это просто гениально. Надо было вообще все параметры задать строками, генерировать строковый GUID вместо ID и его тоже искать. И координаты тоже строками записать. Нужно БОЛЬШЕ поиска по строкам.

Есть множество объектов на карте. У каждого есть уникальный ID. Зачем передавать название объекта, когда можно передавать ID? Если по названию находится не сам объект, а его прототип (общий для нескольких объектов), то что мешает в массиве объектов хранить не имя, а индекс прототипа или (лучше) сразу указатель на него и не искать ничего вообще?

Нужно просто нормально организовать данные. Если нужно отрисовать объект, то отрисовка должна происходить не по имени, а по индексу/указателю. Также должно быть можно через индексы/указатели от объекта добраться ко всем данным, которые могут потребоваться для отрисовки. Даже известный мне шедевр игрового убожества, наглядное пособие "как НЕ надо писать игры", и те не додумались каждые 20мс брутфорсить 10к строк, а просто посчитали от имени 4-байтовый хеш, запихнули в хеш-таблицу по первым двум байтам и положили болт на потенциальные коллизии, т.е. у них во время выполнения имен фактически нет вовсе. Не говоря уже о том, что для отрисовки не используется даже ID - он им нужен по-моему только для интегрированных скриптов.

[SCrat.ORS]

Сообщение от Bargest

Есть множество объектов на карте. У каждого есть уникальный ID. Зачем передавать название объекта, когда можно передавать ID? Если по названию находится не сам объект, а его прототип (общий для нескольких объектов), то что мешает в массиве объектов хранить не имя, а индекс прототипа или (лучше) сразу указатель на него и не искать ничего вообще?

Дак я так и делаю.
Сначала загружаю информацию о "протопитах" в отдельный массив.
Потом в рабочий массив загружаю информацию об объектах, тут же попутно нахожу "протопип" по названию, и подгружаю туда же нужную информацию о "прототипе". Т.Е. поиск мне необходим только при первом запуске, что бы получить всю нужную информацию. И потом в процессе работы никакго поиска не произвожу вообще.

[Bargest]

Т.Е. поиск мне необходим только при первом запуске

А ранее было написано:

И при отрисовке объекта на карте мне надо получить его длину и ширину. И тут вызываю поиск по массиву с информацией

Так-то получше, конечно. Но вообще список прототипов можно сделать нормальной хеш-таблицей (без коллизий, т.е. с сохранением оригинальных имен), считать от имени нужного прототипа хеш и сравнивать строку не с 10к других, а с двумя-тремя.
То есть просто копипастим с вики crc8/crc16/crc32, берем младшие 1-2 байта результата, используем как индекс в массиве динамических списков. Каждый N-ный элемент - список прототипов, хеш от имени которых начинается на N. Поскольку хеши стремятся к равномерному "распределению", то таблица будет заполняться равномерно, и в среднем поиск будет производиться не среди 10к строк, а среди 10к/256 или 10к/65536 строк если брать 1 или 2 байта хеша соответственно. А можно взять и 1.5 байта хеша и будет поиск среди 10к/4096, т.е. в среднем среди двух строк.
И кстати, я бы сделал наоборот. Сарзу загружаю информацию об объектах, ищу для них по хеш-таблице прототип, и если не найден - загружаю прототип и добавляю в хеш-таблицу. Это позволит загружать только нужные прототипы, а не все (ведь на одной карте могут использоваться не все прототипы).

[SCrat.ORS]

Сообщение от lmikle

Код:

function Hash(S : String; HashSize : Integer) : Integer;
var
  Sm : Int64;
begin
  Sm := 0;
  For I := 1 To Length(S-1) Do
    Sm := (Sm + Ord(S[i])) * 31;
  Result := (Sm + Ord(S[Length(S)])) mod HashSize;
end;

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

Где-то из этой области? Есть где по-подробнее почитать?

[Bargest]

Можно конечно и свой велосипед придумать, но есть готовые решения, считаемые легко и довольно удобно. Я обычно использую табличные варианты. Из простых есть еще известный ror13-хеш:

Код:

hash := 0;
for i := 1 to length(str) do
   hash := ((hash shl (32-13)) or (hash shr 13)) + str[i];

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

[SCrat.ORS]

Просто оставлю это здесь

Код:

//  Name  : CRC-8
//  Poly  : 0x31    x^8 + x^5 + x^4 + 1
//  Init  : 0xFF
//  Revert: false
//  XorOut: 0x00
//  Check : 0xF7 ("123456789")

function crc8(Buffer:String):byte; 
var
  i,j: Integer;
begin
Result:=$FF;
for i:=1 to Length(Buffer) do begin
  Result:=Result xor ord(buffer[i]);
  for j:=0 to 7 do begin
    if (Result and $80)<>0 then Result:=(Result shl 1) xor $31
    else Result:=Result shl 1;
    end;
  end;
end;

[SCrat.ORS]

Bargest, спасибо за наводку.
Результат:
2 000 000 Строк, 100 000 циклов поиска: Среднее время поиска 0,078 мсек.
Результат Бинарного поиска от M.A.D.M.A.N. (который мне не удалось сделать, поэтому результат его) 12,6 мсек. (0,0126044552868083 сек).
Это конечно несколько разные подходы к организации массивов и поиска, но ради интереса. Так что да,.. хранить нужно с хешем.
M.A.D.M.A.N. Твой результат в мсек. примерно тоже самое что у меня и показывает. Так что все более менее одинаково и твои Мгновенно - это и есть 11 мсек. Вероятно Бинарный поиск дает свои плоды если количество слов более 10млн, т.к. до 2 млн, он по вычислениям почти совпадает с Простым перебором. Вот такое вот исследование.

Вот как реализовал:

Код:

...

Type TMyArray = Packed Record
SomeName:String;
end;

Type
MyArray = array [$00..$FF] of Array of TMyArray;

...

function crc8(Buffer:String):byte;
var
  i,j: Integer;
begin
Result:=$FF;
for i:=1 to Length(Buffer) do begin
  Result:=Result xor ord(buffer[i]);
  for j:=0 to 7 do begin
    if (Result and $80)<>0 then Result:=(Result shl 1) xor $31
    else Result:=Result shl 1;
    end;
  end;
end;

function FindM(const AText: string; const AValues: array of TMyArray): Integer;
var
  I: Integer;
begin
  Result := -1;
  for I := Low(AValues) to High(AValues) do
    if AText=AValues[i].SomeName then
    begin
      Result := I;
      Break;
    end;
end;

Function Find(S:String; M: MyArray):TPoint;
Var
NDX:Integer;
Begin
NDX:=CRC8(s);
Result.X:=NDX;
Result.Y:=FindM(s,M[NDX]);
End;

...

procedure TForm1.Button1Click(Sender: TObject);
Var
I:TPoint;
N:String;
begin
I:=Find('СТРОКА ПОИСКА', MItemInformation); //MItemInformation - Это массив в котором ищем
If i.Y>-1 then N:=MItemInformation[I.X,I.Y].SomeName;
end;