Estoy tratando el problema The Next Palindrome desde el juez en línea de Esfera (SPOJ) donde necesito encontrar un palíndromo para un número entero de hasta un millón de dígitos. Pensé en usar las funciones de Java para invertir cadenas, pero ¿permitirían que una cadena fuera tan larga?¿Cuántos caracteres puede tener Java String?
Usted debe ser capaz de obtener una cadena de longitud Integer.MAX_VALUE (siempre 2147483647 (2 - 1) por la especificación de Java, el tamaño máximo de una matriz, que utiliza la clase String para el almacenamiento interno) o la mitad de su tamaño máximo de almacenamiento dinámico (ya que cada carácter es de dos bytes), el que sea más pequeño.
... o su tamaño de almacenamiento dinámico máximo dividido por 2 ... ya que el carácter es de 2 bytes – ChssPly76
@ ChssPly76: Sí, eso es correcto. Edité mi respuesta, gracias. –
¿cómo puedo averiguar el tamaño máximo de almacenamiento dinámico? Además, no sé qué máquina virtual Java que el juez está utilizando para probar mi problema es Integer.MAX_VALUE parte de la especificación de JVM dependiente? – andandandand
Creo que pueden tener hasta 2^31-1 caracteres, ya que están en una matriz interna, y las matrices están indexadas por enteros en Java.
La implementación interna es irrelevante; no hay ninguna razón por la que los datos de los caracteres no se puedan almacenar en una serie de largos, por ejemplo. El problema es que la interfaz usa enteros para longitud. 'getBytes' y similares pueden tener problemas si intentas una cadena muy grande. –
Eso es cierto, estaba implicando ese hecho. Mi error. – aperkins
Integer.MAX_VALUE es el tamaño máximo de la cadena + depende de su tamaño de memoria, pero el juez de línea Problemas en la propia esfera que no tiene que usar esas funciones
Ha considerado el uso BigDecimal en lugar de String para mantener sus números ?
Depende de lo que la aplicación va a hacer con los números. Si va a hacer cosas textuales como encontrar palíndromos, contar dígitos (decimales), entonces una Cadena es mejor. Si va a hacer aritmética, un BigDecimal (o BigInteger) es mejor. –
El problema es "Para cada K, el menor palíndromo es más grande que K." (donde K es el número dado). Sería trivialmente simple generar el primer palíndromo más pequeño que K. Se necesita aritmética para encontrar uno más grande que K. Ejemplo: Encuentre el siguiente palíndromo más grande que 999999999999, o el siguiente palíndromo más grande que 12922. –
La parte del montón empeora, mis amigos. No se garantiza que UTF-16 esté limitado a 16 bits y puede ampliarse a 32
Excepto que el tipo 'char' de Java es 16 bits exactamente, por lo que la cantidad de bits que UTF-16 usa realmente no importa ... – awksp
Si utiliza el motor de la aplicación de Google, com.google.appengine.api.datastore.Text puede ayudar. Permite que una sola cadena almacene hasta 1 megabyte.
La cadena ya puede almacenar hasta 2GB, por lo que una clase que puede almacenar hasta 1MB no está ayudando aquí. –
Sería útil si incluyese un enlace a una página web que explica esto con más detalle, y amplió su respuesta –
Si bien en teoría puede interpretar caracteres Integer.MAX_VALUE, la JVM está limitada en el tamaño de la matriz que puede usar.
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);
}
}
}
en Oracle Java 8 al día 92 impresiones
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: en Java 9, cuerdas utilizará byte [] lo que significa que los caracteres de múltiples bytes utilizarán más de un byte y reducir el máximo adicional. Si tiene los cuatro puntos de código de bytes, p. Ej. emojis, solo obtendrá alrededor de 500 millones de caracteres
[Compact Strings] (http://openjdk.java.net/jeps/254) en Java 9 use cualquiera Codificación Latin-1 o UTF-16. Sin codificación de longitud variable, es decir, sin caracteres de tres bytes. – apangin
@apangin "No es un objetivo usar codificaciones alternativas como UTF-8" gracias por la corrección. –
Java9 usa byte [] para almacenar String.value, por lo que solo puede obtener cadenas de 1GB en Java9. Java8 por otro lado puede tener cadenas de 2 GB.
Por carácter me refiero a "char" s, algunos caracteres no son representables en BMP (como algunos de los emojis), por lo que se necesitarán más (actualmente 2) caracteres.
¿Estás diciendo que necesitas escribir una función que genere palíndromos, cuyo tamaño está especificado por el usuario y puede tener hasta 1 millón de caracteres de longitud? – Robert
El * Problema * (de SPOJ) puede contener un archivo de 100 Gigabytes, y desea cargarlo en una cadena a la vez? En serio ... ¡usa un escáner! –
Posible duplicado de [Longitud máxima de String en el método Java - longitud de llamada()] (https://stackoverflow.com/questions/816142/strings-maximum-length-in-java-calling-length-method) – Bergi