Форум по Delphi программированию

Delphi Sources



Вернуться   Форум по Delphi программированию > Все о Delphi > Синтаксис
Ник
Пароль
Регистрация <<         Правила форума         >> FAQ Пользователи Календарь Поиск Сообщения за сегодня Все разделы прочитаны

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
  #16  
Старый 13.02.2015, 22:37
Аватар для M.A.D.M.A.N.
M.A.D.M.A.N. M.A.D.M.A.N. вне форума
Sir Richard Abramson
 
Регистрация: 05.04.2008
Сообщения: 5,505
Версия Delphi: XE10
Репутация: выкл
По умолчанию

Цитата:
Сообщение от SCrat.ORS
Результаты тестирования.

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


На Delphi, увы, больше не программирую.
Рекомендуемая литература по программированию

Последний раз редактировалось M.A.D.M.A.N., 13.02.2015 в 22:44.
Ответить с цитированием
  #17  
Старый 13.02.2015, 22:49
Аватар для SCrat.ORS
SCrat.ORS SCrat.ORS вне форума
Активный
 
Регистрация: 20.02.2007
Адрес: Мой адрес не дом и не улица, мой адрес 0x7С00
Сообщения: 208
Версия Delphi: 2006
Репутация: 884
По умолчанию

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 видов... Конечно я согласен, что тупо перебор слово в первой строке найдет мгновенно, а последнее слово - чем больше массив тем дольше,.. Ясен перец Бинарный поиск в огромном массиве найдет в разы быстрее, но у меня почему-то результат обратный - наверное что-то не так сделал - не отрицаю, сам был удивлён.
__________________
Програмистами не рождаются, ими становятся!

Последний раз редактировалось SCrat.ORS, 13.02.2015 в 23:14.
Ответить с цитированием
  #18  
Старый 14.02.2015, 01:20
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

Цитата:
А теперь об ошибке, - когда я передал функции массив длинной 1 700 000, он выбил Ошибку
Раз ошибка Stack Overflow, то скорее всего делфи попыталась выделить полтора ляма строк на стеке из-за кривого объявления его типа.
__________________
jmp $ ; Happy End!
The Cake Is A Lie.
Ответить с цитированием
  #19  
Старый 14.02.2015, 08:48
Аватар для M.A.D.M.A.N.
M.A.D.M.A.N. M.A.D.M.A.N. вне форума
Sir Richard Abramson
 
Регистрация: 05.04.2008
Сообщения: 5,505
Версия Delphi: XE10
Репутация: выкл
По умолчанию

Цитата:
Сообщение от 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 микросекунд.
__________________
— Как тебя понимать?
— Понимать меня не обязательно. Обязательно меня любить и кормить вовремя.


На Delphi, увы, больше не программирую.
Рекомендуемая литература по программированию

Последний раз редактировалось M.A.D.M.A.N., 14.02.2015 в 08:57.
Ответить с цитированием
  #20  
Старый 14.02.2015, 13:06
Аватар для SCrat.ORS
SCrat.ORS SCrat.ORS вне форума
Активный
 
Регистрация: 20.02.2007
Адрес: Мой адрес не дом и не улица, мой адрес 0x7С00
Сообщения: 208
Версия Delphi: 2006
Репутация: 884
По умолчанию

Все-таки в моём понимании массив - это array а не StringList...
А почему в бинарном поиске у меня вылезает ошибка стека при большом количестве записей - не понимаю... другие то функции ошибки не вызывают.
__________________
Програмистами не рождаются, ими становятся!
Ответить с цитированием
  #21  
Старый 14.02.2015, 13:45
Аватар для M.A.D.M.A.N.
M.A.D.M.A.N. M.A.D.M.A.N. вне форума
Sir Richard Abramson
 
Регистрация: 05.04.2008
Сообщения: 5,505
Версия Delphi: XE10
Репутация: выкл
По умолчанию

Чем вообще обусловлен выбор array?
__________________
— Как тебя понимать?
— Понимать меня не обязательно. Обязательно меня любить и кормить вовремя.


На Delphi, увы, больше не программирую.
Рекомендуемая литература по программированию
Ответить с цитированием
  #22  
Старый 14.02.2015, 13:57
Аватар для SCrat.ORS
SCrat.ORS SCrat.ORS вне форума
Активный
 
Регистрация: 20.02.2007
Адрес: Мой адрес не дом и не улица, мой адрес 0x7С00
Сообщения: 208
Версия Delphi: 2006
Репутация: 884
По умолчанию

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

Последний раз редактировалось SCrat.ORS, 14.02.2015 в 14:09.
Ответить с цитированием
  #23  
Старый 14.02.2015, 15:18
Аватар для M.A.D.M.A.N.
M.A.D.M.A.N. M.A.D.M.A.N. вне форума
Sir Richard Abramson
 
Регистрация: 05.04.2008
Сообщения: 5,505
Версия Delphi: XE10
Репутация: выкл
По умолчанию

Цитата:
Сообщение от SCrat.ORS
Да и по жизни я стараюсь использовать array of myTypes для запоминания свойств объектов.
Всё понятно, разговор окончен.
__________________
— Как тебя понимать?
— Понимать меня не обязательно. Обязательно меня любить и кормить вовремя.


На Delphi, увы, больше не программирую.
Рекомендуемая литература по программированию
Ответить с цитированием
  #24  
Старый 14.02.2015, 16:32
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

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

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

Нужно просто нормально организовать данные. Если нужно отрисовать объект, то отрисовка должна происходить не по имени, а по индексу/указателю. Также должно быть можно через индексы/указатели от объекта добраться ко всем данным, которые могут потребоваться для отрисовки. Даже известный мне шедевр игрового убожества, наглядное пособие "как НЕ надо писать игры", и те не додумались каждые 20мс брутфорсить 10к строк, а просто посчитали от имени 4-байтовый хеш, запихнули в хеш-таблицу по первым двум байтам и положили болт на потенциальные коллизии, т.е. у них во время выполнения имен фактически нет вовсе. Не говоря уже о том, что для отрисовки не используется даже ID - он им нужен по-моему только для интегрированных скриптов.
__________________
jmp $ ; Happy End!
The Cake Is A Lie.

Последний раз редактировалось Bargest, 14.02.2015 в 16:42.
Ответить с цитированием
  #25  
Старый 14.02.2015, 17:01
Аватар для SCrat.ORS
SCrat.ORS SCrat.ORS вне форума
Активный
 
Регистрация: 20.02.2007
Адрес: Мой адрес не дом и не улица, мой адрес 0x7С00
Сообщения: 208
Версия Delphi: 2006
Репутация: 884
По умолчанию

Цитата:
Сообщение от Bargest
Есть множество объектов на карте. У каждого есть уникальный ID. Зачем передавать название объекта, когда можно передавать ID? Если по названию находится не сам объект, а его прототип (общий для нескольких объектов), то что мешает в массиве объектов хранить не имя, а индекс прототипа или (лучше) сразу указатель на него и не искать ничего вообще?
Дак я так и делаю.
Сначала загружаю информацию о "протопитах" в отдельный массив.
Потом в рабочий массив загружаю информацию об объектах, тут же попутно нахожу "протопип" по названию, и подгружаю туда же нужную информацию о "прототипе". Т.Е. поиск мне необходим только при первом запуске, что бы получить всю нужную информацию. И потом в процессе работы никакго поиска не произвожу вообще.
__________________
Програмистами не рождаются, ими становятся!
Ответить с цитированием
  #26  
Старый 14.02.2015, 17:04
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

Цитата:
Т.Е. поиск мне необходим только при первом запуске
А ранее было написано:
Цитата:
И при отрисовке объекта на карте мне надо получить его длину и ширину. И тут вызываю поиск по массиву с информацией
Так-то получше, конечно. Но вообще список прототипов можно сделать нормальной хеш-таблицей (без коллизий, т.е. с сохранением оригинальных имен), считать от имени нужного прототипа хеш и сравнивать строку не с 10к других, а с двумя-тремя.
То есть просто копипастим с вики crc8/crc16/crc32, берем младшие 1-2 байта результата, используем как индекс в массиве динамических списков. Каждый N-ный элемент - список прототипов, хеш от имени которых начинается на N. Поскольку хеши стремятся к равномерному "распределению", то таблица будет заполняться равномерно, и в среднем поиск будет производиться не среди 10к строк, а среди 10к/256 или 10к/65536 строк если брать 1 или 2 байта хеша соответственно. А можно взять и 1.5 байта хеша и будет поиск среди 10к/4096, т.е. в среднем среди двух строк.
И кстати, я бы сделал наоборот. Сарзу загружаю информацию об объектах, ищу для них по хеш-таблице прототип, и если не найден - загружаю прототип и добавляю в хеш-таблицу. Это позволит загружать только нужные прототипы, а не все (ведь на одной карте могут использоваться не все прототипы).
__________________
jmp $ ; Happy End!
The Cake Is A Lie.

Последний раз редактировалось Bargest, 14.02.2015 в 17:14.
Ответить с цитированием
  #27  
Старый 14.02.2015, 17:20
Аватар для SCrat.ORS
SCrat.ORS SCrat.ORS вне форума
Активный
 
Регистрация: 20.02.2007
Адрес: Мой адрес не дом и не улица, мой адрес 0x7С00
Сообщения: 208
Версия Delphi: 2006
Репутация: 884
По умолчанию

Цитата:
Сообщение от 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;
Далее создаешь массив. Добавление - вычисление хэша (т.е. получение индекса) и помещение в нужную ячейку данных. Ну тут еще коллизии надо разрешить, но это делается просто сдвигом по массиву. Поиск аналогично. С удалением сложнее. Там надо делать спец признак, иначе есть возможность потерять некоторые строки.
Где-то из этой области? Есть где по-подробнее почитать?
__________________
Програмистами не рождаются, ими становятся!
Ответить с цитированием
  #28  
Старый 14.02.2015, 17:22
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

Можно конечно и свой велосипед придумать, но есть готовые решения, считаемые легко и довольно удобно. Я обычно использую табличные варианты. Из простых есть еще известный ror13-хеш:
Код:
hash := 0;
for i := 1 to length(str) do
   hash := ((hash shl (32-13)) or (hash shr 13)) + str[i];
После чего делаем массив списков, в списке храним все элементы с соответствующим хешом. При поиске берем по индексу список и проверяем все его элементы уже на полное совпадение строки.
При удалении в данном случае достаточно опять же найти нужный элемент и исключить из соответствующего списка.
И вообще, вот.
__________________
jmp $ ; Happy End!
The Cake Is A Lie.

Последний раз редактировалось Bargest, 14.02.2015 в 17:37.
Ответить с цитированием
  #29  
Старый 14.02.2015, 18:12
Аватар для SCrat.ORS
SCrat.ORS SCrat.ORS вне форума
Активный
 
Регистрация: 20.02.2007
Адрес: Мой адрес не дом и не улица, мой адрес 0x7С00
Сообщения: 208
Версия Delphi: 2006
Репутация: 884
По умолчанию

Просто оставлю это здесь
Код:
//  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;
__________________
Програмистами не рождаются, ими становятся!
Ответить с цитированием
  #30  
Старый 14.02.2015, 19:21
Аватар для SCrat.ORS
SCrat.ORS SCrat.ORS вне форума
Активный
 
Регистрация: 20.02.2007
Адрес: Мой адрес не дом и не улица, мой адрес 0x7С00
Сообщения: 208
Версия Delphi: 2006
Репутация: 884
По умолчанию

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;

__________________
Програмистами не рождаются, ими становятся!

Последний раз редактировалось SCrat.ORS, 14.02.2015 в 19:37.
Ответить с цитированием
Ответ


Delphi Sources

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB-коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход


Часовой пояс GMT +3, время: 16:34.


 

Сайт

Форум

FAQ

RSS лента

Прочее

 

Copyright © Форум "Delphi Sources" by BrokenByte Software, 2004-2023

ВКонтакте   Facebook   Twitter