Sto provando il problema The Next Palindrome dal Giudice Sphere Online (SPOJ) in cui ho bisogno di trovare un palindromo per un numero intero di un milione di cifre. Ho pensato di usare le funzioni di Java per invertire le stringhe, ma avrebbero permesso che una stringa fosse così lunga?Quanti caratteri può avere una stringa Java?
Si dovrebbe essere in grado di ottenere una stringa di lunghezza Integer.MAX_VALUE (sempre 2147483647 (2 -1) dalla specifica Java, la dimensione massima di un array, che la classe String utilizza per la memoria interna) o la metà del vostro dimensione massima dell'heap (poiché ogni carattere è di due byte), qualunque sia il più piccolo.
... o la dimensione massima dell'heap divisa per 2 ... poiché il carattere è 2 byte – ChssPly76
@ ChssPly76: Sì, è corretto. Ho modificato la mia risposta, grazie. –
come individuare la dimensione massima dell'heap? Inoltre, non so quale macchina virtuale java che il giudice sta usando per testare il mio problema è la parte Integer.MAX_VALUE delle specifiche di JVM dipendenti? – andandandand
Credo che possano essere fino a 2^31-1 caratteri, in quanto sono tenuti da un array interno e gli array sono indicizzati da numeri interi in Java.
L'implementazione interna è irrilevante - non c'è motivo per cui i dati dei personaggi non possano essere archiviati in una serie di long, per esempio. Il problema è che l'interfaccia usa gli int per la lunghezza. 'getBytes' e simili potrebbero avere problemi se si tenta una stringa molto grande. –
Questo è vero - stavo insinuando questo fatto. Colpa mia. – aperkins
Integer.MAX_VALUE è la dimensione massima di stringa + dipende della vostra dimensione della memoria, ma il problema sul giudice in linea della sfera non devi usare quelle funzioni
Hai pensato di usare BigDecimal invece di String per contenere i numeri ?
Dipende da cosa l'applicazione farà con i numeri. Se sta per fare solo cose testuali come trovare i palindromi, contare cifre (decimali), allora una stringa è meglio. Se sta per fare aritmetica, un BigDecimal (o BigInteger) è migliore. –
Il problema è "Per ogni K, emette il palindromo più piccolo maggiore di K." (dove K è il numero indicato). Sarebbe banalmente semplice produrre il primo palindromo più piccolo di K. Hai bisogno dell'aritmetica per trovare uno più grande di K. Esempio: Trova il prossimo palindromo più grande di 999999999999, o il successivo palindromo più grande di 12922. –
La parte heap peggiora, amici miei. UTF-16 non può essere limitato a 16 bit e può espandersi a 32
Tranne il tipo 'char' di Java è 16 bit esattamente, quindi il numero di bit UTF-16 utilizzati non ha molta importanza ... – awksp
Se si utilizza il motore di app di google, com.google.appengine.api.datastore.Text può essere d'aiuto. Consente a una singola stringa di archiviare fino a 1 megabyte.
La stringa può già memorizzare fino a 2 GB, quindi una classe che può memorizzare fino a 1 MB non aiuta in questo caso. –
Sarebbe utile se si includesse un collegamento a una pagina Web che spiegasse questo in maggiore dettaglio e ampliato sulla risposta –
Mentre è possibile in teoria caratteri Integer.MAX_VALUE, la JVM è limitata nelle dimensioni dell'array che può utilizzare.
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);
}
}
}
su Oracle Java 8 aggiornamento 92 stampe
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
Nota: in Java 9, Archi utilizzerà byte [] il che significa che i caratteri multi-byte useranno più di un byte e ridurre il massimo ulteriore. Se disponi di tutti e quattro i code-point di byte, ad es. emoji, otterrai solo circa 500 milioni di caratteri
[Stringhe compatte] (http://openjdk.java.net/jeps/254) in Java 9 utilizzare sia Codifica Latin-1 o UTF-16. Nessuna codifica di lunghezza variabile, ovvero nessun carattere di tre byte. – apangin
@apangin "Non è un obiettivo utilizzare codifiche alternative come UTF-8" grazie per la correzione. –
Java9 utilizza il byte [] per memorizzare String.value, quindi puoi ottenere circa 1GB di stringhe in Java9. Java8 d'altra parte può avere stringhe da 2GB.
Per carattere intendo "char", alcuni caratteri non sono rappresentabili in BMP (come alcuni degli emoji), quindi saranno necessari più (attualmente 2) caratteri.
stai dicendo che è necessario scrivere una funzione che genera palindromi, la cui dimensione è specificata dall'utente e può avere una lunghezza massima di 1 milione di caratteri? – Robert
Il * problema * (da SPOJ) può contenere un file da 100 GB e ti piacerebbe caricarlo in una stringa in una volta? Seriamente ... per favore usa uno scanner! –
Possibile duplicato di [Lunghezza massima della stringa nel metodo Java - length length()] (https://stackoverflow.com/questions/816142/strings-maximum-length-in-java-calling-length-method) – Bergi