XGM Forum
Сайт - Статьи - Проекты - Ресурсы - Блоги

Форуме в режиме ТОЛЬКО ЧТЕНИЕ. Вы можете задать вопросы в Q/A на сайте, либо создать свой проект или ресурс.
Вернуться   XGM Forum > Warcraft> Барахолка
Ник
Пароль
Войти через VK в один клик
Сайт использует только имя.

Ответ
 
user_jasser

offline
Опыт: 232
Активность:
Ассоциативное индексирование
Предлагаю вашему вниманию еще одну наработку.
Что она из себя представляет? В общем это без малого хэш, реализованный на jass.
Зачем он нужен? В первую очередь для динамического индексирования RB_объектов или ревкодов, а также, можно сохранять значение и извлекать его по 32битному ключу.

Как работает? Сначало генерируется хеш-значение в таблице(63*128). Здесь береться шесть младших бит старшего слова и семь младших бит младшего.
hash =((val*0x200)/0x2000000)*((val*0x1000000)/0x1000000)
в результате генерируются индекс в хеш-таблице.
Дальше ключ делиться на два слова и сохраняться в две хешь-структуры, индекс структуры младшего слова возвращаеться из функции.

[hash] <----> [Hi] <----> [Lo]
return [Lo]
Коллизии решаются четырех-связным списком :

Код:
library HashSystem
//!************ HashSystem ************
//  Name: HashSystem v.1.0.0
//  Author: AiwaDoter
//  Date: 23.05.09 20:40
//!************************************

struct hash extends array
private integer iWord
    private hash prev
    private hash head
    private hash link
 hash data

private hash ids
    private hash si_v 
    private static hash si_f=0
    private static integer si_i=0
    
//! textmacro clear takes THIS
        set $THIS$.data = 0
        set $THIS$.prev = 0
        set $THIS$.head = 0
        set $THIS$.link = 0
        set $THIS$.iWord = 0
        set $THIS$.si_v = hash.si_f
        set hash.si_f = $THIS$   
//! endtextmacro

//! textmacro create takes THIS, PREV, IWORD 
        if( hash.si_f!=0 )then
            set $THIS$ = hash.si_f
            set hash.si_f = $THIS$.si_v
         else
            set hash.si_i = hash.si_i+1
            set $THIS$ = hash.si_i
        endif
        debug if( integer($THIS$)>8190 )then
        debug   call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,1000.,"Unable to allocate id for an object of type: hash")
        debug   return 0
        debug endif
        set $THIS$.si_v= -1
        set $THIS$.iWord= $IWORD$
        set $THIS$.prev= $PREV$
//! endtextmacro

//! textmacro search
        loop
            exitwhen ( this.iWord == iWord )
            if( this == 0 )then
//! endtextmacro
//! textmacro endsearch takes RET 
                set this.head = head
                set head.link = this
                return $RET$
            endif
            set head = this
            set this = this.link
        endloop      
//! endtextmacro

//! textmacro hash takes THIS, I
        local hash $THIS$ =(($I$*0x200)/0x2000000)*(($I$*0x1000000)/0x1000000)
        if( $THIS$<0 )then
            set $THIS$ = -$THIS$
        endif
//! endtextmacro
    
    static method find takes integer val returns hash
        local hash head
        local integer iWord = val/0x10000
        //! runtextmacro hash("this","val")
        if( this.ids == 0 )then
        //! runtextmacro create("this.ids","this","iWord")
        //! runtextmacro create("this.ids.data","this.ids","(val*0x10000)/0x10000")
            return this.ids.data
         else
           set this = this.ids
        //! runtextmacro search()
            //! runtextmacro create("this","head.prev","iWord")
            //! runtextmacro create("this.data","this","(val*0x10000)/0x10000")
        //! runtextmacro endsearch("this.data")
           set this = this.data
           set iWord = (val*0x10000)/0x10000
        //! runtextmacro search()
            //! runtextmacro create("this","head.prev","iWord")
        //! runtextmacro endsearch("this")   
            return this
        endif   
    endmethod
   
    method free takes nothing returns nothing
        if( this != this.prev.data )then
            set this.head.link = this.link
         else
            set this.prev.data = this.link
            if( this.prev.data == 0 )then
                if( this.prev != this.prev.prev.ids )then
                    set this.prev.head.link = this.prev.link
                 else
                    set this.prev.prev.ids = this.prev.link 
                endif
            //! runtextmacro clear("this.prev")
            endif            
        endif
    //! runtextmacro clear("this")
    endmethod

endstruct

endlibrary


Преимущества перед gamecache - создает ассоциативный индекс для переменных с массивом(gamecache этого не делает).
Работает быстрее чем gamecache на 35-12% при небольшом количестве сохраненных объектов 1..1000.

Недостатки это - способность работать только с integer, каждому ключу можно присвоить только одно значение.
При болеше 2000 сохраненных ключей может работать медленей чем gamecache на 3% и более. Поэтому чтоб работало быстро нужно следить за наполнением таблицы и удалять ненужные ключи!.

Применять достаточно просто :
Код:
local hash h = hash.find(H2I(GetTriggerUnit())) // возвращает хэшь-структуру если такой нет то создает новую по ключу.
set h.data = hash.find('abcd').data
.....
set h.free()
Прикрепленные файлы
Тип файла: w3x DDH.w3x (47.6 Кбайт, 26 просмотров )

Отредактировано user_jasser, 27.05.2009 в 15:04.
Старый 27.05.2009, 01:39
Ranger21
I love beatiul days XD
offline
Опыт: 13,274
Активность:
Ммм... интересная штука, а применение в чём?=)
Старый 27.05.2009, 09:25
Мирдж

offline
Опыт: 7,981
Активность:
Ranger21, как замена стандартному кешу Варика:
Цитата:
Преимущества перед gamecache - создает ассоциативный индекс для переменных с массивом(gamecache этого не делает).
Работает быстрее чем gamecache на 35-12% при небольшом количестве сохраненных объектов 1..1000.

user_jasser, я, конечно, не разбираюсь, как это все работает, но могу предложить решение проблемы с хранением других видов переменных: просто для каждого типа создать свой префикс (если такое возможно)... Там же код вида "0х[числа]" - вместо ноля подставлять другие числа, и все (правда, все равно будет ограничение - 10 типов переменных MAX) (сразу прошу прощения за мое полное незнание в этом вопросе :))
Старый 27.05.2009, 10:43
agentex

offline
Опыт: 34,534
Активность:
Цитата:
Недостатки это - способность работать только с integer, каждому ключу можно присвоить только одно значение.

фтопку. кому это тогда нужно? Плюс все это можно спокойно сделать без вжасса
Старый 27.05.2009, 13:25
Ranger21
I love beatiul days XD
offline
Опыт: 13,274
Активность:
Да уж... алгоритмика и внедрение в варик прочих вещей это конечно хорошо, но всё это можно реализовать по другому :P
Старый 27.05.2009, 13:47
NETRAT

offline
Опыт: 83,762
Активность:
hash = hash у тебя написано неправильно
мда, если это работает быстрее того что прошито в движок, видимо gamecache имеет невероятно карявую реализацию

Отредактировано NETRAT, 27.05.2009 в 14:27.
Старый 27.05.2009, 14:21
user_jasser

offline
Опыт: 232
Активность:
NETRAT
Да это работает быстрее.. Я согласен с утверждением, что интерпретаторы по определению в раз 10 медленей и жасс этому далеко не исключение, но всеже это работает так как я написал выше. Это при том что gamecache имел равные права..

Отредактировано user_jasser, 27.05.2009 в 16:31.
Старый 27.05.2009, 14:56
Ответ

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск

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

BB-коды Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход



Часовой пояс GMT +3, время: 02:34.