2

私はJavaで1つのプログラムを実装しましたが、驚くべきことに、特定のテストケースで1億7700万のメモリを消費しました（プログラムは1つのWebサイトでテストされているため、持っていません）。

問題は、文字列S1に存在する文字列S2のすべての文字を見つけることでした。そして、そのようなケースはN個あります。

public static void main(String[] args) throws Exception {
    BufferedReader bin = new BufferedReader (new InputStreamReader (System.in));
    String jewel, stone;
    int t = Integer.parseInt (bin.readLine());
    int count;
    int i;

    while (t-->0) {
        count = 0;
        jewel = bin.readLine();
        stone = bin.readLine();
        for (i=0; i<stone.length(); i++) {
            if (jewel.indexOf(stone.charAt(i)) !=-1) {
                count++;
            }
        }
        System.out.println(count);
    }
}

また、177MのRAMがどのように使用されているのかもわかりません。彼らが巨大なファイルをテストしているとしても、2つの文字列しかありません。ただし、コードは完全に機能し、テストケースは合格しました。

Javaプログラムは大量のメモリを消費していたので、同じプログラムのCバージョンを作成することを計画しました。次のとおりです。

int main ()
{
  char * pch;
    char jewel[100], stone[100];
    int n;
    scanf("%d",&n);
    int len;    
    int tp;
    int count = 0;
    getchar(); // remove trailing '\n'
    while (n-->0) {

        gets(jewel);
        pch = gets(stone);
        count = 0;

        while(*pch ) {
            if (strchr(jewel, *pch)) {
                count++;
            }
            pch++;
        }
        printf("%d\n", count);
    }
  return 0;
}

いくつかの既存のケースでは、それは機能しています。プログラムも正しいようです。しかし、なぜそれがすべてのテストケースに正しく合格しているのか理解できません。

すべての文字列バッファは、新しい行で区切られた着信文字列を保持するのに十分な長さです。

編集：に 変更""+stone.charAt(i))しても効果stone.charAt(i))がなく、同じ量のメモリが必要でした。また、なぜこのCコードはすべてのテストケースに合格できないのですか？

4

2 に答える 2

10

""+stone.charAt(i)短命の文字列オブジェクトを作成します。これは少量のメモリを占有し、最終的にはガベージ コレクターによって解放されます [*]。

一方、C コードはメモリをまったく割り当てません。

Java のガベージ コレクタは、必要になるまで機能するとは限りません。プログラムで使用できるメモリが 177MB を超えていて、プログラムが 177MB の存続期間の短いオブジェクトを頻繁に作成する場合は、それで問題ありません。メモリが不足し始めた場合、またはガベージ コレクタが実行中の可能性のあるアイドル時間があることに気付いた場合、そのメモリの一部を解放します。したがって、プログラムのメモリ使用量は、利用可能なメモリに合わせて大きくなる可能性があります。

または、使用可能なメモリがまだある場合でも GC が実行される場合があります。GC が (たとえば) 10MB の割り当てごとに強制的に実行された場合、このコードのメモリ使用量は約 10MB になると予想されるため、この場合はそうではないと思います。別のJVMではそうなるかもしれません。

[*] Java 実装が実行できる理論的な最適化があります。オブジェクトへの参照がループをエスケープしないことに注意し、GC のチャーンを回避するために別の方法でオブジェクトを割り当て/解放します。この場合はそうではないと思いますが、異なる JVM、または異なるオプションを持つ同じ JVM では、ガベージ コレクション戦略が大きく異なる可能性があることを知っておく価値があります。

于 2012-05-02T10:09:34.697 に答える
2

Java コードは、バッファリングされたリーダーと入力ストリーム リーダーを作成します。これらはどちらも大量のメモリを使用することが保証されており、ガベージ コレクタが実行されるまで解放されません (プログラムが終了するまで解放されない可能性があります)。

jewel = bin.readLine();

Java では、.readline を呼び出すたびにヒープ上に新しい文字列が作成され、割り当てによって前の文字列が「解放可能」としてマークされますが、GC がそれを取り除くまでメモリ内に残ります。

C は、メモリ管理に関してほとんど何もしません。メモリのチャンクを割り当てる可能性のある唯一の行はgets、おそらくプログラムのメモリ使用量にカウントされないコンソール入力バッファを使用するだけです。

リンゴとオレンジを比較して果汁を作っていると思います。ガベージ コレクションとバッファリングされた読み取りクラスを使用するように C コードを書き直すと、同等のプログラムが作成される場合があります。

于 2012-05-02T11:29:46.307 に答える