Что-то я в последнее время стал делать из 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("<Тип индексатора>", "<Тип значений>", "<Имя библиотеки сравнения>", "<Максимальный суммарный размер всех словарей данного типа>")
Эта инструкция объявит тип массива 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
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, перестраивающий словарь для наиболее быстрого доступа к элементам. Следует учесть, что он достаточно медленный, поэтому после каждого обновления его вызывать не стоит.
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-спеллов.
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 сделан на основе бинарного древа, так что доступ к элементам осуществляется с логарифмической скоростью. При перестроении дерево раскладывается в массив, который снова собирается в дерево, в результате чего сортируется. Если возникнут вопросы, задавайте, не стесняйтесь.
Ty3uK, основная причина, по которой я писал на vJass'е - текстмакросы, позволяющие создавать словари любых типов и любого размера. Вряд ли конечный пользователь захочет вручную копировать исходник и везде заменять типы на те, которые ему нужны. Плюс еще вместо set d["abc"] = 123 надо было бы писать call Dictionary_string_integer_set(d, "abc", 123), что понижало бы читабельность кода.
Quote (Ty3uK)
самое обидное, что потом этот аккуратный и красивый код превращается в ЭТО
SirNikolas, я и не спорю, просто говорю о том, что код "толстеет" на глазах - вошел на парсер 39 кб, а вышел - 93 Так и все-таки: имет ли смысл делать такие фичи на жасс2?
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) --------------------------------------------- В принципе, ты можешь на чем угодно его базировать - условие сортировки задает пользователь.
Вещь то конечно стоющая, но я думаю работать быстрее хеша не будет, ведь код как никак грузит проц, а хэш где-то там встроен в движке - т.о. предположительно работает быстрее... Но на мой взгляд эту вещь нужно использовать как минимум изза удобства =)
Добавлено (17 Декабрь 2011, 14:00:58) --------------------------------------------- ах да, зачем эти сложности с "расчёской"? и почему чем больше элементов тем больше выигрыш в скорости работы?
Чтобы дойти до самой дальней ветви, нужно пройти 5 узлов (3-4-7-6-5). После перестроения все ветви дерева станут одинаковой (или приблизительно одинаковой) длины:
и почему чем больше элементов тем больше выигрыш в скорости работы?
если я правильно понял, то тут используется бинарный поиск элементов и как в следствие он будет значительно быстрее линейного поиска при большем количестве данных в массиве
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, ты предлагаешь имитировать стек вызовов и заменить рекурсию циклом?
вполне возможно, но скорость может упасть + параллельно надо будет хранить адрес возврата если руки кривые и захотят менять что-то, то рекурсия вызовет печальные последствия
SirNikolas, как часто происходит переформирование дерева? если при каждом добавлении элемента то это печаль, ведь ХТ и нужна для добавления в неё элементов в процессе игры, тоесть на спелл касте и т.п.?
SirNikolas, Хмммм Ну впринципе нет смысла в этом методе, ведь он требует времени, а смысл его вызывать есть лишь при добавлении элементов в таблицу => не факт что это быстрее
method ToArray takes nothing returns integer local thistype s = this local integer stack_top = 0 local integer n = 0 local $value_type$ default = thistype(-1).value local integer array ret_addr local thistype array arg_stack set ret_addr[0] = 0 loop loop if ret_addr[stack_top] == 0 then set ret_addr[stack_top] = 1 if s.n1 != -1 then set arg_stack[stack_top] = s set stack_top = stack_top + 1 set ret_addr[stack_top] = 0 set s = s.n1 exitwhen true endif endif if ret_addr[stack_top] == 1 then set ret_addr[stack_top] = 2 if s.value != default then set indexAr[n] = s.index set valueAr[n] = s.value set n = n + 1 endif set s.Empty = true if s.n2 != -1 then set arg_stack[stack_top] = s set stack_top = stack_top + 1 set ret_addr[stack_top] = 0 set s = s.n2 exitwhen true endif endif if stack_top == 0 then return n endif set stack_top = stack_top - 1 set s = arg_stack[stack_top] endloop endloop return 0 endmethod
Ранее раскрытием рекурсии никогда не занимался, так что прошу оценить.