1

私は化学式を多用する科学研究用のソフトウェアに取り組んでいます。「炭素13」、「窒素14」などのオブジェクトDictionary<Isotope, int>である内部を使用して化学式の内容を追跡します。これは、化学式内のそれらの同位体の数を表します。したがって、式C2H3NOは次のように存在します。Isotopeint

{"C12", 2
"H1", 3
"N14", 1
"O16", 1}

これはすべて問題なくダンディですが、2つの化学式を一緒に追加したい場合Isotope、値を更新するために2回のハッシュ関数を計算する必要があります。次のコード例を参照してください。

public class ChemicalFormula {
    internal Dictionary<Isotope, int> _isotopes = new Dictionary<Isotope, int>();

    public void Add(Isotope isotope, int count)
    {
        if (count != 0)
        {
            int curValue = 0;
            if (_isotopes.TryGetValue(isotope, out curValue))
            {
                int newValue = curValue + count;
                if (newValue == 0)
                {
                    _isotopes.Remove(isotope);
                }
                else
                {
                    _isotopes[isotope] = newValue;
                }
            }
            else
            {
                _isotopes.Add(isotope, count);
            }
            _isDirty = true;
        }
    }
}

これは遅くなるようには思えないかもしれませんが、何十億もの化学式を足し合わせているときですが、この方法は一貫してプログラムの最も遅い部分です（実行時間の> 45％）。私は「H5921C3759N1023O1201S21」のような大きな化学式を扱っていますが、これらは一貫して小さな化学式によって追加されています。

私の質問は、このようなデータを保存するためのより良いデータ構造はありますか？ダブルハッシュ関数を回避するために、（値型ではなく）参照型の値にアクセスできるように、を含む単純なIsotopeCountオブジェクトを作成しようとしました。intしかし、これは有益ではなかったようです。

EDIT Isotopeは不変であり、プログラムの存続期間中は変更されないため、ハッシュコードをキャッシュできるはずです。

私はソースコードにリンクしているので、ここにコピーして貼り付けるのではなく、クラスをより深く見ることができます。

4

4 に答える 4

0

アイソトープの数が限られていて、メモリの問題がない場合に考えられる別の解決策：

public struct Formula
{
   public int C12;
   public int H1;
   public int N14;
   public int O16;
}

あなたは有機化学を見ていると思いますので、それほど多くの同位体を扱う必要はないかもしれません。ルックアップが問題である場合、これはかなり高速になります...

于 2012-07-30T20:14:24.410 に答える
0

二重ハッシュ関数を回避するために（値型ではなく）参照型の値にアクセスできるように、intを含む単純なIsotopeCountオブジェクトを作成しようとしました。しかし、これは有益ではなかったようです。

まあそれはダブルハッシュを止めるでしょう...しかし明らかにそれはスペースの点でもっと悪いです。どのようなパフォーマンスの違いに気づきましたか？

これを頻繁に行う場合に強く検討する必要があるもう1つのオプションは、Isotope不変であると想定して、クラス内にハッシュをキャッシュすることです。（そうでない場合は、辞書キーとして使用するのは少なくとも多少心配です。）

ほとんどのIsotope値を辞書キー（または候補）として使用する可能性が高い場合は、初期化中にハッシュを計算する価値があります。それ以外の場合は、特に可能性の低いハッシュ値（理想的な世界では、任意の値）を選択し、それを「キャッシュされていない」値として使用して、遅延計算します。

実行時間の45％を使用しGetHashCodeている場合、それを最適化することを検討しましたか？それは実際にですかGetHashCode、それともEqualsどちらが問題ですか？（あなたは「ハッシュ」について話しますが、私はあなたが「一般的なハッシュルックアップ」を意味しているのではないかと思います。）

このタイプの関連するビットを投稿できれば、Isotopeさらにサポートできる可能性があります。

編集：.NET 4を使用しているかどうかを検討ConcurrentDictionaryする別のオプションは、そのAddOrUpdateメソッドを使用することです。次のように使用します。

public void Add(Isotope isotope, int count)
{
    // I prefer early exit to lots of nesting :)
    if (count == 0)
    {
        return 0;
    }

    int newCount = _isotopes.AddOrUpdate(isotope, count, 
                                         (key, oldCount) => oldCount + count);
    if (newCount == 0)
    {
        _isotopes.Remove(isotope);
    }
    _isDirty = true;
}
于 2012-07-30T19:51:42.710 に答える
0

タイプごとのアイソトープカウントへのランダムアクセスが実際に必要ですか、それともキーを値に関連付ける手段として辞書を使用していますか？

後者だと思います。

あなたへの私の提案は、辞書ではなく、IsotopeTuplesのソートされた配列（またはリスト）で作業することです。

class IsotopeTuple{
   Isotope i;
   int count;
}

同位体の名前でソートされています。

なぜ並べ替え？

したがって、2つの同位体を一緒に「追加」する場合は、両方の配列をトラバースすることで線形時間でこれを行うことができます（これが明確であることを願って、必要に応じて詳しく説明します）。ハッシュ計算は必要ありません。順序の超高速比較だけです。

これは、次元が単語であるベクトル乗算を処理する場合の古典的なアプローチです。テキストマイニングで広く使用されています。

トレードオフはもちろん、初期ベクトルの構築が（n）log（n）であるということですが、影響を感じるかどうかは疑問です。

于 2012-07-30T20:00:08.917 に答える
0

Isotope次に、事前に計算されたハッシュを使用して不変にする必要があるという意見を示します。それはすべてをはるかに簡単にするでしょう。

（実際、機能指向プログラミングはそのような種類の計算に適していて、不変のオブジェクトを扱います）

于 2012-07-30T20:01:21.787 に答える