Java，“Scanner”的内存使用情况

Question

我正在运行一个在线自动程序评估平台，对于其中一个练习，Java的“Scanner”使用了太多的内存（我们刚开始支持Java，所以这个问题之前没有出现过）。由于我们正在教授算法给初学者，我们不能只是要求他们通过读取一个字节来重新编写代码。

根据我们的测试，扫描仪使用高达200个字节来读取一个整数...

练习：10,000个整数，100个连续整数的哪个窗口具有最大总和？

内存使用很小（您只需要记住最后100个整数），但经典版与“Scanner / nextInt()”和手动版本之间存在2.5 Mb的内存差异。

2.5 Mb用于读取10,000个整数==> 200 Bytes用于读取一个整数？？

是否有任何简单的解决方案可以向初学者解释？或者以下函数（或类似函数）是正确的方式？

---

我们的测试函数可以更快地读取整数，同时使用更少的内存：

public static int read_int() throws IOException
   {
     int number = 0;
     int signe = 1;

     int byteRead = System.in.read();
     while (byteRead != '-'  && ((byteRead < '0') || ('9' < byteRead)))
       byteRead = System.in.read();
     if (byteRead == '-'){
       signe = -1;
       byteRead = System.in.read();
     }
     while (('0' <= byteRead) && (byteRead <= '9')){
        number *= 10;
        number += byteRead - '0';
        byteRead = System.in.read();
     }
     return signe*number;
   }

使用Scanner编写代码，如请求的那样：

---

import java.util.Scanner;

class Main {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int nbValues = sc.nextInt();
      int widthWindow = sc.nextInt();

      int values[] = new int[widthWindow];

      int sumValues = 0;
      for (int idValue = 0; idValue < widthWindow; idValue++){
         values[idValue] = sc.nextInt();
         sumValues += values[idValue];
      }

      int maximum = sumValues;
      for (int idValue = widthWindow; idValue < nbValues; idValue++)
      {
         sumValues -= values[ idValue % widthWindow ];
         values[ idValue % widthWindow ] = sc.nextInt();

         sumValues += values[ idValue % widthWindow ];
         if (maximum < sumValues)
             maximum = sumValues;
      }
      System.out.println(maximum);
   }
}

按要求，内存使用量与整数数量的函数关系如下：

• 10,000个整数：2.5Mb
• 20,000个整数：5Mb
• 50,000个整数：15Mb
• 100,000个整数：30Mb
• 200,000个整数：50Mb
• 300,000个整数：75Mb

- Loïc Février

---

你能展示一下如何使用Scanner的示例代码吗？ - rsp

如果您将更改为100,000个整数，内存使用量会增加25mb吗？ - artbristol

问题已更新：是的，它需要25 Mb！ - Loïc Février

BufferedReader 在每个整数数量上使用多少内存？ - c-an

Answer 1

我们最终决定重写Scanner类的部分代码。这样我们只需要包含我们的Scanner而不是Java的Scanner，其余代码保持不变。我们不再有任何内存问题，并且程序运行速度提高了20倍。

下面的代码来自我的同事Christoph Dürr：

import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;

class Locale {
   final static int US=0;
}

public class Scanner {
   private BufferedInputStream in;

   int c;

   boolean atBeginningOfLine;

   public Scanner(InputStream stream) {
      in = new BufferedInputStream(stream);
      try {
         atBeginningOfLine = true;
         c  = (char)in.read();
      } catch (IOException e) {
         c  = -1;
      }
   }

   public boolean hasNext() {
      if (!atBeginningOfLine) 
         throw new Error("hasNext only works "+
         "after a call to nextLine");
      return c != -1;
   }

   public String next() {
      StringBuffer sb = new StringBuffer();
      atBeginningOfLine = false;
      try {
         while (c <= ' ') {
            c = in.read();
         } 
         while (c > ' ') {
            sb.append((char)c);
            c = in.read();
         }
      } catch (IOException e) {
         c = -1;
         return "";
      }
      return sb.toString();
   }

   public String nextLine() {
      StringBuffer sb = new StringBuffer();
      atBeginningOfLine = true;
      try {
         while (c != '\n') {
            sb.append((char)c);
            c = in.read();
         }
         c = in.read();
      } catch (IOException e) {
         c = -1;
         return "";
      }
      return sb.toString();   
   }

   public int nextInt() {
      String s = next();
      try {
         return Integer.parseInt(s);
      } catch (NumberFormatException e) {
         return 0; //throw new Error("Malformed number " + s);
      }
   }

   public double nextDouble() {
      return new Double(next());
   }

   public long nextLong() {
      return Long.parseLong(next());
   } 

   public void useLocale(int l) {}
}

通过将代码集成到我的问题中，在读取每个字符时“构建”数字，可以使速度更快。

- Loïc Février

Answer 2

在我开发的 Android 应用程序中，当调查严重的内存膨胀时，我遇到了这个问题。

Android 有一个工具可以记录所有分配。

事实证明，仅解析单个 nextDouble() 调用，Java 就会进行 128 次分配。其中前 8 个超过 1000 字节，最大的一个是 4102 字节！

不用说，这完全无法使用。我们正在努力保持电池耗电量低，这真的没有帮助。

我将尝试使用已发布的替代 Scanner 代码，谢谢！

以下是证据：

4047    4102    char[]  13      java.lang.AbstractStringBuilder enlargeBuffer   
4045    3070    char[]  13      java.lang.String        <init>  
4085    2834    char[]  13      java.lang.AbstractStringBuilder enlargeBuffer   
4048    2738    char[]  13      java.lang.AbstractStringBuilder enlargeBuffer   
4099    1892    char[]  13      java.lang.AbstractStringBuilder enlargeBuffer   
4108    1264    char[]  13      java.lang.AbstractStringBuilder enlargeBuffer   
4118    1222    char[]  13      java.lang.AbstractStringBuilder enlargeBuffer   
4041    1128    int[]   13      java.util.regex.Matcher usePattern  
[...]

第二列是分配大小（可能是以字节为单位，尽管Android设备监视器没有指定）。

底线：除非您有足够的电力和CPU可供使用，否则不要使用Scanner。

- Gerhard Wesp

---

如果您添加列名，那将非常好。 - c-an

Answer 3

这是来自Scanner的nextInt()代码。

    public int nextInt(int radix) {
    // Check cached result
    if ((typeCache != null) && (typeCache instanceof Integer)
    && this.radix == radix) {
        int val = ((Integer)typeCache).intValue();
        useTypeCache();
        return val;
    }
    setRadix(radix);
    clearCaches();
    // Search for next int
    try {
        String s = next(integerPattern());
        if (matcher.group(SIMPLE_GROUP_INDEX) == null)
            s = processIntegerToken(s);
        return Integer.parseInt(s, radix);
    } catch (NumberFormatException nfe) {
        position = matcher.start(); // don't skip bad token
        throw new InputMismatchException(nfe.getMessage());
    }
}

正如你所看到的，它具有基数和符号感知功能，使用缓存等功能。因此，额外的内存使用都是来自于旨在提高Scanner效率的功能。

- mcfinnigan

---

我能理解，但为什么垃圾回收器不能清理并减少内存占用？使用我们的函数，可以在500 KB的内存中读取300,000个整数。 - Loïc Février

因此，请派生自己的FastScanner并覆盖nextInt。感谢指出java.util.Scanner的低效率。 - Joop Eggen

@Joop Eggen：我本来想这样做，但我的问题是：在Java中是否有其他方法（无需修改）可以使用简单的代码（我们针对初学者）和小内存占用读取多个整数？我完全不是Java专家... - Loïc Février

抱歉，据我所知没有重复的方法。假设您希望将输入文件作为文本处理，您可以将每个数字放在自己的一行上，并使用Integer.parseInt进行BufferedReader循环。但人们仍然会倾向于制作一些Scanner包装类。 - Joop Eggen

Answer 4

您可以将所有值读入数组，然后开始对数组求和。

在读取数组时，您仍需要这么多内存，但是在读取后，它将用于其他目的。

您的代码结构将受益，即使现在您可以为数字使用不同的来源-例如util.Random，并仍然搜索最大总和的数组，或者搜索相同的数组以获取不同的序列长度，而无需重新读取输入。

顺便说一下：我看你的代码很困难，因为：

• value/values/sumValues/nb_values-(为什么不是maximumValues)? - 所有变量都是值，所以这没有帮助理解。
• 循环通常用i和j或n进行索引。 Value是误导性的
• length_sequence也是误导性的。 '序列长度'的意思，但每个人都会使用'长度'，因为与其他长度没有歧义。
• 您为琐碎的事情使用长名称，但对于不太琐碎的名称使用神秘的缩写。 我读了您的问题描述和代码，不知道您的代码是做什么的：nb_values是什么？非阻塞？空字节？附近？这是什么？

我的第一印象是，对于一系列的整数：

3 9 2 4 6 4 3 2 4 4 5 6 9 3 2 1 9 9 9

你需要搜索长度为3的序列，直到第9个值（不包括3和9本身），并寻找最大值（2+4+6），（4+6+4）......（4+4+5），但结果是34。你需要将前9个值相加。

建议：

import java.util.Scanner;

class MaxChunk {

   int chunksize;

   public int[] readValues () {
      Scanner sc = new Scanner (System.in);
      chunksize = sc.nextInt ();
      int length = sc.nextInt ();
      int values[] = new int [length];
      for (int i = 0; i < length; i++)
      {
         values[i] = sc.nextInt();
      }   
      return values;
   }

   public int calc (int values[]) {
      int sum = 0;
      for (int i = 0; i < chunksize; i++)
      {
         sum += values[i];
      }

      int maximum = sum;

      for (int j = chunksize; j < values.length; j++)
      {
         sum -= values [j - chunksize];
         sum += values [j];
         if (maximum < sum)
             maximum = sum;
      }
      return maximum;  
   }

   public static void main (String[] args) {
      MaxChunk maxChunk = new MaxChunk ();
      int values[] = maxChunk.readValues ();
      System.out.println (maxChunk.calc (values));
   }
}

echo "3 9 2 4 6 4 3 2 4 4 5 6 9 3 2 1 9 9" | java MaxChunk

返回14。

- user unknown

---

这段代码不是我写的（它不遵守我们的规约）。 "nb_values" 在这里的意思是 "值的数量"。 我用更好的变量名进行了编辑。 这个练习的目的是尽可能少地使用内存（我们想要一个长度为 chunksize 的数组，不要超过这个长度），因此在之后释放它并没有什么帮助。 - Loïc Février