由网友(?我身边的不可以不是你)分享简介：我在写一些JavaScript code应该从画布中选择一个随机的项目，如果该项目符合一定的要求。有不同类型的项目（圆形，三角形，正方形等）和通常有不为每个项目种类数相同。的项目被安排在一个层次结构中（这样的方可以包含几个圈，和一个圆可以包含其他圆圈等 - 它们都可以嵌套）。I'm writing a bit of...

我在写一些JavaScript code应该从画布中选择一个随机的项目，如果该项目符合一定的要求。有不同类型的项目（圆形，三角形，正方形等）和通常有不为每个项目种类数相同。的项目被安排在一个层次结构中（这样的方可以包含几个圈，和一个圆可以包含其他圆圈等 - 它们都可以嵌套）。

I'm writing a bit of JavaScript code which should select a random item from a canvas if the item meets certain requirements. There are different kinds of items (circles, triangles, squares etc.) and there's usually not the same number of items for each kind. The items are arranged in a hierarchy (so a square can contain a few circles, and a circle can contain other circles and so on - they can all be nested).

现在，在选择一个随机的项目我（原）的做法是：

Right now, my (primitive) approach at selecting a random item is to:

递归遍历画布上，并建立一个（可能是巨大的！）的产品清单 随机播放列表 从前面的迭代洗牌列表，直到我找到符合一些额外要求的项目。

这里的问题是，它并不能很好地扩展。我经常碰到内存问题，因为无论是递归深度过大或项目的总清单变得太大。

The problem with this is that it doesn't scale well. I often run into memory issues because either the recursion depth is too high or the total list of items becomes too large.

我正在考虑，让我考虑选择元素，我穿过帆布来改写这个code - 但我不知道我怎么能随意选择一个元素，如果我不知道有多少元素在总。

I was considering to rewrite this code so that I consider choosing elements as I traverse the canvas - but I don't know how I could "randomly" choose an element if I don't know how many elements there are in total.

是否有人有一些想法如何解决此问题？

Does anybody have some idea how to solve this?

推荐答案

开始用 max_r = -1 和 rand_node = NULL 。遍历树。对于每个节点会议的标准：

Start with max_r = -1 and rand_node = null. Iterate through the tree. For each node meeting the criteria:

r = random()
if r > max_r:
  rand_node = node
  max_r = r

在结束 rand_node 将只需要一次迭代中随机选择的节点。

At the end rand_node will be a randomly selected node with only a single iteration required.