6

我正在尝试编写一个程序,它将伪随机地自动生成(基于种子值,因此我可以多次重新运行相同的测试)由文件组成的不断增长的目录结构。(这是为了对源代码控制数据库安装进行压力测试)

我想知道你们中是否有人知道类似于可能在这里工作的准随机“空间填充”序列(例如van der Corput 序列Halton 序列)。

编辑:或分形算法。这听起来有点像分形算法。


编辑2:没关系,我想我找到了明显的解决方案,从一棵空树开始,然后只使用伪随机生成器的顺序输出来确定性地(基于生成的数字和到目前为止生成的树的状态)做一个N 个动作,例如创建新子目录、添加新文件、重命名文件、删除文件等。

我想这样做,而不是仅仅将文件顺序转储到文件夹结构中,因为我们遇到了这样一种情况,即我们在处理大量 #s 文件时遇到了一些问题,并且不确定到底是什么原因。(树深度、重命名次数、删除次数等)

我需要生成的不仅仅是1棵固定的树,使用策略是:把树结构长一点,评估一些性能统计,再把树结构增长一点,评估一些性能统计等。

4

3 回答 3

2

如果这只是为了测试,那么一些简单、幼稚的生成算法有什么问题?就像,生成随机 (1-10) 数量的子目录,为它们生成名称,然后为每个目录递归地生成子目录和一些文件。

这很容易定制,您可以控制rand. 对于更时髦的需求,文件/目录数量的分布可以是非线性的,但更适合您的需求。

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

于 2009-02-05T20:12:22.687 回答
1

这是一组不同的问题,这使它成为一个有趣的难题。

首先我们有伪随机数生成器。有很多东西可用。我只希望有一个函数可以在 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。

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

于 2009-02-05T20:28:52.077 回答
1

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

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

于 2009-02-05T20:39:44.257 回答