Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   www.boolean.name > Программирование игр для компьютеров > BlitzMax > FAQ и уроки

Ответ
 
Опции темы
Старый 28.09.2011, 06:04   #1
Greymem
Нуждающийся
 
Регистрация: 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, 06:25   #2
Randomize
[object Object]
 
Аватар для Randomize
 
Регистрация: 01.08.2008
Адрес: Планета Земля
Сообщений: 4,134
Написано 2,327 полезных сообщений
(для 6,472 пользователей)
Ответ: [Вопрос] Оптимизация поиска в листе

TMap - хеш таблица
Тобеж индексированый список.
Располагается в модуле brl.map

http://en.wikibooks.org/wiki/BlitzMa...tructures/Maps
__________________
Retry, Abort, Ignore? █
AMD Ryzen 7 1700X x8 3.4Ghz; 16Gb ram; Radeon RX 570
AMD Athlon II x4 2.6Ghz; 8Gb ram; Nvidia Geforce GTX 750 Ti
(Offline)
 
Ответить с цитированием
Эти 3 пользователя(ей) сказали Спасибо Randomize за это полезное сообщение:
Greymem (28.09.2011), moka (28.09.2011), SBJoker (28.09.2011)
Старый 28.09.2011, 06:32   #3
Greymem
Нуждающийся
 
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений
(для 3 пользователей)
Ответ: [Вопрос] Оптимизация поиска в листе

То есть все равно придется вести два списка?
Или первый список полностью переделать на TMap? Я уже понял, что в этом случае данные можно будет искать посредством MapValueForKey
Но что у нас с быстродействием?
(Offline)
 
Ответить с цитированием
Старый 28.09.2011, 07:07   #4
Randomize
[object Object]
 
Аватар для Randomize
 
Регистрация: 01.08.2008
Адрес: Планета Земля
Сообщений: 4,134
Написано 2,327 полезных сообщений
(для 6,472 пользователей)
Сообщение Ответ: [Вопрос] Оптимизация поиска в листе

Сообщение от 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? █
AMD Ryzen 7 1700X x8 3.4Ghz; 16Gb ram; Radeon RX 570
AMD Athlon II x4 2.6Ghz; 8Gb ram; Nvidia Geforce GTX 750 Ti
(Offline)
 
Ответить с цитированием
Эти 3 пользователя(ей) сказали Спасибо Randomize за это полезное сообщение:
Greymem (28.09.2011), moka (28.09.2011), NitE (28.09.2011)
Старый 28.09.2011, 07:59   #5
Greymem
Нуждающийся
 
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений
(для 3 пользователей)
Ответ: [Вопрос] Оптимизация поиска в листе

Спасибо за наглядный пример.

Интересно а как занести в переменную скажем 200 элементов? =) Это-же все равно придется создавать массив, лист или такую структуру?

И еще вопрос, если не возражаете, как можно обновить данные по ключу? тоже INSERT или сначала удалить ключ, а потом снова создать? Последний проблемный.
(Offline)
 
Ответить с цитированием
Старый 28.09.2011, 08:26   #6
Randomize
[object Object]
 
Аватар для Randomize
 
Регистрация: 01.08.2008
Адрес: Планета Земля
Сообщений: 4,134
Написано 2,327 полезных сообщений
(для 6,472 пользователей)
Ответ: [Вопрос] Оптимизация поиска в листе

Сообщение от 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? █
AMD Ryzen 7 1700X x8 3.4Ghz; 16Gb ram; Radeon RX 570
AMD Athlon II x4 2.6Ghz; 8Gb ram; Nvidia Geforce GTX 750 Ti
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Greymem (28.09.2011)
Старый 28.09.2011, 08:33   #7
Greymem
Нуждающийся
 
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений
(для 3 пользователей)
Ответ: [Вопрос] Оптимизация поиска в листе

Вообще громандное спасибище!!! Будешь учавствовать в альфа-тесте игры? =)))
Даже больше незнаю чем и отблагодарить. =)
Обидно что придется переписывать несколько десятков строк кода из-за такой вкусности.

И все таки вернемся к быстродействию.
В Итоге-то заносить, искать, обновлять данные в хеш-таблице быстрее чем в обычном листе, как думаете?
(Offline)
 
Ответить с цитированием
Старый 28.09.2011, 08:35   #8
Randomize
[object Object]
 
Аватар для Randomize
 
Регистрация: 01.08.2008
Адрес: Планета Земля
Сообщений: 4,134
Написано 2,327 полезных сообщений
(для 6,472 пользователей)
Ответ: [Вопрос] Оптимизация поиска в листе

Сообщение от Greymem Посмотреть сообщение
Вообще громандное спасибище!!! Будешь учавствовать в альфа-тесте игры? =)))
Удачи с проектом

У нас тут есть раздел проектов на BlitzMax:
http://forum.boolean.name/forumdisplay.php?f=106
Буду рад если ваша игра появится там.

Сообщение от Greymem Посмотреть сообщение
И все таки вернемся к быстродействию.
В Итоге-то заносить, искать, обновлять данные в хеш-таблице быстрее чем в обычном листе, как думаете?
Практически одинаково. Хеш таблица имеет небольшой выйгрыш, но внутреннее убранство у таблицы и листа почти одинаковое.
За такие копейки борьбу устраивать нет смысла - всё равно всё сожрёт рендер.
__________________
Retry, Abort, Ignore? █
AMD Ryzen 7 1700X x8 3.4Ghz; 16Gb ram; Radeon RX 570
AMD Athlon II x4 2.6Ghz; 8Gb ram; Nvidia Geforce GTX 750 Ti
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Greymem (29.09.2011)
Старый 29.09.2011, 08:24   #9
Greymem
Нуждающийся
 
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений
(для 3 пользователей)
Ответ: [Вопрос] Оптимизация поиска в листе

Спасибо, думаю тему можно закрыть
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
Randomize (29.09.2011)
Старый 16.10.2011, 18:33   #10
Черный крыс
 
Сообщений: n/a
Ответ: [Вопрос] Оптимизация поиска в листе

brl.map - это не хэш таблица, там используются повороты влево/вправо, хэш таблица же при поиске высчитывает индекс ключа по его названию.

Насчет быстродействия - зря вы так, на таких задачках можно здорово потерять в производительности программы.
1) Если список обьектов не надо индексировать - тут идеально подойдут простые Листы.
2) Если индексировать надо - юзать индексированные списки.

Насчет TList - официальное решение довольно грамотное, но... не безупречное, оно тоже довольно медленное, существует мой модуль API.List - это ускоренная версия TList'a, почти по всем параметрам быстрее стандартного, ищи его в теме "Ускоренный TList" под моим авторством.

Насчет индексированного листа то BRL.MAP тоже далеко не оптимальное решение, существует модуль API.HASH - это настоящая хэш-таблица, и работает гораздо шустрее MAP'a, ищи его в моей подписи.
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
moka (16.10.2011)
Старый 15.11.2011, 15:38   #11
Greymem
Нуждающийся
 
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений
(для 3 пользователей)
Ответ: [Вопрос] Оптимизация поиска в листе

Вернемся к нашим таблицам.

Как организовать многомерный массив с данными разных типов?
Мне нужно создать таблицу, столбцы которой разных типов, какой нибудь универсальный тип подскажите?

А то для каждой таблицы создавать свой тип со своими полями надоедает.
Пока что использую многомерный массив где все столбцы типа "строка", я просто сам запоминаю из какого столбца в какой тип переводить, но это-же не дело.
__________________
Мозги... у них есть метод "Storm"
(Offline)
 
Ответить с цитированием
Старый 15.11.2011, 15:48   #12
Randomize
[object Object]
 
Аватар для Randomize
 
Регистрация: 01.08.2008
Адрес: Планета Земля
Сообщений: 4,134
Написано 2,327 полезных сообщений
(для 6,472 пользователей)
Ответ: [Вопрос] Оптимизация поиска в листе

String - если нужно хранить Int, Float, Double, Short, Byte просто легко преобразовывать из них в него и обратно.
Object - для вообще всех данных включая String
__________________
Retry, Abort, Ignore? █
AMD Ryzen 7 1700X x8 3.4Ghz; 16Gb ram; Radeon RX 570
AMD Athlon II x4 2.6Ghz; 8Gb ram; Nvidia Geforce GTX 750 Ti
(Offline)
 
Ответить с цитированием
Старый 15.11.2011, 15:58   #13
Greymem
Нуждающийся
 
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений
(для 3 пользователей)
Ответ: [Вопрос] Оптимизация поиска в листе

Сообщение от Randomize Посмотреть сообщение
String - если нужно хранить Int, Float, Double, Short, Byte просто легко преобразовывать из них в него и обратно.
Object - для вообще всех данных включая String
Так вот я и использую String, да вот только иногда среди 20 столбцов забывается что где. =)
__________________
Мозги... у них есть метод "Storm"
(Offline)
 
Ответить с цитированием
Старый 16.11.2011, 10:22   #14
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,503
Написано 2,958 полезных сообщений
(для 5,224 пользователей)
Ответ: [Вопрос] Оптимизация поиска в листе

А что списка типов (структур/классов) в BlitzMax нету?
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Старый 16.11.2011, 10:26   #15
Greymem
Нуждающийся
 
Регистрация: 31.05.2010
Сообщений: 63
Написано 3 полезных сообщений
(для 3 пользователей)
Ответ: [Вопрос] Оптимизация поиска в листе

Сообщение от pax Посмотреть сообщение
А что списка типов (структур/классов) в BlitzMax нету?
Постараюсь объяснить, как я вас понял.

Есть списки типов конечно же. Только вот у типа фиксированное количество столбцов, каждый столбец(поле) определенного типа.

Таблиц у меня немерена куча, для каждой таблицы создавать отдельный тип как минимум - проблемно.
__________________
Мозги... у них есть метод "Storm"
(Offline)
 
Ответить с цитированием
Ответ


Опции темы

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +1, время: 23:18.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com