测试集合中不存在的新随机值

您可以在1-1000000中选择一个随机数,然后线性向前搜索,直到找到一个空闲的位置(最终在1000000匹配失败后重叠到1)。 这样数字的分布 不是线性的 (这是当集合大部分是空的,但随后会变得越来越糟),但这比每次检查随机值快得多(我希望随机性的歪斜对测试来说不太重要),但是您确定只需要调用一次Random(),并且查找空空间所需的检查不能超过1000000次。

我想知道您是否可以将您的功能(或测试或两者)分为两部分:

1. 随机数生成(至少是属于代码的部分,而不是标准API调用,除非您也要测试它)。例如,您可以使用此代码(或者根据您的技术,使用更精细的版本):

2. 调用方法的事实必须返回一个不在列表中的值。

   public class RandomGenerator {  
     public int getValue() {  
       return `<random implementation>`;  
     }  
   }
   
   public class RandomNewGenerator {
      RandomGenerator randomGenerator = new RandomGenerator();
      public int getValue(List<Integer> ints) { 
         // note that a Set<Integer> would be more efficient
         while(true) {
           Integer i = randomGenerator.getValue();
           if (!ints.contains(i)) {
             return i;
           }
         }
      }
   }
   

在真正的代码中,我会更改一些东西(使用接口、使用Spring注入等等)。

这样,在对RandomNewGenerator的测试中,可以使用返回已知系列值的实现重写RandomGenerator。 然后,您可以测试RandomNewGenerator,而无需面对任何随机 .

我相信这确实是 JUnit的精神测试,使它们简单、快速,甚至更好:可重复 !最后一个质量实际上允许您的测试用作回归测试,这非常方便。

示例测试代码:

    public class RandomNewGeneratorTest {
      // do the set up 
      private List<Integer> empties = ...//
      private List<Integer> basics =  ...  // set up to include 1,2, 7, 8

      private class Random extends RandomNewGenerator {
         int current;
         Random(int initial) {
            current = initial;
         }
         public int getValue() {  
           return current++; // incremental values for test, not random
         }
       }

      public void testEmpty() {
         RandomNewGenerator randomNewGenerator = new RandomNewGenerator();
         // do a simple injection of dependency
         randomNewGenerator.randomGenerator = new Random(1); 
         // random starts at 1, builds up
         assertEquals(1, randomNewGenerator.getValue(empties);
         assertEquals(2, randomNewGenerator.getValue(empties);
         assertEquals(3, randomNewGenerator.getValue(empties);
         assertEquals(4, randomNewGenerator.getValue(empties);
      }

      public void testBasic() {
         RandomNewGenerator randomNewGenerator = new RandomNewGenerator();
         // do a simple injection of dependency
         randomNewGenerator.randomGenerator = new Random(5); 
         // random starts at 5, builds up
         // I expect 7, 8 to be skipped
         assertEquals(5, randomNewGenerator.getValue(basics);
         assertEquals(6, randomNewGenerator.getValue(basics);
         assertEquals(9, randomNewGenerator.getValue(basics);
      }

    }

请注意,此代码只是一个原始示例。您可以根据需要以任何方式更改它,例如,向随机生成器提供它必须返回的值序列。例如,您可以测试是否在同一行中返回两个相同的数字。

一种可能有效的方法是获取初始列表并为所有索引填充100万个元素向量。 i 从1…1000000开始,如果 我 有,如果 我 没有被拿走。

计算初始列表的大小,调用此大小 s .

生成随机数 j , 0 <= j < s . 循环遍历数组,并找到 J 元素是0,然后返回它。

编辑:仔细观察@lapo的答案-我的答案看起来是一样的,但要慢一点。

一旦你选择的数字集开始变得太满,拉波的答案的分布就不是线性的。通过以下修改,您将得到整数的均匀分布:

• 将初始的一组数字保存在一个位数组中,其中位数组中的每个元素对应于初始集合中的一个数字。true表示集合中存在项,否则为false。

• 接下来,创建一个从1到1000000的整数数组。 Shuffle 数组。这组数字将是你的新钥匙。

• 按住指向新键列表中最后一个索引的指针。当您想要生成一个新的键时,增加指向新键中下一个项的指针;您可以测试它是否已经在您的初始设置中选择了常量时间。如果集合中已经存在该项,请增加指向新键中下一项的指针,否则返回该项并将其在位数组中的状态设置为true。

什么意味着长久?将一个值与列表中的1.000.000值进行比较只需几毫秒。我看不到任何其他的解决方案,然后将其与除列表之外的所有值进行比较,然后您可以缩小范围进行检查。当然,您可以对列表进行排序,然后执行不超过20个步骤的二进制搜索,但是排序比线性搜索更昂贵。

我刚刚在一台速度很慢的电脑上做了一个测试,用了20毫秒的时间扫描了一个列表,其中有1000.000个数字对应于C中的给定数字。使用一个阵列,需要14毫秒。速度不够快吗?二进制搜索在0.3微秒内完成了任务。最后,使用散列集进行查找只需要大约90纳秒。

如果你必须写算法,我建议你做一个简单的技巧。进入列表-一个带有分配的号码,一个带有未分配的号码,所有号码从1到1000.000.000开始。如果您需要一个新的号码,只需得到一个介于零(包括零)和未分配号码列表长度(不包括零)之间的随机号码,在这个索引处选择号码并将其移动到分配号码列表。完成。

我也测试了这种方法,大约花费了460毫秒的时间来获取所有1.000.000个数字,从未分配的数字列表到分配的数字列表,使用未分配的数字的散列集来加速删除和分配的数字列表。只需460纳秒就可以在给定范围内生成一个新的唯一随机数。为了避免随机数生成器和哈希算法之间的干扰,必须使用经过排序的字典。

最后,你也可以把1到1000.000.000之间的数字,但是它们会被放到一个列表中,随机移动一段时间,然后一个接一个地从列表中取出。除了第一次随机播放列表外,它将在任何时候运行。