双自连接寻找增加更多独特价值的项目

Question

我有一个Dictionary<Key, <Quality,Item>>，它跟踪质量和项目之间的关系。质量是一个对象类型，项目是一个对象类型，在其他地方我有有效质量和有效项目的列表。物品有一个固定的品质列表，总是不止一个。质量可以由任意数量的项目保持，包括0，这取决于程序的状态。

目前，Item对象也会在List中跟踪它们自己的品质，这是我解决这个问题的失败策略之一。我不知道这是否有帮助，它现在肯定帮不了我，如果被证明是无用的，可能会被撕掉。

我已经有了一个LINQ自连接，它收集了对唯一的项目，成功地共享至少一个质量。

var r = from KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_1
        in QualitiesToItems
        join KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_2
        in QualitiesToItems
        on virtQ2I_1.Value.Item1.name equals virtQ2I_2.Value.Item1.name
        where (virtQ2I_1.Value.Item2.name != virtQ2I_2.Value.Item2.name)
        select new List<Item>
        {
            virtQ2I_1.Value.Item2, 
            virtQ2I_2.Value.Item2
        };

之后，我使用另一个Dictionary来清理<ItemA,>被认为与<ItemB,>相同的小问题。

What Is Needed:每个三元组的唯一项目的列表，这些项目与三元组中至少一个其他项目共享至少一个质量。大麻烦的复杂性:三元组中的第三项不能只是共享一个现有的共有品质;它必须为这段关系带来一些新的东西。我需要从几百个项目的列表中快速得到结果——我现有的解决方案不能满足这最后一个要求。

例子:

• ItemA是毛茸茸的、金发的、四条腿的、受过训练的
• ItemB是毛茸茸的，罗文，六条腿，和训练
• ItemC是有羽毛的，蓝色的，两条腿的，训练有素的

• ItemD是缩放的，Rowan, Slithers和未训练的

  • ItemA和ItemB将已经作为有效对被拾取，毛茸茸的和训练有素的。(B:当然是另一回事A:C和B:C)

  • ItemA、ItemB和ItemC不像a:B那样构成有效的三元组已经接受过培训，ItemC与两者没有任何共同之处ItemA或ItemB;A:B:C和A:B有相同的质量清单，因此C被拒绝为"多余的"或"多余的"

  • itemema、ItemB和ItemD组成一个有效的三元组，因为ItemD形成一对在罗文周围用ItemB。A:B:D的结果是毛茸茸的，罗文的，训练有素的……我需要A:B:D的组合来进入我的返回结果列表。

从我的配对方式到我需要在合理的时间内处理几百个项目的三胞胎方式，我都遇到了问题。

我认为我是非常聪明的，当我写了一个方法来寻找两个项目之间的共享品质，并在我的新LINQ查询中使用它，但结果是…当在超过几十个项目上使用时相当慢，并且我的计算机与将要运行该程序的一些机器相比，性能太强了。

var r = from KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_1 
        in QualitiesToItems 
        join KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_2 
        in QualitiesToItems
        on virtQ2I_1.Value.Item1.name equals virtQ2I_2.Value.Item1.name
        join KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_3
        in QualitiesToItems
        on virtQ2I_2.Value.Item1.name equals virtQ2I_3.Value.Item1.name
        where (virtQ2I_1.Value.Item2.name != virtQ2I_2.Value.Item2.name &&
        virtQ2I_1.Value.Item2.name != virtQ2I_3.Value.Item2.name &&
        virtQ2I_2.Value.Item2.name != virtQ2I_3.Value.Item2.name &&
        Item.SharedQualities(this, new Item[2] { virtQ2I_1.Value.Item2, virtQ2I_2.Value.Item2 }).Count !=
        Item.SharedQualities(this, new Item[3] { virtQ2I_1.Value.Item2, virtQ2I_2.Value.Item2, virtQ2I_3.Value.Item2 }).Count)
        select new List<Item>
        {
            virtQ2I_1.Value.Item2, 
            virtQ2I_2.Value.Item2, 
            virtQ2I_3.Value.Item2
        };

所以:这工作，但我不喜欢它。是否有一种方法来取代我的函数调用(和新的项目数组)与一些纯粹的LINQ中期查询?一定存在。

Answer 1

对这个问题进行了更多的思考，提供了一个解决方案，它在LINQ中做了最糟糕的繁重工作，并且比我在原始帖子中尝试的性能要好得多。

//collect two-pair items
var result = from KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_1
                    in QualitiesToItems
         join KeyValuePair<int, Tuple<Quality, Item>> virtQ2I_2
                 in QualitiesToItems
         on virtQ2I_1.Value.Item1.name equals virtQ2I_2.Value.Item1.name
         where (virtQ2I_1.Value.Item2.name != virtQ2I_2.Value.Item2.name)
         select new List<Item> {
                    virtQ2I_1.Value.Item2, 
                    virtQ2I_2.Value.Item2
                    };
List<List<Item>> ItemsForSets = result.ToList();
// self-join raw two-pair item list to generate three-set items
result =    from List<Item> leftSide in ItemsForSets 
        join List<Item> rightSide in ItemsForSets
        on leftSide[1] equals rightSide[0]
        where (leftSide[0] != rightSide[1])
        select new List<Item> {
                    leftSide[0], 
                    leftSide[1],
                    rightSide[1]
                    };
ItemsForSets.AddRange(result.ToList());
// clean up results - preventing A:B and B:A from being considered unique,
//    and ensuring all third ingredients actually contribute to a relationship.
foreach (List<Item> items in ItemsForSets)
{
    List<Quality> sharedQualities = Item.SharedQualities(this, items.ToArray());
    sharedQualities.Sort();
    List<String> sortedItems = items.ConvertAll(item => item.name); // I need the string names elsewhere 
    // TODO: I should rewrite to work directly with Items and convert after confirming I actually need the item.
    sortedItems.Sort(); // first part of preventing A:B B:A problems
    if (!Sets.ContainsKey(String.Join(", ", sortedItems))) // Dictionary provides second part.
    {
        if (items.Count == 3)
        {
            List<Quality> leftPairQualities = Item.SharedQualities(this, items.GetRange(0, 2).ToArray());
            leftPairQualities.Sort();
            if (leftPairQualities.SequenceEqual(sharedQualities))
            { // if the third item does not add a new quality
                continue; // short circuit out to the next item
            }
        }
        // otherwise add to the list.
        Sets.Add(String.Join(", ", sortedItems), new Potion(items, sharedQualities));
    }
}

我可以做更多的清理，我可能可以用另一个LINQ查询替换foreach，但这会消除大的障碍，并显著提高性能。