1

面接通り問題文字列類似性をしました。最初はPythonでこれを行いました。これにより、最後の5つのテストケースでTimeLimitExceededエラーが発生しました。それから私はJavaで同じものを試し、解決策が受け入れられました。最後の5つのテストケースのJavaバージョンとPythonバージョンの時間差は非常に大きかったが、最初の5つのテストケースではPythonがJavaを上回っていた。どうしてこんなことに？

文字列の長さは100000まで可能です。

stringsim.py

N=int(raw_input())
while N!=0:
    rootstr=[i for i in raw_input()]
    solution=0
    for i in xrange(len(rootstr)):
        for j in xrange(i,len(rootstr)):
            if(rootstr[j-i]==rootstr[j]):solution+=1
            else:break
    print solution
    N-=1

Solution.java：

class Solution{
    public static void main(String[] args) {
    java.util.Scanner sc=new java.util.Scanner(System.in);
    int N=sc.nextInt(),sol;
    while(N--!=0){
        sol=0;
        char[] s=sc.next().toCharArray();
        for(int i=0;i<s.length;i++){
            for(int j=i;j<s.length;j++){
                if(s[j]==s[j-i]) sol++;
                else break;
            }
        }
        System.out.println(sol);
    }
    }
}

Javaの実行時間：
1成功0.172387
2成功0.172177
3成功0.172185
4成功0.172178
5成功0.263904
6成功2.82661
7成功4.66869
8成功4.83201
9成功1.36585
10成功1.02123

Pythonの場合：
1成功0.081229
2成功0.081047
3成功0.081032
4成功0.081015
5成功0.910672
6制限時間を超えました。16.1818
7制限時間を超えました。16.2357
8制限時間を超えました。16.2001
9制限時間を超えました。16.2408
10制限時間を超えました。16.1831
4

2 に答える 2

1

iccthedral のコメントに同意します。Java JIT は、最初のいくつかの小さな入力に対して Python が高速である理由の 1 つとなる可能性があります。これを確認するには、入力の順序を逆にして (大きな入力が最初になるように)、同じプロセス内のすべての入力に対して実行し、個々の入力ごとに時間を再度測定します。その場合、最後のいくつかの (小さな) 入力で Python が遅い場合、推定が確認されます。

それを確認するもう 1 つの方法は、小さな入力を最後にも追加し (最初にもそれらを保持します)、Java がすべてを実行するのにどれだけ時間がかかるかを確認することです。デルタが小さな入力のみの実行時間よりもはるかに大きい場合、推定が確認されます。

Java JIT は、Java バイトコードをマシン コード (CPU が直接かつ非常に迅速に実行できる) にコンパイルします。ただし、Java が実行に多くの時間を費やす Java メソッドのみが変換されます。(これは、すべてのメソッドをマシン コードに変換すると時間がかかり、結果のマシン コードが大量のメモリを必要とするためです。) したがって、Java プロセスが起動すると、すべてのメソッドをバイトコードとして実行し始め、それぞれに費やされた時間を測定します。メソッドのしきい値に達すると、JIT を使用してそのメソッドをマシン コードにコンパイルします。その後、メソッドははるかに高速に実行されます。ただし、プロセスの実行の開始時には、すべてのメソッドが遅くなり、JIT の実行でビジー状態になるため、Java プロセスは短時間でさらに遅くなります。

これはあなたのケースで起こっている可能性があります.Pythonが単純な問題の答えを見つけ終わるまでに、Javaはまだバイトコードを実行しているか、JITを実行してバイトコードをマシンコードにコンパイルしています. しかし、最終的には Java が追いつくでしょう。マシン コードの方がはるかに高速だからです。

于 2012-09-22T10:03:15.507 に答える
1

Javaで自分で時間を測定してみてください。メインメソッド内でミリ秒をカウントすることを意味します。Python でも同じことを行います。あなたの答えの時間はOSで測定されていると思います-Javaプロセスの実行時間。最初の 5 つの例の時間は、ほとんどが JVM プロセスの開始のオーバーヘッドである可能性があります。

于 2012-09-22T10:31:47.080 に答える