работа с невероятно большими числами в .NET

StackOverflow https://stackoverflow.com/questions/279038

Вопрос

Я пытаюсь решить проблемы с projecteuler.net , но продолжаю сталкиваться с парой проблем.

Первый - это вопрос хранения больших количеств элементов в List<t>. Я продолжаю получать OutOfMemoryException при хранении больших количеств в списке.

Теперь я признаю, что могу делать это не лучшим образом, но есть ли способ определить, сколько памяти может потреблять приложение?

Обычно происходит сбой, когда я получаю около 100 000 000 элементов: S

Во-вторых, некоторые вопросы требуют добавления огромных чисел. Я использую тип данных ulong, где я думаю, что число станет очень большим, но мне все же удается обойти самое большое поддерживаемое целое число и получить отрицательные числа.

Есть ли у вас какие-либо советы по работе с невероятно большими числами?

Это было полезно?

Решение

Рассмотрим System.Numerics.BigInteger .

Другие советы

Вам нужно использовать класс большого числа, который использует некоторые базовые математические принципы, чтобы разделить эти операции. Эта реализация библиотеки C # BigInteger в CodePoject представляется наиболее перспективной. В статье есть несколько хороших объяснений того, как работают операции с массивными числами.

Также смотрите: Большие целые числа в C #

Что касается Project Euler, то вы можете лаять не то дерево, если сталкиваетесь с исключениями OutOfMemory. С их сайта:

  

Каждая задача была разработана в соответствии с & правилом одной минуты &, что означает, что, хотя для разработки успешного алгоритма с более сложными задачами может потребоваться несколько часов, эффективная реализация позволит решение, которое будет получено на компьютере со скромным питанием менее чем за одну минуту.

Как сказал пользователь Jakers, если вы используете большие числа, возможно, вы делаете это неправильно.

Из всех проблем ProjectEuler, которые я сделал, до сих пор ни одна из них не требовала математики с большими числами. Это больше о поиске правильного алгоритма, чтобы избежать больших чисел.

Хотите подсказки? Публикуйте здесь, и мы могли бы начать интересную тему Эйлера.

Я предполагаю, что это C #? В F # встроены способы решения обеих этих проблем (тип BigInt и ленивые последовательности).

Вы можете использовать обе техники F # из C #, если хотите. Тип BigInt можно использовать на других языках, если вы добавите ссылку на базовую сборку F #.

Ленивые последовательности - это в основном просто синтаксически дружественные перечислители. Поместить 100 000 000 элементов в список не очень хороший план, поэтому вам следует пересмотреть свои решения, чтобы обойти это. Если вам не нужно хранить информацию, выбросьте ее! Если его пересчитать дешевле, чем хранить, выбросьте!

См. ответы в этом нить . Возможно, вам потребуется использовать одну из доступных сторонних библиотек / классов больших целых чисел или дождаться C # 4.0, который будет включать собственный тип данных BigInteger.

Что касается определения того, сколько памяти будет использовать приложение, вы можете проверить доступную память перед выполнением операции, используя класс MemoryFailPoint .

Это позволяет вам предварительно выделить память перед выполнением операции, чтобы вы могли проверить, не завершится ли операция, прежде чем выполнять ее.

Вам не нужно использовать BigInteger. Вы можете сделать это событие со строковым массивом чисел. 

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

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

Я не уверен, что это хороший способ справиться с этим, но я использую следующее в своем проекте.

У меня есть " двойной theRelevantNumber " переменная и " int PowerOfTen " для каждого элемента и в моем соответствующем классе у меня есть " int relatedDecimals " переменная.

Итак ... когда встречаются большие числа, они обрабатываются так:

Сначала они изменяются на x, yyy форму. Таким образом, если было введено число 123456 789 и & Quot; powerOfTen & Quot; было 10, это началось бы так:

theRelevantNumber = 123456,789 PowerOfTen = 10 Число было тогда: 123456,789 * 10 ^ 10

Затем оно изменяется на: 1,23456789 * 10 ^ 15

Затем он округляется по количеству соответствующих десятичных знаков (например, 5) до 1,23456, а затем сохраняется вместе с " PowerOfTen = 15 "

При сложении или вычитании чисел любое число за пределами соответствующих десятичных знаков игнорируется. Смысл, если вы берете:

1 * 10 ^ 15 + 1 * 10 ^ 10 изменится на 1,00001, если " релевантные_десятичные " равно 5, но не изменится, если " релевантное_десятичное " 4.

Этот метод позволяет вам без проблем работать с числами до doubleLimit * 10 ^ intLimit, и, по крайней мере, для ООП это не так сложно отследить.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top