Ich versuche The Next Palindrome Problem von Sphere Online Judge (SPOJ), wo ich ein Palindrom für eine ganze Zahl von bis zu einer Million Ziffern finden muss. Ich habe überlegt, Java-Funktionen zum Umkehren von Strings zu verwenden, aber würden sie zulassen, dass ein String so lang ist?Wie viele Zeichen kann eine Java-Zeichenfolge haben?
Sie sollten in der Lage sein, einen String der Länge zu erhalten Integer.MAX_VALUE (immer 2147483647 (2 -1) von der Java-Spezifikation, die maximale Größe eines Arrays, die die String-Klasse für die internen Speicher verwendet) oder die Hälfte Ihrer Maximale Heap-Größe (da jedes Zeichen zwei Bytes ist), je nachdem, welcher Wert kleiner ist.
... oder Ihre maximale Heap-Größe geteilt durch 2 ... da das Zeichen 2 Byte ist – ChssPly76
@ ChssPly76: Ja, das ist richtig. Ich habe meine Antwort bearbeitet, danke. –
Wie finde ich die maximale Größe des Heapspeichers heraus? Außerdem weiß ich nicht, welche Java Virtual Machine der Richter verwendet, um mein Problem zu testen ist Integer.MAX_VALUE Teil der Spezifikation von JVM abhängig? – andandandand
Ich glaube, sie können bis zu 2^31-1 Zeichen, da sie von einem internen Array gehalten werden, und Arrays werden von Ganzzahlen in Java indiziert.
Die interne Implementierung ist irrelevant - es gibt keinen Grund, warum die Zeichendaten nicht in einem Array von Longs gespeichert werden könnten. Das Problem ist, dass die Schnittstelle Längen verwendet. 'getBytes' und ähnliche können Probleme haben, wenn Sie nach einer sehr großen Zeichenfolge suchen. –
Das stimmt - ich deutete diese Tatsache an. Mein Fehler. – aperkins
Integer.MAX_VALUE maximale Größe der Zeichenfolge + Ihrer Speichergröße hängt aber das Problem auf Online-Richter Sphäre Sie
diese Funktionen nichtHaben Sie statt String betrachtet mit BigDecimal verwenden müssen, um Ihre Zahlen zu halten ?
Es hängt davon ab, was die Anwendung mit den Nummern machen wird. Wenn es nur textliche Dinge wie das Finden von Palindromen oder das Zählen von (Dezimal-) Ziffern gibt, dann ist ein String besser. Wenn es um Arithmetik geht, ist ein BigDecimal (oder BigInteger) besser. –
Das Problem ist "Gib für jedes K das kleinste Palindrom aus, das größer als K ist." (wobei K die angegebene Zahl ist). Es wäre trivial einfach, das erste Palindrom kleiner als K auszugeben. Du benötigst Arithmetik, um eins größer als K zu finden. Beispiel: Finde das nächste Palindrom größer als 999999999999 oder das nächste Palindrom größer als 12922. –
Der Haufen Teil wird schlechter, meine Freunde. UTF-16 ist nicht garantiert auf 16 Bit beschränkt und kann auf 32 erweitert werden
Außer Javas "char" -Typ ist 16 Bits genau, also ist die Anzahl der Bits, die UTF-16 verwendet, nicht wirklich wichtig ... – awksp
Wenn Sie die App-Engine von Google verwenden, kann com.google.appengine.api.datastore.Text helfen. Es ermöglicht eine einzelne Zeichenfolge, bis zu 1 Megabyte zu speichern.
String kann bereits bis zu 2GB speichern, also hilft eine Klasse, die bis zu 1MB speichern kann, hier nicht. –
Es wäre hilfreich, wenn Sie einen Link zu einer Webseite einfügen, der dies ausführlicher erklärt, und auf Ihre Antwort –
Während Sie theoretisch Integer.MAX_VALUE Zeichen können, ist die JVM in der Größe des Arrays beschränkt, das es verwenden kann.
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);
}
}
}
auf Oracle Java 8 Update 92 druckt
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
Hinweis: in Java 9 wird Strings verwenden byte [], die das Multi-Byte-Zeichen bedeuten wird mehr als ein Byte verwenden und die Verringerung Maximum weiter. Wenn Sie alle vier Byte-Code-Punkte z.B. Emojis, Sie werden nur rund 500 Millionen Zeichen erhalten
[Compact Strings] (http://openjdk.java.net/jeps/254) in Java 9 verwenden Latin-1 oder UTF-16-Codierung. Keine Codierung mit variabler Länge, dh keine drei Byte langen Zeichen. – apangin
@apangin "Es ist kein Ziel, alternative Kodierungen wie UTF-8 zu verwenden" danke für die Korrektur. –
Java9 verwendet Byte [], um String.value zu speichern, so dass Sie nur etwa 1GB Strings in Java9 erhalten können. Java8 hingegen kann 2GB Strings haben.
Mit Charakter meine ich "Char" s, einige Zeichen sind nicht in BMP darstellbar (wie einige der Emojis), so dass es mehr (derzeit 2) Zeichen braucht.
Sie sagen, dass Sie eine Funktion schreiben müssen, die Palindrome generiert, deren Größe benutzerdefiniert ist und bis zu 1 Million Zeichen lang sein kann? – Robert
Das * Problem * (von SPOJ) kann eine 100Gigabyte-Datei enthalten, und Sie möchten es gleichzeitig in eine Zeichenfolge laden? Ernsthaft ... bitte benutze einen Scanner! –
Mögliches Duplikat von [Maximale Länge von String in Java - rufende length() Methode] (https://stackoverflow.com/questions/816142/strings-maximum-length-in-java-calling-length-method) – Bergi