Добрый вечер. Тут говорится, что при обращении к массиву выделяется память на 1024 элемента.
Вопрос. Выделение памяти в хеш-таблицах работает так же? То есть при обращении к первым выделится 1024, а при вызове FlushChildHashtable() - освободится? 1.26а

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

да, массив постоянно будет делать reAllocMem , если текущий размер окажется мельче, чем номер ячейки. Поэтому, если массив будет часто писаться с инкрементом, то выгоднее сперва прописать в последнее допустимое значение (8191 для 26 патча) типа MyArray[8191]=0
чисто чтобы его по памяти не возили туда-сюда каждые X значений (не смотрел, сколько изначально выделяется)
я вот у себя пофиксил такую же байду с таблицей строк. игра выделяет по 16 ячеек под строки, а у меня в доте они генерируются десятками в секунду. Каждую секунду игра делала ре-аллок памяти, а к середине игры там уже несколько мб таблица туда-сюда ездила. Сделал аллок в разы больше - и таблица всего 2 раза переедет за 40 минут игры максимум. Экономия тактов налицо.
Хеш-таблицы вообще не являются массивами, гугл в помощь, поэтому там об этом думать не стоит. Стоит думать лучше о том, чтобы первичных (родительских) ключей было меньше, чем вторичных, чисто исходя из того, что в этом случае перебор по таблице окажется быстрее
`
ОЖИДАНИЕ РЕКЛАМЫ...
0
28
4 года назад
0
ScorpioT1000, у него 1.26.
0
17
4 года назад
0
Проверил по другому. Да, обращение к заполненной hashtable чуть тяжелее, как и должно быть. В ходе экспериментов было выяснено:
  1. Обращение к последним добавленным parentKey быстрее, чем к первым.
  1. Обращение к последним childKey внутри одного parentKey быстрее, чем к первым добавленным.
  1. При постоянном обращении к одному и тому же элементу со временем нагрузка выравнивается.
  1. Падение производительности незначительное, обычно это 6-0 фпс.
Слишком много сходства между parent и child, надеюсь это хеш-таблица хеш-таблиц, а списки там лишь для решения коллизий, как и сказал ScorpioT1000 (что объясняет пункт 1 и 2)
0
16
4 года назад
0
чел, который ковырял таблицы, остался недоволен их качеством, ну и то, что ключи делаются по битовому (userKey & parentUniqueKey) вместо реальной хеш-функции, что повышает шанс коллизий в теории. Но я сам ни разу не сталкивался с коллизиями, хз
0
28
4 года назад
Отредактирован PT153
0
В любой хеш-таблице будут коллизии, их можно решать по-разному, одним способом является chaining: в ячейке массива hash(key) хранится не (key, value), а ссылка на список, который хранит все элементы (key, value), у которых hash(key) одинаков.
3
14
4 года назад
3
Для доступа к ячейке хэштаблицы jass'а нужно пройти через 3 словаря.
Ключ для первого - номер хэштаблицы, для остальных двух - parentKey и childKey.
Игра использует собственные коллекции.
Вот как выглядит поиск в их словаре:
code
type
	generic TSHashTable<TKey, TValue, TKeyManager> = object
	public type
		PValue = ^TValue;
		TItems = specialize TSLinkedList<TValue>;
		PItems = ^TItems;
		TPages = specialize TSGrowableArray<TItems>;
	public
		vtable: Pointer;
		Items: TItems;
		Counter: Dword;
		Pages: TPages;
		HashMask: Dword;
	end;

function TSHashTable.Find(const AKey: TKey): PValue;
var
	Hash: Dword;
	Index: Integer;
	Page: PItems;
	Item: PValue;
begin
	Result:= nil;

	if HashMask = Dword(-1) then exit;
	
	Hash:= TKeyManager.GetKeyHash(AKey);
	Index:= Hash and HashMask;
	Page:= Pages.ItemPointers[Index];

	for Item in Page do begin
		if (Item^.HashKeyData.Hash = Hash) and
			TKeyManager.IsKeysEqual(Item^.HashKeyData.Key, AKey)
		then begin
			Result:= Item;
			break;
		end;
	end;
end;
0
17
4 года назад
0
Интересно, что в Pascal есть дженерики. Тогда у нас 3 расширяемых массива, но количество номеров хеш-таблиц ограничено же 256ю.
IceFog, спасибо за разъяснение ситуации с массивами и списками)
Чтобы оставить комментарий, пожалуйста, войдите на сайт.