参数匹配测试算法

SimilarParamChecker.java

package com.mccxj.test;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

import org.junit.Test;

public class SimilarParamChecker {
    /**
     * 500*10000 62221129501 59791067860 58769352530
     * 
     * @throws Exception
     */
    // @Test
    public void test1() throws Exception {

        final String match1 = "User=?&Password=BB&CurrentTab=LOG&CurrentTab2=LOG";
        final String match2 = "User=?&Password=?&CurrentTab=LOG1";
        final String match3 = "User=?&Password=?&CurrentTab=LOG";

        ExecutorService pool = Executors.newFixedThreadPool(50);
        int tasksize = 100;
        final CountDownLatch latch = new CountDownLatch(tasksize);

        long s = System.nanoTime();
        for (int k = 0; k < tasksize; k++) {
            pool.submit(new Runnable() {
                @Override
                public void run() {
                    Random r = new Random(100000000);
                    for (int i = 0; i < 10000; i++) {
                        String toMatch = "XX="
                                         + r.nextInt()
                                         + "&User=AA&Password=BB&CurrentTab=LOG";
                        Map<String, String> matchs = new HashMap<String, String>();
                        String[] split = toMatch.split("&");
                        for (String mss : split) {
                            String[] split2 = mss.split("=");
                            matchs.put(split2[0], split2[1]);
                        }
                        if (similar(match1, matchs)
                            || similar(match2, matchs)
                            || similar(match3, matchs)) {}
                    }
                    latch.countDown();
                }
            });
        }

        latch.await();
        System.out.println("Test1: " + (System.nanoTime() - s));
    }

    /**
     * 500*10000 3871929603 4198027333 4127755902 5000*10000 41449749130
     * 500*100000 40286881783 50000000 104203036210
     * 
     * @throws Exception
     */
    @Test
    public void test2() throws Exception {

        final String match1 = "User=?&Password=BB&CurrentTab=LOG&CurrentTab2=LOG";
        final String match2 = "User=?&Password=?&CurrentTab=LOG1";
        final String match3 = "User=?&Password=?&CurrentTab=LOG";

        ExecutorService pool = Executors.newFixedThreadPool(50);
        int tasksize = 1;
        final CountDownLatch latch = new CountDownLatch(tasksize);

        long s = System.nanoTime();
        for (int k = 0; k < tasksize; k++) {
            pool.submit(new Runnable() {
                @Override
                public void run() {
                    Random r = new Random(100000000);
                    for (int i = 0; i < 50000000; i++) {
                        String toMatch = "XX="
                                         + r.nextInt()
                                         + "&User=AA&Password=BB&CurrentTab=LOG";

                        UrlMatcher matcher = new UrlMatcher(toMatch);
                        if (matcher.match(match1) || matcher.match(match2) || matcher.match(match3)) {}
                    }
                    latch.countDown();
                }
            });
        }

        latch.await();
        System.out.println("Test2: " + (System.nanoTime() - s));
    }

    private boolean similar(String match, Map<String, String> matchs) {

        String[] ms = match.split("&");
        for (String m : ms) {
            String[] split2 = m.split("=");
            if (!matchs.containsKey(split2[0]))
                return false;

            if (!"?".equals(split2[1])) {
                if (!split2[1].equals(matchs.get(split2[0])))
                    return false;
            }
        }
        return true;
    }

    class UrlMatcher {
        private String toMatch;
        int[] pos = new int[20];
        int ps;

        public UrlMatcher(String toMatch) {
            int ss = 0;
            this.toMatch = toMatch;
            int len = toMatch.length();
            int st = 0;
            int ed = 0;
            for (int i = 0; i < len; i++) {
                char c = toMatch.charAt(i);
                if (c == '=') {
                    ed = i - 1;
                    pos[ss++] = st;
                    pos[ss++] = ed;
                    st = i + 1;
                    pos[ss++] = st;
                } else if (c == '&') {
                    pos[ss++] = i - 1;
                    st = i + 1;
                }
            }
            pos[ss] = len - 1;
            ps = (ss + 1);
        }

        public boolean match(String m) {
            int len = m.length();
            int st = 0;
            int ed = 0;
            int vs = 0;
            int ve = 0;

            for (int i = 0; i < len; i++) {
                char c = m.charAt(i);
                if (c == '=') {
                    ed = i - 1;
                    vs = i + 1;
                } else if (c == '&') {
                    ve = i - 1;

                    if (!match2(m, st, ed, vs, ve)) {
                        return false;
                    }

                    st = i + 1;
                }
            }
            return match2(m, st, ed, vs, len - 1);
        }

        boolean match2(String m, int st, int ed, int vs, int ve) {
            boolean ma = true;
            for (int i = 0; i < ps; i = i + 4) {
                if (pos[i + 1] - pos[i] == ed - st) {
                    int sst = st - pos[i];
                    for (int j = pos[i]; j <= pos[i + 1]; j++) {
                        if (toMatch.charAt(j) != m.charAt(sst + j)) {
                            ma = false;
                        }
                    }

                    if (ma) {
                        if (ve == vs && '?' == m.charAt(vs)) {
                            return true;
                        } else {
                            if (pos[i + 3] - pos[i + 2] == ve - vs) {
                                int vst = vs - pos[i + 2];
                                for (int j = pos[i + 2]; j <= pos[i + 3]; j++) {
                                    if (toMatch.charAt(j) != m.charAt(vst + j)) {
                                        return false;
                                    }
                                }
                                return true;
                            } else {
                                return false;
                            }
                        }
                    }

                }
            }
            return false;
        }
    }
}