我知道标题可能会误导人，常见的答案可能是'再去搜索'，但是我已经尽可能多地搜索了堆栈溢出，我没有找到一个能满足我的答案。
我需要创建一个算法，它将删除嵌套的、交叉引用的列表中所有相似的项。
一般规则:
- 项可以有子项，并且可以引用其他项。
- 对象不能同时引用另一个对象并有子对象。
- 在一个列表中可以有很多对象(最多100k)，对于子对象总是有多达1级的深度，但是每个对象的未知的，可变长度的引用链。
- 引用链不是无限的，它们通常有多达5-15个元素，并且总是以已知ClassType字段的对象结束。
- 可能存在"死链"——即不被任何对象引用但引用其他对象的项。
- 对象的子元素不是列表的一部分——它们可以引用其他元素，但不能单独引用。
- 为了比较两个对象，它们的属性必须与它们的子对象(如果存在)和被引用对象(如果存在)相同。
- 当比较子对象或引用对象时，同样的规则适用。
- 唯一ID分配给每个对象(这不是一个哈希码，而不是对象创建的顺序)-两个对象将是相同的，尽管他们有不同的ID。没有相同ID的对象。
内存需求和CPU占用率没有指定-首选高性能。我目前的方法(将每个对象与另一个对象进行比较的蛮力方法)是放慢速度，可能需要长达1小时的运行时间。最好的执行速度是1分钟。我的方式迭代集合无限次，因为相同的对象被发现，它只使用单线程。我希望得到多线程更确定的方法。
考虑以下对象定义:
public enum ClassType
{
Type_Base,
Type_A,
Type_B,
Type_C,
};
public class MyObject
{
public string Name { get; }
public uint ID { get; }
public ClassType ClassType { get; }
public uint ReferencedID { get; }
public List<MyObject> Children { get; } = new List<MyObject>( );
}
和MyObject的ID属性索引的集合，用于快速访问:
Dictionary<uint, MyObject> Preserved; // Top-most objects, has to be preserved
Dictionary<uint, MyObject> AllObjects; // Dictionary of all objects
另外，考虑以下比较方法:
public static bool AreObjectsSame( MyObject l, MyObject r, Dictionary<uint, MyObject> allObjects )
{
// Null-Check
if ( l is null ) throw new ArgumentNullException( nameof( l ) );
if ( r is null ) throw new ArgumentNullException( nameof( r ) );
if ( allObjects is null ) throw new ArgumentNullException( nameof( allObjects ) );
// Compare class type and name
if ( l.ClassType != r.ClassType ) return false;
if ( l.Name != null && r.Name != null && !l.Name.Equals( r.Name, StringComparison.InvariantCulture ) ) return false;
// Compare referenced ID objects
if ( l.ReferencedID != 0 && r.ReferencedID != 0 )
{
if ( !AreObjectsSame( allObjects[ l.ReferencedID ], allObjects[ r.ReferencedID ], allObjects ) ) return false;
}
// Compare children objects
if ( l.Children.Count != r.Children.Count ) return false;
for ( int i = 0; i < l.Children.Count; ++i )
{
if ( !AreObjectsSame( l.Children[ i ], r.Children[ i ], allObjects ) ) return false;
}
return true;
}
现在让我们检查一个对象链。具有子对象的对象以类似的方式工作，因此为了解释简单，我将跳过它们。
MyObject ("Name_A", Type_A) -> MyObject ("Name_B", Type_B) -> MyObject ("Name_C", Type_A) -> MyObject ("Name_D", Type_Base)
MyObject ("Name_E", Type_C) -> MyObject ("Name_F", Type_C) -> MyObject ("Name_C", Type_A) -> MyObject ("Name_D", Type_Base)
MyObject ("Name_G", Type_A) -> MyObject ("Name_D", Type_Base)
现在，我们可以把上面的对象链优化成这样:
MyObject ("Name_A", Type_A) -> MyObject ("Name_B", Type_B) -> MyObject ("Name_C", Type_A) -> MyObject ("Name_D", Type_Base)
MyObject ("Name_E", Type_C) -> MyObject ("Name_F", Type_C) ->-|
MyObject ("Name_G", Type_A) -------------------------------->-/
这导致我们删除3个重复的节点并重新排列其中两个节点的引用id。
可能的解决方案
一种可能的解决方案是为每个元素预先计算其自己的哈希码，并使用该哈希码以蛮力方式比较元素。如果比较为真，则执行逐字段比较(以消除哈希码中可能的冲突)。
是否有更好的方法删除重复项?我该怎么做呢?
一些快速的建议:
- 是的，预先计算哈希码并只对具有相同哈希码的项目进行深入比较
- 在A对B进行检验后，不要对A对B进行检验，按一定顺序取项，只对索引X处的项进行大于X的检验
- 在比较过程中不删除项目，而是将剩余的项目单独收集，并在结束时删除原始项目
- 在遍历所有项的算法中使用像array这样的可索引集合。
但首先使用一些分析器工具，比如Redgate的性能分析器。很多时候我都在"优化"这个算法利用了我的直觉，没有取得任何可衡量的成功，但却让它变得更难以理解。在尝试了一个分析器之后，我发现，一个谁会想到的代码，比如字符串操作，过度使用的对象实例化，比我的算法要花更多的时间!分析器可以指向真正的代码。需要优化:)