단위 테스트 적절한 데이터 구조 생성

Question

데이터 구조가 올바르게 구축되었는지 여부를 어떻게 테스트합니까? 수정 된 Radix 트리의 종류를 구현하고 있으며 데이터 구조가 올바르게 쌓이는 지 확인하는 방법이 궁금합니다.

나무를 고려하십시오 TreeNode {String, Int} 노드. 다음 예에서와 같이 항상 새로운 자식을 0과 같은 가장 깊은 값 노드로 추가하고 싶습니다.

Root, 0
- Child_1, 5
- Child_2, 0
   - Child_3, 1

질문은, 단위 테스트 방법입니다 나무 구조 당신이 원했던대로 쌓이는가? Treenode에는 하나의 방법 만 있습니다 insert.

지금까지 내 생각은 글을 쓰는 것이 었습니다 TreeVisitor 그것은 나무를 걸어 가서 각 노드를 문자열로 변환합니다. 위의 예에서 트리는 다음과 같이 보일 수 있습니다.

[Root, 0 [Child_1, 5][Child_2, 0 [Child_3, 1]]]

트리를 만드는 알고리즘을 알면 어떤 요소를 삽입하는지 알고 있으면 해당 문자열을 수동으로 만들 수 있습니다. 내 단위 테스트는 다음과 같습니다 (동일한 예제 사용).

TreeNode root = new TreeNode("Root", 0);
root.insert(new TreeNode("Child_1", 5));
root.insert(new TreeNode("Child_2", 0));
root.insert(new TreeNode("Child_3", 1));
TreeVisitor visitor = new TreeVisitor();
String expected = "[Root, 0 [Child_1, 5][Child_2, 0 [Child_3, 1]]]";
asssertEquals(expected, visitor.visit(root));

나는 그것이 최선의 접근 방식이 아니라는 느낌을 받았습니다. 방문자가 변경 되 자마자 모든 테스트가 실패합니다 (단순히 변경 사항을 변경하십시오. [ ] 에게 ( )). 또한이 접근법을 사용하면 꽤 작은 나무를 테스트 할 수 있습니다 (수동으로 계산할 수있는만큼 크게). 더 큰 것을 어떻게 테스트 하시겠습니까?

일반적인 질문은 테스트 작성 방법 데이터 구조가 올바르게 쌓이는 지 확인?

사람들이 .sum (a, b)가 예상대로 작동하는지 테스트하는 12 개의 튜토리얼에서 신선한 테스트 아이디어가 잘못 될 수 있다고 생각합니다.

Answer 1

이것은 테스트 중심 디자인의 경우처럼 보입니다. '삽입'메소드 만있는 인터페이스는 사용할 수 없기 때문에 테스트 할 수 없습니다. 당신이 지은 나무를 볼 수 없거나 아무것도 할 수없고 나무를 짓는 것은 어디든 당신을 얻지 못합니다.

고객이 트리에 액세스하는 방법 (액세스 방법, 방문자 인터페이스 등)을 찾으십시오. 그런 다음 그들을 통해 테스트하십시오.

내부 복잡성이있는 경우 공개 인터페이스를 통해 쉽게 얻을 수 없습니다 (예 : 나무는 트리 뷰에 넣은 나무의 유형보다 자바 트리 맵과 비슷합니다).

• 주장과 불변
• 노출 된 DebugverifyTree 방법과 같은 것.
• BRUTE FORCE : 36542 의사 랜덤 품목 삽입, 모든 경우를 다루는 커버리지 도구를 사용하십시오.

테스트를 작성할 때마다 '이 테스트가 실패하면이 코드의 모든 고객이주의할까요?'라는 질문을하십시오. 그렇지 않은 경우 삭제하십시오.

Answer 2

아마도 당신은 구현을 대체 할 수 있습니다 트린 노드 현재 하위 클래스를 사용한 단위 테스트에서 현재 어린이 세트를 재귀 적으로 검사 할 수있는 방법을 노출시킵니다. 이 방법은 다음에 추가 될 것입니다 트린 노드 단위 테스트를 지원하고 기존 기능을 대체하지 않기 위해 구현하므로 여전히 유효한 테스트가 있습니다.

Answer 3

내가 일반적으로하는 일은 당신이 테스트하는 것을 나타내는 가치 나 이름을 만드는 것입니다. 따라서 나무의 경우 이름은 깊이와 자식 색인을 나타낼 수 있습니다.

TreeNode root = new MyTreeNode("0.0", 0);
root.insert(new MyTreeNode("1.0", 5));
root.insert(new MyTreeNode("1.1", 0));
root.insert(new MyTreeNode("2.0", 1));
verify(root, 0, 0);
...
public void verify(TreeNode node, int depth, int index) {
   verifyName(node, depth, index);
   int numChildren = node.getChildCount();
   depth++;
   for (int i = 0; i < numChildren; i++) {
      verify(node.getChildAt(i), depth, i);
   }
}
public void verifyName(TreeNode node, int depth, int index) {
   StringBuilder expectedName = new StringBuilder();
   expectedName.append(depth).append('.').append(index);
   assertEquals("Tree node not in expected place",
                expectedName.toString(), node.getName());
}

이제 나는 상당히 큰 나무를 테스트하는 것을 상상할 수있었습니다. 재귀 깊이가 문제라면 스택을 사용하여 재귀 방법을 풀 수 있습니다.

public void verify(TreeNode root) {
   Stack<TreeNode> toBeVerified = new Stack<TreeNode>();
   verifyName(root, 0, 0);
   toBeVerified.push(root);

   while(!toBeVerified.isEmpty()) {
     TreeNode node = toBeVerified.pop();
     int depth = getDepth(node.getName()) + 1;
     int numChildren = node.getChildCount();
     for (int i = 0; i < numChildren; i++) {
        verifyName(node, depth, i);
        toBeVerified.push(node);
     }
   }
}
public int getDepth(String name) {
   return Integer.parseInt(name.substring(0, name.indexOf('.')));
}