lavorare con numeri incredibilmente grandi in .NET

Question

Sto cercando di risolvere i problemi su projecteuler.net ma continuo a riscontrare un paio di problemi.

La prima è una questione di memorizzazione di grandi quantità di elementi in un List<t>. Continuo a ricevere OutOfMemoryException quando memorizzo grandi quantità nell'elenco.

Ora ammetto che potrei non fare queste cose nel modo migliore ma, c'è un modo per definire la quantità di memoria che l'app può consumare?

Di solito si blocca quando ricevo circa 100.000.000 di elementi: S

In secondo luogo, alcune delle domande richiedono l'aggiunta di numeri enormi. Uso un tipo di dati ulong dove penso che il numero diventerà super grande, ma riesco ancora a superare il più grande int supportato e entrare in numeri negativi.

Hai qualche consiglio per lavorare con numeri incredibilmente grandi?

Answer 1

Prendi in considerazione System.Numerics.BigInteger .

Answer 2

È necessario utilizzare una classe di numeri di grandi dimensioni che utilizza alcuni principi matematici di base per suddividere queste operazioni. Questa implementazione di una libreria C # BigInteger su CodePoject sembra essere la più promettente. L'articolo contiene alcune buone spiegazioni di come funzionano anche le operazioni con numeri enormi.

Vedi anche: Interi grandi in C #

Answer 3

Per quanto riguarda Project Euler, potresti aver abbaiato l'albero sbagliato se stai colpendo le eccezioni OutOfMemory. Dal loro sito Web:

  

Ogni problema è stato progettato secondo una " regola di un minuto " ;, ciò significa che sebbene possano essere necessarie diverse ore per progettare un algoritmo di successo con problemi più difficili, un'implementazione efficiente consentirà una soluzione da ottenere su un computer modestamente alimentato in meno di un minuto.

Answer 4

Come ha detto l'utente Jakers, se stai usando i grandi numeri, probabilmente stai sbagliando.

Dei problemi di ProjectEuler che ho riscontrato, finora nessuno ha richiesto calcoli matematici. Si tratta più di trovare l'algoritmo corretto per evitare i grandi numeri.

Desideri suggerimenti? Pubblica qui e potremmo avere un interessante thread di Euler avviato.

Answer 5

Presumo che questo sia C #? F # ha incorporato metodi per gestire entrambi questi problemi (tipo BigInt e sequenze pigre).

Puoi usare entrambe le tecniche F # da C #, se lo desideri. Il tipo BigInt è ragionevolmente utilizzabile da altre lingue se aggiungi un riferimento all'assembly F # principale.

Le sequenze pigre sono sostanzialmente solo enumeratori amichevoli della sintassi. Mettere 100.000.000 di elementi in un elenco non è un ottimo piano, quindi dovresti ripensare le tue soluzioni per aggirare il problema. Se non hai bisogno di conservare le informazioni, gettale via! Se è più economico ricalcolarlo che conservarlo, buttalo via!

Answer 6

Vedi le risposte in questo thread. Probabilmente dovrai utilizzare una delle librerie / classi di interi di grandi dimensioni di terze parti disponibili o attendere C # 4.0 che includerà un tipo di dati nativo BigInteger.

Answer 7

Per quanto riguarda la quantità di memoria utilizzata da un'app, è possibile controllare la memoria disponibile prima di eseguire un'operazione utilizzando Classe MemoryFailPoint .

Ciò consente di preallocare la memoria prima di eseguire l'operazione, in modo da poter verificare se un'operazione non riuscirà prima di eseguirla.

Answer 8

Non è necessario utilizzare BigInteger. È possibile eseguire questo evento con un array di numeri stringa.

class Solution
{

    static void Main(String[] args)
    {
        int n = 5;
        string[] unsorted = new string[6] { "3141592653589793238","1", "3", "5737362592653589793238", "3", "5" };

        string[] result = SortStrings(n, unsorted);

        foreach (string s in result)
            Console.WriteLine(s);
        Console.ReadLine();
    }
    static string[] SortStrings(int size, string[] arr)
    {

        Array.Sort(arr, (left, right) =>
        {

            if (left.Length != right.Length)
                return left.Length - right.Length;
            return left.CompareTo(right);
        });

        return arr;
    }
}

Answer 9

string Add(string s1, string s2)
{
        bool carry = false;
        string result = string.Empty;

        if (s1.Length < s2.Length)
            s1 = s1.PadLeft(s2.Length, '0');
        if(s2.Length < s1.Length)
            s2 = s2.PadLeft(s1.Length, '0');

        for(int i = s1.Length-1; i >= 0; i--)
        {
            var augend = Convert.ToInt64(s1.Substring(i,1));
            var addend = Convert.ToInt64(s2.Substring(i,1));
            var sum = augend + addend;
            sum += (carry ? 1 : 0);
            carry = false;
            if(sum > 9)
            {
                carry = true;
                sum -= 10;
            }
            result = sum.ToString() + result;
        }
        if(carry)
        {
            result = "1" + result;
        }

    return result;
}

Answer 10

Non sono sicuro che sia un buon modo di gestirlo, ma nel mio progetto utilizzo quanto segue.

Ho un " raddoppia il RilevantNumber " variabile e un " int PowerOfTen " per ogni articolo e nella mia classe pertinente ho un " int rilevanteDecimals " variabile.

Quindi ... quando si incontrano grandi numeri vengono gestiti in questo modo:

Prima vengono cambiati in x, yyy form. Quindi, se è stato inserito il numero 123456.789 e & Quot; powerOfTen & Quot; aveva 10 anni, sarebbe iniziato così:

theRelevantNumber = 123456.789 PowerOfTen = 10 Il numero era quindi: 123456.789 * 10 ^ 10

Viene quindi modificato in: 1,23456789 * 10 ^ 15

Viene quindi arrotondato dal numero di decimali rilevanti (ad esempio 5) a 1,23456 e quindi salvato insieme a " PowerOfTen = 15 "

Quando si sommano o sottraggono numeri insieme, qualsiasi numero al di fuori dei decimali rilevanti viene ignorato. Significato se prendi:

1 * 10 ^ 15 + 1 * 10 ^ 10 cambierà in 1.00001 se " rilevanteDecimali " è 5 ma non cambierà affatto se " rilevanteDecimali " sono 4.

Questo metodo ti consente di gestire i numeri su doubleLimit * 10 ^ intLimit senza alcun problema, e almeno per OOP non è così difficile tenerne traccia.