Y a-t-il une limite de longueur de tableau maximale en C ++?

Existe-t-il une longueur maximale pour un tableau en C ++?

Est-ce une limite C ++ ou dépend-il de ma machine? Est-ce tweakable? Cela dépend-il du type de masortingce?

Puis-je casser cette limite d’une manière ou d’une autre ou dois-je rechercher une meilleure façon de stocker des informations? Et quelle devrait être la manière la plus simple?

Ce que je dois faire est de stocker long long int sur un tableau, je travaille dans un environnement Linux. Ma question est la suivante: que dois-je faire si je dois stocker un tableau de N entiers longs avec N> 10 chiffres?

J’en ai besoin parce que j’écris un algorithme cryptographique (comme par exemple le p-Pollard) pour l’école et que je frappe ce mur d’entiers et de longueur de représentation des tableaux.

Il y a deux limites, non imposées par C ++ mais par le matériel.

La première limite (qui ne doit jamais être atteinte) est définie par les ressortingctions du type de taille utilisé pour décrire un index dans le tableau (et sa taille). Il est donné par la valeur maximale que le système std::size_t peut prendre. Ce type de données doit toujours être le plus grand type entier d’un système.

L’autre limite est une limite de mémoire physique. Plus vos objects sont grands dans le tableau, plus cette limite est atteinte rapidement car la mémoire est pleine. Par exemple, un vector d’une taille donnée n prend environ quatre fois plus de mémoire qu’un tableau de type vector (moins une petite valeur constante). Par conséquent, un vector peut contenir plus d’éléments qu’un vector avant que la mémoire ne soit pleine. Il en va de même pour les tableaux natifs de style C int[] et char[] .

De plus, cette limite supérieure peut être influencée par le type d’ allocator utilisé pour construire le vector car un allocator est libre de gérer la mémoire comme il le souhaite. Un allocateur très étrange mais non concevable pourrait regrouper la mémoire de telle manière que des instances identiques d’un object partagent des ressources. De cette façon, vous pouvez insérer beaucoup d’objects identiques dans un conteneur qui utiliserait toute la mémoire disponible.

En dehors de cela, C ++ n’impose aucune limite.

Personne n’a mentionné la limite de la taille du cadre de la stack .

Il y a deux endroits où la mémoire peut être allouée:

  • Sur le tas (mémoire allouée dynamicment).
    La taille limite est une combinaison du matériel disponible et de la capacité du système d’exploitation à simuler l’espace en utilisant d’autres périphériques pour stocker temporairement des données inutilisées ( c.-à-d. Déplacer des pages sur le disque dur).
  • Sur la stack (variables déclarées localement).
    La taille limite est définie ici par le compilateur (avec des limites matérielles possibles). Si vous lisez la documentation du compilateur, vous pouvez souvent modifier cette taille.

Ainsi, si vous allouez un tableau de manière dynamic (la limite est grande et décrite en détail par d’autres publications).

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

Si le tableau est alloué sur la stack, vous êtes limité par la taille du cadre de la stack. Les vecteurs NB et les autres conteneurs ont une petite présence dans la stack, mais le plus gros des données sera généralement sur le tas.

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

Du sharepoint vue pratique plutôt que théorique, sur un système Windows 32 bits, la quantité totale de mémoire disponible pour un seul processus est de 2 Go. Vous pouvez casser la limite en allant sur un système d’exploitation 64 bits avec beaucoup plus de mémoire physique, mais le choix de faire cela ou de rechercher des alternatives dépend beaucoup de vos utilisateurs et de leurs budgets. Vous pouvez également l’étendre en utilisant PAE .

Le type du tableau est très important, car l’alignement de structure par défaut sur de nombreux compilateurs est de 8 octets, ce qui est très inutile si l’utilisation de la mémoire pose problème. Si vous utilisez Visual C ++ pour cibler Windows, consultez la directive #pragma pack pour résoudre ce problème.

Une autre chose à faire est d’examiner ce que les techniques de compression en mémoire peuvent vous aider, telles que les masortingces éparses, la compression à la volée, etc. Là encore, cela dépend fortement des applications. Si vous modifiez votre message pour donner plus d’informations sur ce qui se trouve réellement dans vos tableaux, vous obtiendrez des réponses plus utiles.

Edit: Étant donné un peu plus d’informations sur vos exigences exactes, vos besoins de stockage semblent être compris entre 7,6 Go et 76 Go non compressés, ce qui nécessiterait un boîtier 64 bits plutôt coûteux pour stocker en tant que tableau en mémoire en C ++. Cela soulève la question de savoir pourquoi vous souhaitez stocker les données en mémoire, où l’on suppose une vitesse d’access et permettre un access aléatoire. La meilleure façon de stocker ces données en dehors d’un tableau est essentiellement liée à la manière dont vous souhaitez y accéder. Si vous devez accéder aux membres du groupe de manière aléatoire, pour la plupart des applications, il existe des moyens de regrouper des groupes de données auxquelles on accède simultanément. Par exemple, dans les grandes bases de données SIG et spatiales, les données sont souvent classées par zone géographique. En termes de programmation C ++, vous pouvez remplacer l’opérateur de tableau [] pour extraire des parties de vos données du stockage externe, si nécessaire.

Je suis d’accord avec ce qui précède, que si vous initialisez votre tableau avec

  int myArray[SIZE] 

alors SIZE est limité par la taille d’un entier. Mais vous pouvez toujours faire un morceau de mémoire avec un pointeur, aussi gros que vous le souhaitez, à condition que malloc ne retourne pas NULL.

Pour résumer les réponses, étendez-les et répondez directement à votre question:

Non, C ++ n’impose aucune limite pour les dimensions d’un tableau.

Mais comme la baie doit être stockée quelque part dans la mémoire, les limites liées à la mémoire imposées par d’autres parties du système informatique s’appliquent. Notez que ces limites ne concernent pas directement les dimensions (= nombre d’éléments) du tableau, mais plutôt sa taille (= quantité de mémoire prise). Les dimensions ( D ) et la taille en mémoire ( S ) d’un tableau ne sont pas identiques car elles sont liées par la mémoire prise par un seul élément ( E ): S = D * E.

Maintenant, E dépend de:

  • le type des éléments du tableau (les éléments peuvent être plus petits ou plus grands)
  • alignement de la mémoire (pour augmenter les performances, les éléments sont placés à des adresses qui se multiplient, ce qui introduit
    «espace perdu» (remplissage) entre les éléments
  • taille des parties statiques des objects (dans la programmation orientée object, les composants statiques des objects du même type ne sont stockés qu’une seule fois, indépendamment du nombre d’objects de même type)

Notez également que vous obtenez généralement différentes limitations liées à la mémoire en allouant les données du tableau à la stack (en tant que variable automatique: int t[N] ) ou en tas (alocation dynamic avec les mécanismes malloc() / new ou STL), ou dans la partie statique de la mémoire de processus (en tant que variable static int t[N] : static int t[N] ). Même lors de l’allocation sur le tas, vous avez encore besoin d’une petite quantité de mémoire sur la stack pour stocker les références aux blocs de mémoire alloués au tas (mais cela est généralement négligeable).

La taille du type size_t n’a aucune influence sur le programmeur (je suppose que le programmeur utilise le type size_t pour l’indexation, comme il est conçu pour lui), car le fournisseur du compilateur doit le taper dans un type entier suffisamment grand pour traiter la quantité maximale de mémoire possible. l’architecture de la plateforme donnée.

Les sources des limitations de taille de la mémoire proviennent de

  • quantité de mémoire disponible pour le processus (limitée à 2 ^ 32 octets pour les applications 32 bits, même sur les kernelx de système d’exploitation 64 bits),
  • la division de la mémoire de processus (par exemple, quantité de mémoire de processus conçue pour la stack ou le segment de mémoire),
  • la fragmentation de la mémoire physique (de nombreux petits fragments de mémoire libre dispersés ne sont pas applicables au stockage d’une structure monolithique),
  • quantité de mémoire physique,
  • et la quantité de mémoire virtuelle.

Ils ne peuvent pas être modifiés au niveau de l’application, mais vous êtes libre d’utiliser un autre compilateur (pour modifier les limites de taille de la stack), ou de porter votre application sur 64 bits, ou de la transférer sur un autre système d’exploitation. configuration de la mémoire virtuelle de la machine (virtuelle? physique?).

Il n’est pas rare (et même conseillé) de traiter tous les facteurs ci-dessus comme des perturbations externes et donc comme des sources possibles d’erreurs d’exécution, et de vérifier et de réagir avec soin aux erreurs liées à l’allocation de mémoire dans votre code de programme.

Donc finalement: alors que C ++ n’impose aucune limite, vous devez toujours vérifier les conditions de mémoire indésirables lors de l’exécution de votre code … 🙂

Une chose que je ne pense pas a été mentionnée dans les réponses précédentes.

Je ressens toujours une «mauvaise odeur» dans le sens du refactoring lorsque les gens utilisent de telles choses dans leur conception.

Il s’agit d’un vaste ensemble et peut-être pas le meilleur moyen de représenter vos données, tant du sharepoint vue de l’efficacité que du sharepoint vue des performances.

à votre santé,

Rob

Si vous devez gérer des données aussi volumineuses, vous devez les diviser en plusieurs parties faciles à gérer. Tout ne rentre pas dans la mémoire d’un petit ordinateur. Vous pouvez probablement charger une partie des données du disque (quel que soit le format adapté), effectuer vos calculs et les modifier, les stocker sur le disque, puis répéter jusqu’à la fin.

Comme beaucoup d’excellentes réponses l’ont noté, il existe de nombreuses limites qui dépendent de votre version du compilateur C ++, du système d’exploitation et des caractéristiques de votre ordinateur. Cependant, je suggère le script suivant sur Python qui vérifie la limite sur votre machine.

Il utilise la recherche binary et à chaque itération, vérifie si la taille moyenne est possible en créant un code qui tente de créer un tableau de la taille. Le script essaie de le comstackr (désolé, cette partie ne fonctionne que sous Linux) et ajuste la recherche binary en fonction du succès. Vérifiez-le:

 import os cpp_source = 'int a[{}]; int main() {{ return 0; }}' def check_if_array_size_comstacks(size): # Write to file 1.cpp f = open(name='1.cpp', mode='w') f.write(cpp_source.format(m)) f.close() # Attempt to comstack 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_comstacks(m): l = m else: r = m answer = l + check_if_array_size_comstacks(r) print '{} is the maximum avaliable length'.format(answer) 

Vous pouvez l’enregistrer sur votre ordinateur et le lancer pour imprimer la taille maximale que vous pouvez créer. Pour ma machine c’est 2305843009213693951.

Comme cela a déjà été souligné, la taille du tableau est limitée par votre matériel et votre système d’exploitation (man ulimit). Votre logiciel, cependant, ne peut être limité que par votre créativité. Par exemple, pouvez-vous stocker votre “tableau” sur le disque? Avez-vous vraiment besoin de longue durée? Avez-vous vraiment besoin d’un tableau dense? Avez-vous même besoin d’un tableau?

Une solution simple serait d’utiliser Linux 64 bits. Même si vous ne disposez pas d’assez de mémoire vive pour votre baie, le système d’exploitation vous permettra d’allouer de la mémoire, car la mémoire virtuelle disponible pour votre processus est probablement beaucoup plus grande que la mémoire physique. Si vous avez vraiment besoin d’accéder à tout ce qui se trouve dans le tableau, cela revient à le stocker sur le disque. Selon vos modèles d’access, il peut y avoir des moyens plus efficaces de le faire (par exemple: utiliser mmap (), ou simplement stocker les données de manière séquentielle dans un fichier (auquel cas Linux 32 bits suffirait)).

Je ferais le tour en faisant un tableau dynamic 2D:

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

plus à ce sujet ici https://stackoverflow.com/a/936702/3517001