JASS: группа или массив?
Здравствуйте.
Анализируя свой код подробнее, стремясь выяснить, что и как работает, хотел бы получить у уважаемых адептов JASS разъяснение важного для меня вопроса о том, как две конструкции JASS обходятся с памятью.
» Есть блок кода, который можно впихнуть в любую бибилотеку или область

Индексация боевых единиц при помощи массива

globals
    unit array UnitIndexer // Конечно, даже по меркам vJASS, если написать UnitIndexer[размер_массива_ниже_8191], это будет синтаксический сахар, так как массивы в WarCraft III статические и меньше 8192 ячеек в памяти инициализировать не станут.
    integer Indexer_Index = 0
endglobals

function GetUnitIndex takes unit whichUnit returns integer
    // Знаю, что не самая оптимальная реализация, но задача этого кода - показать суть дела.
    local integer i = 0

    loop
        exitwhen i > Indexer_Index
        if UnitIndexer[i] == whichUnit then
            return i
        endif
        set i = i + 1
    endloop

    return -1
endfunction

function IsUnitIndexed takes unit whichUnit returns boolean
    return GetUnitIndex(whichUnit) >= 0
endfunction

function IndexNewUnit takes unit whichUnit returns nothing
    // Не стану показывать проверку на дубликаты и "защиту от дураков", чтобы не усложнять код.
    set UnitIndexer[Indexer_Index] = whichUnit
    set Indexer_Index = Indexer_Index + 1
endfunction
» И есть другой блок кода - иной подход к реализации того же самого

Нахождение боевой единицы через группу

globals
    group UnitIndexer = null
endglobals

function IsUnitIndexed takes unit whichUnit returns boolean
    return IsUnitInGroup(whichUnit,UnitIndexer)
endfunction

function IndexNewUnit takes unit whichUnit returns nothing
    if UnitIndexer == null then
        set UnitIndexer = CreateGroup()
    endif
    call GroupAddUnit(UnitIndexer,whichUnit)
endfunction
Какой способ лучше с точки зрения памяти?
С массивами - понятно, создаётся 8191 экземпляр для хранения ссылки на объект unit.
Группа видится мне динамическим массивом, который аллоцирует и деаллоцирует память по необходимости.
Расскажите мне, как на самом деле обстоит дело.
В ожидании ответа,
Singularity, 29.06.2017

Лучший ответ:
Странное понимание механики. Не бывает универсального лучшего способа, потому и существуют разные способы для конкретных ситуаций.
А экономить байты и такты процессора, заранее пользуясь интерпретируемым скриптовым языком, это вообще моветон.
Разве массив в WarCraft III не предынициализирует 8192 ячейки памяти (по Вашей формуле, в моём случае он потребляет 8192*4=32768 байт, то есть 32Кб)? Он ведь не динамический.
Нет, он динамический. Исходный размер при создании - 1024. И расширяется на 1024 ячейки по мере доступа вплоть до максимальных 8192.


Views: 3 713

» Лучшие комментарии


DracoL1ch #1 - 3 years ago 4
Голосов: +4 / -0
чего ты хочешь добиться? ни один костыль не работает быстрее, чем нативка. нативки групп быстрее любого перебора на жассе. доступ к массиву чуть-чуть быстрее, чем к группе, но в 99.9% случаев вы не используете вечные таймеры с 0.02 таймаутом, чтобы это что-то решало.
если работаешь с группами - то так и работай. это связанный список с динамической линковкой юнитов, ничего в нем плохого нет. а про память волноваться следовало в 90х - сегодня +- мегабайт никто и не заметит. Ну а если прям зудит - массив это ~10 байт на служебные и максимальныйиндекс*4 под данные. Группа - ~200 байт под служебные и кол-во юнитов*4 под список
nvc123 #3 - 3 years ago 0
Голосов: +0 / -0
кол-во юнитов*4 под список
если это список то по идее узлы должны хранить ссылки на соседей и должно получаться *8 или *12
Singularity #4 - 3 years ago (изм. ) 0
Голосов: +0 / -0
DracoL1ch:
чего ты хочешь добиться? ни один костыль не работает быстрее, чем нативка. нативки групп быстрее любого перебора на жассе. доступ к массиву чуть-чуть быстрее, чем к группе, но в 99.9% случаев вы не используете вечные таймеры с 0.02 таймаутом, чтобы это что-то решало.
если работаешь с группами - то так и работай. это связанный список с динамической линковкой юнитов, ничего в нем плохого нет. а про память волноваться следовало в 90х - сегодня +- мегабайт никто и не заметит. Ну а если прям зудит - массив это ~10 байт на служебные и максимальныйиндекс*4 под данные. Группа - ~200 байт под служебные и кол-во юнитов*4 под список
Подождите, подождите. Откуда взяты цифры в 10 байт и в 200 байт?
Разве массив в WarCraft III не предынициализирует 8192 ячейки памяти (по Вашей формуле, в моём случае он потребляет 8192*4=32768 байт, то есть 32Кб)? Он ведь не динамический.
В ожидании ответа,
Singularity, 29.06.2017
Ярг Восьмой #5 - 3 years ago (изм. ) 0
Голосов: +0 / -0
Хеш-таблица для чего была придумана? В ней же можно хранить индекс боевой единицы, используя её хендл-идентификатор. А ещё есть Set\GetUnitUserData..., если конечно он не забронирован другой системой.
DracoL1ch #6 - 3 years ago (изм. ) 0
Голосов: +0 / -0
ай, точно, каждый линк в цепочке то ли 5, то ли 6 4-байтовых dword, там не только на соседей, но еще и контрольная какая-то инфа, не знаю, для чего, так что группа тяжелее в разы выходит
нет, массив переносится при необходимости добавить места, по умолчанию он не выделяет ничего, а когда доходит до запроса - начинает работать
цифры взяты из структуры. состав массива не знаю, но адрес начала хранится в 0xC, т.е. минимум 12 байт под начальные данные, а там хз что дальше, но немного.
группа же до 0x5C простирается, или 23 4-байтовых, глянул в своей разметке
сначала писал числа от балды по примерной памяти. эта инфа абсолютно не важна
Doc #7 - 3 years ago 0
Голосов: +0 / -0
В чем смысл чето городить. На 1 юнита достаточно одной структуры в любой карте. Адрес структуры можно хранить в кастом велью. Единственные места где нужно пользоваться самим юнитом это там куда этот юнит приходит (ивенты) и там куда он уходит (нативки). В остальном пользуемся самой структурой.
Clamp #8 - 3 years ago (изм. ) 0
Голосов: +0 / -0
Индексация боевых единиц при помощи массива
Очевидное преимущество в том, что юнита можно заменить на что угодно и оно будет работать как надо. Кроме того, если стак обрабатывается таймером с высоким периодом, то массив будет показывать себя заметно лучше в плане быстродействия, пруф, бенчмарк.

Если группа - это связанный список, то "под капотом" почти всех функций из Groups API используются рекурсивные алгоритмы, и чем больше в группе юнитов, тем медленнее они работают.

А код из статьи Скорпа можно было оставить и без подобной переработки.
DracoL1ch #9 - 3 years ago 0
Голосов: +0 / -0
с чего вдруг рекурсивные? Обычные циклы-переборы. На Си скорость выходит такая, что любые костыли-попытки на жассе в пролете.
Clamp #10 - 3 years ago 0
Голосов: +0 / -0
Обычные циклы-переборы.
Хочу пример обычного цикла-перебора для связанного списка =)
nvc123 #11 - 3 years ago (изм. ) 0
Голосов: +0 / -0
Clamp, любую рекурсию можно превратить в цикл
кроме того связанный список поддерживает итераторы которые внезапно используются в циклах
вот тебе пример для списка с граничным узлом
int size(List list){
	int size=0;
	Node n=list.node(); 
	while(n.hasNext()){
		size++;
		n=n.next();
	}
}
без граничного будет тоже самое только с проверкой на пустоту и do while
DracoL1ch #12 - 3 years ago (изм. ) 0
Голосов: +0 / -0
Ну вот из псевдокода по IsUnitInGroup:
v5 начинается с 0-го элемента списка
while ( *(_DWORD *)(v5 + 8) != a2 )
{
v5 = *(_DWORD *)(v5 + 4);
if ( v5 <= 0 )
goto LABEL_8;
}
Приведи задачу, где необходима будет именно рекурсия, я че-то не понимаю
Singularity #13 - 3 years ago (изм. ) 0
Голосов: +0 / -0
Хеш-таблица для чего была придумана? В ней же можно хранить индекс боевой единицы, используя её хендл-идентификатор. А ещё есть Set\GetUnitUserData..., если конечно он не забронирован другой системой.
Стоит отдать хэш-таблице должное - она точно ещё тяжелее группы.
с чего вдруг рекурсивные? Обычные циклы-переборы. На Си скорость выходит такая, что любые костыли-попытки на жассе в пролете.
Собственно, моя задача в том, чтобы сделать быструю систему с максимальным взаимодействием с ядром WarCraft III, то есть плагин, а не костыль.
Вот и ищу способ.
В надежде на ответ,
Singularity, 29.06.2017
quq_CCCP #14 - 3 years ago 0
Голосов: +0 / -0
Ну дык пиши весь код карты на асме или вовсе инжекти мемхаком дллку, на Си все будет ближе и быстрее.
Hanabishi #16 - 3 years ago (изм. ) 8
Голосов: +8 / -0

Странное понимание механики. Не бывает универсального лучшего способа, потому и существуют разные способы для конкретных ситуаций.
А экономить байты и такты процессора, заранее пользуясь интерпретируемым скриптовым языком, это вообще моветон.
Разве массив в WarCraft III не предынициализирует 8192 ячейки памяти (по Вашей формуле, в моём случае он потребляет 8192*4=32768 байт, то есть 32Кб)? Он ведь не динамический.
Нет, он динамический. Исходный размер при создании - 1024. И расширяется на 1024 ячейки по мере доступа вплоть до максимальных 8192.
Singularity #17 - 3 years ago (изм. ) 0
Голосов: +0 / -0
Нет, он динамический. Исходный размер при создании - 1024. И расширяется на 1024 ячейки по мере доступа вплоть до максимальных 8192.
Спасибо за пояснение, я этого не знал. То есть, сначала инициализируется 1024 ячейки, когда происходит доступ к следующим 1024-м, инициализируется ещё 1024 и это происходит до максимума в 8192, понял ли я это верно?
Мдамс, над статьёй работать ещё и работать...
Засучив рукава,
Singularity, 29.06.2017
Clamp #18 - 3 years ago 0
Голосов: +0 / -0
любую рекурсию можно превратить в цикл
Разумеется, да, только далеко не всегда целесообразно так делать.
DracoL1ch:
Ну вот из псевдокода по IsUnitInGroup
Так лол, сишные компиляторы всегда переводят хвостовую рекурсию в плоскую итерацию, ЕМНИП.

Минут через несколько вкину пример, в котором, на мой взгляд, применение рекурсии весьма оправдано.
Время программиста всегда дороже времени процессора \о/
Hanabishi #19 - 3 years ago 0
Голосов: +0 / -0
о есть, сначала инициализируется 1024 ячейки, когда происходит доступ к следующим 1024-м, инициализируется ещё 1024 и это происходит до максимума в 8192, понял ли я это верно?
Да.
Разумеется, да, только далеко не всегда целесообразно так делать.
Так лол, сишные компиляторы всегда переводят хвостовую рекурсию в плоскую итерацию, ЕМНИП.
Вроде как нет, от того в вещах типа быстрой сортировки и случается переполнение стека вызовов. Но в случае вара это вообще пофиг, так как ограничение на на количество операций.
Clamp #20 - 3 years ago (изм. ) 0
Голосов: +0 / -0
» пример
struct Foo
{
    thistype prev = 0;
    thistype next = 0;
    // ...

    thistype getFirst() {
        if (this.prev != 0) {
            return prev.getFirst();
        }
        return this;
    }
};

Foo getFirstOf(Foo given) {
    if (given.prev != 0) {
        return getFirstOf(given.prev);
    }
    return given;
}

Foo createListAndReturnLastObject(int listLenght) {
    Foo st_1 = Foo.create();
    Foo st_2;
    int i = 0;
    while (i++ < listLenght) {
        st_2 = Foo.create();
        st_1.next = st_2;
        st_2.prev = st_1;
        st_1 = st_2;
    }
    return st_2;
}

void Test() {
    Foo bar = getFirstOf(createListAndReturnLastObject(31));
}
То есть сам список как объект не обязательно описывать, ИМО. Вообще, я не вполне уверен в теме, так что буду рад исправлениям и пояснениям, если они уместны. Код на JASS, но логика вполне понятна и отлично переносится в цпп. Трахаться с указателями по памяти влом, нет IDE под рукой.

Разумеется, можно запариться и сделать через цикл, но это будет довольно-таки перегруженный и тяжело воспринимаемый код, как по мне.
nvc123 #21 - 3 years ago 0
Голосов: +0 / -0
 thistype getFirst() { 
	if (this.prev != 0) { 
		return getFirst(); 
	} 
	return this; 
}
бесконечная рекурсия
nvc123 #23 - 3 years ago 2
Голосов: +2 / -0
твой вариант
Foo getFirstOf(Foo given) { 
	if (given.prev != 0) { 
		return getFirstOf(given.prev); 
	} 
	return given; 
} 
легко заменяется на
Foo getFirstOf(Foo given) { 
	Foo temp=given;
	while (temp.prev != 0) { 
			temp=temp.prev; 
	} 
	return temp; 
} 
что довольно легко воспринимается и не является перегруженным
рекурсия нужна в основном в операциях над деревьями и сетями
т.е. там где происходит ветвление
а список как и массив это "прямая дорога" и с ними лучше работать циклами
Clamp #24 - 3 years ago 0
Голосов: +0 / -0
nvc123, достаточно убедительно. Буду дома - закину другой кейс, но, скорее всего, уже в блог, чтобы не оффтопить.

Да, а что насчёт метода в самой структуре?
nvc123 #25 - 3 years ago 0
Голосов: +0 / -0
многие люди в качестве примера того что такое рекурсия показывают факториал или списки т.к. их намного проще понять чем те же деревья
но при этом забывают упомянуть что это пример того что такое рекурсия
а не пример того в каких ситуациях надо использовать рекурсию
и потом есть толпы джуниоров которые не знают в каких ситуациях рекурсия оправдана
Clamp:
Да, а что насчёт метода в самой структуре?
с ним тоже самое
thistype getFirst() { 
	Foo temp=this;
	while (temp.prev != 0) { 
			temp=temp.prev; 
	} 
	return temp; 
} 
Clamp #26 - 3 years ago (изм. ) 0
Голосов: +0 / -0
в каких ситуациях рекурсия оправдана
Тем не менее, не вижу ощутимого преимущества в решении через цикл, там растёт стак вызовов, здесь (офк не в wc, а в целом) растёт потребление памяти.
многие люди в качестве примера того что такое рекурсия
TBH, никогда не читал статей или примеров про рекурсию. Мне интересна алгоритмика (и то меньше, чем архитектура ПО), но специальность у меня совершенно не "программист", хоть джун, хоть не джун.

Предлагаю завершать офтоп, вечером в блоге закину другой пример, аж интересно.
nvc123 #27 - 3 years ago (изм. ) 0
Голосов: +0 / -0
Тем не менее, не вижу ощутимого преимущества в решении через цикл, там растёт стак вызовов, здесь (офк не в wc, а в целом) растёт потребление памяти.
потребление памяти растёт на фиксированную величину(сложность О(1), тратит 4/8 байт)
а стэк вызова забивается при каждом следующем элементе(сложность О(n), тратит n * 4/8 байт)
и размер стека как правило довольно мал
а если список хранится не в оперативной памяти и содержит несколько миллионов элементов то у тебя не хватит оперативки чтобы держать весь этот стек
а писать свою реализацию потоков хранящую стек вызовов на ж.д. только ради того чтобы работать с рекурсией не самая лучшая идея
главный + рекурсии в возврате на несколько шагов назад что используется в деревьях и подобных структурах (например прошлись по 1 ветки, вернулись к развилке и прошлись по другой)
например подсчитать количество файлов не являющихся папками в папке
class File{
	
	int countNoDirs(){
		return 1;
	}
}

class Dir extends File{ // папка наследуется от файла
	private List<File> files;
	
	int countNoDirs(){ // переопределённый метод
		int count=0;
		for(File f:files){
			count+=f.countNoDirs();
		}
		return count;
	}
}
сделать подобное без рекурсии тот ещё гемор
Doc #28 - 3 years ago (изм. ) 0
Голосов: +0 / -0
Щас бы использовать рекурсию для прохода по массива в языке без поддержки хвостовой рекурсии и засирать стек вызовов ммм.
Плохо читал, это уже написали оказывается.
Рекурсия это просто использование стека вызовов для хранения стейта, ничего больше. Не нужно её использовать там где проще без нее обойтись.
Clamp #29 - 3 years ago 0
Голосов: +0 / -0
языке без поддержки хвостовой рекурсии
Си

для прохода по массива
Тащемта по списку =О
Doc #30 - 3 years ago 0
Голосов: +0 / -0
нет никакой разницы, плиз.
void myForEach(Value[] values, Consumer<Value> action, int index) {
    if (values.length == index) {
        return;
    }

    action.accept(values[index]);
    myForEach(values, action, index + 1);
}
вместо того чтобы хранить index в локалке значение хранится в стеке вместе с values и action.