Сейчас 22:39:21 Четверг, 28 марта, 2024 год
[ x ] Главная ⇒ Форум ⇐ RSS Файлы Cтатьи Картинки В о й т и   или   з а р е г и с т р и р о в а т ь с я


[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 2
  • 1
  • 2
  • »
Модератор форума: PUVer, SirNikolas, Ty3uK  
Форум о Warcraft 3 » Раздел для картостроителей » GUI / Jass » [Система] Dictionary
[Система] Dictionary
SirNikolasДата: Четверг, 15 Декабря 2011, 19:51:17 | Сообщение # 1
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:

Класс Dictionary


Что-то я в последнее время стал делать из JASS'а C++ :)



Предисловие


Данный класс - это ассоциативный массив, он является эквивалентом классов std::map в C++ и System.Collections.Generic.Dictionary в C#. Проще говоря, это массив, в качестве индексов в котором выступают не целые числа, а любые типы, которые Вы укажете.


Использование


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


Объявление типа


Думаю, можно не говорить, что следует скопировать триггер Dictionary себе в карту. Затем Вам нужно определить функции, которые будут сравнивать индексы. Создаются они по такому шаблону:
Code
library_once <Имя>
     public function less takes <Имя типа> left, <Имя типа> right returns boolean
         <Условие, если левый операнд меньше правого>
     endfunction

     public function equal takes <Имя типа> left, <Имя типа> right returns boolean
         <Условие, если операнды равны>
     endfunction
endlibrary
Разберем на конкретном примере - пусть нам нужен массив с индексатором integer:
Code
library_once IntegerComparison
     public function less takes integer op1, integer op2 returns boolean
         return op1 < op2
     endfunction

     public function equal takes integer op1, integer op2 returns boolean
         return op1 == op2
     endfunction
endlibrary

После этого необходимо объявить массив нужного типа. Делается это с помощью следующей инструкции препроцессора:
Code
//! runtextmacro DeclareDictionary("<Тип индексатора>", "<Тип значений>", "<Имя библиотеки сравнения>", "<Максимальный суммарный размер всех словарей данного типа>")
Например:
Code
//! runtextmacro DeclareDictionary("integer", "unit", "IntegerComparison", "8191")
Эта инструкция объявит тип массива unit с индексом integer. Для сравнения ключей будут использоваться функции из библиотеки IntegerComparison, размер всех словарей - 8191. Этот размер не стоит уменьшать - память Вы этим не сэкономите.
Обратите внимание: все значения макроса пишутся в кавычках!

Все необходимые приготовления сделаны, можно начинать кодить.


Работа с классом


Нужно просто объявить переменную типа Dictionary_<Тип индексатора>_<Тип значений> и инициализировать ее значением Dictionary_<Тип индексатора>_<Тип значений>.Create(), затем можно использовать ее как обычный массив:
Code
function Example1 takes nothing returns nothing
     local Dictionary_integer_unit d = Dictionary_integer_unit.Create()
     set d[0] = CreateUnit(...)
     set d[1] = null
     set d[-1] = CreateUnit(...)//Записываем по отрицательному индексу. Да, это возможно!
     set d[100500] = CreateUnit(...)//И это тоже разрешено!
     call KillUnit(d[0])
     call RemoveUnit(d[-1])
     //После использования, если массив временный, его необходимо уничтожить:
     call d.Destroy()
endfunction
Однако гораздо чаще требуются словари, которые существуют всю игру и, следовательно, не требуют удаления. Их можно делать глобальными:
Code
globals
     Dictionary_integer_unit MyDict
endglobals

function InitTrig_Example2 takes nothing returns nothing
     set MyDict = Dictionary_integer_unit.Create()
     set MyDict[0] = CreateUnit(...)
endfunction
Следует запомнить, что глобальный словарь, к сожалению, нельзя создать сразу же в globals.
Code
globals
     Dictionary_integer_unit MyDict = Dictionary_integer_unit.Create()//Недопустимо!
endglobals


Можно полностью очистить массив, не удаляя его:
Code
call MyDict.Clear()

Также есть свойство, показывающее количество элементов в данный момент:
Code
local Dictionary_integer_unit d = Dictionary_integer_unit.Create()
set d[0] = CreateUnit(...)
set d[1] = CreateUnit(...)
set d[2] = CreateUnit(...)
set d[3] = CreateUnit(...)
call BJDebugMsg(I2S(d.Count))//Выведет "4"
call d.Destroy()
После "Count" скобки не пишутся.

Также существует способ "пройтись" по всему словарю, вызвав для каждого поля некоторую функцию.
Code
function SomeFunc takes integer index, integer value returns nothing
     call BJDebugMsg(I2S(index) + ": " + I2S(value))
endfunction

function AnotherFunc takes nothing returns nothing
     local Dictionary_integer_integer d = Dictionary_integer_integer.Create()
     set d[-1] = 2
     set d[3] = 5
     set d[6] = 8
     set d[0x2000] = 10
     call d.ForEach(SomeFunc)
     call d.Destroy()
endfunction
Обратите внимание: в метод ForEach передается только имя функции без ключевого слова function. Кроме того, можно передать лишь такие функции, которые принимают индекс и значение и ничего не возвращают.
Функция SomeFunc будет вызвана для всех полей словаря в порядке возрастания индексов.

При попытке получить из словаря значение, которое не было туда помещено, будет возвращено значение по умолчанию. Вы также можете просто узнать, есть ли оно там:
Code
local Dictionary_integer_unit d = Dictionary_integer_unit.Create()
set d[0] = CreateUnit(...)
call BJDebugMsg(I2S(GetHandleId(d[2])))//d[2] пуст, поэтому будет возвращен юнит null, ID которого равен 0
if not d.Exists[2] then
     call BJDebugMsg("По индексу 2 ничего не записано")
endif
call d.Destroy()

Если Вы делаете большую базу данных, которая не меняется всю игру, и Вам нужно ее максимальное быстродействие, Вам может оказаться полезным метод Rebuild, перестраивающий словарь для наиболее быстрого доступа к элементам. Следует учесть, что он достаточно медленный, поэтому после каждого обновления его вызывать не стоит.
Code
//! runtextmacro DeclareDictionary("integer", "string", "IntegerComparison", "8191")

globals
     Dictionary_integer_string SpellData
endglobals

function Trig_Spells_Actions takes nothing returns boolean
     local string s = SpellData[GetSpellAbilityId()]
     if s != null then
         call ExecuteFunc(s)
     endif
     return false
endfunction

function InitTrig_Spells takes nothing returns nothing
     local trigger trig = CreateTrigger()
     local integer i = 0
     loop
         call TriggerRegisterPlayerUnitEvent(trig, Player(i), EVENT_PLAYER_UNIT_SPELL_EFFECT,  null)
         exitwhen i == 15
         set i = i + 1
     endloop
     call TriggerAddCondition(trig, Condition(function Trig_Spells_Actions))
     set trig = null

     set SpellData = Dictionary_integer_string.Create()
     set SpellData['A000'] = "Trig_FireStorm_Actions"
     set SpellData['A001'] = "Trig_IceWall_Actions"
     set SpellData['A002'] = "Trig_PoisonTouch_Actions"
     set SpellData['A003'] = "Trig_HandOfGod_Actions"
     set SpellData['A004'] = "Trig_TimeLapse_Actions"
     //...
     call SpellData.Rebuild()
endfunction

Еще один способ применения, который я упомянул ранее - создание MUI-спеллов.
Code
//! runtextmacro DeclareDictionary("handle", "TimeLapseStruct", "HandleComparison", "8191")

library_once HandleComparison
     public function less takes handle op1, handle op2 returns boolean
         return GetHandleId(op1) < GetHandleId(op2)
     endfunction

     public function equal takes handle op1, handle op2 returns boolean
         return op1 == op2
     endfunction
endlibrary

globals
     Dictionary_handle_TimeLapseStruct TimeLapseDict
endglobals

struct TimeLapseStruct
     unit u
     real x
     real y
endstruct

function Trig_TimeLapse_Timer takes nothing returns nothing
     local timer t = GetExpiredTimer()
     local TimeLapseStruct s = TimeLapseDict[t]
     call SetUnitX(s.u, s.x)
     call SetUnitY(s.u, s.y)
     //Обнуление
     set TimeLapseDict[t] = 0
     call DestroyTimer(t)
     call s.destroy()
     set t = null
endfunction

function Trig_TimeLapse_Actions takes nothing returns nothing
     local TimeLapseStruct s = TimeLapseStruct.create()
     local timer t = CreateTimer()
     set s.u = GetSpellTargetUnit()
     set s.x = GetWidgetX(s.u)
     set s.y = GetWidgetY(s.u)
     set TimeLapseDict[t] = s
     call TimerStart(t, 5., false, function Trig_TimeLapse_Timer)
     set t = null
endfunction

function InitTrig_TimeLapse takes nothing returns nothing
      set TimeLapseDict = Dictionary_handle_TimeLapseStruct.Create()
endfunction
Важный момент - в таких случаях необходимо ВСЕГДА обнулять данные массивов, даже если это integer, real или string.


Взгляд изнутри


Этот раздел посвящен тем, кто хочет разобраться, как именно (и почему :) ) данная система работает.

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


Если возникнут вопросы, задавайте, не стесняйтесь. :)
Прикрепления: Dictionary.w3x (27.6 Kb) · Dictionary.j (8.8 Kb)


 

Ty3uKДата: Пятница, 16 Декабря 2011, 10:30:32 | Сообщение # 2
Группа: Ветераны
Сообщений: 6125
Награды: 2
Репутация: 1617
Блокировки:
Такая система не имеет смысла на обычном жасс 2?

SirNikolas, самое обидное, что потом этот аккуратный и красивый код превращается в ЭТО


╭∩╮(︶︿︶)╭∩╮
"Ульта Тайда мне в жопу!" © k0fe1n
Статьи: MUI-1|MUI-2|Шрифт
Полезности: JASP|JNGP|Уголок библиотек


Сообщение отредактировал Ty3uK - Пятница, 16 Декабря 2011, 10:30:44
 

SirNikolasДата: Пятница, 16 Декабря 2011, 13:02:02 | Сообщение # 3
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Ty3uK, основная причина, по которой я писал на vJass'е - текстмакросы, позволяющие создавать словари любых типов и любого размера. Вряд ли конечный пользователь захочет вручную копировать исходник и везде заменять типы на те, которые ему нужны. Плюс еще вместо set d["abc"] = 123 надо было бы писать call Dictionary_string_integer_set(d, "abc", 123), что понижало бы читабельность кода.
Quote (Ty3uK)
самое обидное, что потом этот аккуратный и красивый код превращается в ЭТО
Все это можно выразить двумя словами: "It works!"




Сообщение отредактировал SirNikolas - Пятница, 16 Декабря 2011, 13:19:33
 

Ty3uKДата: Пятница, 16 Декабря 2011, 13:06:36 | Сообщение # 4
Группа: Ветераны
Сообщений: 6125
Награды: 2
Репутация: 1617
Блокировки:
SirNikolas, ;) я и не спорю, просто говорю о том, что код "толстеет" на глазах - вошел на парсер 39 кб, а вышел - 93 ^_^
Так и все-таки: имет ли смысл делать такие фичи на жасс2?


╭∩╮(︶︿︶)╭∩╮
"Ульта Тайда мне в жопу!" © k0fe1n
Статьи: MUI-1|MUI-2|Шрифт
Полезности: JASP|JNGP|Уголок библиотек


Сообщение отредактировал Ty3uK - Пятница, 16 Декабря 2011, 13:07:39
 

SirNikolasДата: Пятница, 16 Декабря 2011, 13:21:30 | Сообщение # 5
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Вообще реально, только с массивами надо будет мучиться. Если тебе надо, могу перевести.

 

Ty3uKДата: Пятница, 16 Декабря 2011, 13:40:27 | Сообщение # 6
Группа: Ветераны
Сообщений: 6125
Награды: 2
Репутация: 1617
Блокировки:
SirNikolas, нет, спасибо, я просто так спросил ^_^

╭∩╮(︶︿︶)╭∩╮
"Ульта Тайда мне в жопу!" © k0fe1n
Статьи: MUI-1|MUI-2|Шрифт
Полезности: JASP|JNGP|Уголок библиотек
 

[DUОS]Дата: Пятница, 16 Декабря 2011, 17:54:00 | Сообщение # 7
Группа: Заблокированные
Сообщений: 6279
Награды: 9
Репутация: 1708
Блокировки:
SirNikolas,
Я апплодирую стоя... Класс и правда превосходен, базирован на хендлидах, ага?


НУ И ЧТО ТЕПЕРЬ?


Кликайте на дракошку ;)
 

SirNikolasДата: Пятница, 16 Декабря 2011, 18:00:36 | Сообщение # 8
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Quote (|DUОS|)
базирован на хендлидах, ага?
Чего?..
Quote (SirNikolas)
Класс Dictionary сделан на основе бинарного древа


 

[DUОS]Дата: Пятница, 16 Декабря 2011, 18:01:56 | Сообщение # 9
Группа: Заблокированные
Сообщений: 6279
Награды: 9
Репутация: 1708
Блокировки:
SirNikolas,
Я не про бинарку... Я про то, что там объекты становятся индексами через GetHandleId(object) или другой механизм?


НУ И ЧТО ТЕПЕРЬ?


Кликайте на дракошку ;)
 

SirNikolasДата: Пятница, 16 Декабря 2011, 18:06:10 | Сообщение # 10
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Ага)
Quote (SirNikolas)
Code
library_once HandleComparison
     public function less takes handle op1, handle op2 returns boolean
         return GetHandleId(op1) < GetHandleId(op2)
     endfunction

     public function equal takes handle op1, handle op2 returns boolean
         return op1 == op2
     endfunction
endlibrary


Добавлено (16 Декабрь 2011, 18:06:10)
---------------------------------------------
В принципе, ты можешь на чем угодно его базировать - условие сортировки задает пользователь.


 

[DUОS]Дата: Пятница, 16 Декабря 2011, 18:08:21 | Сообщение # 11
Группа: Заблокированные
Сообщений: 6279
Награды: 9
Репутация: 1708
Блокировки:
SirNikolas,
Ну что ж, я так и подумал :)


НУ И ЧТО ТЕПЕРЬ?


Кликайте на дракошку ;)
 

HexingДата: Суббота, 17 Декабря 2011, 14:00:58 | Сообщение # 12
10 уровень
Группа: Проверенные
Сообщений: 1645
Награды: 1
Репутация: 432
Блокировки:
Вещь то конечно стоющая, но я думаю работать быстрее хеша не будет, ведь код как никак грузит проц, а хэш где-то там встроен в движке - т.о. предположительно работает быстрее...
Но на мой взгляд эту вещь нужно использовать как минимум изза удобства =)

Добавлено (17 Декабрь 2011, 14:00:58)
---------------------------------------------
ах да, зачем эти сложности с "расчёской"? и почему чем больше элементов тем больше выигрыш в скорости работы?


 

SirNikolasДата: Суббота, 17 Декабря 2011, 14:17:30 | Сообщение # 13
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Если в дерево будут писаться целочисленные в следующем порядке: { 3, 1, 2, 4, 7, 6, 5 }, получится следующая картина:
Code
3
{
     1
     {
         null
         2 { null; null }
     }
     4
     {
         null
         7
         {
             6
             {
                 5 { null; null }
                 null
             }
             null
         }
     }
}
Чтобы дойти до самой дальней ветви, нужно пройти 5 узлов (3-4-7-6-5). После перестроения все ветви дерева станут одинаковой (или приблизительно одинаковой) длины:
Code
4
{
     2
     {
         1 { null; null }
         3 { null; null }
     }
     6
     {
         5 { null; null }
         7 { null; null }
     }
}
И теперь путь до самого удаленного значения составляет 3 узла.
Quote (Hexing)
и почему чем больше элементов тем больше выигрыш в скорости работы?
Я написал "выигрыш в скорости работы относительно линейного поиска", который чаще всего используется в подобных случаях.




Сообщение отредактировал SirNikolas - Суббота, 17 Декабря 2011, 14:23:00
 

DragoNДата: Суббота, 17 Декабря 2011, 14:22:57 | Сообщение # 14
Инквизитор
Группа: Стримеры
Сообщений: 4348
Награды: 7
Репутация: 2776
Блокировки:
Quote (Hexing)
и почему чем больше элементов тем больше выигрыш в скорости работы?

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


El Psy Congroo
 

SirNikolasДата: Суббота, 17 Декабря 2011, 14:24:31 | Сообщение # 15
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
DragoN, да, так и есть.

 

HexingДата: Суббота, 17 Декабря 2011, 14:36:58 | Сообщение # 16
10 уровень
Группа: Проверенные
Сообщений: 1645
Награды: 1
Репутация: 432
Блокировки:
SirNikolas, но ведь на разложение и складывание "древа" тратится время, не так ли?

 

SirNikolasДата: Суббота, 17 Декабря 2011, 14:42:06 | Сообщение # 17
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Да, это делается рекурсивно.
Code
static $indexator_type$ array indexAr
static $value_type$ array valueAr

method ToArray takes integer n returns integer
     if n1 != -1 then
         set n = n1.ToArray(n)
     endif
     if value != thistype(-1).value then
         set indexAr[n] = index
         set valueAr[n] = value
         set n = n + 1
     endif
     set Empty = true//call .destroy()
     if n2 != -1 then
         return n2.ToArray(n)
     endif
     return n
endmethod

static method FromArray takes integer n, integer jump, integer max returns thistype
     local thistype this = create()
     if jump > 0 and n - jump >= 0 then
         set this.n1 = FromArray(n - jump, jump / 2, n)
     else
         set this.n1 = -1
     endif
     set this.index = indexAr[n]
     set this.value = valueAr[n]
     if jump > 0 and n + jump < max then
         set this.n2 = FromArray(n + jump, jump / 2, max)
     else
         set this.n2 = -1
     endif
     return this
endmethod
Поэтому его стоит применять к тем древам, которые неизменны всю игру.


 

DragoNДата: Суббота, 17 Декабря 2011, 14:49:02 | Сообщение # 18
Инквизитор
Группа: Стримеры
Сообщений: 4348
Награды: 7
Репутация: 2776
Блокировки:
а вообще рекурсия - зло trollface


El Psy Congroo
 

SirNikolasДата: Суббота, 17 Декабря 2011, 14:50:36 | Сообщение # 19
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
DragoN, ты предлагаешь имитировать стек вызовов и заменить рекурсию циклом?

 

DragoNДата: Суббота, 17 Декабря 2011, 15:08:28 | Сообщение # 20
Инквизитор
Группа: Стримеры
Сообщений: 4348
Награды: 7
Репутация: 2776
Блокировки:
Quote (SirNikolas)
DragoN, ты предлагаешь имитировать стек вызовов и заменить рекурсию циклом?

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


El Psy Congroo
 

HexingДата: Суббота, 17 Декабря 2011, 15:12:39 | Сообщение # 21
10 уровень
Группа: Проверенные
Сообщений: 1645
Награды: 1
Репутация: 432
Блокировки:
SirNikolas, как часто происходит переформирование дерева? если при каждом добавлении элемента то это печаль, ведь ХТ и нужна для добавления в неё элементов в процессе игры, тоесть на спелл касте и т.п.?

 

SirNikolasДата: Суббота, 17 Декабря 2011, 15:22:25 | Сообщение # 22
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
При вызове пользователем метода Rebuild().

 

HexingДата: Суббота, 17 Декабря 2011, 17:04:42 | Сообщение # 23
10 уровень
Группа: Проверенные
Сообщений: 1645
Награды: 1
Репутация: 432
Блокировки:
SirNikolas, Хмммм
Ну впринципе нет смысла в этом методе, ведь он требует времени, а смысл его вызывать есть лишь при добавлении элементов в таблицу => не факт что это быстрее


 

SirNikolasДата: Суббота, 17 Декабря 2011, 17:58:47 | Сообщение # 24
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Вот что я намутил:
Ранее раскрытием рекурсии никогда не занимался, так что прошу оценить.


 

HexingДата: Суббота, 17 Декабря 2011, 18:17:25 | Сообщение # 25
10 уровень
Группа: Проверенные
Сообщений: 1645
Награды: 1
Репутация: 432
Блокировки:
ужас) только ты способен это понять, но выглядит круто coolstory

 

Форум о Warcraft 3 » Раздел для картостроителей » GUI / Jass » [Система] Dictionary
  • Страница 1 из 2
  • 1
  • 2
  • »
Поиск:

Copyright © 2006 - 2024 Warcraft3FT.info При копировании материалов c сайта ставьте, пожалуйста, активную обратную ссылку на нас • Design by gReeB04ki ©
Хостинг от uCoz