2

I implemented one program in Java, which surprising took 177M memory for particular test-cases (I do not have since program are tested by one website).

The problem was to find out all the characters of string S2, which are present in string S1. And there are N such cases.

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

I also do not understand, how it is taking 177M of ram. Even if they are testing a huge file then also only 2 strings are there. However code was perfectly working and test-cases passed.

Since java program was taking huge amount of memory, so I planned to write a C version of same program. which is following:

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

On few existing cases, it is working. Program seems to be correct too. But I am unable to understand why it is passing all test cases correctly.

All the strings buffer are long enough to hold the incoming strings, which are separated by new lines.

EDIT: Changing ""+stone.charAt(i)) to stone.charAt(i)) did not help and took same amount of memory. Also why this C code is not able to pass all the test cases ?

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 都会在堆上创建一个新字符串，赋值会将前一个字符串标记为“free-able”，但它会在内存中徘徊，直到 GC 摆脱它。

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

我认为您正在将苹果与橙子进行比较来制作果汁。重新编写 C 代码以使用垃圾收集和缓冲读取类，您可能有一个等效的程序。

于 2012-05-02T11:29:46.307 回答