Java, использование памяти для "Сканера"

Question

Я использую онлайн-платформу для автоматической оценки программ, и для одного из упражнений «сканер» Java использует слишком много памяти (мы только начинаем поддерживать Java, поэтому проблема не возникала раньше).Поскольку мы преподаем алгоритмику начинающим, мы не можем просто попросить их перекодировать их самостоятельно, читая один байт за другим.

Согласно нашим тестам, сканер использует до 200 байт для чтения ОДНОГОцелое число ...

Упражнение: 10 000 целых чисел, какое окно из 100 последовательных целых чисел имеет максимальную сумму?

Использование памяти мало (вам нужно запомнить только последние 100 целых чисел)но между классической версией с «Scanner / nextInt ()» и ручной версией (см. ниже) мы можем видеть разницу в 2,5 МБ в памяти.

2,5 МБ для чтения 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,5 МБ
• 20 000: 5 МБ
• 50 000: 15 МБ
• 100 000: 30 МБ
• 200 000: 50 МБ
• 300 000: 75 МБ

Answer 1

Мы наконец решили переписать (частично) класс Scanner.Таким образом, нам нужно только включить наш сканер вместо Java, а остальная часть кода остается прежней.У нас больше нет проблем с памятью, и программы работают в 20 раз быстрее.

Приведенный ниже код принадлежит одному из моих коллег Кристофу Дюрру:

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

еще быстрее, интегрировав код в моем вопросе, где мы «строим» числа, читая символы после символа.

Answer 2

Я сталкивался с этим вопросом при исследовании серьезного раздувания памяти в разрабатываемом приложении Android.

В Android есть инструмент для регистрации всех выделений.

Оказывается, что для разбора простоодин вызов nextDouble (), Java делает 128 выделений.Верхние 8 имеют размер более 1000 байтов, самый большой - 4102 байта (!)

Излишне говорить, что это абсолютно непригодно.Мы изо всех сил пытаемся сохранить низкий уровень заряда батареи, это действительно не помогает.

Я постараюсь использовать опубликованный код замены сканера, спасибо!

Вот доказательства:

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 Device Monitor это не указано).

Итог: не используйте сканер, если у вас нетмного энергии и процессора, чтобы сэкономить.

Answer 3

Вы можете прочитать все значения в массив, а затем начать суммирование по массиву.

При чтении массива вам все равно потребуется столько памяти, но после чтения он будет свободен для других целей.

Структура вашего кода выиграет, imho, потому что теперь вы можете использовать другой источник для ваших чисел - например, util.Random, и все равно искать в массиве наибольшую сумму или искать в том же массиве для разных длин последовательности , без перечитывания ввода.

Кстати: мне было трудно читать код, потому что:

• значение / значения / sumValues ​​/ nb_values ​​- (почему не MaximumValues)? - все переменные являются значениями, поэтому это не помогает понять.
• циклы обычно индексируются с i и j или n. Значение вводит в заблуждение
• length_sequence также вводит в заблуждение. длина последовательности подразумевается, но все будут использовать только «длину», так как нет никакой разницы с другими длинами.
• Вы используете длинные имена для тривиальных вещей, но загадочное сокращение для не очень тривиальных. Я прочитал ваше описание проблемы и код и не знаю, что делает ваш код: что вы подразумевали под nb_values. Неблокируемый? Null-Byte? Рядом, поблизости? Что это?

Мое первое впечатление было, что для последовательности Ints:

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.

Answer 4

Это код для 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());
    }
}

Как вы можете видеть, он работает с особыми знаками и знаками, использует кеширование и т. Д. Таким образом, дополнительное использование памяти зависит от функциональности, разработанной для повышения эффективности сканера.