Как получить результаты эффективно из Octree/Quadtree?

Question

Я работаю над частью программного обеспечения 3D, которое иногда должно выполнять пересечения между массивными числами кривых (иногда ~ 100 000). Самый естественный способ сделать это - выполнить проверку ограничивающего прямоугольника N^2, а затем пересекаются кривые, перекрывающие ограничивающие поля.

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

Вот мой проект: Каждый октябрьский узел реализован как класс со списком поднодов и упорядоченным списком индексов объектов.

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

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

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

Любые предложения?

Answer 1

SortedDictionary (.NET 2+) или SortedSet (только .NET 4), вероятно, то, что вы хотите. Это древовидные структуры.

SortedList является немым классом, который не отличается от List структурно.

Однако мне все еще не совсем понятно, зачем вам этот список сортироваться. Возможно, если бы вы могли подробнее остановиться на этом вопросе, мы могли бы найти решение, в котором вам вообще не нужна сортировка. Например, простой HashSet мог бы сделать. Это быстрее при поиске и вставках, чем SortedList или в любой из древовидных структур, если хеширование выполнено правильно.

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

Сначала я реализовал слияние с помощью SortedDictionary для хранения глав всех массивов. На каждой итерации я удалял наименьший элемент из словаря и добавлял следующий из того же массива. Тесты производительности показали, что накладные расходы SortedDictionary огромны, поэтому почти невозможно сделать это быстрее, чем простая сортировка + сортировка. Он даже борется за то, чтобы соответствовать производительности SortedList на небольших тестах.

Затем я заменил SortedDictionary на заказную двоичную реализацию кучи. Улучшение производительности было огромным (более 6 раз). Этой реализации Кучи даже удается обойти .Distinct() (что обычно является самым быстрым) в некоторых тестах.

Вот мой код:

class Heap<T> 
{ 
    public Heap(int limit, IComparer<T> comparer) 
    { 
     this.comparer = comparer; 
     data = new T[limit]; 
    } 

    int count = 0; 
    T[] data; 

    public void Add(T t) 
    { 
     data[count++] = t; 
     promote(count-1); 
    } 

    IComparer<T> comparer; 

    public int Count { get { return count; } } 

    public T Pop() 
    { 
     T result = data[0]; 
     fill(0); 
     return result; 
    } 

    bool less(T a, T b) 
    { 
     return comparer.Compare(a,b)<0; 
    } 

    void fill(int index) 
    { 
     int child1 = index*2+1; 
     int child2 = index*2+2; 
     if(child1 >= Count) 
     { 
      data[index] = data[--count]; 
      if(index!=count) 
       promote(index); 
     } 
     else 
     { 
      int bestChild = child1; 
      if(child2 < Count && less(data[child2], data[child1])) 
      { 
       bestChild = child2; 
      } 

      data[index] = data[bestChild]; 
      fill(bestChild); 
     } 
    } 

    void promote(int index) 
    { 
     if(index==0) 
      return; 
     int parent = (index-1)/2; 
     if(less(data[index], data[parent])) 
     { 
      T tmp = data[parent]; 
      data[parent] = data[index]; 
      data[index] = tmp; 
      promote(parent); 
     } 
    } 
} 

struct ArrayCursor<T> 
{ 
    public T [] Array {get;set;} 
    public int Index {get;set;} 
    public bool Finished {get{return Array.Length == Index;}} 
    public T Value{get{return Array[Index];}} 
} 

class ArrayComparer<T> : IComparer<ArrayCursor<T>> 
{ 
    IComparer<T> comparer; 
    public ArrayComparer(IComparer<T> comparer) 
    { 
     this.comparer = comparer; 
    } 

    public int Compare (ArrayCursor<T> a, ArrayCursor<T> b) 
    { 
     return comparer.Compare(a.Value, b.Value); 
    } 
} 

static class HeapMerger 
{ 
    public static IEnumerable<T> MergeUnique<T>(this T[][] arrays) 
    { 
     bool first = true; 
     T last = default(T); 
     IEqualityComparer<T> eq = EqualityComparer<T>.Default; 
     foreach(T i in Merge(arrays)) 
      if(first || !eq.Equals(last,i)) 
      { 
       yield return i; 
       last = i; 
       first = false; 
      } 
    } 

    public static IEnumerable<T> Merge<T>(this T[][] arrays) 
    { 
     var map = new Heap<ArrayCursor<T>>(arrays.Length, new ArrayComparer<T>(Comparer<T>.Default)); 

     Action<ArrayCursor<T>> tryAdd = (a)=> 
     { 
      if(!a.Finished) 
       map.Add(a); 
     }; 

     for(int i=0;i<arrays.Length;i++) 
      tryAdd(new ArrayCursor<T>{Array=arrays[i], Index=0}); 

     while(map.Count>0) 
     { 
      ArrayCursor<T> lowest = map.Pop(); 
      yield return lowest.Value; 
      lowest.Index++; 
      tryAdd(lowest); 
     } 
    } 
} 

Answer 2

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

var results = new SortedList<Node>(octTree.Count); 
// now find the node and add the points 
results = result.TrimToSize(); // reclaim space as needed 

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