.NETで信じられないほど大きな数で作業する
-
07-07-2019 - |
質問
projecteuler.net の問題を解決しようとしていますが、いくつかの問題が発生し続けています。
最初の問題は、List<t>
に大量の要素を格納することです。リストに大量に保存すると、OutOfMemoryExceptionが発生し続けます。
これらのことを最善の方法で行っていないかもしれませんが、アプリが消費できるメモリ量を定義する方法はありますか?
通常、100,000,000個の要素を取得するとクラッシュします:S
第二に、いくつかの質問では大量の数字を追加する必要があります。数値が非常に大きくなると思われるulongデータ型を使用しますが、サポートされている最大のintを超えてラップし、負の数値を取得できます。
信じられないほど大きな数を扱うためのヒントはありますか?
解決
他のヒント
これらの操作を分割するには、いくつかの基本的な数学プリンシパルを使用する多数のクラスを使用する必要があります。 CodePojectでの C#BigIntegerライブラリの実装が最も有望であるようです。この記事には、大量の演算がどのように機能するかについての良い説明もあります。
また見なさい: C#の大きな整数
プロジェクトオイラーに関する限り、OutOfMemory例外をヒットしている場合、間違ったツリーを起動している可能性があります。彼らのウェブサイトから:
各問題は<!> quot; 1分間のルール<!> quot;に従って設計されています。つまり、より困難な問題を抱える成功したアルゴリズムの設計には数時間かかる場合がありますが、効率的な実装により適度なパワーを備えたコンピューターで1分以内に得られるソリューション。
ユーザーJakersが言ったように、Big Numbersを使用している場合、おそらく間違っているのでしょう。
私がやったProjectEulerの問題のうち、これまでに大きな数の計算を必要としたものはありませんでした。 大きな数を避けるための適切なアルゴリズムを見つけることについての詳細。
ヒントが必要ですか?ここに投稿すると、面白いオイラースレッドが開始される可能性があります。
これはC#だと思いますか? F#では、これらの問題(BigInt型と遅延シーケンス)の両方を処理する方法が組み込まれています。
必要に応じて、C#の両方のF#テクニックを使用できます。コアF#アセンブリへの参照を追加する場合、BigInt型は他の言語から合理的に使用できます。
遅延シーケンスは、基本的には単なる構文フレンドリーな列挙子です。リストに1億個の要素を入れるのは素晴らしい計画ではないので、それを回避するためにソリューションを再考する必要があります。情報を保持する必要がない場合は、捨ててください!格納するよりも再計算する方が安い場合は、捨ててください!
このスレッド。おそらく、利用可能なサードパーティのビッグ整数ライブラリ/クラスのいずれかを使用するか、ネイティブBigIntegerデータ型を含むC#4.0を待つ必要があります。
アプリが使用するメモリ量を定義する限り、 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;
}
それが適切な処理方法であるかどうかはわかりませんが、プロジェクトでは以下を使用します。
<!> quot; double theRelevantNumber <!> quot;があります。変数と<!> quot; int PowerOfTen <!> quot;各アイテムおよび関連するクラスには、<!> quot; int relatedDecimals <!> quot;があります。変数。
そのため、大量のデータが検出されると、次のように処理されます:
最初にx、yyy形式に変更されます。したがって、数値123456,789が入力され、<!> quot; powerOfTen <!> quot; 10だった場合、次のように開始されます:
theRelevantNumber = 123456,789 PowerOfTen = 10 数は123456,789 * 10 ^ 10
でしたその後、次のように変更されます。 1,23456789 * 10 ^ 15
次に、関連する小数の数(5など)で1,23456に丸められ、<!> quot; PowerOfTen = 15 <!> quot;とともに保存されます。
数字を一緒に加算または減算する場合、関連する小数以外の数字は無視されます。あなたが取る場合の意味:
1 * 10 ^ 15 + 1 * 10 ^ 10 <!> quot; relevantDecimals <!> quot;の場合、1,00001に変更されます。 5ですが、<!> quot; relevantDecimals <!> quot;の場合はまったく変更されません。 4です。
このメソッドを使用すると、doubleLimit * 10 ^ intLimitまでの数値を問題なく処理できます。少なくともOOPの場合、追跡するのはそれほど難しくありません。