|
28.09.2011, 10:04
|
#1
|
Нуждающийся
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений (для 3 пользователей)
|
[Вопрос] Оптимизация поиска в листе
Доброго времени суток, уважаемые.
Ситуация.
Есть лист, содержит данные произвольного типа.
Type TObj
Field Name:String = ""
Field value1:int;
Field value2:Float;
End Type
Global Objs:TList = CreateList() ;
Local Obj:TObj = New TObj;
Obj.Name="First";
Obj.value1=1;
Obj.value2=2;
Objs.AddLast(Obj);
.............
Теперь нам надо найти элемент по имени.
1 Способ
Он же самый лёгкий. Первый способ это просто запустить цикл по листу и проверять NAME
Function FindListElement(Name:String)
Local LObj:TObj;
For LObj = EachIn Objs
If LObj.Name = Name Then
......
Exit;
EndIf;
Next;
End Function
2 Способ
Создать отдельный лист который будет содержать только строки, порядок элементов в листе строк, будет совпадать с порядком элементов в листе Objs. При добавлении данных в лист Objs , имя конкретного элемента будет добавляться в наш лист строк, при удалении удаляться. Таким образом мы сможем найти строку в "кэшированном" листе методом FindLast(), запомнить индекс элемента с таким именем, и по этому-же индексу получить элемент из первого листа Objs.
Что лучше?
|
(Offline)
|
|
28.09.2011, 10:25
|
#2
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,360
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
TMap - хеш таблица
Тобеж индексированый список.
Располагается в модуле brl.map
http://en.wikibooks.org/wiki/BlitzMa...tructures/Maps
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
Эти 3 пользователя(ей) сказали Спасибо Randomize за это полезное сообщение:
|
|
28.09.2011, 10:32
|
#3
|
Нуждающийся
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений (для 3 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
То есть все равно придется вести два списка?
Или первый список полностью переделать на TMap? Я уже понял, что в этом случае данные можно будет искать посредством MapValueForKey
Но что у нас с быстродействием?
|
(Offline)
|
|
28.09.2011, 11:07
|
#4
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,360
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
Сообщение от Greymem
То есть все равно придется вести два списка?
|
Нет. TMap это и есть эти самые 2 списка.
Сообщение от Greymem
Но что у нас с быстродействием?
|
Заглянем в код:
Method _FindNode:TNode( key:Object )
Local node:TNode=_root
While node<>nil
Local cmp=key.Compare( node._key )
If cmp>0
node=node._right
Else If cmp<0
node=node._left
Else
Return node
EndIf
Wend
Return node
End Method
Фактически тут происходит тоже самое что и у тебя во "втором способе".
За единственным исключением что тут нет листов в принципе. Тут структура сама по себе ориентирована на список "ключ":"Значение"
Вообще по чаще заглядывай в модули:
BlitzMax\mod\brl.mod\map.mod
Там по коду можно сообразить что да как работает.
Ну и кратенький пример использования:
SuperStrict
Framework brl.basic
Import brl.map
Import brl.random
' произвольный тип
Type MyObj
Field i:Int = 33
Field z:Int = 77
' для отчётности
Method ToString:String()
Return "my values: " + i + " " + z
EndMethod
EndType
Local map:TMap = New TMap
' Заполняем рандомными объектами нашу "карту"
For Local i:Int = 0 Until 100
Local obj:MyObj = New MyObj
obj.i = Rand(0, 100)
obj.z = Rand(10, 20)
map.Insert("Object" + i, obj)
Next
' Теперь попробуем проверить существует ли объект с определённым ключом
Print "Object #1: " + map.Contains("Object1")
Print "Object #33: " + map.Contains("Object33")
Print "Object #33: " + map.Contains("Object33")
Print "Object #155: " + map.Contains("Object155")
' Попрбуем извлеч
Print "Object77: " + MyObj(map.ValueForKey("Object77")).ToString()
Print "Object12: " + MyObj(map.ValueForKey("Object12")).ToString()
Print "Object5: " + MyObj(map.ValueForKey("Object5")).ToString()
' Но так делать опастно! Лучше сначала проверять на наличе объекта по ключу или делать так:
Local _object:MyObj = MyObj(map.ValueForKey("Object35"))
If _object Then ' Если объект нашёлся то код выполнится
Print _object.ToString()
EndIf
' Смоделируем ошибочную ситуацию
_object:MyObj = MyObj(map.ValueForKey("Object935"))
If _object Then
Print _object.ToString()
Else
Print "Cant find"
EndIf
Чтоб всё шустро работало просто не производи поиск по таблице постоянно в цикле. Лучше ищи один раз и заноси в переменную.
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
Эти 3 пользователя(ей) сказали Спасибо Randomize за это полезное сообщение:
|
|
28.09.2011, 11:59
|
#5
|
Нуждающийся
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений (для 3 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
Спасибо за наглядный пример.
Интересно а как занести в переменную скажем 200 элементов? =) Это-же все равно придется создавать массив, лист или такую структуру?
И еще вопрос, если не возражаете, как можно обновить данные по ключу? тоже INSERT или сначала удалить ключ, а потом снова создать? Последний проблемный.
|
(Offline)
|
|
28.09.2011, 12:26
|
#6
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,360
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
Сообщение от Greymem
Спасибо за наглядный пример.
|
Всегда рад
Сообщение от Greymem
Интересно а как занести в переменную скажем 200 элементов? =) Это-же все равно придется создавать массив, лист или такую структуру?
|
Ну это главная особенность хеш таблицы, что в неё можно занести абсолютно всё. Даже ещё одну хеш таблицу
map.Insert("My Map", new TMap) map.Insert("My List", new TList)
И еще вопрос, если не возражаете, как можно обновить данные по ключу? тоже INSERT или сначала удалить ключ, а потом снова создать? Последний проблемный.
|
Да, именно так.
Local key:String = "Object39"
If map.Contains(key) Then map.Remove(key)
map.Insert(key, newObject)
Где newObject - новый объект
Когда мы вызываем Remove удаляется не только ключ, но и значение.
К сожалению тут происходит двойной поиск:
map.Contains(key) и map.Remove(key)
Этого можно избежать только работая напрямую с Node (звено хеш таблици)
Примерно так:
Local key:String = "Object39"
Local node:TNode = map._FindNode(key)
node._value = newObject
Собственно node содержит и _key(ключ) и _value(сам объект).
Но с методами/переменными, которые начинаются с "_" надо поострожнее. Это так сказать стиль писания на BlitzMax так как в нём нет инкапсуляции - приватные методы и поля начинают с нижнего подчёркивания.
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
28.09.2011, 12:33
|
#7
|
Нуждающийся
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений (для 3 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
Вообще громандное спасибище!!! Будешь учавствовать в альфа-тесте игры? =)))
Даже больше незнаю чем и отблагодарить. =)
Обидно что придется переписывать несколько десятков строк кода из-за такой вкусности.
И все таки вернемся к быстродействию.
В Итоге-то заносить, искать, обновлять данные в хеш-таблице быстрее чем в обычном листе, как думаете?
|
(Offline)
|
|
28.09.2011, 12:35
|
#8
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,360
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
Сообщение от Greymem
Вообще громандное спасибище!!! Будешь учавствовать в альфа-тесте игры? =)))
|
Удачи с проектом
У нас тут есть раздел проектов на BlitzMax:
http://forum.boolean.name/forumdisplay.php?f=106
Буду рад если ваша игра появится там.
Сообщение от Greymem
И все таки вернемся к быстродействию.
В Итоге-то заносить, искать, обновлять данные в хеш-таблице быстрее чем в обычном листе, как думаете?
|
Практически одинаково. Хеш таблица имеет небольшой выйгрыш, но внутреннее убранство у таблицы и листа почти одинаковое.
За такие копейки борьбу устраивать нет смысла - всё равно всё сожрёт рендер.
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
29.09.2011, 12:24
|
#9
|
Нуждающийся
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений (для 3 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
Спасибо, думаю тему можно закрыть
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
16.10.2011, 22:33
|
#10
|
|
Ответ: [Вопрос] Оптимизация поиска в листе
brl.map - это не хэш таблица, там используются повороты влево/вправо, хэш таблица же при поиске высчитывает индекс ключа по его названию.
Насчет быстродействия - зря вы так, на таких задачках можно здорово потерять в производительности программы.
1) Если список обьектов не надо индексировать - тут идеально подойдут простые Листы.
2) Если индексировать надо - юзать индексированные списки.
Насчет TList - официальное решение довольно грамотное, но... не безупречное, оно тоже довольно медленное, существует мой модуль API.List - это ускоренная версия TList'a, почти по всем параметрам быстрее стандартного, ищи его в теме "Ускоренный TList" под моим авторством.
Насчет индексированного листа то BRL.MAP тоже далеко не оптимальное решение, существует модуль API.HASH - это настоящая хэш-таблица, и работает гораздо шустрее MAP'a, ищи его в моей подписи.
|
|
|
Сообщение было полезно следующим пользователям:
|
|
15.11.2011, 19:38
|
#11
|
Нуждающийся
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений (для 3 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
Вернемся к нашим таблицам.
Как организовать многомерный массив с данными разных типов?
Мне нужно создать таблицу, столбцы которой разных типов, какой нибудь универсальный тип подскажите?
А то для каждой таблицы создавать свой тип со своими полями надоедает.
Пока что использую многомерный массив где все столбцы типа "строка", я просто сам запоминаю из какого столбца в какой тип переводить, но это-же не дело.
__________________
Мозги... у них есть метод "Storm"
|
(Offline)
|
|
15.11.2011, 19:48
|
#12
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,360
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
String - если нужно хранить Int, Float, Double, Short, Byte просто легко преобразовывать из них в него и обратно.
Object - для вообще всех данных включая String
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
15.11.2011, 19:58
|
#13
|
Нуждающийся
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений (для 3 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
Сообщение от Randomize
String - если нужно хранить Int, Float, Double, Short, Byte просто легко преобразовывать из них в него и обратно.
Object - для вообще всех данных включая String
|
Так вот я и использую String, да вот только иногда среди 20 столбцов забывается что где. =)
__________________
Мозги... у них есть метод "Storm"
|
(Offline)
|
|
16.11.2011, 14:22
|
#14
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
А что списка типов (структур/классов) в BlitzMax нету?
|
(Offline)
|
|
16.11.2011, 14:26
|
#15
|
Нуждающийся
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений (для 3 пользователей)
|
Ответ: [Вопрос] Оптимизация поиска в листе
Сообщение от pax
А что списка типов (структур/классов) в BlitzMax нету?
|
Постараюсь объяснить, как я вас понял.
Есть списки типов конечно же. Только вот у типа фиксированное количество столбцов, каждый столбец(поле) определенного типа.
Таблиц у меня немерена куча, для каждой таблицы создавать отдельный тип как минимум - проблемно.
__________________
Мозги... у них есть метод "Storm"
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 07:28.
|