forum.boolean.name - [Вопрос] Оптимизация поиска в листе

Страница 1 из 2

Показывать 64 сообщений этой темы на одной странице

forum.boolean.name (http://forum.boolean.name/index.php)

- FAQ и уроки (http://forum.boolean.name/forumdisplay.php?f=110)

- - [Вопрос] Оптимизация поиска в листе (http://forum.boolean.name/showthread.php?t=15555)

Greymem

28.09.2011 10:04

[Вопрос] Оптимизация поиска в листе

Доброго времени суток, уважаемые.

Ситуация.

Есть лист, содержит данные произвольного типа.

Код:

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.

Что лучше?

Randomize

28.09.2011 10:25

Ответ: [Вопрос] Оптимизация поиска в листе

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

http://en.wikibooks.org/wiki/BlitzMa...tructures/Maps

Greymem

28.09.2011 10:32

Ответ: [Вопрос] Оптимизация поиска в листе

То есть все равно придется вести два списка?
Или первый список полностью переделать на TMap? Я уже понял, что в этом случае данные можно будет искать посредством MapValueForKey
Но что у нас с быстродействием?

Randomize

28.09.2011 11:07

Ответ: [Вопрос] Оптимизация поиска в листе

Цитата:

Сообщение от Greymem (Сообщение 203645)

То есть все равно придется вести два списка?

Нет. TMap это и есть эти самые 2 списка.

Цитата:

Сообщение от Greymem (Сообщение 203645)

Но что у нас с быстродействием?

Заглянем в код:

Код:

        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

Чтоб всё шустро работало просто не производи поиск по таблице постоянно в цикле. Лучше ищи один раз и заноси в переменную.

Greymem

28.09.2011 11:59

Ответ: [Вопрос] Оптимизация поиска в листе

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

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

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

Randomize

28.09.2011 12:26

Ответ: [Вопрос] Оптимизация поиска в листе

Цитата:

Сообщение от Greymem (Сообщение 203652)

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

Всегда рад ;)

Цитата:

Сообщение от Greymem (Сообщение 203652)

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

Ну это главная особенность хеш таблицы, что в неё можно занести абсолютно всё. Даже ещё одну хеш таблицу :)

PHP код:




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 так как в нём нет инкапсуляции - приватные методы и поля начинают с нижнего подчёркивания.

Greymem

28.09.2011 12:33

Ответ: [Вопрос] Оптимизация поиска в листе

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

И все таки вернемся к быстродействию.
В Итоге-то заносить, искать, обновлять данные в хеш-таблице быстрее чем в обычном листе, как думаете?

Randomize

28.09.2011 12:35

Ответ: [Вопрос] Оптимизация поиска в листе

Цитата:

Сообщение от Greymem (Сообщение 203657)

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

Удачи с проектом :)

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

Цитата:

Сообщение от Greymem (Сообщение 203657)

И все таки вернемся к быстродействию.
В Итоге-то заносить, искать, обновлять данные в хеш-таблице быстрее чем в обычном листе, как думаете?

Практически одинаково. Хеш таблица имеет небольшой выйгрыш, но внутреннее убранство у таблицы и листа почти одинаковое.
За такие копейки борьбу устраивать нет смысла - всё равно всё сожрёт рендер.

Greymem

29.09.2011 12:24

Ответ: [Вопрос] Оптимизация поиска в листе

Спасибо, думаю тему можно закрыть

Черный крыс

16.10.2011 22:33

Ответ: [Вопрос] Оптимизация поиска в листе

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

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

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

Насчет индексированного листа то BRL.MAP тоже далеко не оптимальное решение, существует модуль API.HASH - это настоящая хэш-таблица, и работает гораздо шустрее MAP'a, ищи его в моей подписи.

Greymem

15.11.2011 19:38

Ответ: [Вопрос] Оптимизация поиска в листе

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

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

А то для каждой таблицы создавать свой тип со своими полями надоедает.
Пока что использую многомерный массив где все столбцы типа "строка", я просто сам запоминаю из какого столбца в какой тип переводить, но это-же не дело.

Randomize

15.11.2011 19:48

Ответ: [Вопрос] Оптимизация поиска в листе

String - если нужно хранить Int, Float, Double, Short, Byte просто легко преобразовывать из них в него и обратно.
Object - для вообще всех данных включая String

Greymem

15.11.2011 19:58

Ответ: [Вопрос] Оптимизация поиска в листе

Цитата:

Сообщение от Randomize (Сообщение 209834)

Так вот я и использую String, да вот только иногда среди 20 столбцов забывается что где. =)

pax	16.11.2011 14:22

Ответ: [Вопрос] Оптимизация поиска в листе

А что списка типов (структур/классов) в BlitzMax нету?

Greymem

16.11.2011 14:26

Ответ: [Вопрос] Оптимизация поиска в листе

Цитата:

Сообщение от pax (Сообщение 209920)

А что списка типов (структур/классов) в BlitzMax нету?

Постараюсь объяснить, как я вас понял.

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

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

Часовой пояс GMT +4, время: 14:05.

Страница 1 из 2

Показывать 64 сообщений этой темы на одной странице