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

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

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

Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
0
37
4 года назад
Отредактирован ScorpioT1000
0
Есть вероятность, что это один хешмап с конкатенацией двух ключей при работе из jass
0
16
4 года назад
0
Точно помню, что хештаблица варкрафта не эквивалентна настоящей, там даже по ключам ограничения есть, но деталей не помню, для кодера жасс это неважно.
Мы не экономим парентов, мы стараемся, чтобы корзин для поиска было меньше, чем яиц в них. На вскидку это связный список, а не массив, но я не эксперт в реализациях, да и исходников не имею
0
17
4 года назад
Отредактирован Vlod
0
  1. parentKey и childKey могут принимать значения от 2147483647 до -2147483648.
  1. Количество parentKey или childKey ограничено 18747, то есть не более 351450009 элементов.
  1. Не зависимо от загруженности таблицы и порядка опроса ключей, обращения выдают одинаковую нагрузку на поток.
  1. Так как существует функция FlushChildHashtable(), то конкатенация ключей возможна, но маловероятна.
0
16
4 года назад
0
в моих тестах было - чем больше данных в таблице, тем дольше они ищутся, т.к. списковый перебор, не? иначе объясни устройтво, плез Vlod:
0
17
4 года назад
0
Оцениваю не время, а количество операций. То есть: если блок кода больше нагружает, то внутри одного потока он выполнится меньшее количество раз.
Тест проводился следующим образом:
  1. Сначала проверил, что и parentKey и childKey принимают все доступные int-ы.
  1. Дальше нужно было наполнить таблицу и посмотреть на разницу в работе. В процессе выяснилось, что значения перестали сохраняться. Экспериментально были вычислен порог для parentKey. Далее проверил, что childKey ведут себя так же и каждый родительский ключ может иметь не более 18747 дочерних.
  1. Когда мы убедились, что hashtable наполняется корректно, можно начать нагрузочное тестирование. Максимальное кол-во элементов 74985 (все доступные parentKey и три полных childKey) и варьировалось в зависимости от цели конкретного теста.
  1. Нагрузочное тестирование.
4.1 Запоминаем количество успешных обращений к пустой hashtable внутри одного потока.
4.2.1 Заполняем все доступные parentKey.
4.2.2 Считаем количество обращений к первому, к последнему, к выбранным мной случайно. Получаем идентичное число операций с пустой hashtable.
  • 4.3. Проверяем, нет ли встроенного кеширования. Обращаемся к случайному parentKey. Запускаем несколько раз, результат не меняется. (Либо обход списка инкапсулирован в виртуальной машине, либо это не список)
  1. Идентично с childKey.

Таким образом, мы видим внешнее поведение, как оно внутри, узреть не удастся
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}}}}
Показан только небольшой набор комментариев вокруг указанного. Перейти к актуальным.
Чтобы оставить комментарий, пожалуйста, войдите на сайт.