Existe um limite máximo de comprimento de matriz em C ++?

Existe um tamanho máximo para uma matriz em C ++?

É um limite de C ++ ou depende da minha máquina? É tweakable? Depende do tipo que o array é feito?

Posso quebrar esse limite de alguma forma ou tenho que procurar uma maneira melhor de armazenar informações? E qual deve ser o caminho mais simples?

O que tenho que fazer é armazenar long long int em um array, estou trabalhando em um ambiente Linux. Minha pergunta é: o que devo fazer se precisar armazenar uma matriz de N inteiros longos com N> 10 dígitos?

Eu preciso disso porque estou escrevendo algum algoritmo criptográfico (como por exemplo o p-Pollard) para a escola, e atingi essa parede de inteiros e comprimento de representação de matrizes.

Existem dois limites, ambos não aplicados pelo C ++, mas pelo hardware.

O primeiro limite (nunca deve ser alcançado) é definido pelas restrições do tipo de tamanho usado para descrever um índice na matriz (e o tamanho dele). É dado pelo valor máximo que o std::size_t do sistema pode suportar. Esse tipo de dados deve sempre ser o maior tipo inteiro de um sistema.

O outro limite é um limite de memory física. Quanto maiores forem seus objects na matriz, mais cedo esse limite é atingido porque a memory está cheia. Por exemplo, um vector de um determinado tamanho n normalmente leva cerca de quatro vezes mais memory do que uma matriz do tipo vector (menos um valor constante pequeno). Portanto, um vector pode conter mais itens que um vector antes que a memory esteja cheia. A mesma conta para os arrays nativos de estilo C int[] e char[] .

Além disso, esse limite superior pode ser influenciado pelo tipo de allocator usado para construir o vector porque um allocator está livre para gerenciar a memory da maneira que desejar. Um alocador concebível muito estranho, mas que não pode ser alterado, poderia reunir a memory de tal forma que instâncias idênticas de um object compartilham resources. Dessa forma, você poderia inserir muitos objects idênticos em um contêiner que, de outra forma, consumiria toda a memory disponível.

Além disso, o C ++ não impõe nenhum limite.

Ninguém mencionou o limite no tamanho do quadro da pilha .

Existem dois lugares onde a memory pode ser alocada:

  • No heap (memory alocada dinamicamente).
    O limite de tamanho aqui é uma combinação de hardware disponível e a capacidade do sistema operacional de simular espaço usando outros dispositivos para armazenar temporariamente dados não utilizados (por exemplo, mover páginas para o disco rígido).
  • Na pilha (variables ​​declaradas localmente).
    O limite de tamanho aqui é definido pelo compilador (com possíveis limites de hardware). Se você ler a documentação do compilador, muitas vezes você pode ajustar esse tamanho.

Assim, se você alocar um array dinamicamente (o limite é grande e descrito em detalhes por outros posts.

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

Alternativamente, se a matriz é alocada na pilha, então você está limitado pelo tamanho do quadro da pilha. Os vetores de NB e outros contêineres têm uma pequena presença na pilha, mas geralmente a maior parte dos dados estará no heap.

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

Olhando para ele do ponto de vista prático, em vez de teórico, em um sistema Windows de 32 bits, a quantidade máxima total de memory disponível para um único processo é de 2 GB. Você pode quebrar o limite indo para um sistema operacional de 64 bits com muito mais memory física, mas se fazer isso ou procurar alternativas depende muito dos usuários pretendidos e de seus orçamentos. Você também pode estendê-lo um pouco usando o PAE .

O tipo da matriz é muito importante, pois o alinhamento da estrutura padrão em muitos compiladores é de 8 bytes, o que é um grande desperdício se o uso da memory for um problema. Se você estiver usando o Visual C ++ para direcionar o Windows, verifique a diretiva de pacote # pragma como uma maneira de superar isso.

Outra coisa a fazer é verificar o que, em técnicas de compactação de memory, pode ajudá-lo, como matrizes esparsas, compression rápida, etc … Novamente, isso é altamente dependente de aplicativos. Se você editar sua postagem para fornecer mais informações sobre o que realmente está em suas matrizes, poderá obter respostas mais úteis.

Edit: Dado um pouco mais informações sobre suas necessidades exatas, suas necessidades de armazenamento parecem estar entre 7.6 GB e 76 GB não compactados, o que exigiria uma checkbox de 64 bits bastante cara para armazenar como um array na memory em C ++. Isso levanta a questão: por que você deseja armazenar os dados na memory, onde presume a velocidade de access e permitir access random. A melhor maneira de armazenar esses dados fora de uma matriz é basicamente baseada em como você deseja acessá-los. Se você precisar acessar os membros da matriz aleatoriamente, para a maioria dos aplicativos, tendem a haver maneiras de agrupar grupos de dados que tendem a ser acessados ​​ao mesmo tempo. Por exemplo, em grandes bancos de dados geocharts e espaciais, os dados geralmente ficam lado a lado por área geográfica. Em termos de programação C ++, é possível replace o operador da matriz [] para buscar partes de seus dados do armazenamento externo, conforme necessário.

Eu concordaria com o acima, que se você está inicializando sua matriz com

  int myArray[SIZE] 

então TAMANHO é limitado pelo tamanho de um inteiro. Mas você pode sempre armazenar um pedaço de memory e ter um ponteiro para ele, tão grande quanto você quiser, desde que malloc não retorne NULL.

Para resumir as respostas, estenda-as e responda diretamente à sua pergunta:

Não, o C ++ não impõe nenhum limite para as dimensões de um array.

Mas como o array tem que ser armazenado em algum lugar na memory, os limites relacionados à memory impostos por outras partes do sistema do computador se aplicam. Observe que esses limites não se relacionam diretamente com as dimensões (= número de elementos) da matriz, mas com seu tamanho (= quantidade de memory obtida). As dimensões ( D ) e o tamanho da memory ( S ) de uma matriz não são os mesmos, pois são relacionados pela memory obtida por um único elemento ( E ): S = D * E.

Agora E depende de:

  • o tipo dos elementos da matriz (os elementos podem ser menores ou maiores)
  • alinhamento de memory (para aumentar o desempenho, os elementos são colocados em endereços que são multiplos de algum valor, o que introduz
    ‘espaço desperdiçado’ (preenchimento) entre elementos
  • tamanho de partes estáticas de objects (na programação orientada a objects, componentes estáticos de objects do mesmo tipo são armazenados apenas uma vez, independente do número de objects do mesmo tipo)

Observe também que você geralmente obtém diferentes limitações relacionadas à memory alocando os dados da matriz na pilha (como uma variável automática: int t[N] ) ou na pilha (alocação dinâmica com malloc() / new ou usando mecanismos STL) ou na parte estática da memory de processo (como uma variável static int t[N] : static int t[N] ). Mesmo ao alocar no heap, você ainda precisa de uma pequena quantidade de memory na pilha para armazenar referências aos blocos de memory alocados no heap (mas isso é insignificante, geralmente).

O tamanho do tipo size_t não tem influência sobre o programador (suponho que o programador use o tipo size_t para indexação, como foi projetado para ele), pois o provedor do compilador tem que typedef lo para um tipo inteiro grande o suficiente para endereçar a quantidade máxima de memory possível. a arquitetura da plataforma fornecida.

As fonts das limitações de tamanho de memory

  • quantidade de memory disponível para o processo (que é limitada a 2 ^ 32 bytes para aplicativos de 32 bits, mesmo em kernels de 64 bits),
  • a divisão da memory de processo (por exemplo, quantidade da memory de processo projetada para pilha ou heap),
  • a fragmentação da memory física (muitos pequenos fragments de memory livre espalhados não são aplicáveis ​​ao armazenamento de uma estrutura monolítica),
  • quantidade de memory física,
  • e a quantidade de memory virtual.

Eles não podem ser “ajustados” no nível do aplicativo, mas você está livre para usar um compilador diferente (para alterar os limites de tamanho de pilha), ou portar seu aplicativo para 64 bits ou portá-lo para outro SO ou alterar o físico configuração de memory virtual da máquina (virtual? física?).

Não é incomum (e até aconselhável) tratar todos os fatores acima como distúrbios externos e, portanto, como possíveis fonts de erros de tempo de execução, e verificar cuidadosamente e reagir a erros relacionados à alocação de memory em seu código de programa.

Então, finalmente: enquanto o C ++ não impõe nenhum limite, você ainda tem que verificar se há condições adversas relacionadas à memory ao executar seu código … 🙂

Uma coisa que não acho que foi mencionada nas respostas anteriores.

Estou sempre sentindo um “mau cheiro” no sentido de refatoração quando as pessoas estão usando essas coisas em seu design.

Essa é uma grande variedade e possivelmente não é a melhor maneira de representar seus dados, tanto do ponto de vista da eficiência quanto do ponto de vista do desempenho.

Felicidades,

Roubar

Se você tiver que lidar com dados tão grandes, precisará dividi-los em partes gerenciáveis. Nem tudo vai caber na memory de qualquer computador pequeno. Você provavelmente pode carregar uma parte dos dados do disco (o que for razoavelmente adequado), realizar seus cálculos e alterações, armazená-los em disco e repetir até completar.

Como muitas respostas excelentes notaram, há muitos limites que dependem da sua versão do compilador C ++, do sistema operacional e das características do computador. No entanto, sugiro o seguinte script no Python que verifica o limite em sua máquina.

Ele usa pesquisa binária e em cada iteração verifica se o tamanho do meio é possível criando um código que tente criar uma matriz do tamanho. O script tenta compilá-lo (desculpe, esta parte funciona apenas no Linux) e ajusta a pesquisa binária dependendo do sucesso. Confira:

 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) 

Você pode salvá-lo em sua máquina e iniciá-lo, e ele imprimirá o tamanho máximo que você pode criar. Para minha máquina é 2305843009213693951.

Como já foi dito, o tamanho do array é limitado pelo seu hardware e pelo seu SO (man ulimit). Seu software, porém, só pode ser limitado pela sua criatividade. Por exemplo, você pode armazenar sua “matriz” no disco? Você realmente precisa de muito tempo? Você realmente precisa de um array denso? Você precisa mesmo de um array?

Uma solução simples seria usar o Linux de 64 bits. Mesmo que você não tenha fisicamente memory RAM suficiente para o seu array, o sistema operacional permitirá que você aloque memory como se você fizesse, já que a memory virtual disponível para o seu processo provavelmente é muito maior que a memory física. Se você realmente precisa acessar tudo na matriz, isso equivale a armazená-lo no disco. Dependendo de seus padrões de access, pode haver maneiras mais eficientes de fazer isso (ou seja, usar mmap () ou simplesmente armazenar os dados sequencialmente em um arquivo (nesse caso, o Linux de 32 bits seria suficiente)).

Eu iria contornar isso fazendo uma matriz dinâmica 2D:

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

mais sobre isso aqui https://stackoverflow.com/a/936702/3517001