Ile znaków może mieć ciąg Java?

157

Próbuję rozwiązać problem z następnym palindromem z Sphere Online Judge (SPOJ), gdzie muszę znaleźć palindrom dla liczby całkowitej do miliona cyfr. Myślałem o użyciu funkcji Java do odwracania ciągów znaków, ale czy pozwoliłyby na to, aby String był tak długi?

java string

— andandandand
źródło

czy mówisz, że musisz napisać funkcję generującą palindromy, których rozmiar jest określany przez użytkownika i może mieć do 1 miliona znaków?

— Robert,

3

Problem (od SPOJ) może zawierać plik 100Gigabyte, a chcesz załadować go na sznurku na raz? Poważnie ... użyj skanera!

— Ponury

Możliwy duplikat maksymalnej długości łańcucha w Javie - wywołanie metody length ()

— Bergi

242

Powinieneś być w stanie uzyskać ciąg o długości

Integer.MAX_VALUEzawsze 2,147,483,647 (2 ³¹ - 1)
(zdefiniowany w specyfikacji Java, maksymalny rozmiar tablicy, której klasa String używa jako pamięci wewnętrznej)
LUB
Half your maximum heap size(ponieważ każdy znak ma dwa bajty) w zależności od tego, który jest mniejszy .

— Bill the Lizard
źródło

43

... lub twój maksymalny rozmiar sterty podzielony przez 2 ... ponieważ znak ma 2 bajty

— ChssPly76

2

@ ChssPly76: Tak, zgadza się. Zredagowałem odpowiedź, dziękuję.

— Bill the Lizard

2

jak sprawdzić maksymalny rozmiar sterty? Ponadto nie wiem, która maszyna wirtualna Java jest używana przez sędziego do testowania mojego problemu. Jest to część Integer.MAX_VALUE w specyfikacji zależna od JVM?

— andandandand

6

Integer.MAX_VALUE to zawsze 2147483647 (2 ^ 31 - 1), to część specyfikacji Java.

— cd1

4

Zakładając 64-bitową maszynę JVM, ponieważ do przechowywania ciągu o takiej długości potrzeba 8 GB pamięci wirtualnej.

— Robert Fraser

21

Uważam, że mogą mieć maksymalnie 2 ^ 31-1 znaków, ponieważ są przechowywane przez wewnętrzną tablicę, a tablice są indeksowane przez liczby całkowite w Javie.

— aperkins
źródło

Wewnętrzna implementacja jest nieistotna - nie ma powodu, dla którego dane znakowe nie mogłyby być przechowywane na przykład w tablicy długich znaków. Problem polega na tym, że interfejs używa wartości typu ints jako długości. getBytesi podobne mogą mieć problemy, jeśli spróbujesz uzyskać bardzo duży ciąg.

— Tom Hawtin - tackline

To prawda - sugerowałem ten fakt. Mój błąd.

— aperkins

15

Chociaż teoretycznie można używać znaków Integer.MAX_VALUE, maszyna JVM jest ograniczona pod względem rozmiaru tablicy, z której może korzystać.

public static void main(String... args) {
    for (int i = 0; i < 4; i++) {
        int len = Integer.MAX_VALUE - i;
        try {
            char[] ch = new char[len];
            System.out.println("len: " + len + " OK");
        } catch (Error e) {
            System.out.println("len: " + len + " " + e);
        }
    }
}

na Oracle Java 8 Update 92

len: 2147483647 java.lang.OutOfMemoryError: Requested array size exceeds VM limit
len: 2147483646 java.lang.OutOfMemoryError: Requested array size exceeds VM limit
len: 2147483645 OK
len: 2147483644 OK

Uwaga: w Javie 9, łańcuchy znaków będą używać bajtu [], co oznacza, że znaki wielobajtowe będą wykorzystywać więcej niż jeden bajt i dalej zmniejszać maksimum. Jeśli masz wszystkie czterobajtowe punkty kodowe, np. Emoji, otrzymasz tylko około 500 milionów znaków

— Peter Lawrey
źródło

2

Kompaktowe ciągi w Javie 9 używają kodowania Latin-1 lub UTF-16. Bez kodowania o zmiennej długości, czyli bez znaków trzy bajtowych.

— apangin

@apangin "Nie jest celem używanie alternatywnych kodowań, takich jak UTF-8", dziękuję za korektę.

— Peter Lawrey

5

Czy rozważałeś używanie BigDecimalzamiast Stringtrzymania swoich liczb?

— Thorbjørn Ravn Andersen
źródło

1

To zależy od tego, co aplikacja zrobi z liczbami. Jeśli ma zamiar robić tylko rzeczy tekstowe, takie jak znajdowanie palindromów, zliczanie (dziesiętnych) cyfr, to String jest lepszy. Jeśli ma wykonywać arytmetykę, lepsza jest BigDecimal (lub BigInteger).

— Stephen C,

Problem polega na tym, że „dla każdego K wypisz najmniejszy palindrom większy niż K.” (gdzie K jest podaną liczbą). Wyprowadzenie pierwszego palindromu mniejszego niż K. Wymagałoby zastosowania arytmetyki, aby znaleźć jeden większy niż K. Przykład: Znajdź następny palindrom większy niż 999999999999 lub następny palindrom większy niż 12922.

— Thorbjørn Ravn Andersen

4

Integer.MAX_VALUE to maksymalny rozmiar ciągu + zależy od rozmiaru twojej pamięci, ale problem z sferą online oceniający nie musisz używać tych funkcji

— Mite Mitreski
źródło

3

Java9 używa bajtu [] do przechowywania wartości String.value, więc w Java9 można uzyskać tylko około 1 GB ciągów znaków. Z drugiej strony Java8 może mieć ciągi 2 GB.

Przez znak mam na myśli "znaki", niektóre znaki nie są reprezentowane w BMP (jak niektóre z emotikonów), więc zajmie więcej (obecnie 2) znaków.

— Revin
źródło

4

Czy możesz dołączyć odniesienie do języka Java-9 ograniczającego rozmiar ciągu do 1 GB z 2 GB

— Aditya Gupta

-1

Część sterty się pogarsza, przyjaciele. Nie ma gwarancji, że UTF-16 będzie ograniczony do 16 bitów i może rozszerzać się do 32

— Joe Plante
źródło

2

Z wyjątkiem Java chartyp jest dokładnie 16 bitów, więc liczba bitów używa UTF-16 nie ma znaczenia ...

— awksp