将两种不同的信息组合成二进制代码

Question

我有Dictionary<string,T>，其中字符串代表记录的键，我还有另外两条关于记录的信息，我需要为字典中的每条记录维护，它们是记录的类别及其冗余度（重复了多少次）。

例如：记录XYZ1属于类别1，重复了1次。因此实现必须是这样的：

"XYZ1", {1,1}

现在继续，我可能会在我的数据集中遇到相同的记录，因此必须像这样更新键的值：

"XYZ1", {1,2} "XYZ1", {1,3} ...

由于我正在处理大量记录，例如 100K，我尝试了这种方法，但它似乎效率低下，因为从字典中获取值然后切片 {1,1} 然后将两个切片转换为整数的额外工作量给执行带来很多开销。

我正在考虑使用二进制数字来表示类别和重排，并可能使用位掩码来获取这些片段。

编辑： 我尝试使用具有 2 个属性的对象，然后使用 Tuple<int,int>。复杂性变得更糟了！

我的问题：是否可以这样做？

如果没有（在复杂性方面）有什么建议吗？

Answer 1

类别似乎永远不会改变。因此，与其使用简单的字符串作为字典的键，不如这样做：

Dictionary<Tuple<string,int>,int> 其中字典的键是 Tuple<string,int>，其中 string 是记录，int 是类别。那么字典中的值只是一个计数。

字典可能是您要完成的任务最快的数据结构，因为它具有接近恒定的时间 O(1) 查找和输入。

您可以通过使用元组来加快速度，因为现在类别是键的一部分，不再是您必须单独访问的一些信息。

同时，您也可以将字符串作为键并存储一个Tuple<int,int>作为值，只需将Item1设置为类别，将Item2设置为计数。

两种方式的速度大致相当。无论哪种方式，以这种方式处理 100k 条记录应该都非常快。

Answer 2

你是什么类型的T？您可以定义一个自定义类型，其中包含您需要的信息（类别和出现次数）。

class MyInfo {
  public int c { get; set; } 
  public int o { get; set; }
}

Dictionary<String, MyInfo> data;

然后在遍历您的数据时，您可以轻松地检查某个键是否已经存在。如果是，则增加出现次数，否则插入一个新元素。

MyInfo d;
foreach (var e in elements) {
    if (!data.TryGet(e.key, out d))
        data.Add(e.key, new MyInfo { c = e.cat, o= 1});
    else
        d.o++;
}

编辑

您也可以将类别和出现次数合并为一个 UInt64。例如取高32位的类别（即可以有40亿个类别）和低32位的出现次数（即每个键可以出现40亿次）

Dictionary<string, UInt64> data;

UInt64 d;
foreach (var e in elements) {
    if (!data.TryGet(e.key, out d)) 
       data[e.key] = (e.cat << 32) + 1;
    else 
        data[e.key] = d + 1;

}

如果您想获取某个特定键的出现次数，您只需检查值的相应部分即可。

var d = data["somekey"];
var occurrences = d & 0xFFFFFFFF;  
var category = d >> 32;

将两种不同的信息组合成二进制代码

combining two different information in binary code

c#

binary

dictionary

bitmask