Help figure out.

There is a Yandex.Contest task – removal of duplicates.

– Condition:

Dan one-time array of 32-bit numbers.
It is required to remove all repetitions from it.

It is advisable to get a solution that does not read the input file entirely
In memory, i.e. uses only a constant amount of memory in the process.
Work.

– input format:

The first line of the input file contains the only number N, N ≤
1000000.

On the following n strings are numbers – elements of the array, one by one
on the string. Numbers are sorted by inconsideration. Output format

The output file must contain the following in ascending order.
Unique elements of the input massif.

My decision does not pass to exceed the limit of the memory (must be no more than 20MB, with my decision 20+ – 22MB)

found Decision from Githab, it passes (occupied 16MB memory )

Can someone explain the principal difference.

ps.

I tried to solve through String (compare via Equal).

I tried to solve through an array of charms (created its own function Equal).

Trim () also used.

With all attempts, the result is the same (20 -22MB).

My code:

import java.io.bufferedReader;
Import java.io.InputStreamReader;
Public Class First {
  Public Static Void Main (String [] Args) Thrown Exception {
    BufferedReader Reader = New BufferedReader (new inputStreamReader (System.in));
    int Range = Integer.Parseint (Reader.ReadLine ());
    if (Range & lt; 1) Return;
    int number = integer.paraseint (Reader.ReadLine ());
    INT NEXTNUMBER;
    For (int i = 0; i & lt; Range-1; I ++) {
      NextNumber = Integer.Parseint (Reader.ReadLine ());
      if (Number! = NEXTNUMBER) {
        System.Out.printLN (Number);
      }
      Number = NextNumber;
    }
    System.Out.printLN (Number);
  }
}

Code from Githab:

mport java.io. *;
Public Class TaskcSolution {
  Private Static Final String File_input = "Input.txt";
  Private Static Final String File_Output = "Output.txt";
  Private Static BufferedReader BufferedReader = NULL;
  Private Static BufferedWriter BufferedWriter = NULL;
  Private Static int max_char_array_size = 15;
  Public Static Void Main (String [] Args) Thrown Exception {
    init ();
    run ();
    Close ();
  }
  Private Static Void Init () Throws IoException {
    BufferedReader = New BufferedReader (New FileReader (File_Input));
    BufferedWriter = New BufferedWriter (New FileWriter (File_Output));
  }
  Private Static Void Run () Throws IoException {
    int n = integer.valueof (string.valueof (readline ()). Trim ());
    if (N & LT; 1) Return;
    char [] m = writeline (readline ());
    char [] l = m;
    int i = 1;
    While (I & LT; N) {
      m = readline ();
      if (! Equals (M, L)) L = Writeline (M);
      ++ I;
    }
  }
  Private Static Void Close () Throws IoException {
    bufferedwriter.close ();
    bufferedreader.close ();
  }
  Private Static Char [] ReadLine () Throws IoException {
    char [] res = new char [max_char_array_size];
    INT COUNT = 0;
    While (True) {
      int b = buffereder.read ();
      if (b == '\ n' || b == -1) break;
      if (b == '\ r') continue;
      Res [Count] = (char) b;
      COUNT ++;
    }
    RETURN RES;
  }
  Private Static Char [] Writeline (Char [] Inttofile) Throws IoException {
    bufferedwriter.write (inttofile);
    bufferedwriter.newline ();
    Return inttofile;
  }
  Private Static Boolean Equals (Char [] Chars1, Char [] Chars2) Throws IoException { 
For (int i = 0; i & lt; max_char_array_size; ++ i) {
      If (Chars1 [i]! = Chars2 [i])
        RETURN FALSE;
    }
    RETURN TRUE;
  }
}

Answer 1

I also spent a lot of time on this task. Redid the code completely on static calls, removed the creation of new objects. I tried even periodically call System.gc () 🙂
But it turned out that the key point was the care of using System.in and System.out .

The reduced solution allows you to meet in time and memory limitations with a reserve (251ms and 10.87Mb). So, of course, it should not be written in the general case to Java, but the performance is the same ..

import java.io. *;
Public Class Solution {
  STATIC FINAL INT MAX_INT_LENGTH = 12;
  STATIC FINAL STRING INPUT = "INPUT.TXT";
  STATIC FINAL STRING OUTPUT = "OUTPUT.TXT";
  Static BufferedReader R;
  static bufferedwriter w;
  Static Final Char [] Curr = New Char [max_int_length];
  Static Final Char [] Prev = New Char [Max_int_LengTh];
  Public Static Void Main (String ... Args) Throws IoException {
    R = New BufferedReader (New FilerEader (INPUT));
    w = new BufferedWriter (New FileWriter (Output);
    int n = integer.paraseint (r.Readline ());
    if (N & LT; 1) Return;
    readcurr ();
    copycurrtoprev ();
    printcurr ();
    For (int i = 0; i & lt; n - 1; i ++) {
      readcurr ();
      If (! currequalsprev ()) {
        printcurr ();
        copycurrtoprev ();
      }
    }
    R.Close ();
    W.Close ();
  }
  Private Static Void ReadCurr () Throws IoException {
    int b = 0;
    For (int i = 0; i & lt; max_int_length; i ++) {
      B = R.Read ();
      if (b & lt; 0) {
        Curr [i] = '\ n';
        Break;
      }
      Curr [i] = (char) b;
      if (b == '\ n') break;
    }
  }
  Private Static Void Printcurr () Throws IoException {
    For (int i = 0 ;; I ++) {
      w.Write (Curr [i]);
      if (Curr [i] == '\ n') break;
    }
  }
  Private Static Boolean Currequalsprev () {
    For (int i = 0; i & lt; max_int_length; i ++) {
      if (Curr [i]! = Prev [i]) Return False;
      if (Curr [i] == '\ n') break;
    }
    RETURN TRUE;
  }
  Private Static Void CopyCurrtoprev () {
    For (int i = 0; i & lt; max_int_length; i ++) {
      PREV [I] = CURR [I];
      if (Curr [i] == '\ n') break;
    }
  }
}

Answer 2

Here is my solution – 162ms 8.76MB. Everything comes down to low-level operations.

import java.io. *;
Import java.util.arrays;
Public Class Contest {
  Public Static Void Main (String ... Args) Thrown Exception {
    BYTE [] Buffer = New Byte [128];
    Byte [] LastValue = New Byte [128];
    INT LastValuesize = 0;
    Try (BufferedInputStream BIS = New BufferedInputStream (New FileInputStream ("Input.txt"), 8192);
       BufferedOutputStream BOS = New BufferedoutStream (New FileoutPutStream ("Output.txt"), 8192)) {
      INT COUNTVALUSIZE = ReadValue (BIS, Buffer);
      INT COUNT = INTEGER.PARSEINT (ArrayS.Copyofrange (Buffer, 0, CountValueSize)));
      For (int i = 0; I & lt; Count; I ++) {
        INT NEXTVALUESIZE = ReadValue (BIS, BUFFER);
        if (i == 0 ||! ISVALUESEQUAL (Buffer, NextValuesize, LastValue, LastValuesize)) {
          Bos.Write (Buffer, 0, NextValuesize);
          bos.write ('\ n');
          System.ArrayCopy (Buffer, 0, LastValue, 0, NextValueSize);
          LastValueSize = NextValuesize;
        }
      }
    }
  }
  Private Static Int ReadValue (InputStream IS, Byte [] Buffer) Throws IoException {
    INT Counter = 0;
    int i;
    While ((i = is.read ())! = '\ n' & amp; & amp; i & gt; 0) {
      Buffer [Counter ++] = (byte) i;
    }
    RETURN COUNTER;
  } 
Private Static Boolean Isvaluesequal (Byte [] First, int FirstSize, Byte [] Second, Int Secondsize) {
    If (FirstSize! = Secondsize) {
      RETURN FALSE;
    }
    For (int i = 0; i & lt; firstSize; i ++) {
      IF (first [i]! = Second [i]) {
        RETURN FALSE;
      }
    }
    RETURN TRUE;
  }
}

Answer 3

Also, forbid all the tests for a long time, read the answer here, changed in his decision that did not take place the 193th memory test reading from System.in to read and write to files, when choosing a compiler Oracle Java 7 this decision is accepted As a correct, when choosing a compiler Oracle Java 8, the same solution gets an error to exceed memory limit on the 193th test.
What a little is alarming, it was similar and on another task – D – generation of bracket sequences.

import java.io.bufferedReader;
Import java.io.bufferedwriter;
Import java.io.FileReader;
Import java.io.FileWriter;
Public Class Third {
  STATIC FINAL STRING INPUT = "INPUT.TXT";
  STATIC FINAL STRING OUTPUT = "OUTPUT.TXT";
  Static BufferedReader Br;
  Static BufferedWriter BW;
  Public Static Void Main (String [] Args) Thrown Exception {
    Br = New BufferedReader (NEW FILEREADER (INPUT));
    BW = New BufferedWriter (New FileWriter (Output));
    int n = integer.valueof (Br.Readline ());
    String Last = "";
    STRING CURR = LAST;
    For (int i = 0; i & lt; n; i ++) {
      Curr = Br.ReadLine (). Intern ();
      If (Last! = Curr) {
        Last = Curr;
        BW.WRITE (CURR);
        bw.write ('\ n');
      }
    }
    Br.Close ();
    bw.close ();
  }
}