如何利用预分组数据实现通用多维度分组？是否具备合理性？

我有一组已按属性值预分组的记录，数据结构如下。现在需要按指定属性（如JobPosition和EmploymentClassification）的组合对记录进行分组，同时希望复用预分组数据以避免遍历全量记录，但担心合并交集时的性能问题。另外，运行时的属性名和值并非硬编码，需要实现适配任意规模索引字典的通用方案。

现有预分组数据结构 #

Dictionary<string, Dictionary<string, List<string>>> Data = new Dictionary<string, Dictionary<string, List<string>>>()
{
    { "JobPosition", new Dictionary<string, List<string>>() 
        {
            { "Sales", new List<string>(){ "Record_ID_1", "Record_ID_2" } },
            { "Engineer", new List<string>(){ "Record_ID_3", "Record_ID_4" } },
            { "Manager", new List<string>(){ "Record_ID_5" } },
        }
    },
    {
        "EmploymentClassification", new Dictionary<string, List<string>>()
        {
            { "Full_Time", new List<string>(){ "Record_ID_1", "Record_ID_2", "Record_ID_5" } },
            { "Part_Time", new List<string>(){ "Record_ID_3", "Record_ID_4" } },
        }
    }
};

预期分组结果 #

Dictionary<List<KeyValuePair<string, string>>, List<string>> final = new Dictionary<List<KeyValuePair<string, string>>, List<string>>()
{
    {
        new List<KeyValuePair<string, string>>()
        {
            new KeyValuePair<string, string>("JobPosition", "Sales"),
            new KeyValuePair<string, string>("EmploymentClassification", "Full_Time")
        },
        new List<string>(){ "Record_ID_1", "Record_ID_2" }
    },
    {
        new List<KeyValuePair<string, string>>()
        {
            new KeyValuePair<string, string>("JobPosition", "Engineer"),
            new KeyValuePair<string, string>("EmploymentClassification", "Part_Time")
        },
        new List<string>(){ "Record_ID_3", "Record_ID_4" }
    },
    {
        new List<KeyValuePair<string, string>>()
        {
            new KeyValuePair<string, string>("JobPosition", "Manager"),
            new KeyValuePair<string, string>("EmploymentClassification", "Full_Time")
        },
        new List<string>(){ "Record_ID_5" }
    },
};

核心诉求与顾虑 #

• 复用预分组数据，避免遍历全量记录
• 实现通用方案，适配任意数量的属性和属性值
• 担忧合并交集时的性能问题，不确定是否比直接遍历记录更高效

已尝试方案（性能极差） #

分组键类 #

public class PropertyValueGroupKey
{
    public List<Tuple<string, string>> Values { get; set; } = new List<Tuple<string, string>>();
    public override bool Equals(object obj)
    {
        if(obj is PropertyValueGroupKey other)
        {
            if (other.Values.Count != this.Values.Count)
                return false;
            return other.Values.All(x => this.Values.FirstOrDefault(y => y.Item1 == x.Item1 && y.Item2 == x.Item2) != null);
        }
        return false;
    }

    public override int GetHashCode()
    {
        int hash = 0;
        foreach (var element in Values)
        {
            hash = hash ^ EqualityComparer<string>.Default.GetHashCode(element.Item1);
            hash = hash ^ EqualityComparer<string>.Default.GetHashCode(element.Item2);
        }
        return hash;
    }
}

实现代码 #

var baseIndex = indicies.FirstOrDefault();
foreach(var entry in baseIndex.Value)
{
    var groupKey = new PropertyValueGroupKey();
    groupKey.Values.Add(Tuple.Create(baseIndex.Key, entry.Key));
    foreach(var otherIndex in indicies)
    {
        if (otherIndex.Key == baseIndex.Key)
            continue;
        else
        {
            foreach(var otherEntry in otherIndex.Value)
            {
                groupKey.Values.Add(Tuple.Create(otherIndex.Key, otherEntry.Key));
            }
        }
    }
    var data = filteredRecords;
    foreach(var key in groupKey.Values)
    {
        data = indicies[key.Item1][key.Item2].Values.Intersect(data);
    }
    final.Add(groupKey, data.ToList());
}

问题分析 #

1. 错误的组合生成逻辑：代码会将所有其他属性的所有值都添加到分组键中，导致生成无效的组合（比如同时包含Full_Time和Part_Time）
2. 低效的相等性判断：Equals方法中使用FirstOrDefault遍历整个列表，性能极差
3. 哈希码实现缺陷：使用XOR会导致不同组合产生相同哈希码的概率较高，影响字典性能
4. 交集计算未优化：未利用哈希集合加速交集判断，且未从最小列表开始计算

优化解决方案 #

1. 高效分组键实现（使用Record） #

利用C# 9+的record类型自动实现值相等性和高效哈希码：

public record PropertyValueGroupKey(IReadOnlyList<KeyValuePair<string, string>> Values)
{
    public override string ToString() => string.Join(", ", Values.Select(kv => $"{kv.Key}:{kv.Value}"));
}

2. 生成属性值组合（笛卡尔积） #

生成所有合法的属性值组合（每个属性选一个值）：

public static IEnumerable<IReadOnlyList<KeyValuePair<string, string>>> GetPropertyValueCombinations(Dictionary<string, Dictionary<string, List<string>>> indices)
{
    if (!indices.Any())
    {
        yield return Array.Empty<KeyValuePair<string, string>>();
        yield break;
    }

    // 将每个属性的所有值转换为(属性名, 属性值)的键值对
    var propertyOptions = indices.Select(kv => 
        kv.Value.Select(v => new KeyValuePair<string, string>(kv.Key, v.Key))
    ).ToList();

    // 初始化结果为第一个属性的所有选项
    var combinations = propertyOptions[0].Select(opt => new List<KeyValuePair<string, string>> { opt });

    // 逐步合并后续属性的选项，生成笛卡尔积
    foreach (var options in propertyOptions.Skip(1))
    {
        combinations = from combo in combinations
                       from opt in options
                       select new List<KeyValuePair<string, string>>(combo) { opt };
    }

    foreach (var combo in combinations)
    {
        yield return combo.AsReadOnly();
    }
}

3. 计算交集并生成最终分组 #

优化交集计算逻辑，从最小列表开始并使用哈希集合加速：

public static Dictionary<PropertyValueGroupKey, List<string>> CombineIndices(Dictionary<string, Dictionary<string, List<string>>> indices)
{
    var finalGroups = new Dictionary<PropertyValueGroupKey, List<string>>();

    foreach (var combo in GetPropertyValueCombinations(indices))
    {
        // 获取当前组合对应的所有记录列表
        var recordLists = combo.Select(kv => indices[kv.Key][kv.Value]).ToList();
        
        // 从最小的列表开始计算交集，减少后续计算量
        var smallestList = recordLists.OrderBy(l => l.Count).First();
        var currentIntersection = smallestList.ToList();

        foreach (var list in recordLists.Where(l => l != smallestList))
        {
            var recordSet = new HashSet<string>(list);
            currentIntersection = currentIntersection.Where(id => recordSet.Contains(id)).ToList();
            
            // 交集为空时提前退出，避免无效计算
            if (!currentIntersection.Any())
                break;
        }

        if (currentIntersection.Any())
        {
            var groupKey = new PropertyValueGroupKey(combo);
            finalGroups[groupKey] = currentIntersection;
        }
    }

    return finalGroups;
}

性能说明 #

• 复用预分组数据：无需遍历全量记录，仅处理预分组后的列表交集
• 优化交集计算：从最小列表开始，使用哈希集合将查找时间降至O(1)
• 高效键实现：record类型提供的值相等性和哈希码比自定义类更可靠高效
• 提前终止：交集为空时立即停止计算，减少不必要的操作

当预分组列表较大且属性组合数量可控时，此方案比直接遍历全量记录更高效。若属性组合数量极大（如数十个属性每个有上百个值），则需权衡组合数与全量记录数的规模，选择更合适的方案。

内容的提问来源于stack exchange，提问作者B.degans