Java与C版相同的算法

Question

我在Java中实现了一个程序,对于特定的测试用例来说,令人惊讶的是需要177M内存(我没有,因为程序是由一个网站测试的).

问题是找出字符串S2中存在于字符串S1中的所有字符.还有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代码无法通过所有测试用例？

Answer 1

""+stone.charAt(i)创建一个短暂的字符串对象.这占用了少量内存,最终将被垃圾收集器[*]释放.

另一方面,您的C代码根本不分配任何内存.

Java的垃圾收集器在它需要之前不一定能够工作.如果你的程序有超过177MB的可用内存,并且该程序通过创建177MB的短期对象来生成,那么就这样吧.如果你开始耗尽内存,或者垃圾收集器注意到它可能正在运行的空闲时间,那么它将释放一些内存.因此,您的程序的内存使用可能会增长到适合可用的内存.

或者,即使仍有可用内存,GC也可能会运行.如果GC被强制运行(例如)每10MB的分配,那么你期望这个代码的内存使用大约为10MB,所以我想在这种情况下它不会.在另一个JVM上也许会.

[*] Java实现可以执行一个理论上的优化,注意到没有对该对象的引用转义循环,然后以不同的方式分配/释放它以避免搅动GC.我猜这种情况并没有发生,但值得知道的是,不同的JVM或具有不同选项的相同JVM可能具有非常不同的垃圾收集策略.