如何高效地从八叉树/四叉树中获取结果？

Question

我正在开发一款3D软件，有时需要对大量的曲线（有时达到10万条）进行交集计算。最自然的方法是进行N^2包围盒检查，然后对那些边界框重叠的曲线进行交点计算。

我听说八叉树效果不错，于是我决定尝试实现它，看看是否能提高性能。

设计如下： 每个八叉树节点都是一个类，包含子节点列表和有序对象索引列表。

当添加一个对象时，将其添加到完全包含该对象的最低节点上，或者添加到该节点的某些子节点中，如果该对象没有填充满所有子节点。

现在，我想要检索与给定对象共享树节点的所有对象。为此，遍历所有树节点，如果它们包含给定的索引，则将它们的其他索引添加到有序列表中。

这是高效的，因为每个节点内的索引已经排序，因此查找每个索引是否已经在列表中是很快的。但是，列表最终需要调整大小，这占据了算法的大部分时间。因此，我需要一种类似树状数据结构的东西，可以让我有效地添加有序数据，并且在内存方面也很高效。

有什么建议吗？

- reveazure

---

我相信你对于调整大小会导致问题的看法是错误的。调整大小与添加具有相同的复杂度，即填充大小为N的列表的复杂度为O(N)。另一方面，如果元素不按顺序添加，则维护列表排序所需的元素移动具有O(N*N)的复杂度。 - Rotsor

Answer 1

假设您将OctTree的大小作为树的属性保留，那么您应该能够预分配一个比您可能放入其中的物品数量更大的列表。预分配大小将使调整大小不会发生，只要大小大于您所需的大小即可。我假设您正在使用SortedList来保持有序结果。

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

另一种方法是通过在节点本身中保持树的大小低于当前节点来增强数据结构。然后，您将能够找到感兴趣的节点并直接确定列表需要的大小。您只需要修改插入/删除操作以更新插入/删除节点祖先的每个节点的大小即可完成操作的末尾。

- tvanfosson

---

我也可以用普通列表来做到这一点，但是预先分配如此大量的内存感觉有点不太好。 - reveazure

将项目添加到 SortedList 中的问题显然不是重新分配，而是确保列表保持排序（将较大的元素移到末尾，以便可以插入新项目）。 - Rotsor

@Rotsor - 我并不是建议他使用 SortedList，而是假设他正在使用并建议如何使其更高效，消除了扩容的需求，这是他的观察结果，而不是我的。如果他愿意使用其他有序列表，SortedDictionary 是一个明确的选择。看起来键是唯一的，所以我不知道为什么它不能工作。另一方面，也许他知道项目已按键顺序插入，因此重新排序不是问题。 - tvanfosson

@Rotsor，这就是为什么我认为可能需要使用树形结构的原因。 - reveazure

@Reveazure - SortedDictionary使用红黑树实现，如果您的键是唯一的，它将正常工作。因为它使用链接实现（而不是数组索引实现），所以您不需要/无法预分配容量。如果您不需要排序，则普通字典具有更好的性能特征。 - tvanfosson

Answer 2

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);
        }
    }
}

- Rotsor

---

我选择在节点内部使用排序列表的原因是每个节点中条目的数量通常较少，因此散列表似乎是不必要的。但是既然我有了排序列表，似乎应该能够比无序列表更有效地合并它们。这就是我正在询问的问题。至于遍历节点，我显然只关注包含我想要进行交集的对象的节点。每个节点都有一个最小和最大索引；如果对象的索引在最小值和最大值之间，我检查节点是否包含该对象。等等。 - reveazure

你是正确的，花费时间的是元素的移动，而不是实际的重新分配。我之前就已经想到了这一点，但后来又忘记了。 - reveazure

好的，你可以利用这些已排序的数组通过合并它们来获益，但是这个过程会比较复杂，我相信哈希表仍然可能更快。 - Rotsor