1

我正在开发大量处理化学公式的科学研究软件。我使用内部来跟踪化学式的内容，Dictionary<Isotope, int>其中Isotope是“Carbon-13”，“Nitrogen-14”之类的对象，并且int表示化学式中这些同位素的数量。所以公式 C2H3NO 会像这样存在：

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

这一切都很好，但是当我想将两个化学式相加时，我最终不得不计算Isotope两次的哈希函数来更新一个值，请参见下面的代码示例。

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包含 a 的简单对象，int这样我就可以访问引用类型（而不是值类型）中的值以避免双重哈希函数。然而，这似乎并没有什么好处。

EDIT Isotope是不可变的，在程序的生命周期内不应更改，因此我应该能够缓存哈希码。

我已链接到源代码，因此您可以更深入地查看这些类，而不是我在这里复制和粘贴它们。

4

4 回答 4

0

您实际上是否需要按类型随机访问同位素计数，或者您是否使用字典作为将键与值关联的手段？

我猜是后者。

我对您的建议不是使用字典，而是使用 IsotopeTuples 的排序数组（或列表），例如：

class IsotopeTuple{
   Isotope i;
   int count;
}

按同位素名称排序。

为什么要排序？

因为那时，当您想将两个同位素“添加”在一起时，您可以通过遍历两个阵列在线性时间内完成此操作（希望这很清楚，如果需要我可以详细说明）。不需要哈希计算，只需超快速的顺序比较。

在处理维度为单词的向量乘法时，这是一种经典的方法。广泛用于文本挖掘。

权衡当然是初始向量的构造是 (n)log(n)，但我怀疑你是否会感受到影响。

于 2012-07-30T20:00:08.917 回答
0

我尝试创建一个包含 int 的简单 IsotopeCount 对象，这样我就可以访问引用类型（而不是值类型）中的值以避免双重哈希函数。然而，这似乎并没有什么好处。

那么它会停止双重哈希......但显然它在空间方面更糟。您注意到什么性能差异？

如果您经常这样做，您应该强烈考虑的另一个选项是在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

Isotope我赞同应该使用预先计算的哈希值使其不可变的观点。这将使一切变得简单得多。

（事实上​​，面向函数的编程更适合这种类型的计算，它处理不可变对象）

于 2012-07-30T20:01:21.787 回答
0

如果您的同位素数量有限且没有内存问题，您可以想到的另一种解决方案：

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

我猜你正在研究有机化学，所以你可能不必处理那么多同位素，如果查找是问题，这个会很快......

于 2012-07-30T20:14:24.410 回答