我正在运行一个在线自动程序评估平台,并且对于其中一个练习,Java“扫描仪”使用了过多的内存(我们刚刚开始支持 Java,所以之前没有出现过这个问题)。由于我们是在向初学者教授算法,因此我们不能只要求他们通过一个字节一个字节地读取来自己重新编码。
根据我们的测试,扫描器最多使用 200 字节来读取一个整数...
练习:10 000 个整数,100 个连续整数中哪个窗口的总和最大?
内存使用量很小(您只需要记住最后 100 个整数)但是在带有“Scanner/nextInt()”的经典版本和手动版本(见下文)之间我们可以看到 2.5 Mb 的内存差异.
2.5 Mb 读取 10 000 个整数 ==> 200 字节读取一个整数??
是否有任何可以向初学者解释的简单解决方案,或者是否可以使用以下功能(或类似功能)?
我们的测试函数可以更快地读取整数,同时使用更少的内存:
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;
}
根据要求使用扫描仪的代码:
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
最佳答案
我们最终决定重写(部分)Scanner 类。这样我们只需要包含我们的扫描器而不是 Java 的扫描器,其余代码保持不变。我们不再有任何内存问题,程序速度提高了 20 倍。
下面的代码来 self 的一位同事 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) {}
}
通过将代码集成到我的问题中,我们通过一个接一个地读取一个字符来“构建”数字,可能会更快。
关于Java, "Scanner"的内存使用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8135903/