È la dimensione di una matrice limitata dal limite superiore di int (2147483647)?

Question

Sto facendo esercizi di alcune Project Euler e ho eseguito in uno scenario in cui I ho vogliono matrici che sono più grandi di 2.147.483.647 (il limite superiore della 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 Crivello di Atkin , si sa, quindi volevo solo un 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 al problema. Ma ciò che viene detto io sarò ancora tenta di rispondere alla tua domanda.

Come accennato in questo articolo lì è un limite di 2 GB su qualsiasi oggetto in Net. Per tutti x86, x64 e IA64.

  

Come con 32 bit operativo Windows   sistemi, v'è un limite 2GB sulla   dimensione di un oggetto è possibile creare, mentre   l'esecuzione di un'applicazione gestita a 64 bit   su un sistema operativo Windows a 64 bit.

Anche se si definisce una matrice troppo grande in pila, si avrà un overflow dello stack. Se si definisce la matrice sul mucchio, cercherà di allocare tutto in un unico grande blocco continuo. Sarebbe preferibile utilizzare un ArrayList che ha allocazione dinamica implicita sul mucchio. Questo non vi permetterà di andare oltre il 2 GB, ma probabilmente permetterà di ottenere più vicino ad esso.

Credo che il limite di dimensione dello stack sarà più grande solo se si utilizza un x64 o IA64 architettura e il sistema operativo. Utilizzando x64 o IA64 si avrà a 64 bit di memoria assegnabile invece di 32 bit.

Se non si è in grado di allocare la lista di array tutto in una volta, probabilmente si può allocare in parti.

Utilizzando una lista di array e l'aggiunta di 1 oggetto alla volta su una macchina 2008 x64 di Windows con 6GB di RAM, il massimo che può ottenere l'ArrayList a è la dimensione: 134217728. Così ho davvero penso che si debba trovare una soluzione migliore per il problema che non utilizza la quantità di memoria. Forse la scrittura su un file invece di utilizzare RAM.

Answer 2

Il limite matrice è, afaik, fissati come int32 anche su 64 bit. C'è un limite alla dimensione massima di un singolo oggetto. Tuttavia, si potrebbe avere una bella matrice irregolare grande abbastanza facilmente.

Peggio; perché i riferimenti sono più grandi di 64, per gli array ref-tipo è effettivamente ottenere meno elementi in un singolo array.

qui :

  

Ho ricevuto un numero di query come   motivo per cui la versione a 64 bit del 2.0   NET runtime ha ancora massima dell'array   dimensioni limitato a 2GB. Dato che   sembra essere un tema caldo negli ultimi tempi ho   capito un po 'di storia e di un   la discussione delle opzioni per ottenere   intorno a questa limitazione era in ordine.

     

In primo luogo alcune informazioni di base; in 2.0   versione del runtime .NET (CLR) che   preso una decisione consapevole di progettazione   mantenere la dimensione massima consentita dell'oggetto   nel GC Heap a 2GB, anche sul   versione a 64 bit del runtime. Questo è   la stessa della corrente 1.1   implementazione del CLR a 32 bit,   tuttavia si sarebbe difficile premuto per   effettivamente il gestore di allocare una 2GB   oggetto sul CLR a 32 bit perché il   spazio di indirizzi virtuali è semplicemente troppo   frammentato per trovare realisticamente un 2GB   buco. Generalmente le persone non sono   particolarmente interessati a creare   tipi che sarebbero> 2GB quando   istanziato (o dovunque vicino),   tuttavia, poiché gli array sono solo   tipo speciale di tipo gestito, che sono   creato all'interno del heap gestito hanno   soffrono anche di questa limitazione.

---

Si deve notare che nel NET 4.5 dimensione della memoria limite è eventualmente rimosso dal gcAllowVeryLargeObjects bandiera, tuttavia, questo non cambia la massima dimensione dimensioni. Il punto chiave è che se si dispone di array di un tipo personalizzato, o array multi-dimensionali, allora si può ora andare oltre 2 GB di dimensione della memoria.

Answer 3

Non hai bisogno di una matrice che grande a tutti.

Quando il metodo viene eseguito in problemi di risorse, non basta guardare a come espandere le risorse, guarda il metodo anche. :)

Ecco una classe che utilizza un buffer di 3 MB per calcolare i numeri primi con il crivello di Eratostene. La classe tiene traccia dei numeri primi fino a che punto si è calcolato, e quando il campo deve essere ampliato crea un buffer di testare altri 3 milioni di numeri.

Si mantiene i numeri primi si trovano in una lista, e quando la gamma si amplia i numeri primi previos vengono utilizzati per escludere i numeri nel buffer.

Ho fatto qualche test, e un buffer di circa 3 MB è 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 4

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

Su una nota più ampia, ho il sospetto che se avete bisogno di array di grandi dimensioni si dovrebbe davvero cambiare il modo si sta avvicinando il problema.

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, direi che, come non si è definito un tipo per l'esempio ArrayList, quindi la matrice sarebbe stato assegnato come un array di riferimenti a oggetti. Questo potrebbe significare che in realtà si sta assegnano 4-8GB di memoria seconda dell'architettura.

Answer 6

Secondo MSDN , l'indice di array di byte non può essere maggiore di 2147483591. per NET 4,5 prima era anche un limite di memoria per un array. NET 4.5 questo massimo è lo stesso, ma per altri tipi può essere fino a 2.146.435,071 mila.

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;
    }