尝试降低时间复杂度时 Pi 测试突变幸存

Question

我有一个算法可以检查给定字符串列表中的哪个字符串与另一个给定字符串最匹配，它是-

    String calcMostMatching(String mainStr, List<String> strings) {
        String mostMatching = null;
        if (strings.size() == 1) {
          // if size is 1, return the only present string.
            mostMatching = strings.get(0);
        } else {
            // This algorithm also works for size() == 1 but I don't                       
            // want to use it when size() == 1
            char[] charArrayOfMainStr = mainStr.toCharArray();
            for (String str : strings) {
                char[] charArrayOfStr = str.toCharArray();
                int min = Math.min(charArrayOfMainStr.length, charArrayOfStr.length)
                for (int i = 0; i < min; i++) {
                    int count = 0;
                    if (charArrayOfMainStr[i] == charArrayOfStr[i]) {
                        count++;
                    } else {
                        break;
                    }
                }
                // Now I store the value of count for 
               // each string but let us say a method like str.setCounter(count);
            }

            // Now I will iterate over the loop to check the mostMatchingString

            mostMatching = strings.get(0);
            for (int i = 1; i < strings.size(); i++) {
                if (mostMatching.getCounter() < strings.get(i).getCounter()) {
                    mostMatching = strings.get(i);
                }
            }

        }
        return mostMatching;
    }

现在坑测试失败了-

if (strings.size() == 1) {
   mostMatching = strings.get(0);
}

说用 false 替换了 strings.size() == 1 但所有测试用例仍然通过。是的，所有测试用例都会通过，但我想在列表只有一个值时降低时间复杂度。

如果你不知道坑测试，有人可以帮我修改这个算法，这样当 size() == 1 除了我所做的以外，它不会进入循环。

注意- 这不是真正的代码，我已将其简化为最小的可重现示例，实际代码有所不同且相当复杂，它会检查各种参数，而不仅仅是比较 getCounter() 个值。

我怎样才能杀死这个突变，或者我必须忽略它。

Answer 1

由于性能不是通过单元测试衡量的属性代码，仅用于优化性能的代码将导致等效的突变杀了。

作为临时练习，您还可以进行最简单的运行性能测试，但这会很困难，因为它们通常会给出定量结果，而不是布尔值 pass/fail。它也会非常慢。

由于您的优化针对的是 n 较低的情况，因此衡量可观察到的改进尤其困难。可能这里根本没有实际的改进。除非您的性能测量证明它的存在是合理的，否则最简单的方法是通过删除 if 语句来降低代码的复杂性。

Answer 2

Saying replaced strings.size() == 1 with false but still all the test cases pass.

所以，如果测试失败，那么 PiTest 会很高兴。我建议您增加单元测试的范围，以涵盖执行路径。比如说，如果你有这样的代码 -

String calcMostMatching(String mainStr, List<String> strings) {
    String mostMatching = null;
    if (strings.size() == 1) {
        // if size is 1, return the only present string.
        mostMatching = strings.get(0);
    } else {
        // move the complex code to another method
        mostMatching = doSomeComplexAlgo(mainStr, strings);
    }
    return mostMatching;
}
String doSomeComplexAlgo(String mainStr, List<String> strings) {
    // do something complex
    return strings.get(0);
}

在单元测试中，我们添加了另一个 verify 方法。它验证 doSomeComplexAlgo 方法未使用单个字符串列表调用。现在，如果 PiTest 测试更改了 size，那么测试应该会失败，因为 doSomeComplexAlgo 将被调用 -

@Test
public void testCalcMostMatchingWithSizeOne() {
    SomeTestClass someTestClass = Mockito.spy(new SomeTestClass());
    String result = someTestClass.calcMostMatching("", List.of("A"));

    // This will fail if the mutation testing changes the List length
    Mockito.verify(someTestClass, Mockito.times(0)).doSomeComplexAlgo(Mockito.anyString(), Mockito.anyList());
}

尝试降低时间复杂度时 Pi 测试突变幸存

Pi Test mutation surviving when trying to reduce time complexity

java

algorithm

pitest