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

Question

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

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

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

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

Вам не нужно использовать 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;
    }
}

Answer 7

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

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

Answer 8

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

Answer 9

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

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

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

Сначала они меняются на x, yyy форму. Таким образом, если было введено число 123456 789 и «powerOfTen» равнялось 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, и, по крайней мере, для ООП это не так сложно отследить.

Answer 10

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