java - java string.replace の実行がメソッドで遅すぎる

Question

特定のプレースホルダーをメソッドの文字列に置き換える引数として文字列を持つメソッドがあります。

public static String format(String in)
{
    in=in.replace("[time]",getTime()); //just some methods returning strings
    in=in.replace("[name]",getName());
}

私の問題は、文字列 "[time]" が文字列に含まれていなくても、format(String) が呼び出されるたびにメソッド getTime() および getName() が呼び出されることです。format(String) を何百回も呼び出すので、すべての文字列を解析するのに最大 1 分かかります。getTime() と getName() は実行に多くの時間を要し、部分文字列 "[time]" と "[name]" はめったに使用されないため、replace メソッドが getTime() または getName() のみを呼び出した場合は、はるかに高速になります。プレースホルダです。私が見る最速の解決策は、string.replace() を replace(String) に書き直すことです。今私の2つの質問は次のとおりです。

これを行うより速い方法はありますか？
replace(String) を書く最速の方法はどれですか?

score 1 · Accepted Answer

getTime()文字列内の検索にかかる時間がandを呼び出すよりも短い場合は、最初getName()に使用します。contains

if (in.contains("[time]"))
{
    in=in.replace("[time]",getTime());
}

次に、必要な場合にのみ呼び出しgetTime()ます。についても同じですgetName()。

または、常に同じ結果を返す場合getTime()は、getName()一度だけ呼び出して、後で使用できるように結果を保存します。

score 1 · Accepted Answer

論理的には、replace は文字列を置換する前にまず文字列を検索する必要があるため、文字列が見つからない場合は、contains を呼び出すのと同じです。contains は単純に検索を行うためです。したがって、最初に検索しても速度は上がりません。

コードが同じソース文字列に対して何度も繰り返し検索を行っている可能性があるようです。もしそうなら、答えはそれをやめることかもしれません。最初にすべてをスキャンし、置き換えられた結果を保存してから、必要に応じてそれらを取得することをお勧めします。

score 0 · Accepted Answer

何が最速かを判断するには、パフォーマンステストが重要です。

これを書く3つの異なる方法をベンチマークする小さなコード...

import java.io.IOException;
import java.util.Properties;
import java.util.Vector;


public class BenchmarkStringStuff {


    public static void main(String[] args) {
        try {
            System.getProperties().store(System.out, "");
        } catch (IOException ioe ) {
            System.out.println("Failed to write properties to STDOUT");
            return;
        }


        BenchmarkStringStuff bss = new BenchmarkStringStuff();
        bss.benchmark(10);
        bss.benchmark(1000);
        bss.benchmark(100000);
        bss.benchmark(1000000);
    }

    public void benchmark(int numTests) 
    {
        Vector<Test> tests = new Vector<Test>();
        tests.add(new OriginalCode());
        tests.add(new TwoSearches());
        tests.add(new SearchOnceAndSubstring());


        Vector<String> testStrings = new Vector<String>();
        // we have a very poor sample, here.  You should test with a better 
        // representation of your expected values
        testStrings.add("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa[time]aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");

        Performance overallRuntime = new Performance("overall combined runtime");
        overallRuntime.setCount(numTests * testStrings.size() * tests.size());
        overallRuntime.start();
        for( Test test : tests )
        {
            Performance codePerformance = new Performance(test.getClass().getName());
            codePerformance.setCount(numTests * testStrings.size());
            codePerformance.start();
            for(String testString : testStrings)
            {
                //Performance stringPerformance = new Performance(testString);
                //stringPerformance.setCount(numTests);
                //stringPerformance.start();
                for(int i=0; i<numTests; i++)
                {
                    test.test(testString);
                }
                //stringPerformance.end();
                //System.out.println(stringPerformance.toString());
            }
            codePerformance.end();
            System.out.println(codePerformance.toString());
        }
        overallRuntime.end();
        System.out.println(overallRuntime.toString());
        System.out.println();

    }

    private static String getTime()
    { 
        return "a date"; 
        // static value to avoid any caching behavior - we
        // want to test the algorithm, not the external stuff.
        // you should use your real getTime method to see real numbers
        // for your application
    }

    private static String getName(){ return "a name"; }


    private interface Test {
        public String test(String in);
    }

    public class OriginalCode implements Test {

        public String test(String in)
        {
            in=in.replace("[time]",getTime()); //just some methods returning strings
            in=in.replace("[name]",getName());
            return in;
        }
    }

    public class TwoSearches implements Test {
        public String test(String in)
        {
            if (in.contains("[time]"))
            {
                in=in.replace("[time]",getTime());
            }
            return in;
        }
    }

    public class SearchOnceAndSubstring implements Test {
        public String test(String in)
        {
            String REPLACEME = "[time]";
            int idx = in.indexOf(REPLACEME);
            if( idx == 0 )
            {
                in=getTime() + in.substring(REPLACEME.length());
            }
            else if( idx > 0 )
            {
                in = in.substring(0,idx) + getTime();
                if( idx+REPLACEME.length() < in.length())
                {
                    in += in.substring(idx+REPLACEME.length());
                }
            }
            return in;
        }
    }





    private class Performance
    {
        long start = 0;
        long end = 0;
        String name = null;
        public int count = 0;

        public Performance(String name)
        {
            this.name = name;
        }

        public void start(){ start = System.currentTimeMillis(); }
        public void end() { end   = System.currentTimeMillis(); }
        public void setCount(int count){ this.count = count; } 

        /** be sure to call start & stop first **/
        public long total(){ return end - start; }


        public String toString()
        {
            return count + "cycles    start:"+start+"     end:"+end+"    total:"+total() + "   <---- " + name;
        }
    }
}

そして、このコードを実行した結果 (パフォーマンスに関係のないものは編集済み)...

#
#Thu Mar 14 18:45:37 EDT 2013
java.runtime.name=Java(TM) SE Runtime Environment
java.vm.version=20.5-b03
java.vm.vendor=Sun Microsystems Inc.
java.vendor.url=http\://java.sun.com/
java.vm.name=Java HotSpot(TM) Client VM
sun.java.launcher=SUN_STANDARD
sun.os.patch.level=Service Pack 1
java.vm.specification.name=Java Virtual Machine Specification
java.runtime.version=1.6.0_30-b12
os.arch=x86
java.vm.specification.vendor=Sun Microsystems Inc.
user.variant=
os.name=Windows 7
java.specification.name=Java Platform API Specification
java.class.version=50.0
sun.management.compiler=HotSpot Client Compiler
os.version=6.1
java.specification.version=1.6
java.class.path=REDACTED
java.vm.specification.version=1.0
sun.java.command=BenchmarkStringStuff
sun.arch.data.model=32
java.specification.vendor=Sun Microsystems Inc.
java.version=1.6.0_30
java.vendor=Sun Microsystems Inc.
sun.desktop=windows
sun.cpu.isalist=pentium_pro+mmx pentium_pro pentium+mmx pentium i486 i386 i86
10cycles    start:1363301137531     end:1363301137531    total:0   <---- BenchmarkStringStuff$OriginalCode
10cycles    start:1363301137531     end:1363301137531    total:0   <---- BenchmarkStringStuff$TwoSearches
10cycles    start:1363301137531     end:1363301137531    total:0   <---- BenchmarkStringStuff$SearchOnceAndSubstring
30cycles    start:1363301137531     end:1363301137531    total:0   <---- overall combined runtime

1000cycles    start:1363301137531     end:1363301137546    total:15   <---- BenchmarkStringStuff$OriginalCode
1000cycles    start:1363301137546     end:1363301137546    total:0   <---- BenchmarkStringStuff$TwoSearches
1000cycles    start:1363301137546     end:1363301137562    total:16   <---- BenchmarkStringStuff$SearchOnceAndSubstring
3000cycles    start:1363301137531     end:1363301137562    total:31   <---- overall combined runtime

100000cycles    start:1363301137562     end:1363301138108    total:546   <---- BenchmarkStringStuff$OriginalCode
100000cycles    start:1363301138108     end:1363301138451    total:343   <---- BenchmarkStringStuff$TwoSearches
100000cycles    start:1363301138451     end:1363301138499    total:48   <---- BenchmarkStringStuff$SearchOnceAndSubstring
300000cycles    start:1363301137562     end:1363301138499    total:937   <---- overall combined runtime

1000000cycles    start:1363301138499     end:1363301143663    total:5164   <---- BenchmarkStringStuff$OriginalCode
1000000cycles    start:1363301143663     end:1363301146784    total:3121   <---- BenchmarkStringStuff$TwoSearches
1000000cycles    start:1363301146784     end:1363301147190    total:406   <---- BenchmarkStringStuff$SearchOnceAndSubstring
3000000cycles    start:1363301138499     end:1363301147190    total:8691   <---- overall combined runtime

勝者は SearchOnceAndSubstring で、他のものより一貫して桁違いに高速です。

char 配列を直接操作することによる他の最適化もあるかもしれませんが、SearchOnceAndSubstring は非常に近く、文字列の連結でほとんどの時間が失われるのではないかと思います。そのパフォーマンステストは、読者の演習として残しておきます。

java - java string.replace の実行がメソッドで遅すぎる

3 に答える 3

Related

Reference