基于TDD的表达式验证

 

 

下面是一个关于表达式验证的测试代码, 令人出乎意料的是以栈方式检验检查表达式的开销要远远超出于以查找方式对表达式进行检查.

 是否JVM对String类的所有接口作了强化？特此附上代码,期待大虾解释其原因.

测试代码:

 

@RunWith(Parameterized.class)
public class ExpressionValidatorTest {
    private ExpressionValidator validator;

    public ExpressionValidatorTest(ExpressionValidator validator) {
        this.validator = validator;
    }

    @Parameters
    public static Collection<Object[]> parameters() {
        return Arrays.asList(
                new Object[]{new StackBasedExpressionValidator()},
                new Object[]{new SearchBasedExpressionValidator()}
        );
    }

    @Test
    public void plainText() throws Exception {
        assertTrue(validator.validate("abc"));
    }

    @Test
    public void leftBraceOnly() throws Exception {
        assertFalse(validator.validate("{abc"));
    }

    @Test
    public void rightBraceOnly() throws Exception {
        assertFalse(validator.validate("abc}"));
    }

    @Test
    public void simpleExpression() throws Exception {
        assertTrue(validator.validate("{abc}"));
    }

    @Test
    public void nestedBraces() throws Exception {
        assertFalse(validator.validate("{{abc}}"));
    }

    @Test
    public void antisymmetryBraces() throws Exception {
        assertFalse(validator.validate("}abc{"));
    }

    @Test
    public void badExpression() throws Exception {
        assertFalse(validator.validate("{abc}}"));
        assertFalse(validator.validate("{{abc}"));
    }

    @Test
    public void mixedExpression() throws Exception {
        assertTrue(validator.validate("{abc} and {efg}"));
    }

    @Ignore
    @Test(timeout = 5000)
    public void hugeExpression() throws Exception {
        StringBuilder expressionBuilder = new StringBuilder();
        for (int k = 0; k < 100000; k++)
            expressionBuilder.append("{username} and {password}");
        assertTrue(validator.validate(expressionBuilder.toString()));
    }

}

 Java代码:

 

public interface ExpressionValidator {
    char START_EL = '{';
    char END_EL = '}';

    boolean validate(String expression);
}

public class SearchBasedExpressionValidator
        implements ExpressionValidator {
    public boolean validate(String expression) {
        int leftPos = 0;
        int prevRightPos = 0;
        while (true) {
            leftPos = expression.indexOf(START_EL, leftPos);
            int rightPos = expression.indexOf(END_EL, prevRightPos);
            if (notFound(leftPos))
                return notFound(rightPos);
            if (notFound(rightPos) ||
                    !between(leftPos, prevRightPos, rightPos))
                return false;
            leftPos = leftPos + 1;
            prevRightPos = rightPos + 1;
        }
    }

    private boolean notFound(int leftPos) {
        return leftPos < 0;
    }

    private boolean between(int target, int x, int y) {
        return notAfter(x, target) && notAfter(target, y);
    }

    private boolean notAfter(int x, int y) {
        return x <= y;
    }
}

public class StackBasedExpressionValidator
        implements ExpressionValidator {

    public static final boolean POP = false;
    public static final boolean PUSH = true;

    public boolean validate(String expression) {
        boolean state = POP;
        char[] chars = expression.toCharArray();
        int length = chars.length;
        int k = 0;
        do {
            switch (chars[k]) {
                case START_EL:
                    if (isPushed(state))
                        return false;
                    state = PUSH;
                    break;
                case END_EL:
                    if (isPopup(state))
                        return false;
                    state = POP;
                    break;
            }
        } while (++k < length);
        return isPopup(state);
    }

    private boolean isPushed(boolean state) {
        return state==PUSH;
    }

    private boolean isPopup(boolean state) {
        return state==POP;
    }
}