伪随机目录树生成？

Question

我正在尝试编写一个程序，将基于种子值（以便可以多次重新运行相同的测试）伪随机自动生成一个不断增长的目录结构，其中包含文件。（这是为了对源代码控制数据库安装进行压力测试）

我想知道是否有类似于准随机的“填充空间”序列（例如van der Corput sequences或Halton sequences）适用于此处。

编辑：或者使用分形算法。这听起来很像是分形算法。

---

编辑2：算了，我觉得我想到了一个显而易见的解决方案，从空树开始，仅使用伪随机生成器的顺序输出（基于生成的数字和到目前为止生成的树的状态）确定N个操作之一，例如创建新子目录、添加新文件、重命名文件、删除文件等。

我希望这样做而不是将文件顺序转储到文件夹结构中，因为我们遇到了大量文件的问题，并且不确定导致问题的确切原因。（树深度、重命名次数、删除次数等）

我需要生成的不仅是1棵固定的树，使用策略是：稍微增加树结构，评估一些性能统计数据，再稍微增加树结构，评估一些性能统计数据，以此类推。

- Jason S

---

如果你得到了答案，一定要确保只用于善良的力量。这听起来像是一个有趣的问题需要解决。 - Sean Bright

你是用你的能力做善事，还是做了不可思议的事情？ - Erik Forbes

Answer 1

如果这只是为了测试，使用一些简单、朴素的生成算法有什么问题呢？比如，生成一个随机（1-10）数量的子目录，为它们生成名称，然后对每个目录递归生成子目录和一定数量的文件。

这很容易定制化，你可以控制rand的种子。对于更奇特的需求，文件/目录数量的分布可以是非线性的，但要适合你的需求。

听起来像是可以在半小时内完成的东西。我不认为需要数学或复杂的东西。当然，除非这只是为了好玩 :-)

- eliben

Answer 2

正如你在第二次编辑中提到的那样，我可能会将整个过程实现为文件树遍历，PRNG决定“更改目录”，“创建目录”，“向上移动一级”，“创建文件”，“删除文件”并具有另一个值来确定要删除的文件，要更改的目录以及为文件和目录生成名称。

我使用了类似的方法来对我编写的工作流服务器进行压力测试（尽管我不需要跟踪工作项的位置，只需要随机选择一个进行操作）。

- Vatine

---

这基本上就是我决定要做的事情。换句话说，将其变成一个有限状态机（几乎是一个元胞自动机）。 - Jason S

Answer 3

这是一组不同的问题，使其成为一个有趣的谜题。

首先我们有伪随机数生成器。有很多可用的东西。我只希望有一个函数，可以创建0..n-1范围内的数字。

然后我们有一种算法来确定单个节点上的子节点数量。使用线性函数很诱人，但这不是对现实的公平表示。因此，您可以创建以下功能：

randomsize() {
  int n = Random(0,10);
  if (n<10) return n;

  return Random(0,9) + 10 * random;
}

这个函数生成小数字。大多数将在0..9范围内，但顶部几乎是无限的。如果您想要更大的数字，也可以使用更大的阈值。

randomsize() {
  int n = Random(0,100);
  if (n<10) return n;

  return Random(0,9) + 10 * random;
}

最后一个问题是如何创建一棵树。这相当简单。但是您应该记住算法必须结束。因此，您需要执行以下操作之一：

• 使用最大深度
• 根据嵌套级别减少生成的数字
• 确定叶子节点数占总子节点数的百分比。该百分比应在较高级别上递增（一级为10-50，二级为20-60，五级为50-100，六级为60-100，直到九级及更高级别为90-100）。

当然，您可以调整参数以创建所需的树。

- Gamecat