代码之家 › 专栏 › 技术社区 › Nick Van Brunt

分层绘图的循环或排序?

loops sorting algorithm

Nick Van Brunt · 技术社区 · 16 年前

假设一个对象集合,每个对象都需要在一个特定的图层上绘制,那么在什么时候(或曾经)更好地对每个对象逐层排序,而不是循环多次并在每次传递时绘制一个图层?更重要的是,你如何得出这个结论?如果你要排序的话,你会使用排序算法的加分吗?

for (obj = each in collection) {
  for (i=0; i<=topLayer; i++) {
    if (obj.layer == i) {
      obj.draw()
    }
  }
}

/* vs. */

function layerCompare(obj1, obj2) {
  return (obj1.layer > obj2.layer)
}

collection.sort(layerCompare) 

for (obj = each in collection) {
    obj.draw()
}

6 回复 | 直到 16 年前

twolfe18 16 年前

如果循环遍历每个层和每个对象,即O(m*n),其中m是层数,n是对象数。但是,如果您使用QuickSort之类的东西提前对层进行排序,则可以对它们进行排序 O(n*log(n)) 然后把它们拉进去 O(n) ,总复杂度为 O(n*log(n) + n) = O(n*log(n)) .

所以从理论上讲,对它们进行分类总是更好的。在实践中,您必须进行基准测试。

编辑:在第二次检查时,截止点是 m < log(n) . 如果层的数量小于对象数量的日志,那么应该执行双循环,否则对它们进行排序。

plinth 16 年前

如果您的代码是这样的,没有多少层来来去去,那么始终保持层的排序就变得非常有意义了。这样做的一个方法是使一个层本身成为一个可绘制的对象,可以包含对象。此时,您的层被构建到层对象本身的递归性质中。

或者,您可以有一个层列表,其中每个层都是一个对象列表。

MusiGenesis 16 年前

我将为每一层维护一个单独的集合(并且不将层作为每个对象的属性),从而使问题变得无意义。将一个对象重新分配到一个不同的层(通过添加和删除)只会(大约)比更改一个对象的层属性贵两倍,并且您将完全避免为在每个层中获取对象而进行排序或一系列迭代的成本。

Dolphin 16 年前

最大的问题是你的类型有多聪明。项目添加/删除/更改层的频率是多少?插入和冒泡排序(通常被认为性能较差)对于几乎排序的数据非常有效。

另一个问题是,通过排序可以节省多少工作?您的渲染功能对于少量的层很好,但对于越多的层,效果就越差。从复杂性的角度来看,您需要同时考虑层的数量和项的数量,以及每层的分布情况。

如果您有一个小的(当然是相对的)层数,那么为每个层单独设置一个集合(可能是链接列表)并在其更改时将其移动到适当的层可能是有意义的。

Martin Hock 16 年前

如果层数固定,则可以使用 Pigeonhole sort 这是一个O(N)算法。例如,如果有256个编号为0到255的层,请创建一个数组 List<Obj>[] a 大小为256,然后针对每个对象 obj 在你的收藏中,表演 a[obj.layer].add(obj) . 最后,从头到尾遍历数组并绘制对象(如果0返回, for (int i = 0; i < a.length; i++) {for (Obj obj : a[i]) {draw(obj);}}

但我同意,维护这些列表比一直重新生成它们要好。最简单的方法是将对象存储在由顺序允许的顺序排列的集合数据结构中(例如,Java中的树集)。

Pete Kirkham 16 年前

如果你有 n 对象和我层,循环的成本是 n 乘以绘图成本 C _画 和 n×L 测试层的成本 C _画 .

C _{试验与油漆} =(c) _画 +C _测试 ×L)×N

添加项的成本是集合的插入成本;在层之间移动对象的成本可以忽略不计。

在大多数情况下,绘图的成本要比测试的成本大得多。( C _画 & gt;c _测试 )所以它取决于层数,不管 长×N 这个词会有明显的效果( C _画 C _测试 &?l)。

排序意味着您有大约两个测试和一个 N LN _二 n ;第一个近似值,大约需要 3×C _测试 N LN _二 n .您不需要重新排序,除非添加或删除对象或更改其图层,因此绘图成本通常只有线性成本。(使用成本估算而不是试图划分不同的成本的原因 o 价值观是,它给出的是规模的比较,而不是增长——两者之间的界限 O(L n) 和 O(n Ln) 不是时候 L==LN ,要么 o 可能有一个很大的常数项;你必须自己测量它的实际值,而不是我所做的猜测)

C _{分类并重新喷漆} =(c) _画 +3×C _测试 ×LN _二 n)×n

C _仅油漆 = C _画 ×n个

然而,从软件设计的角度来看,我总是倾向于让每一层在做编辑器时都有自己的成员集合——这使得对层的操作更好地进行封装(显示层、隐藏层、仅从一个层中选择、将层移到顶部等)。

对于相当复杂的图形,除非可能的层数很大,否则任何一种方法都将以最快的速度进行,因为绘图成本是最大的。如果需要 1024×C _测试 画一个 32×32 像素对象,则需要100层以上 C _{试验与油漆} 比…慢10% C _仅油漆 . 为自己量时间。