Что такое грубый и точный поиск по сетке?

Это моя собственная цитата. Но это основано на общем образце, с которым я столкнулся на собственном опыте. Кроме того, я бы отказался от таких терминов, как «родительский» и «дочерний», когда говорил о сетках. У вас только что есть большая 2-мерная или N-мерная таблица / матрица, хранящая материал. На самом деле здесь нет никакой иерархии - эти структуры данных более сопоставимы с массивами, чем с деревьями.

"Грубый" и "Тонкий"

Под «грубым» и «точным» я имел в виду, что «грубые» поисковые запросы, как правило, дешевле, но дают больше ложных срабатываний. Более грубая сетка будет иметь меньшее разрешение сетки (меньшее количество ячеек большего размера). Грубый поиск может включать обход / поиск в меньшем и большем количестве ячеек сетки. Например, скажем, мы хотим увидеть, пересекает ли элемент точку / точку в гигантской ячейке (представьте себе сетку 1x1, хранящую все в симуляции). Если точка пересекает ячейку, мы можем получить много элементов, возвращаемых в этой ячейке, но, возможно, только один или ни один из них фактически не пересекает точку.

Таким образом, «грубый» запрос является широким и простым, но не очень точным для сужения списка кандидатов (или «подозреваемых»). Он может вернуть слишком много результатов и по-прежнему оставить много обработки, необходимой для сужения того, что на самом деле пересекает параметр поиска *.

Это как в тех детективных шоу, когда они ищут в базе данных возможного убийцу, ввод «белого мужчины» может не потребовать большой обработки для перечисления результатов, но может дать слишком много результатов, чтобы должным образом сузить круг подозреваемых. «Хорошо» будет противоположным и может потребовать дополнительной обработки базы данных, но сузить результат до одного подозреваемого. Это грубая и ошибочная аналогия, но я надеюсь, что она поможет.

Часто ключ к широкой оптимизации пространственных индексов до того, как мы перейдем к таким вещам, как оптимизация памяти, говорим ли мы о пространственных хэшах или квадродеревьях, - это найти хороший баланс между «грубым» и «точным». Слишком «хорошо», и мы можем потратить слишком много времени на обход структуры данных (поиск множества маленьких ячеек в однородной сетке или потратить слишком много времени на обход дерева для адаптивных сеток, таких как квадродеревья). Слишком "грубый" пространственный индекс может дать слишком много результатов, чтобы значительно сократить время, необходимое для дальнейшей обработки. Что касается пространственных хешей (структура данных, которая мне лично не очень нравится, но она очень популярна в геймдеве), часто требуется много размышлений, экспериментов и измерений для определения оптимального размера ячейки для использования.

В случае однородных сеток NxM их "грубость" или "тонкость" (большие или маленькие ячейки и высокое или низкое разрешение сетки) не только влияет на время поиска по запросу, но также может влиять на время вставки и удаления, если элементы больше точка. Если сетка слишком мелкая, один большой или средний элемент, возможно, придется вставить во множество крошечных ячеек и удалить из многих крошечных ячеек, используя много дополнительной памяти и обработки. Если он слишком грубый, элемент может быть вставлен и удален только в / из одной большой ячейки, но за счет способности структуры данных сузить количество кандидатов, возвращаемых поисковым запросом, до минимума. Без должного внимания, слишком «мелкий / гранулированный» может стать очень узким местом на практике, и разработчик может найти свою сеточную структуру, использующую гигабайты ОЗУ для скромного размера ввода. С вариантами дерева, такими как квадродеревья, аналогичная вещь может произойти, если максимально допустимая глубина дерева слишком высока, вызывая взрывное использование памяти и обработку, когда конечные узлы квадродерева хранят мельчайшие размеры ячеек (мы даже можем начать работать с числами с плавающей запятой. ошибки точности, которые снижают производительность, если разрешено подразделение ячеек до слишком маленького размера в дереве).

Суть повышения производительности с помощью пространственных показателей часто заключается в уравновешивании. Например, мы обычно не хотим применять усеченную отсечку к отдельным полигонам, визуализируемым в компьютерной графике, потому что это, как правило, не только избыточно по сравнению с тем, что оборудование уже делает на этапе отсечения, но также слишком "мелко / гранулярно" и требует слишком большая обработка сама по себе по сравнению со временем, необходимым для простого запроса на рендеринг одного или нескольких полигонов. Но мы можем добиться огромных улучшений производительности с помощью чего-то более «грубого», например, применения отсечения усеченного конуса ко всему существу или космическому кораблю (всей модели / сетке), что позволит нам избежать запроса на рендеринг множества полигонов одновременно с помощью одного теста. Поэтому я часто использую термины «грубый» и «мелкий / гранулярный» в такого рода обсуждениях (пока я не найду лучшую терминологию, которую сможет легко понять большее количество людей).

Равномерная и адаптивная сетка

Вы можете думать о дереве квадрантов как о «адаптивной» сетке с адаптивными размерами ячеек сетки, упорядоченными иерархически (работая от «грубого» до «точного», когда мы углубляемся от корня к листу в единой интеллектуальной и адаптивной структуре данных), в отличие от простая «равномерная» сетка NxM.

Адаптивная природа древовидных структур очень умна и может обрабатывать широкий спектр вариантов использования (хотя, как правило, требуется некоторое изменение максимальной глубины дерева и / или минимального разрешенного размера ячейки и, возможно, того, сколько максимальных элементов хранится в ячейке / узел до того, как он разделится). Однако может быть сложнее оптимизировать древовидные структуры данных, потому что иерархическая природа не так легко поддается виду непрерывной компоновки памяти, для прохождения которой так хорошо подходят наше аппаратное обеспечение и иерархия памяти. Поэтому очень часто я нахожу, что структуры данных, которые не связаны с деревьями, легче оптимизировать в том же смысле, что оптимизация хеш-таблицы может быть проще, чем оптимизация красно-черного дерева, особенно когда мы можем многое предвидеть в отношении типа данных. мы собираемся хранить заранее.

Еще одна причина, по которой я предпочитаю более простые и непрерывные структуры данных во многих контекстах, заключается в том, что требования к производительности моделирования в реальном времени часто требуют не только высокой частоты кадров, но и согласованной и предсказуемой частоты кадров. Согласованность важна, потому что даже если видеоигра имеет очень высокую частоту кадров для большей части игры, но какая-то часть игры приводит к значительному падению частоты кадров даже на короткий период времени, игрок может умереть и игра закончится как результат этого. В моем случае часто было очень важно избегать таких сценариев и иметь структуры данных, в значительной степени отсутствующие патологические сценарии наихудшей производительности. В общем, мне легче предсказать характеристики производительности множества более простых структур данных, которые не используют адаптивную иерархию и являются отчасти «глупыми». Очень часто я обнаруживаю, что согласованность и предсказуемость частоты кадров примерно связаны с тем, насколько легко я могу предсказать общее использование памяти структурой данных и насколько это стабильно. Если использование памяти совершенно непредсказуемо и спорадически, я часто (не всегда, но часто) обнаруживаю, что частота кадров также будет спорадической.

Поэтому я часто нахожу лучшие результаты, используя сетки лично, но если сложно определить единственный оптимальный размер ячейки для использования в сетке в конкретном контексте моделирования, я просто использую несколько их экземпляров: один экземпляр с более крупными размерами ячеек для «грубого» поисковые запросы (скажем, 10x10), один с меньшими ячейками для «более точного» поиска (скажем, 100x100) и, возможно, даже один с еще меньшими ячейками для «наилучшего» поиска (скажем, 1000x1000). Если грубый поиск не дал результатов, я не перехожу к более тонкому поиску. Таким образом я получаю некоторый баланс преимуществ квадродеревьев и сеток.

Когда я использовал эти типы представлений в прошлом, я не сохранял ни одного элемента во всех трех экземплярах сетки. Это утроило бы использование памяти для элемента / узла в этих структурах. Вместо этого я вставил индексы занятых ячеек более мелких сеток в более грубые сетки, так как обычно гораздо меньше занятых ячеек, чем общее количество элементов в моделировании. Только самая тонкая сетка с самым высоким разрешением и наименьшими размерами ячеек может хранить элемент. Ячейки в самой тонкой сетке аналогичны листовым узлам квадродерева.

«Слабая двойная сетка», как я называю ее в одном из ответов на этот вопрос, является расширением идеи создания нескольких сеток. Разница в том, что более мелкая сетка на самом деле рыхлая и имеет размеры ячеек, которые расширяются и сжимаются в зависимости от вставленных в нее элементов, всегда гарантируя, что один элемент, независимо от того, насколько он большой или маленький, нужно вставить только в одну ячейку в сетке. . Более грубая сетка хранит занятые ячейки более мелкой сетки, что приводит к двум запросам с постоянным временем (один в более грубой узкой сетке, другой в более мелкой свободной сетке), чтобы вернуть список элементов потенциальных кандидатов, соответствующих параметру поиска. Он также имеет наиболее стабильное и предсказуемое использование памяти (не обязательно минимальное использование памяти, потому что мелкие / свободные ячейки требуют хранения выровненного по оси ограничивающего прямоугольника, который расширяется / сжимается, что добавляет еще 16 байтов или около того к ячейке) и соответствующий стабильный кадр скорости, потому что один элемент всегда вставляется в одну ячейку и не занимает никакой дополнительной памяти, необходимой для его хранения, кроме собственных данных элемента, за исключением случаев, когда его вставка заставляет свободную ячейку расширяться до точки, в которую она должна быть вставлена. дополнительные ячейки в более крупной сетке (что должно быть довольно редким случаем).

Несколько сеток для других целей

Я немного озадачен, потому что я бы интуитивно использовал один или, может быть, 3 std :: map с правильным оператором (), чтобы уменьшить его объем памяти, но я не уверен, что это будет так быстро, поскольку запрос AABB будет означать объединение нескольких доступов, которые являются O (log n).

Я думаю, что у многих из нас есть интуиция, а также, вероятно, подсознательное желание просто полагаться на одно решение для всего, потому что программирование может стать довольно утомительным и повторяющимся, и было бы идеально просто реализовать что-то один раз и повторно использовать это для всего: a " универсальная футболка. Но универсальная рубашка может плохо подойти к нашему очень широкому и мускулистому телу программиста *. Поэтому иногда полезно использовать аналогию с маленьким, средним и большим размером.

• С моей стороны, возможно, это плохая попытка юмора сделать мои многословные тексты менее скучными для чтения.

Например, если вы используете std::map для чего-то вроде пространственного хеша, тогда можно много подумать и возиться, пытаясь найти оптимальный размер ячейки. В видеоигре можно пойти на компромисс с чем-то вроде того, чтобы размер ячейки соответствовал размеру вашего среднего человека в игре (возможно, немного меньше или больше), поскольку многие модели / спрайты в игре могут быть разработаны для людей. использовать. Но это может оказаться очень неудобным и неоптимальным для маленьких вещей и очень неоптимальным для гигантских вещей. В этом случае мы могли бы преуспеть, сопротивляясь нашей интуиции и желанию просто использовать одно решение и использовать несколько (это может быть один и тот же код, но только несколько экземпляров одного и того же экземпляра класса для структуры данных, построенной с различными параметрами).

Что касается накладных расходов на поиск в нескольких структурах данных вместо одной, это лучше всего измерить, и стоит помнить, что входные размеры каждого контейнера в результате будут меньше, что снизит стоимость каждого поиска и, возможно, улучшит локальность ссылки. . Это может превзойти преимущества иерархической структуры, которая требует логарифмического времени поиска, такого как std::map (или нет, лучше всего просто измерить и сравнить), но я предпочитаю использовать больше структур данных, которые делают это в постоянном времени (сетки или хеш-таблицы). В своих случаях я нахожу преимущества, намного превышающие дополнительные затраты, связанные с необходимостью выполнения нескольких поисков для выполнения одного запроса, особенно когда размеры элементов радикально различаются или мне нужна какая-то базовая вещь, напоминающая иерархию с 2 или более сетками NxM, которые варьируются от «грубых» «на« штраф ».

Оптимизация на основе строк

Что касается «оптимизации на основе строк», это очень характерно для однородных сеток фиксированного размера, а не для деревьев. Это относится к использованию отдельного списка / контейнера переменного размера для каждой строки вместо одного для всей сетки. Помимо потенциального сокращения использования памяти для пустых строк, которые просто превращаются в нули, не требуя выделенного блока памяти, это может сэкономить много времени на обработку и улучшить шаблоны доступа к памяти.

Если мы храним один список для всей сетки, тогда нам придется постоянно вставлять и удалять из этого общего списка по мере перемещения элементов, рождения частиц и т. Д. Это может привести к увеличению выделения / освобождению кучи и уменьшению контейнера, но также увеличивает средний шаг памяти для перехода от одного элемента в этом списке к следующему, что, как правило, приводит к большему количеству промахов в кэше в результате загрузки большего количества нерелевантных данных в строку кеша. Кроме того, в наши дни у нас так много ядер, поэтому наличие одного общего контейнера для всей сетки может снизить возможность параллельной обработки сетки (например, поиск одной строки при одновременной вставке в другую). Это также может привести к большему использованию чистой памяти для структуры, поскольку, если мы используем непрерывную последовательность, такую ​​как std::vector или ArrayList, они часто могут хранить объем памяти в два раза больше, чем элементы, необходимые для сокращения времени вставки до амортизированного постоянного времени на сведение к минимуму необходимости перераспределять и копировать прежние элементы в линейном времени за счет сохранения избыточной емкости.

Связывая отдельный контейнер среднего размера для каждой строки сетки или каждого столбца вместо гигантского контейнера для всей сетки, мы можем снизить эти затраты в некоторых случаях *.

• Это тот тип вещей, который вы определенно измеряете до и после, хотя, чтобы убедиться, что он действительно улучшает общую частоту кадров, и, вероятно, в ответ на первую попытку сохранить единый список для всей сетки, обнаруживая множество необязательных промахов кеша в профилировщике .

Это может вызвать вопрос, почему мы не используем отдельный контейнер крошечного списка для каждой отдельной ячейки в сетке. Это балансирующий акт. Если мы сохраним такое количество контейнеров (например, миллион экземпляров 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;
};

Это объединяет некоторые преимущества связанного списка с использованием бесплатного распределителя списков, но без необходимости управлять отдельными реализациями распределителя и структур данных, которые я считаю слишком общими и громоздкими для моих целей. Кроме того, такой способ позволяет нам вдвое уменьшить размер указателя до 32-битного индекса массива на 64-битных архитектурах, что я считаю большим измеренным выигрышем в моих случаях использования, когда требования к выравниванию данных элементов объединены. с 32-битным индексом не требует дополнительных 32-битных отступов для class/struct, что часто случается со мной, поскольку я часто использую 32-битные или меньшие целые числа и 32-битные числа с плавающей запятой одинарной точности или 16- битовые полупоплавки.

Неортодоксальный?

По этому вопросу:

Распространен ли этот тип поиска по сетке?

Я не уверена! Я склонен немного бороться с терминологией, и мне придется попросить у людей прощения и терпения в общении. Я начал программировать с раннего детства в 1980-х, еще до того, как Интернет получил широкое распространение, поэтому я начал полагаться на изобретение множества собственных методов и, как следствие, на использование моей собственной грубой терминологии. Я получил степень в области компьютерных наук примерно через полтора десятилетия спустя, когда мне исполнилось 20 лет, и я исправил некоторые из своих терминов и заблуждений, но у меня было много лет, просто катая свои собственные решения. Поэтому я часто не уверен, сталкивались ли другие люди с некоторыми из тех же решений или нет, и есть ли для них официальные имена и термины или нет.

Это делает общение с другими программистами трудным и временами очень разочаровывающим для нас обоих, и мне нужно проявить много терпения, чтобы объяснить, что я имею в виду. Я сделал привычкой на собраниях всегда начинать с показа чего-то с многообещающими результатами, которые имеют тенденцию делать людей более терпеливыми с моими грубыми и многословными объяснениями того, как они работают. Они, как правило, дают моим идеям гораздо больше шансов, если я начну с демонстрации результатов, но я часто очень разочарован ортодоксальностью и догматизмом, которые могут преобладать в этой отрасли, которые иногда могут ставить концепции гораздо больше, чем выполнение и фактические результаты. . В душе я прагматик, поэтому не думаю о том, «какая структура данных лучшая»? Я думаю о том, что мы можем эффективно реализовать лично, учитывая наши сильные и слабые стороны, а также о том, что нам интуитивно и противоречит интуиции, и я готов бесконечно идти на компромисс в отношении чистоты концепций в пользу более простого и менее проблематичного выполнения. Мне просто нравятся хорошие, надежные решения, которые естественным образом скатываются с кончиков наших пальцев, независимо от того, насколько они ортодоксальны или неортодоксальны, но в результате многие из моих методов могут оказаться неортодоксальными (или нет, и я, возможно, еще не нашел людей, которые сделали те же вещи). Я нахожу этот сайт полезным в редких случаях для поиска коллег, которые говорят: «О, я тоже это сделал! Я нашел лучшие результаты, если мы сделаем это [...]» или кто-то указывает: «Что Вы предлагаете называется [...] ".

Грубо говоря, в ситуациях, когда производительность критична, я позволяю профилировщику придумывать структуру данных за меня. Другими словами, я придумываю какой-нибудь быстрый первый черновик (обычно очень ортодоксальный), измеряю его с помощью профилировщика и позволяю результатам профилировщика дать мне идеи для второго черновика, пока я не схожусь к чему-то одновременно простому, производительному и соответствующим образом масштабируемому. для требований (которые в процессе могут стать довольно необычными). Я очень счастлив отказаться от множества идей, так как считаю, что нам нужно отсеять множество плохих идей в процессе исключения, чтобы придумать хорошую, поэтому я стараюсь циклически перебирать множество реализаций и идей и пришел стать действительно быстрым прототипом (у меня есть психологическая склонность упорно влюбляться в решения, на которые я потратил много времени, поэтому, чтобы противостоять этому, я научился тратить минимальное время на решение, пока оно не станет очень, очень многообещающим) .

Вы можете увидеть мою точную методологию в действии в самих ответах на этот вопрос, где я итеративно сошелся через множество профилирований и измерений в течение нескольких дней и создания прототипа от довольно ортодоксального квадродерева к этому неортодоксальному решению с «жесткой двойной сеткой». который обрабатывал наибольшее количество агентов при наиболее стабильной частоте кадров и был, в любом случае, для меня намного быстрее и проще в реализации, чем все предыдущие структуры. Мне пришлось перебрать множество ортодоксальных решений и измерить их, чтобы сформировать окончательную идею необычного лузово-тайтового варианта. Я всегда начинаю и отдаю предпочтение ортодоксальным решениям и начинаю внутри коробки, потому что они хорошо задокументированы и поняты, и просто очень осторожно и робко выхожу наружу, но я часто оказываюсь немного нестандартным, когда требования высоки. достаточно. Я не новичок в самых высоких требованиях, поскольку в моей отрасли и как довольно низкоуровневый тип, работающий над движками, способность обрабатывать больше данных с хорошей частотой кадров часто приводит не только к большей интерактивности для пользователя, но и позволяет художникам создавать более подробный контент с более высоким визуальным качеством, чем когда-либо прежде. Мы всегда стремимся к все более высокому визуальному качеству при хорошей частоте кадров, и это часто сводится к сочетанию производительности и избеганию грубых приближений, когда это возможно. Это неизбежно приводит к некоторой степени неортодоксальности с множеством внутренних решений, очень уникальных для конкретного движка, и каждый движок имеет свои уникальные сильные и слабые стороны, если сравнивать что-то вроде CryEngine, Unreal Engine, Frostbite и Unity.

Например, у меня есть эта структура данных, которую я использую с детства, и я не знаю ее названия. Это простая концепция, и это всего лишь иерархический битовый набор, который позволяет найти пересечения потенциально миллионов элементов всего за несколько итераций простой работы, а также пересекать миллионы элементов, занимающих набор, всего за несколько итераций (менее требования к линейному времени для прохождения всего в наборе только через саму структуру данных, которая возвращает диапазоны занятых элементов / наборов битов вместо отдельных элементов / битовых индексов). Но я понятия не имею, как это называется, потому что это просто то, что я накатал, и я никогда не встречал, чтобы кто-то говорил об этом в информатике. Я обычно называю это «иерархическим битовым набором». Первоначально я называл его «разреженным битовым деревом», но это кажется немного многословным. Это вообще не особо умная концепция, и я не удивлюсь или разочарован (на самом деле вполне счастлив), если обнаружу, что кто-то другой обнаруживает то же решение до меня, но только то, о котором я никогда не нахожу людей, которые используют или о котором никогда не говорят. Он просто расширяет возможности обычного плоского битового набора в быстром нахождении пересечений множеств с побитовым ИЛИ и быстро перемещает все установленные биты с использованием FFZ / FFS, но сокращает требования к линейному времени для обоих до логарифмических (с основанием логарифма, являющимся числом намного больше, чем 2).

В любом случае, я не удивлюсь, если некоторые из этих решений будут очень неортодоксальными, но также не удивлюсь, если они будут достаточно ортодоксальными, и я просто не смог найти собственное название и терминологию для этих методов. Мне больше всего нравятся такие сайты, как одинокий поиск кого-то, кто использовал подобные методы, и попытки найти для них собственные имена и термины, часто заканчивающиеся разочарованием. Я также надеюсь улучшить свою способность объяснять их, хотя я всегда был здесь таким плохим и многословным. Я считаю, что использование изображений очень помогает мне, потому что человеческий язык невероятно пронизан двусмысленностями. Мне также нравится преднамеренно неточный образный язык, который охватывает и отмечает двусмысленность, такую ​​как метафора, аналогия и юмористические преувеличения, но я не обнаружил, что программисты склонны так ценить это из-за отсутствия точности. Но я никогда не считал, что точность настолько важна, пока мы можем передать содержательную часть и то, что «круто» в идее, в то время как они могут рисовать свои собственные интерпретации остального. Приносим извинения за объяснение в целом, но, надеюсь, это проясняет некоторые вещи о моей грубой терминологии и общей методологии, которую я использую, чтобы прийти к этим методам. Английский также не является моим родным языком, так что это добавляет еще один уровень запутанности, когда мне приходится как бы переводить свои мысли в английские слова и много с этим бороться.