tamaño - ¿Existe un límite máximo de longitud de matriz en C++?

vectores en c++ ejercicios resueltos

Question

¿Hay una longitud máxima para una matriz en C ++?

¿Es un límite de C ++ o depende de mi máquina? ¿Es modificable? ¿Depende del tipo de la matriz está hecha?

¿Puedo romper ese límite de alguna manera o tengo que buscar una mejor manera de almacenar información? ¿Y cuál debería ser la forma más simple?

Lo que tengo que hacer es almacenar long long int en una matriz, estoy trabajando en un entorno Linux. Mi pregunta es: ¿qué debo hacer si necesito almacenar una matriz de N enteros largos largos con N> 10 dígitos?

Necesito esto porque estoy escribiendo algún algoritmo criptográfico (como por ejemplo el p-Pollard) para la escuela, y golpeo esta pared de números enteros y la longitud de la representación de matrices.

Answer 1

Como se mencionaron muchas respuestas excelentes, existen muchos límites que dependen de su versión del compilador de C ++, el sistema operativo y las características de la computadora. Sin embargo, sugiero la siguiente secuencia de comandos en Python que verifica el límite en su máquina.

Utiliza la búsqueda binaria y en cada iteración comprueba si el tamaño medio es posible creando un código que intenta crear una matriz del tamaño. El script intenta compilarlo (lo siento, esta parte solo funciona en Linux) y ajusta la búsqueda binaria según el éxito. Echale un vistazo:

import os

cpp_source = ''int a[{}]; int main() {{ return 0; }}''

def check_if_array_size_compiles(size):
        #  Write to file 1.cpp
        f = open(name=''1.cpp'', mode=''w'')
        f.write(cpp_source.format(m))
        f.close()
        #  Attempt to compile
        os.system(''g++ 1.cpp 2> errors'')
        #  Read the errors files
        errors = open(''errors'', ''r'').read()
        #  Return if there is no errors
        return len(errors) == 0

#  Make a binary search. Try to create array with size m and
#  adjust the r and l border depending on wheather we succeeded
#  or not
l = 0
r = 10 ** 50
while r - l > 1:
        m = (r + l) // 2
        if check_if_array_size_compiles(m):
                l = m
        else:
                r = m

answer = l + check_if_array_size_compiles(r)
print ''{} is the maximum avaliable length''.format(answer)

Puede guardarlo en su máquina y ejecutarlo, e imprimirá el tamaño máximo que puede crear. Para mi máquina es 2305843009213693951.

Answer 2

Como ya se ha señalado, el tamaño de la matriz está limitado por su hardware y su sistema operativo (man ulimit). Sin embargo, su software solo puede estar limitado por su creatividad. Por ejemplo, ¿puedes almacenar tu "matriz" en el disco? ¿Realmente necesitas largos largos enteros? ¿Realmente necesitas una matriz densa? ¿Incluso necesitas una matriz?

Una solución simple sería usar Linux de 64 bits. Incluso si físicamente no tiene suficiente memoria RAM para su matriz, el sistema operativo le permitirá asignar memoria como si lo hiciera, ya que la memoria virtual disponible para su proceso es probablemente mucho más grande que la memoria física. Si realmente necesita acceder a todo en la matriz, esto equivale a almacenarlo en el disco. Dependiendo de sus patrones de acceso, puede haber maneras más eficientes de hacerlo (es decir: usando mmap (), o simplemente almacenando los datos secuencialmente en un archivo (en cuyo caso sería suficiente con Linux de 32 bits)).

Answer 3

Estoy de acuerdo con lo anterior, que si estás iniciando tu matriz con

 int myArray[SIZE] 

luego, TAMAÑO está limitado por el tamaño de un número entero. Pero siempre puedes malloc un trozo de memoria y tener un puntero al mismo, tan grande como quieras, siempre que malloc no devuelva NULL.

Answer 4

Hay dos límites, ambos no aplicados por C ++ sino por el hardware.

El primer límite (nunca se debe alcanzar) se establece por las restricciones del tipo de tamaño utilizado para describir un índice en la matriz (y el tamaño de la misma). Está dado por el valor máximo que puede tener el std::size_t del sistema. Este tipo de datos siempre debe ser el tipo de entero más grande de un sistema.

El otro límite es un límite de memoria física. Cuanto más grandes son los objetos en la matriz, más pronto se alcanza este límite porque la memoria está llena. Por ejemplo, un vector<int> de un tamaño dado n típicamente toma aproximadamente cuatro veces más memoria que una matriz de tipo vector<char> (menos un pequeño valor constante). Por lo tanto, un vector<char> puede contener más elementos que un vector<int> antes de que la memoria esté llena. Lo mismo cuenta para las matrices de estilo C nativas int[] y char[] .

Además, este límite superior puede estar influenciado por el tipo de allocator utilizado para construir el vector porque un allocator es libre de administrar la memoria de la forma que quiera. Un asignador concebible muy extraño, pero no obstante, podría agrupar la memoria de tal forma que instancias idénticas de un objeto compartan recursos. De esta forma, podría insertar muchos objetos idénticos en un contenedor que de otra forma agotaría toda la memoria disponible.

Aparte de eso, C ++ no impone ningún límite.

Answer 5

Me gustaría ir alrededor de esto haciendo una matriz dinámica 2d:

long long** a = new long long*[x];
for (unsigned i = 0; i < x; i++) a[i] = new long long[y];

más sobre esto aquí https://.com/a/936702/3517001

Answer 6

Mirándolo desde un punto de vista práctico en lugar de teórico, en un sistema de Windows de 32 bits, la cantidad total máxima de memoria disponible para un único proceso es de 2 GB. Puede superar el límite yendo a un sistema operativo de 64 bits con mucha más memoria física, pero si hacer esto o buscar alternativas depende en gran medida de los usuarios previstos y sus presupuestos. También puede extenderlo un poco usando PAE .

El tipo de matriz es muy importante, ya que la alineación predeterminada de la estructura en muchos compiladores es de 8 bytes, lo cual es un gran desperdicio si el uso de la memoria es un problema. Si está utilizando Visual C ++ para apuntar a Windows, consulte la directiva #pragma pack como una forma de superar esto.

Otra cosa que hay que hacer es ver lo que las técnicas de compresión de memoria pueden ayudarlo, como matrices dispersas, compresión sobre la marcha, etc. De nuevo, esto depende en gran medida de la aplicación. Si editas tu publicación para obtener más información sobre lo que realmente está en tus matrices, es posible que obtengas respuestas más útiles.

Editar: Dada un poco más de información sobre sus requisitos exactos, sus necesidades de almacenamiento parecen estar entre 7,6 GB y 76 GB sin comprimir, lo que requeriría una caja de 64 bits bastante costosa para almacenar como una matriz en la memoria en C ++. Se plantea la pregunta de por qué desea almacenar los datos en la memoria, donde se supone que la velocidad de acceso y permitir el acceso aleatorio. La mejor manera de almacenar estos datos fuera de una matriz se basa en gran medida en cómo desea acceder a ella. Si necesita acceder a los miembros de la matriz aleatoriamente, para la mayoría de las aplicaciones suele haber formas de agrupar grupos de datos a los que se accede habitualmente al mismo tiempo. Por ejemplo, en grandes SIG y bases de datos espaciales, los datos a menudo se agrupan por área geográfica. En términos de programación de C ++ puede anular el operador de matriz [] para obtener partes de sus datos del almacenamiento externo según sea necesario.

Answer 7

Nadie mencionó el límite en el tamaño del marco de pila .

Hay dos lugares en los que se puede asignar memoria:

• En el montón (memoria asignada dinámicamente).
  El límite de tamaño aquí es una combinación de hardware disponible y la capacidad del sistema operativo para simular espacio mediante el uso de otros dispositivos para almacenar temporalmente datos no utilizados ( es decir, mover páginas al disco duro).
• En la pila (variables declaradas localmente).
  El límite de tamaño aquí es el compilador definido (con posibles límites de hardware). Si lee la documentación del compilador, a menudo puede ajustar este tamaño.

Por lo tanto, si asigna una matriz de forma dinámica (el límite es grande y se describe en detalle por otras publicaciones.

int* a1 = new int[SIZE];  // SIZE limited only by OS/Hardware

Alternativamente, si la matriz se asigna en la pila, entonces está limitado por el tamaño del marco de la pila. Los vectores NB y otros contenedores tienen una pequeña presencia en la pila, pero generalmente la mayor parte de los datos estarán en el montón.

int a2[SIZE]; // SIZE limited by COMPILER to the size of the stack frame

Answer 8

Para resumir las respuestas, extenderlas y responder su pregunta directamente:

No, C ++ no impone ningún límite para las dimensiones de una matriz.

Pero como la matriz debe almacenarse en algún lugar de la memoria, se aplican los límites relacionados con la memoria impuestos por otras partes del sistema informático. Tenga en cuenta que estos límites no se relacionan directamente con las dimensiones (= número de elementos) de la matriz, sino más bien con su tamaño (= cantidad de memoria tomada). Las dimensiones ( D ) y el tamaño de la memoria ( S ) de una matriz no son las mismas, ya que están relacionadas por la memoria tomada por un solo elemento ( E ): S = D * E.

Ahora E depende de:

• el tipo de los elementos de la matriz (los elementos pueden ser más pequeños o más grandes)
• alineación de memoria (para aumentar el rendimiento, los elementos se colocan en direcciones que son multiplicadas de algún valor, lo que introduce
  ''espacio perdido'' (relleno) entre los elementos
• tamaño de las partes estáticas de los objetos (en la programación orientada a objetos, los componentes estáticos de los objetos del mismo tipo solo se almacenan una vez, independientemente del número de dichos objetos del mismo tipo)

También tenga en cuenta que generalmente obtiene diferentes limitaciones relacionadas con la memoria al asignar los datos de la matriz en la pila (como una variable automática: int t[N] ), o en el montón (alocation dinámico con malloc() / new o usando mecanismos STL), o en la parte estática de la memoria de proceso (como variable static int t[N] : static int t[N] ). Incluso cuando se distribuye en el montón, todavía necesita una pequeña cantidad de memoria en la pila para almacenar referencias a los bloques de memoria asignados al montón (pero esto es insignificante, por lo general).

El tamaño del tipo size_t no influye en el programador (supongo que el programador usa size_t para indexar, ya que está diseñado para ello), ya que el proveedor del compilador debe escribirlo en un tipo entero lo suficientemente grande como para abordar la cantidad máxima de memoria posible para la arquitectura de plataforma dada.

Las fuentes de las limitaciones de tamaño de memoria provienen de

• cantidad de memoria disponible para el proceso (que está limitada a 2 ^ 32 bytes para aplicaciones de 32 bits, incluso en kernels OS de 64 bits),
• la división de la memoria de proceso (por ejemplo, la cantidad de memoria de proceso diseñada para pila o montón),
• la fragmentación de la memoria física (muchos pequeños fragmentos dispersos de memoria libre no son aplicables para almacenar una estructura monolítica),
• cantidad de memoria física,
• y la cantidad de memoria virtual.

No se pueden "ajustar" a nivel de aplicación, pero puede usar un compilador diferente (para cambiar los límites de tamaño de la pila), o portar su aplicación a 64 bits, o transferirla a otro sistema operativo, o cambiar el físico / configuración de memoria virtual de la máquina (¿virtual? ¿física?).

No es raro (e incluso aconsejable) tratar todos los factores anteriores como perturbaciones externas y, por lo tanto, como posibles fuentes de errores de tiempo de ejecución, y verificar cuidadosamente y reaccionar a los errores relacionados con la asignación de memoria en el código de su programa.

Entonces, finalmente: mientras que C ++ no impone ningún límite, aún debe verificar las condiciones adversas relacionadas con la memoria cuando ejecuta su código ... :-)

Answer 9

Si tiene que lidiar con datos tan grandes, tendrá que dividirlos en fragmentos manejables. No todos encajarán en la memoria en cualquier computadora pequeña. Probablemente pueda cargar una parte de los datos del disco (lo que sea razonablemente apropiado), realizar sus cálculos y cambios en él, almacenarlo en el disco y luego repetirlo hasta que se complete.

Answer 10

Una cosa que no creo ha sido mencionada en las respuestas anteriores.

Siempre percibo un "mal olor" en el sentido refactorio cuando las personas usan tales cosas en su diseño.

Es una gran variedad y posiblemente no la mejor manera de representar sus datos, tanto desde el punto de vista de la eficiencia como desde el punto de vista del rendimiento.

aclamaciones,

Robar