UrsaBoss
WarCraft 3

Что быстрее, искать индекс структуры через loop или хештаблицей?

Добавлен
Так: 
        loop
            set i = i + 1
            if IsUnitInRegion(regionBase[i], GetConstructingStructure()) then
                call TriggerActions(i)
                exitwhen true
            endif
            exitwhen i == 109
        endloop
Или так: 
        local region r = GetTriggeringRegion()

        if IsUnitInRegion( r, GetConstructingStructure() ) then
            call TriggerActions( LoadInteger(hash, GetHandleId(r), 0) )
        endif

Принятый ответ

Хештаблицей будет быстрее:
nvc123:
Extremator:
Cancel:
а что насчёт хештаблиц? Скорость их работы?
всё крайне печально
лол что?
скорость работы глобалок в 1,5 раза быстрее чем у хештейблов
т.е. 10 обращений к хештейблам выполняется столько же времени сколько и 15 к глобалкам
если каждую секунду не выполняется более 1000 обращений к хештейблу то не юзать хэштейблы ради оптимизации та ещё тупость
Да, и для какой цели там сверху стоит "exitwhen true"?
17 июл 2018
  • Размещен: 17.07.2018 07:55:37
  • Создан: 17.07.2018 07:55:37
  • Обновлен: 17.07.2018 07:55:37
1 463
`
ОЖИДАНИЕ РЕКЛАМЫ...
0
12
6 лет назад
Отредактирован Sergarr
0
Хештаблицей будет быстрее:
nvc123:
Extremator:
Cancel:
а что насчёт хештаблиц? Скорость их работы?
всё крайне печально
лол что?
скорость работы глобалок в 1,5 раза быстрее чем у хештейблов
т.е. 10 обращений к хештейблам выполняется столько же времени сколько и 15 к глобалкам
если каждую секунду не выполняется более 1000 обращений к хештейблу то не юзать хэштейблы ради оптимизации та ещё тупость
Да, и для какой цели там сверху стоит "exitwhen true"?
Принятый ответ
0
18
6 лет назад
0
Sergarr:
Да, и для какой цели там сверху стоит "exitwhen true"?
Чтобы из loop выйти и не делать лишних "действий"
Просто юнит не может быть одновременно в нескольких regionBase[i]
0
28
6 лет назад
0
Ну так у тебя сложность цикла O(n), а хештаблицы O(1). Очевидно, что хеш тут будет быстрее.
Если же юнит или предмет будет привязан к структуре, то тогда номер структуры можно сохранять в UserData.
0
16
6 лет назад
0
у хештаблицы не (1), там по-идее связанный список и оно будет перебирать все ячейки, поэтому важно как можно меньше parentKeys иметь, а дробить именно childKeys.
0
28
6 лет назад
Отредактирован PT153
0
DracoL1ch:
у хештаблицы не (1)
В WCIII может и не O(1), но у нормальных хештаблиц есть регулирующее число, которое и определяет этот "почти O(1)".

Всё равно хеш в Jass быстрее цикла, в котором помимо обращения к ячейкам ещё и постоянный инкремент.
2
16
6 лет назад
2
ладно, это моё непонимание сути этих самых O(x), я имел ввиду лишь то, что там всё равно будет прохождение по ряду данных под капотом. циклы в любом случае проиграют хотя бы потому, что они на жассе, а не на родном языке игры.
2
28
6 лет назад
2
Если кому интересно.
Вот книга, где доказано, что у хештаблиц, в которых коллизии решены с помощью цепочек, сложность поиска O(1 + a), где а - коэффициент заполнения хештаблицы, a = n / m, n - количество хранимых элементов, m - размер основного массива.
Загруженные файлы
Чтобы оставить комментарий, пожалуйста, войдите на сайт.