Это моя собственная цитата. Но это основано на общей схеме, с которой я столкнулся в своем личном опыте. Кроме того, такие термины, как «родитель» и «ребенок» - это те слова, которые я бы в значительной степени отбросил, говоря о сетках. Вы только что получили большой 2-мерный или N-мерный материал для хранения таблиц / матриц. На самом деле не существует никакой иерархии - эти структуры данных более сопоставимы с массивами, чем с деревьями.
"Грубо" и "Хорошо"
На "грубой" и «хорошо», я имел в виду, что «грубые» поисковые запросы, как правило, дешевле, но дают больше ложных срабатываний. Более грубая сетка будет с более низким разрешением сетки (меньше, больше ячеек). Грубый поиск может включать обход / поиск меньшего и большего количества ячеек сетки. Например, скажем, мы хотим видеть, пересекается ли элемент с точкой / точкой в гигантской ячейке c (представьте себе только сетку 1x1, хранящую все в симуляции). Если точка пересекает ячейку, мы можем получить множество элементов, возвращаемых в эту ячейку, но, возможно, только один или ни один из них фактически не пересекает точку.
Таким образом, «грубый» запрос является широким и простым, но не очень точно сужает список кандидатов (или «подозреваемых»). Он может возвращать слишком много результатов и все же оставить большую обработку, необходимую для сужения того, что фактически пересекает параметр поиска *.
Это похоже на те детективные шоу, когда они ищут в базе данных возможный убийца, добавление «белого мужчины», возможно, не потребует большой обработки, чтобы перечислить результаты, но может дать слишком много результатов, чтобы должным образом сузить подозреваемых. «Хорошо» будет противоположным и может потребовать дополнительной обработки базы данных, но сузить результат до одного подозреваемого. Это грубая и ошибочная аналогия, но я надеюсь, что она поможет.
Часто ключ к широкой оптимизации пространственных индексов, прежде чем мы перейдем к таким вещам, как оптимизация памяти, независимо от того, говорим ли мы о пространственных хешах или квадродеревах, - это найти хороший баланс между "грубым" и "хорошим". Слишком «хорошо», и мы могли бы потратить слишком много времени на обход структуры данных (поиск множества маленьких ячеек в единой сетке или слишком много времени на обход дерева для адаптивных сеток, таких как квадри). Слишком «грубый» и пространственный индекс могут дать слишком много результатов, чтобы значительно сократить время, необходимое для дальнейшей обработки. Для пространственных хэшей (структура данных мне лично не очень нравится, но они очень популярны в gamedev), часто приходится много думать, экспериментировать и измерять, чтобы определить оптимальный размер ячейки для использования.
При использовании равномерных сеток NxM, насколько они "грубые" или "точные" (большие или маленькие ячейки и высокое или низкое разрешение сетки), не только влияет на время поиска запроса, но также может влиять на время вставки и удаления, если элементы больше точка. Если сетка слишком тонкая, один большой или средний элемент может быть вставлен во множество крошечных ячеек и удален из множества крошечных ячеек, используя много дополнительной памяти и обработки. Если он слишком грубый, элемент может быть вставлен и удален только в одну большую ячейку или из нее, но за счет способности структуры данных сузить число кандидатов, возвращаемых из поискового запроса, до минимума. Не обращая внимания, слишком «мелкий / гранулярный» процесс может стать очень узким на практике, и разработчик может найти свою сеточную структуру, используя гигабайты ОЗУ для скромного размера ввода. С вариантами дерева, такими как quadtree, подобное может произойти, если максимально допустимая глубина дерева слишком велика, что приводит к взрывному использованию памяти и обработке, когда листовые узлы quadtree хранят малейшие размеры ячеек (мы можем даже начать работать с плавающей точкой прецизионные ошибки, которые ухудшают производительность, если ячейкам разрешено делиться на слишком маленький размер в дереве).
Суть ускорения производительности с помощью пространственных индексов часто заключается в подобном акте балансировки. Например, мы обычно не хотим применять усеченный отбор к отдельным полигонам, отображаемым в компьютерной графике, потому что это, как правило, не только избыточно по сравнению с тем, что аппаратное обеспечение уже делает на этапе отсечения, но также слишком «мелко / детально» и требует слишком много большая обработка сама по себе по сравнению со временем, требуемым для запроса одного или нескольких полигонов. Но мы могли бы net значительно улучшить производительность, сделав что-то более "грубое", например, применить отбраковку усеченного конуса для всего существа или космического корабля (всей модели / меня sh), что позволит нам избежать запроса на рендеринг сразу многих полигонов с одного теста. Поэтому я часто использую термины «грубый» и «точный / гранулированный» часто в подобных дискуссиях (пока не найду лучшую терминологию, понятную большему количеству людей).
Унифицированная или адаптивная сетка
Вы можете представить себе квадродерево как «адаптивную» сетку с иерархическими размерами адаптивных ячеек сетки, работающими от «грубого» к «точному», когда мы переходим от root к листу единая интеллектуальная и адаптивная структура данных), в отличие от простой «однородной» сетки NxM.
Адаптивный характер древовидных структур очень интеллектуален и может обрабатывать широкий спектр вариантов использования (хотя обычно для этого требуются некоторые изменение максимальной глубины дерева и / или минимально допустимого размера ячейки и, возможно, сколько максимальных элементов хранится в ячейке / узле до его разделения). Однако оптимизировать структуры данных дерева может быть сложнее, поскольку иерархическая природа не предоставляет сам по себе так легко к виду непрерывного расположения памяти, что наше оборудование и память привет эрархия так хорошо подходит для прохождения. Поэтому очень часто я нахожу, что структуры данных, в которых не используются деревья, проще оптимизировать в том же смысле, в котором оптимизация таблицы ha sh может быть проще, чем оптимизация красно-черного дерева, особенно когда мы можем многое предвидеть тип данных, который мы будем хранить заранее.
Еще одна причина, по которой я склоняюсь к более простым, более непрерывным структурам данных во многих контекстах, заключается в том, что требования к производительности моделирования в реальном времени часто не только быстрая частота кадров, но согласованная и предсказуемая частота кадров. Последовательность важна, потому что даже если видеоигра имеет очень высокую частоту кадров для большей части игры, но некоторая часть игры приводит к значительному падению частоты кадров даже в течение короткого периода времени, игрок может d ie и играть в результате этого. В моем случае часто было очень важно избегать этих типов сценариев ios и иметь структуры данных, в которых в основном отсутствовал патологический сценарий производительности наихудшего случая ios. В целом, мне проще предсказать характеристики производительности множества более простых структур данных, которые не включают адаптивную иерархию и являются своего рода «тупыми». Очень часто я обнаруживаю, что согласованность и предсказуемость частоты кадров примерно связаны с тем, насколько легко я могу предсказать общее использование памяти структурой данных и насколько она стабильна. Если использование памяти крайне непредсказуемо и sporadi c, я часто (не всегда, но часто) нахожу, что частота кадров также будет sporadi c.
Так что я часто нахожу лучшие результаты, используя лично для сеток, но если сложно определить один оптимальный размер ячейки, который будет использоваться для сетки в конкретном контексте моделирования, я просто использую их несколько экземпляров: один экземпляр с большими размерами ячеек для «грубого» поиска (скажем, 10x10), один с меньшими для «более точных» поисков (скажем, 100x100), и, возможно, даже с меньшими ячейками для «лучших» поисков (скажем, 1000x1000). Если в результате грубого поиска не будет найдено результатов, более точные поиски не будут выполнены. Таким образом, я получаю некоторый баланс преимуществ четырех веток и сеток.
То, что я делал, когда использовал эти типы представлений в прошлом, - это не хранение одного элемента во всех трех экземплярах сетки. Это утроило бы использование памяти элементом / узлом элемента в этих структурах. Вместо этого я вставил индексы занятых ячеек более тонких сеток в более грубые сетки, поскольку обычно занимаемых ячеек гораздо меньше, чем общего количества элементов в моделировании. Только самая точная сетка с самым высоким разрешением с наименьшими размерами ячеек будет хранить элемент. Ячейки в самой мелкой сетке аналогичны листовым узлам квадродерева.
"Свободная двойная сетка", как я ее называю в одном из ответов на этот вопрос, является расширением этого мульти Идея Разница заключается в том, что более мелкая сетка фактически свободна и имеет размеры ячеек, которые увеличиваются и уменьшаются в зависимости от вставленных в нее элементов, всегда гарантируя, что один элемент, независимо от его размера или размера, должен быть вставлен только в одну ячейку в сетке. , Более грубая сетка хранит занятые ячейки более мелкой сетки, что приводит к двум запросам с постоянным временем (один в более грубой жесткой сетке, другой в более тонкую свободную сетку), чтобы вернуть список элементов потенциальных кандидатов, соответствующих параметру поиска. Он также имеет наиболее стабильное и предсказуемое использование памяти (не обязательно минимальное использование памяти, потому что для тонких / свободных ячеек требуется сохранение выровненного по оси ограничивающего прямоугольника, который расширяется / сжимается, что добавляет в ячейку еще примерно 16 байтов) и соответствующий стабильный кадр скорость, потому что один элемент всегда вставляется в одну ячейку и не требует никакой дополнительной памяти, необходимой для его хранения, кроме собственных данных элемента, за исключением случаев, когда его вставка приводит к расширению свободной ячейки до точки, в которую она должна быть вставлена дополнительные ячейки в более грубой сетке (что должно быть довольно редким сценарием).
несколько сеток для других целей
Я немного озадачен потому что я бы интуитивно использовал один, или, возможно, 3 std :: map с соответствующим оператором (), чтобы уменьшить объем памяти, но я не уверен, что это будет так быстро, так как запрос AABB будет означать сложение нескольких обращений, которые O (log n).
Я думаю, что это интуиция многих у нас есть, а также, возможно, и подсознательное желание просто опираться на одно решение для всего, потому что программирование может стать довольно утомительным и повторяющимся, и было бы идеально просто реализовать что-то один раз и повторно использовать его для всего: «один размер подходит» все "футболка. Но рубашка одного размера подходит для всех наших очень широких и мускулистых тел программистов *. Поэтому иногда полезно использовать аналогию с маленьким, средним и большим размерами.
- Это очень плохая попытка юмора с моей стороны, чтобы сделать мои скучные тексты менее скучно читать.
Например, если вы используете std::map для чего-то вроде пространственного ха sh, тогда может быть много мыслей и возни с попытками найти оптимальный размер ячейки. В видеоигре можно пойти на компромисс с чем-то вроде создания размера ячейки относительно размера вашего обычного человека в игре (возможно, немного меньше или больше), так как многие модели / спрайты в игре могут быть предназначены для человека использовать. Но это может стать очень рискованным и очень неоптимальным для маленьких вещей и очень неоптимальным для гигантских c вещей. В этом случае мы могли бы преуспеть в том, чтобы сопротивляться нашей интуиции и желаниям просто использовать одно решение и использовать несколько (это мог бы быть все тот же код, но только несколько экземпляров одного и того же экземпляра класса для структуры данных, созданной с различными параметрами).
Что касается затрат на поиск по нескольким структурам данных вместо одной, то это лучше всего измерить, и стоит помнить, что в результате размеры ввода каждого контейнера будут меньше, что снижает стоимость каждого поиска и очень возможно улучшить местность ссылки. Это может превышать преимущества в иерархической структуре, которая требует логарифмического c времени поиска, например std::map (или нет, лучше всего просто измерить и сравнить), но я склонен использовать больше структур данных, которые делают это в постоянном времени (сетки) или ха sh таблицы). В моих случаях я обнаружил, что преимущества намного превышают дополнительные затраты, связанные с требованием множественного поиска для выполнения одного запроса, особенно когда размеры элементов радикально меняются, или я хочу что-то базовое c, напоминающее иерархию с двумя или более сетками NxM, которые варьируются от "грубого" до "точного".
Оптимизация на основе строк
Что касается "оптимизаций на основе строк", это очень специфично c для равномерного фиксированного размерные сетки а не деревья. Это относится к использованию отдельного списка / контейнера переменного размера на строку вместо одного для всей сетки. Помимо потенциального сокращения использования памяти для пустых строк, которые просто превращаются в нули, не требуя выделенного блока памяти, это может сэкономить на большом количестве обработки и улучшить шаблоны доступа к памяти.
Если мы храним один список для всей сетки затем мы должны постоянно вставлять и удалять из этого общего списка, когда элементы перемещаются, частицы рождаются и т. д. c. Это может привести к увеличению количества выделений / освобождений в куче и сокращению контейнера, а также к увеличению среднего шага памяти для перехода от одного элемента в этом списке к следующему, что, как правило, приводит к большему количеству пропусков кэша в результате загрузки ненужных данных. в строку кэша. Также в наши дни у нас так много ядер, что наличие единого общего контейнера для всей сетки может снизить возможность параллельной обработки сетки (например: поиск одной строки при одновременной вставке в другую). Это также может привести к большему использованию памяти net для структуры, так как, если мы используем непрерывную последовательность, такую как std::vector или ArrayList, они часто могут хранить в памяти вдвое больше элементов, необходимых для сокращения времени вставки в амортизированное постоянное время, сводя к минимуму необходимость перераспределения и копирования прежних элементов в линейном времени, сохраняя избыточную емкость.
Связывая отдельный контейнер среднего размера для строки сетки или столбца вместо гиганта c один для всей сетки, мы можем уменьшить эти затраты в некоторых случаях *.
- Это тип вещей, которые вы определенно измеряете до и после, хотя, чтобы убедиться, что это действительно улучшает общий кадр скорости и, вероятно, попытка в ответ на первую попытку сохранить один список для всей сетки, обнаружив множество необязательных пропусков кэша в профилировщике.
Это может вызвать вопрос о том, почему мы не используйте отдельный контейнер для маленьких списков для каждой ячейки в сетка. Это балансирование. Если мы храним такое количество контейнеров (например, миллион экземпляров std::vector для сетки 1000x1000, в которой, возможно, хранится очень мало элементов или нет элементов), это позволило бы обеспечить максимальный параллелизм и минимизировать шаг, чтобы добраться от одного элемента в ячейке к следующему один в ячейке, но это может быть довольно взрывоопасно при использовании памяти и вносить много дополнительной обработки и накладных расходов кучи.
Особенно в моем случае мои лучшие сетки могут хранить миллион ячеек или больше, но я только требуется 4 байта на ячейку. Последовательность переменного размера для каждой ячейки обычно бывала, по крайней мере, примерно на 24 байта или более (обычно намного больше) на ячейку в 64-разрядных архитектурах для хранения данных контейнера (обычно указатель и пара дополнительных целых чисел или три указателя). поверх блока памяти, выделенного из кучи), но помимо этого, каждый отдельный элемент, вставленный в пустую ячейку, может потребовать выделения кучи и принудительного пропуска кэша и сбоя страницы, а также очень часто из-за отсутствия временной локализации. Поэтому я нахожу баланс и предпочтительное место одним контейнером списка на строку, как правило, среди моих наиболее измеренных реализаций.
Я использую то, что я называю «списком массивов с одиночной связью», чтобы хранить элементы в строке сетки и разрешать вставки и удаления в постоянное время, в то же время допуская некоторую степень пространственной локальности с множеством смежных элементов. Это можно описать так:
struct GridRow
{
struct Node
{
// Element data
...
// Stores the index into the 'nodes' array of the next element
// in the cell or the next removed element. -1 indicates end of
// list.
int next = -1;
};
// Stores all the nodes in the row.
std::vector<Node> nodes;
// Stores the index of the first removed element or -1
// if there are no removed elements.
int free_element = -1;
};
Это объединяет некоторые преимущества связанного списка с использованием бесплатного распределителя списков, но без необходимости управлять отдельными реализациями распределителя и структуры данных, которые я считаю слишком общими c и громоздкий для моих целей. Кроме того, делая это таким образом, мы можем вдвое уменьшить размер указателя до 32-битного индекса массива на 64-битных архитектурах, что я считаю большим измерением выигрыша в моих случаях использования, когда требования к выравниванию данных элемента объединены с 32-битным индексом не требуются дополнительные 32-битные отступы для class/struct, что часто случается со мной, так как я часто использую 32-битные или меньшие целые числа и 32-битную одинарную точность с плавающей точкой или 16-разрядные полуплавающие числа.
Неортодокс?
По этому вопросу:
Является ли этот тип поиска по сетке распространенным?
Я не уверен! Я склонен немного бороться с терминологией, и мне придется просить у людей прощения и терпения в общении. Я начал программировать с раннего детства в 1980-х, до того, как inte rnet получил широкое распространение, поэтому я стал полагаться на то, что изобрел множество своих собственных методик и в результате использовал свою грубую терминологию. Я получил степень в области компьютерных наук примерно полтора десятилетия спустя, когда мне исполнилось 20 лет, и я исправил некоторые терминологии и заблуждения, но у меня было много лет, я просто катал свои собственные решения. Поэтому я часто не уверен, сталкивались ли другие люди с такими же решениями или нет, и есть ли для них формальные имена и термины.
Это затрудняет общение с другими программистами и очень расстраивает их. время от времени мы оба, и мне нужно много терпения, чтобы объяснить, что я имею в виду. На встречах я привык всегда показывать что-то с очень многообещающими результатами, что делает людей более терпеливыми с моими грубыми и многословными объяснениями того, как они работают. Они, как правило, дают моим идеям гораздо больше шансов, если я начну с показа результатов, но я часто очень расстраиваюсь из-за ортодоксальности и догматизма, которые могут преобладать в этой отрасли, которые иногда могут расставлять приоритеты в понятиях гораздо больше, чем в исполнении и реальных результатах. , Я прагматик в душе, поэтому я не думаю о том, "какая структура данных лучше?" Я думаю с точки зрения того, что мы можем эффективно реализовать лично, учитывая наши сильные и слабые стороны, и что является интуитивным и не интуитивным для нас, и я готов бесконечно идти на компромисс в отношении чистоты концепций в пользу более простого и менее проблематичного c выполнение. Мне просто нравятся хорошие, надежные решения, которые естественным образом выходят у нас из рук, независимо от того, насколько они ортодоксальны или неортодоксальны, но многие из моих методов могут быть неортодоксальными в результате (или нет, и мне, возможно, еще только предстоит найти людей, которые сделали те же вещи). Я нашел этот сайт полезным в редких случаях для нахождения сверстников, которые говорят: «О, я тоже так делал! Я нашел лучшие результаты, если мы сделаем это [...]», или кто-то указал на что-то вроде «Что то, что вы предлагаете, называется [...]. "
В условиях, критичных к производительности, я, как бы грубо говоря, позволил профилировщику придумать для меня структуру данных. То есть я придумаю какой-нибудь быстрый первый черновик (обычно очень ортодоксальный) и измерим его профилировщиком, и пусть результаты профилировщика дадут мне идеи для второго черновика, пока я не схожу с чем-то простым, производительным и соответствующим образом масштабируемым. для требований (которые могут стать довольно неортодоксальными по пути). Я очень рад отказаться от множества идей, так как считаю, что нам нужно отсеять много плохих идей в процессе исключения, чтобы придумать хорошую, поэтому я склонен перебирать множество реализаций и идей и пришел чтобы стать действительно быстро Prototyper (у меня есть психологическая склонность упорно полюбят решения я потратил много времени на, так прилавок, что я научился тратить абсолютное минимальное время на решении до тех пор, пока не очень, очень перспективный) .
Вы можете увидеть мою точную методологию в работе в самых ответах на этот вопрос, где я итеративно сходился через много профилирования и измерения в течение нескольких дней и прототипирования от довольно ортодоксального квадродерева до это неортодоксальное решение «неплотная двойная сетка», которое обрабатывало наибольшее количество агентов с наиболее стабильной частотой кадров и было, во всяком случае, для меня намного быстрее и проще в реализации, чем все структуры до него. Мне пришлось go проанализировать множество ортодоксальных решений и измерить их, чтобы сформировать окончательную идею для необычного свободного варианта. Я всегда начинаю и одобряю ортодоксальные решения и начинаю внутри коробки, потому что они хорошо документированы и понятны, и просто очень осторожно и робко выхожу наружу, но я часто оказываюсь немного нестандартной, когда требования круче достаточно. Мне не чужды самые крутые требования, поскольку в моей отрасли и в качестве довольно низкоуровневого типа, работающего на движках, способность обрабатывать больше данных с хорошей частотой кадров часто приводит не только к большей интерактивности для пользователя, но и позволяет художникам создавать более детальный контент с более высоким визуальным качеством, чем когда-либо прежде. Мы всегда стремимся к более высокому и более высокому визуальному качеству при хороших частотах кадров, и это часто сводится к сочетанию как производительности, так и возможных грубых приближений, когда это возможно. Это неизбежно приводит к некоторой степени неортодоксальности с множеством собственных решений, уникальных для конкретного движка, и каждый движок имеет свои уникальные сильные и слабые стороны, когда вы сравниваете что-то вроде CryEngine с Unreal Engine с Frostbite с Unity.
Например, у меня есть эта структура данных, которую я использовал с детства, и я не знаю ее названия. Это простая концепция, и это просто иерархический набор битов, который позволяет найти пересечения потенциально миллионов элементов за несколько итераций простой работы, а также обойти миллионы элементов, занимающих множество, всего за несколько итераций (меньше, чем требования линейного времени для прохождения всего в наборе только через саму структуру данных, которая возвращает диапазоны занятых элементов / битов набора вместо отдельных элементов / индексов битов). Но я понятия не имею, как его зовут, потому что это просто то, что я катал, и я никогда не сталкивался с кем-то, кто говорил об этом в информатике. Я склонен называть это «иерархическим набором битов». Первоначально я назвал это "редким битовым деревом", но это кажется немного многословным. Это совсем не очень умная концепция, и я не удивлюсь и не буду разочарован (на самом деле весьма счастлив), когда найду кого-то еще, кто откроет то же самое решение до меня, но я не найду людей, которые используют или говорят о нем никогда. Он просто расширяет преимущества обычного плоского набора битов в быстром нахождении установленных пересечений с помощью побитового ИЛИ и быстро перемещается по всем установленным битам, используя FFZ / FFS, но сокращая требования к линейному времени обоих до логарифмических c (с помощью логарифмической базы будучи числом намного большим, чем 2). 
В любом случае, я не удивлюсь, если некоторые из этих решений очень неортодоксальны, но также не удивлюсь, если они будут достаточно ортодоксальными, а я только что потерпел неудачу найти правильное название и терминологию для этих методов. Для меня привлекательность таких сайтов - это одинокий поиск кого-то, кто использовал подобные методы, и пытался найти подходящие имена и термины, чтобы они часто заканчивались разочарованием. Я также надеюсь улучшить свою способность объяснять их, хотя я всегда был таким плохим и многословным здесь. Я считаю, что использование картинок мне очень помогает, потому что я нахожу, что человеческий язык невероятно пронизан двусмысленностью. Мне также нравится преднамеренно неточный образный язык, который охватывает и отмечает неоднозначности, такие как метафора и аналогия, и юмористическая гипербола, но я не обнаружил, что программисты склонны так ценить из-за отсутствия точности. Но я никогда не считал, что точность настолько важна, пока мы можем передать мясистые вещи и то, что «круто» в идее, в то время как они могут сделать свои собственные интерпретации всего остального. Извиняюсь за все объяснение, но надеюсь, что это прояснит некоторые аспекты моей грубой терминологии и общей методологии, которую я использую для достижения этих методов. Английский sh также не является моим родным языком, так что он добавляет еще один слой свертки, где мне приходится как-то переводить свои мысли в английские sh слова и много с этим бороться.