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

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

да, массив постоянно будет делать reAllocMem , если текущий размер окажется мельче, чем номер ячейки. Поэтому, если массив будет часто писаться с инкрементом, то выгоднее сперва прописать в последнее допустимое значение (8191 для 26 патча) типа MyArray[8191]=0
чисто чтобы его по памяти не возили туда-сюда каждые X значений (не смотрел, сколько изначально выделяется)
я вот у себя пофиксил такую же байду с таблицей строк. игра выделяет по 16 ячеек под строки, а у меня в доте они генерируются десятками в секунду. Каждую секунду игра делала ре-аллок памяти, а к середине игры там уже несколько мб таблица туда-сюда ездила. Сделал аллок в разы больше - и таблица всего 2 раза переедет за 40 минут игры максимум. Экономия тактов налицо.
Хеш-таблицы вообще не являются массивами, гугл в помощь, поэтому там об этом думать не стоит. Стоит думать лучше о том, чтобы первичных (родительских) ключей было меньше, чем вторичных, чисто исходя из того, что в этом случае перебор по таблице окажется быстрее
`
ОЖИДАНИЕ РЕКЛАМЫ...

Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
0
16
4 года назад
Отредактирован DracoL1ch
0
стоп, а каким образом кол-во операций, ограниченных виртуалкой жасса, говорит о трудозатратах перебора внутренних списков? JASS OPlimit считает только кол-во операций байт-кода, скомпилиированного из JASS-кода, внутренняя кухня никак не влияет - будь то тяжеленная функция создания юнита или крохотная функция установки владельца предмету, они займут 10 и 5 байт-слов соответственно, однако производительность второй не в пример выше, потому что операций там - просто сдвиг битов.
я глянул методы Load*() и вижу, что там идет перебор списка по листьям (чайлд) ветки (родителю) дерева, пока не встретится элемент с нужным ID ячейки. так что чем больше данных в таблице, тем дольше перебор
0
17
4 года назад
Отредактирован Vlod
0
Эта hashtable - лист листов?
0
23
4 года назад
0
{}
3
16
4 года назад
3
я хз, в реале с таким не работал, пою что вижу в коде
0
19
4 года назад
0
0
23
4 года назад
0
типично
{id {parent:{id: {parent}}}}
0
37
4 года назад
Отредактирован ScorpioT1000
0
Перебор списка там как решение проблемы коллизий.
А каквы так тестировали, что порвали поток - это надо постараться запустить это в жасс без таймеров и экзекуэьютов. Попробуйте на луа
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) одинаков.
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.