java - Rabin Karp 算法运行速度比 naive 慢

Question

这个问题已经有答案了:

C++ strange results - brute force is quicker than Rabin-Karp...? (1 个回答)

已关闭 3 年前。

我实现了 Rabin-Karp 算法，但它的运行速度比简单的字符串搜索慢(这不是为了作业，我只是对其进行编码以便更好地理解它)。

Rabin Karp(我使用 128 作为 ascii 的基础):

    public long honer(String s){
        long value = (int)s.charAt(0);
        for(int i = 0; i < s.length() - 1; i++){
            value = value*baseASCII + (int)s.charAt(i + 1);
        }
        return value;
    }
    public long updateHoner(Character c0, long honerNumber, Character c4, int length){
        long newNumber = (honerNumber - (int)c0*(long)Math.pow(baseASCII, length))*baseASCII + (int)c4;

        return newNumber;
    }
    public void rabinKarp(String subString){
        long subStringValue = honer(subString);
        long sValue = honer(string.substring(0, subString.length()));
        if(subStringValue == sValue){
            //p.println("match found at index 0");
        }

        for(int i = 1; i <= string.length() - subString.length(); i++){
            sValue = updateHoner(string.charAt(i-1), sValue, string.charAt(i+subString.length()-1), subString.length() - 1);

            if(sValue == subStringValue){
                //p.println("match found at index " + i);
            }
        }
    }

朴素算法:

public void naiveFinder(String subString){
        String found = "";
        for(int i = 0; i <= string.length() - subString.length(); i++){
            for(int j = 0; j < subString.length(); j++ ){
                if(string.charAt(i+j) == subString.charAt(j)){
                    found += string.charAt(i+j);
                }
                else{
                    // reset the string and continue with the next char
                    found = "";
                    break;
                }
                if(found.length() == subString.length()){
                    found = "";
                    //p.println(subString + " found at index " + (i));
                }
            }
        }
    }

测试(主要):

static void main(){
        long init, after;
        StringFinder sf = new StringFinder(getString());
        init =  Calendar.getInstance().getTimeInMillis();
        for(int i = 0; i < 10000; i++)
            sf.rabinKarp("roll");
        after =  Calendar.getInstance().getTimeInMillis();
        p.println("rabin karp without mod : " + (after - init));

        init =  Calendar.getInstance().getTimeInMillis();
        for(int i = 0; i < 10000; i++)
            sf.naiveFinder("roll");
        after =  Calendar.getInstance().getTimeInMillis();
        p.println("naive : " + (after - init));
    }

结果是，运行 Rabin-Karp 算法需要 2517 毫秒，但运行朴素算法只需要 675 毫秒。我怀疑是updateHoner()这需要很长时间，但我不确定。任何见解将不胜感激。

谢谢

编辑:拼写错误

Answer 1

在updateHoner()中:

• 不要重新计算(long)Math.pow(baseASCII, length))*baseASCII - 该值不会改变。计算一次。
• 将参数从 Character 更改为 char 以避免额外的装箱和拆箱