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);
    }
}

我也不明白，它是如何占用177米的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

Java代码创建一个缓冲读取器和一个输入流读取器。这两种方法都保证使用大块内存，直到垃圾回收器运行（可能直到程序退出！）才会释放内存

jewel = bin.readLine();

在java中，每个对的调用。readline将在堆上创建一个新字符串，赋值将把以前的字符串标记为“可释放”，但它将在内存中挂起，直到GC将其清除

C在内存管理方面做得很少。唯一可以分配内存块的行是gets，但它可能只使用控制台输入缓冲区，而不计入程序内存使用量

我想你是在拿苹果和桔子做果汁。重新编写C代码以使用垃圾收集和缓冲读取类，您可能会有一个等效的程序

Answer 2

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

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

Java的垃圾收集器在需要时才开始工作。如果您的程序有超过177MB的可用内存，并且该程序通过创建177MB的短期对象进行翻腾，那么就这样吧。如果您开始耗尽内存，或者如果垃圾收集器注意到它可能正在运行的空闲时间，那么它将释放一些内存。因此，您的程序的内存使用可能会增长，以适应可用的内存

或者，即使内存仍然可用，GC也可以运行。如果GC被迫（例如）每10MB的分配运行一次，那么您会期望这段代码的内存使用量在10MB左右，所以我猜在这种情况下不会。在另一个JVM上可能会这样

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