La dimensione di un array è vincolata dal limite superiore di int (2147483647)?

Question

Sto facendo alcuni esercizi Project Euler e ho eseguito uno scenario in cui I ha desidera matrici di dimensioni superiori a 2.147.483.647 (il limite superiore di int in C#).

Certo questi sono grandi array, ma per esempio, non posso fare questo

// fails 
bool[] BigArray = new BigArray[2147483648]; 

// also fails, cannot convert uint to int 
ArrayList BigArrayList = new ArrayList(2147483648); 

Quindi, posso avere array più grandi?

EDIT: E 'stato per un Sieve of Atkin, si sa, quindi ho solo voluto una davvero grande: D

Answer 1

Ogni volta che si sta lavorando con una serie così grande, probabilmente si dovrebbe cercare di trovare una soluzione migliore per il problema. Ma detto questo cercherò ancora di rispondere alla tua domanda.

Come menzionato in questo article c'è un limite di 2 GB su qualsiasi oggetto in .Net. Per tutti x86, x64 e IA64.

Come con operativi a 32 bit di Windows sistemi, c'è un limite di 2 GB alla dimensione di un oggetto è possibile creare durante l'esecuzione di un 64-bit gestito applicazione su un sistema operativo Windows a 64 bit.

Inoltre, se si definisce un array troppo grande nello stack, si verificherà un overflow dello stack. Se si definisce la matrice sull'heap, tenterà di allocarlo tutto in un unico grande blocco continuo. Sarebbe meglio usare un ArrayList che ha allocazione dinamica implicita sull'heap. Questo non ti permetterà di superare i 2 GB, ma probabilmente ti permetterò di avvicinarti ad esso.

Penso che il limite della dimensione dello stack sarà maggiore solo se si utilizza un'architettura e un sistema operativo x64 o IA64. Usando x64 o IA64 avrai una memoria allocabile a 64 bit invece di 32-bit.

Se non si è in grado di allocare l'elenco di array tutto in una volta, è probabile che sia possibile allocarlo in parti.

Utilizzando un elenco di array e aggiungendo 1 oggetto alla volta su un computer Windows 64 x64 con 6 GB di RAM, il massimo che posso ottenere è ArrayList: 134217728. Quindi penso davvero che sia necessario trovare una soluzione migliore al tuo problema che non usa tanta memoria. Magari scrivendo su un file invece di usare la RAM.

Answer 2

Il limite dell'array è, afaik, corretto come int32 anche su 64 bit. C'è un berretto sulla dimensione massima di un singolo oggetto. Tuttavia, si potrebbe avere abbastanza facilmente un grande array frastagliato.

Peggio; poiché i riferimenti sono maggiori in x64, per gli array di tipo ref in effetti si ottiene in meno di elementi in un singolo array.

Vedi here:

ho ricevuto un numero di query come sul motivo per cui la versione a 64 bit del runtime 2.0 Net ha ancora massima di array dimensioni limitate a 2 GB.Dato che è sembra essere un tema caldo di ritardo I capito un po 'di sfondo e una discussione delle opzioni per ottenere intorno a questa limitazione era in ordine.

Primo sfondo; nella versione 2.0 di .Net runtime (CLR) abbiamo deciso consapevolmente per il di mantenere la dimensione massima dell'oggetto consentita nell'heap GC a 2 GB, anche nella versione a 64 bit del runtime. Questo è uguale alla corrente 1.1 attuazione del CLR 32 bit, tuttavia si sarebbe difficile da effettivamente riescono a allocare un oggetto 2GB sul CLR 32 bit perché lo spazio di indirizzi virtuali è semplicemente troppo frammentato per trovare realisticamente un foro da 2 GB . Generalmente le persone non sono particolarmente preoccupato per la creazione di tipi che sarebbero> 2GB quando istanziato (o dovunque vicino), tuttavia, poiché gli array sono solo uno speciale tipo di tipo gestito quali sono creato all'interno della heap gestito hanno anche soffrire di questa limitazione

---

Va notato che nella NET 4.5 dimensioni limite memoria è opzionalmente rimosso dal flag gcAllowVeryLargeObjects, tuttavia, questo non cambia la massima dimensione dimensioni. Il punto chiave è che se si dispone di matrici di un tipo personalizzato o di matrici a più dimensioni, è ora possibile andare oltre i 2 GB di memoria.

Answer 3

Credo che anche all'interno di un CLR a 64 bit, c'è un limite di 2 GB (o forse 1 GB - non ricordo esattamente) per oggetto. Ciò impedirebbe di creare un array più grande. Il fatto che Array.CreateInstance richieda solo argomenti Int32 per le dimensioni è anch'esso suggestivo.

Su una nota più ampia, sospetto che se hai bisogno di array così grandi, dovresti davvero cambiare il modo in cui ti stai avvicinando al problema.

Answer 4

Non è necessario alcun array di grandi dimensioni.

Quando il metodo si imbatte in problemi di risorse, non limitarsi a esaminare come espandere le risorse, ma anche il metodo. :)

Ecco una classe che utilizza un buffer da 3 MB per calcolare i primi utilizzando il setaccio di Eratostene. La classe tiene traccia di quanto sono stati calcolati i numeri primi e quando l'intervallo deve essere espanso crea un buffer per testare altri 3 milioni di numeri.

Mantiene i numeri primi trovati in un elenco e quando l'intervallo viene espanso, i numeri primi vengono utilizzati per escludere i numeri nel buffer.

Ho eseguito alcuni test e un buffer di circa 3 MB è il più efficiente.

public class Primes { 

    private const int _blockSize = 3000000; 

    private List<long> _primes; 
    private long _next; 

    public Primes() { 
     _primes = new List<long>() { 2, 3, 5, 7, 11, 13, 17, 19 }; 
     _next = 23; 
    } 

    private void Expand() { 
     bool[] sieve = new bool[_blockSize]; 
     foreach (long prime in _primes) { 
     for (long i = ((_next + prime - 1L)/prime) * prime - _next; 
      i < _blockSize; i += prime) { 
      sieve[i] = true; 
     } 
     } 
     for (int i = 0; i < _blockSize; i++) { 
     if (!sieve[i]) { 
      _primes.Add(_next); 
      for (long j = i + _next; j < _blockSize; j += _next) { 
       sieve[j] = true; 
      } 
     } 
     _next++; 
     } 
    } 

    public long this[int index] { 
     get { 
     if (index < 0) throw new IndexOutOfRangeException(); 
     while (index >= _primes.Count) { 
      Expand(); 
     } 
     return _primes[index]; 
     } 
    } 

    public bool IsPrime(long number) { 
     while (_primes[_primes.Count - 1] < number) { 
     Expand(); 
     } 
     return _primes.BinarySearch(number) >= 0; 
    } 

} 

Answer 5

Sono molto un principiante con C# (vale a dire l'apprendimento questa settimana), quindi non sono sicuro dei dettagli esatti di come viene implementato ArrayList. Tuttavia, suppongo che siccome non hai definito un tipo per l'esempio ArrayList, l'array verrebbe assegnato come una matrice di riferimenti a oggetti. Ciò potrebbe significare che in realtà stai allocando 4-8 GB di memoria a seconda dell'architettura.

Answer 6

According to MSDN, l'indice per la matrice di byte non può essere maggiore di 2147483591. Per .NET precedente alla 4.5 era anche un limite di memoria per un array. In .NET 4.5 questo massimo è lo stesso, ma per gli altri tipi può essere fino a 2146435071.

Questo è il codice per l'illustrazione:

static void Main(string[] args) 
    { 
     // ----------------------------------------------- 
     // Pre .NET 4.5 or gcAllowVeryLargeObjects unset 
     const int twoGig = 2147483591; // magic number from .NET 

     var type = typeof(int);   // type to use 
     var size = Marshal.SizeOf(type); // type size 
     var num = twoGig/size;   // max element count 

     var arr20 = Array.CreateInstance(type, num); 
     var arr21 = new byte[num]; 

     // ----------------------------------------------- 
     // .NET 4.5 with x64 and gcAllowVeryLargeObjects set 
     var arr451 = new byte[2147483591]; 
     var arr452 = Array.CreateInstance(typeof(int), 2146435071); 
     var arr453 = new byte[2146435071]; // another magic number 

     return; 
    }