算法效率

书名：代码本色：用编程模拟自然系统
作者：Daniel Shiffman
译者：周晗彬
ISBN：978-7-115-36947-5
第6章目录

6.14　算法效率（为什么程序跑得这么慢）

• 群集行为看起来很不可思议，但它的运行速度会非常慢，群集中的元素越多，程序运行得越慢。

1、优化方法

• 如果我们把屏幕划分成一个个网格，把这2000个Boid对象分配到这些网格中。对于每个Boid对象，只需检查同一单元格内的其他元素。这种技术称为“网格空间分割”

2、如何用Processing实现这种算法？

• 可以用多个ArrayList实现，其中一个ArrayList用于保存所有的Boid对象，就像群集示例中做的。
  ArrayList<Boid> boids;
• 除了这个ArrayList，我们还在另一个二维ArrayList中存放了每个Boid对象引用。对网格中的每个单元格，都有一个对应的ArrayList用于保存此单元格内的元素。
  ArrayList<Boid>[][] grid;
• 在draw()函数中，每个Boid元素都需要根据位置将自己放入合适的单元格内。

int column = int(boid.x) resolution;
int row = int(boid.y) resolution;
grid[column][row].add(boid);

• 当Boid对象检查邻居元素时，只需检查某个单元格内的元素（实际上，为了处理好边界情况，我们还应该检查邻近的单元格）。

3、示例

示例代码6-10　网格空间分割（略）

4、结果

© 著作权归作者所有,转载或内容合作请联系作者