Когда переключаться с неупорядоченных списков на отсортированные списки? [Оптимизация]

Question

Я должен реализовать алгоритм для разложения трехмерных объемов в вокселях. Алгоритм начинается с определения, какие вершины находятся на каждой стороне плана разреза, и на втором шаге, какое ребро пересекает план разреза.

Этот процесс можно оптимизировать, используя преимущества отсортированного списка. Идентификация точки разделения - O log (n). Но я должен поддерживать один такой отсортированный список на ось, и это для вершин и ребер. Так как это должно быть реализовано для использования графическим процессором, у меня также есть некоторые ограничения на управление памятью (т.е. CUDA). Навязчивые списки M / деревья и C наложены.

С полной «вокселизацией» я ожидаю в итоге ~ 4000 точек и 12000 ребер. К счастью, это можно оптимизировать, используя более разумную стратегию избавления от обработанных вокселей и упорядочения остаточных объемов, чтобы свести их количество к минимуму. В этом случае я бы ожидал иметь менее 100 точек и 300 ребер. Это делает процесс более сложным для управления, но может в конечном итоге стать более эффективным.

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

Answer 1

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

Answer 2

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

Возвращаясь к своему первоначальному методу, я также обнаружил значительные возможности оптимизации, которые сильно отстают от метода сокращения объема.

Поскольку мне нужно было выбрать один ответ, я выбрал devinb, потому что он ответил на вопрос, но комментарий Саймона, подкрепленный комментарием Тобиаса Уорре, был для меня столь же ценен.

Спасибо всем вам за помощь в решении этой проблемы. Переполнение стека - впечатляющая услуга.

Answer 3

Вопрос ВСЕГДА сводится к тому, какой оператор является наиболее распространенным: доступ или добавление. Если у вас есть неупорядоченный список, его добавление не займет много времени, а доступ к определенным элементам займет дополнительное время. Если у вас есть отсортированный список, добавление к нему занимает больше времени, но доступ к нему происходит быстрее.

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

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

количество доступов: количество изменений

чтобы определить, является ли сортировка хорошей идеей.