NIEKOLEJ - Niekolejne [JAVA]

[kamf3th]

Witam, mam pytanie odnośnie zadania “Niekolejne” dla języka programowania Java.

SPOJ.com - Problem NIEKOLEJ

Problem polega na tym, że nie mogę zmieścić się w przedziale czasowym wysyłając rozwiązanie dla języka Java. Dodam, że program prawidłowo rozwiązuje problem, ponieważ wcześniej rozwiązałem ten problem przy użyciu C++ i zwróciło AC. Próbowałem używać różnych sztuczek przyśpieszających I/O, typu szybsze wczytywanie danych, szybsze wyświetlanie danych, zapisywanie liczb w łańcuchu a potem jednorazowy odczyt jego, wszystkie próby zawiodły.

Mój kod (bez uwzględniania wyżej wymienionych sztuczek) wygląda następująco:

import java.util.Scanner;

class Niekolejne {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        if (n == 1 || n == 2)
            System.out.print("NIE");
        else {
            for (int i = n - 1; i >= 0; i -= 2)
                System.out.print(i + " ");
            for (int i = n; i >= 0; i -= 2)
                System.out.print(i + " ");
        }
    }
}

Moje pytanie brzmi, jak mogę poprawić działanie tego kodu pod względem optymalizacji czasowej? Co mogę zrobić, aby go choć odrobinę jeszcze przyśpieszyć?

[mariusz193]

można użyć klasy StringBuilder, to znacznie przyspiesza - ale dla tego zadania raczej nie wystarczy, wyprowadzanie danych w Java jest wolne a tu trzeba wysłać około 7 MB w 0,1 sekundy (a to chyba jest już mniej niż wykonanie pustego programu w Java)

[paweliszcz_20k]

Ogólnie rzecz biorąc to dla Javy chyba jest osobna kategoria czasowa dla tego zadania:

POLSKI SPOJ: test your programming skills on-line

Ja Dostałem AC pomimo czasu 0,4.
Potwierdzam -> StringBuilder oraz fast I/O - bez tego ani rusz.
Fast I/O np -> BufferedReader, Outpustream

[narbej]

dla Javy chyba jest osobna kategoria czasowa dla tego zadania

Nie, nie ma. To jest wynik - suma czasów wszystkich testów. Gdyby było np 10 testów każdy z limitem 0.1, a twój program ledwo ledwo by się “wyrabiał” na każdym, to mógłbyś uzyskać sumaryczny czas nawet 1.00. Z drugiej strony, szybki program, który każdy test robiłby z czasem 0.00 [prawdopodobnie dokładniej z czasem mniejszym niż 0.005] to suma takich [zaokrąglanych/ucinanych] czasów jest/byłaby dalej równa 0.00

[kamf3th]

Byłbyś w stanie pokazać mi jak dokładnie użyłeś klasy Outputstream pod SPOJa?

[paweliszcz_20k]

Polecam linki

What's the fastest way to output a string to system out?

Fast I/O in Java in Competitive Programming - GeeksforGeeks

[kamf3th]

Czytałem i jeden i drugi wcześniej, ale dzięki i tak, później jeszcze raz sprawdze te informacje ze stack’a.

[paweliszcz_20k]

ja “jadę” na tej propozycji stack’owej i nie narzekam

[kamf3th]

import java.io.*;

class Niekolejne {
    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        int n = in.nextInt();
        StringBuilder str = new StringBuilder();
        if (n == 1 || n == 2)
            str.append("NIE");
        else {
            for (int i = n - 1; i >= 0; i -= 2)
                str.append(i + " ");
            for (int i = n; i >= 0; i -= 2)
                str.append(i + " ");
        }
        OutputStream out = new BufferedOutputStream(System.out);
        out.write((str.toString()).getBytes());
        out.flush();
    }
}

class Reader {
    final private int BUFFER_SIZE = 1 << 16;
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer;
    private int bytesRead;

    public Reader() {
        din = new DataInputStream(System.in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do
            ret = ret * 10 + c - '0';
        while ((c = read()) >= '0' && c <= '9');
        if (neg)
            return -ret;
        return ret;
    }

    private byte read() throws IOException {
        if (bufferPointer == bytesRead)
            fillBuffer();
        return buffer[bufferPointer++];
    }

    private void fillBuffer() throws IOException {
        bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
        if (bytesRead == -1)
            buffer[0] = -1;
    }
}

Przeczytałem obydwa linki które mi podałeś (oraz inne, która sam odnalazłem w sieci), jednak po licznych próbach dalej mój program działa za wolno. Wyżej umieszczam mój obecny kod, czy mógłbyś na niego zerknąć i doradzić mi co robię źle, lub w jaki sposób mogę to jeszcze przyśpieszyć? Klasa Reader powinna działać szybciej niż wbudowana klasa BufferedReader dlatego jej tutaj użyłem.

[paweliszcz_20k]

No cześć. Według tego artykułu na geeksforgeeks klasa reader powinna być szybsza. Ale pytanie czy w tym wypadku tak jest? Tutaj chodzi o przeczytanie tylko 1 liczby. Szczerze powiem, że nie wiem. Bo (jeszcze) nie jestem takim szpecem od Javy żeby teraz analizować czy taka implementacja klasy reader będzie tutaj rzeczywiście lepsza. Natomiast przetestowałem sobie Twój kod na ideone i porównywałem do swojego. I dla liczb rzędu 4k-8k mój kod był zawsze o kilka setnych sekundy szybszy. Mój algorytm jest tak naprawdę analogiczny do Twojego. Poza tym korzystałem też ze stringbuildera oraz bufferedoutputstream’a i bufferedreader’a. Więc tutaj raczej doszukiwałbym się problemu w niedokładnej implementacji tej klasy reader.
(ewentualnie nie wiem czy ostatniej spacji nie trzeba by usunąć)
ew. może szybsze jest str.append(i).append(" ");

[kamf3th]

Pamiętam, że sprawdzałem wcześniej też str.append(i).append(" "); jednak dalej limit czasu był przekroczony. Spróbuję jeszcze raz i użyje obydwu klas buffered o których wspomniałeś, jednak tak myślę, czy nie byłoby to problemem gdybyś po prostu pokazał mi swój kod w prywatnej wiadomości. Wtedy bym to bardziej atomowo porównał jak to wygląda i wyciągnął ciekawe wnioski na przyszłość.

[kamf3th]

import java.io.*;

class Niekolejne {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        StringBuilder str = new StringBuilder();
        if (n == 1 || n == 2)
            str.append("NIE");
        else {
            for (int i = n - 1; i >= 0; i -= 2)
                str.append(i).append(" ");
            for (int i = n; i >= 0; i -= 2)
                str.append(i).append(" ");
        }
        OutputStream out = new BufferedOutputStream(System.out);
        out.write((str.toString()).getBytes());
        out.flush();
    }
}

Dalej za wolno, choć wersja z podwójnym wywołaniem metody append zużyła trochę mniej pamięci.

Byłbyś w stanie poratować swoim kodem? Nie mam już pomysłów.

[paweliszcz_20k]

Szczerze mówiąc to teraz poza tym, że ja iteruje od 0 do n i deklaracje obiektów mam prawilnie tuż pod main’em to kody mamy identyczne.

[paweliszcz_20k]

Żeby było śmiesznie to ja teraz też dostaję TLE

[paweliszcz_20k]

Tak myślę czy nie lepiej jednak dać pętli while na początek

[kamf3th]

Wcześniej miałeś AC na kompilatorze z Java 12 prawda? Wcześniej SPOJ miał kompilator z Java 8 i z moich testów wyszło, że te same programy napisane na SPOJu wolniej działają na tym odświeżonym kompilatorze niż na Java 8. Dlatego niektóre starsze kody z Javy, które kiedyś wystarczyły do AC mogą obecnie być za wolne.

[kamf3th]

Nie myślałem o użyciu while, spróbuję jutro. Gdzieś czytałem, że podobno można ten problem rozwiązać stosując tylko jedną pętle i to na pewno przyśpieszy program, wydaje mi się, że rzeczywiście jest to możliwe, tylko kod będzie trochę mniej czytelny.

Bardzo ciekawie się zaczyna robić

[paweliszcz_20k]

pętla while nie pomogła, ten szybki reader też nie, sądzę, że trzeba by znaleźć jakiś ultra fast output bo jakby nie było dla dużych liczb jest dosyć długa linia do wydruku

[paweliszcz_20k]

Z pętlą while to chodziło mi o ewentualne czytanie kolejnych linii testów. Ale nie o to chodziło.

Rzeczywiście można to zrobić 1 pętlą for. Nie będę mówił jak żeby nie psuć Ci zabawy :). Podpowiem tylko, że trzeba sprawdzić 0 i parzystość.

Na 1 pętli for oraz “standardowo” bufferedreader, bufferedoutputstream, i stringbuilder dostałem AC - z gorszym czasem niż poprzednio ale jednak AC.
Ale żeby znowu było śmiesznie 10min później dokładnie tym kodem dostałem TLE.
Także życzę miłej zabawy :).