2

HashSet<T>C＃4.0には階層オブジェクトがあります。メインキーはintですが、重複するセカンダリキーが存在する場合があります。重複したセカンダリキーを持つエントリをマージしたいと思います。この例では、2次キーはNameです。

struct Element
{
  int ID;
  string Name;
  List<int> Children;
  List<int> Parents;

  public override int GetHashCode()
  {
    return ID;
  }
}

HashSet<Element> elements = new HashSet<Element>();

// Example Elements
elements.Add(1, "Apple", Children = {10, 11, 12}, Parents = {13,14,15});
elements.Add(2, "Banana", Children = {20, 21, 22}, Parents = {23,24,25});
elements.Add(3, "Apple", Children = {30, 31, 32}, Parents = {33,34,35});
elements.Add(4, "Food", Children = {1, 2, 3}, Parents = {});

目標は、3番目のエントリ{3、 "Apple"、...}を削除してから、他の残りの要素の親と子の参照を更新してマージすることです。最終結果は次のようになります。

{ 1, "Apple", Children = { 10, 11, 12, 30, 31, 32 }, Parents = { 13,14,15, 33, 34, 35 }}
{ 2, "Banana", Children = { 20, 21, 22 }, Parents = { 23,24,25 }}
{ 4, "Food", Children = {1, 2}, Parents = {} }

これが私がこれまでに持っているものですが、HashSetを適切に更新するための最良の方法を見つけることができません。反復中に削除できるように、HashSetをコピーすることから始めます。まず、重複を見つけます。重複がある場合は更新したいので、コピーから削除します。それは私が立ち往生しているところです。重複を更新したら、それらを削除し、スキップリストを使用して再度処理されないようにします。

var copy = new HashSet<Element>(Elements);
HashSet<int> skip = new HashSet<int>();
foreach (var e in Elements)
{
  if (!skip.Contains(e.ID)
  {
    var duplicates = Elements.Where(x => e.Name == x.Name && e.ID != x.ID);
    if (duplicates.Any())
    {           
      foreach (var d in duplicates)
      {
        // Iterate copy and update Parent and Children references
        // How do I do this part? 
      }

      // Remove the duplicates from the copied list
      copy.RemoveWhere(x => duplicates.Select(x => x.ID)
                                      .Contains(x.ID));

      // Don't process the duplicates again
      skip.UnionWith(duplicates);
    } 
  }
}
return copy;

私はこの時点で立ち往生しています。また、Linqでこれを行うための巧妙な方法はありますか？

更新：リストはすでにこのようになっています。最初の内容を制御することはできません。重複を防ぐために、より優れたAddメソッドを持つ新しいラッパーを作成できると思います。

4

3 に答える 3

2

この単一のフィールド要素を追加してみてください。

struct Element
{
  int ID;
  string Name;
  List<int> Children;
  List<int> Parents;
  Bool duplicate;
}

HashSet<Element> Elements = new HashSet();

// Example Elements
Elements.Add(1, "Apple", Children = {10, 11, 12}, Parents = {13,14,15}, duplicate = false);
Elements.Add(2, "Banana", Children = {20, 21, 22}, Parents = {23,24,25}, duplicate = false);
Elements.Add(3, "Apple", Children = {30, 31, 32}, Parents = {33,34,35}, duplicate = false);
Elements.Add(4, "Food", Children = {1, 2, 3}, Parents = {}, duplicate = false);

コピーを繰り返すときに、「duplicate」をtrueにマークします。または、再処理しないように「削除済み」要素を追加します。または何でも。重要なのは、もう1つの要素を追加することです。追加するときはいつでも要素をコピーして新しいものを作成できます。

以前にSinaのコメントに追加するには、次のようなキーを使用できます。

class ElementKey {
  int ID;
  string Name;
}

class Element {
  ElementKey Key;
  List<int> Children;
  List<int> Parents;
  ProcessFlagSet flags;
}

class ProcessFlagSet {
  bool Processed;
  bool Duplicate;
}

Dictionary<ElementKey,Element> ...

そして、後で簡単にリファクタリングが必要になるように、ProcessFlagSetからすべての要素を削除できます。必要がなければ、削除されるまでコンパイルが中断されます。

最後に、ここで独自のAddメソッドを作成することをお勧めします。追加する要素を渡すことを検討してから、追加時にキーが存在するかどうかを確認してください。これにより、手順を節約できます。

于 2012-12-03T01:57:38.030 に答える
2

あなたはこれを試すことができます：

var temp = Elements.GroupBy(e => e.Name)
                   .Select(g => new Element
                   {
                       ID = g.OrderBy(e => e.ID).First().ID,
                       Name = g.Key,
                       Children = g.SelectMany(e => e.Children).ToList(),
                       Parents = g.SelectMany(e => e.Parents).ToList()
                   });
var duplicates = Elements.Where(e => !temp.Any(t => t.ID == e.ID))
                         .Select(e => e.ID)
                         .Distinct();
Elements = new HashSet<Element>(temp);
foreach (Element e in Elements)
{
    e.Children.RemoveAll(i => duplicates.Contains(i));
    e.Parents.RemoveAll(i => duplicates.Contains(i));
}

私が理解している限り、すべての要素をでグループ化するだけでよくName、次に最も低いものを選択してID結合Childrenし、Parents。明らかに、これはこのクエリによって行われます。

于 2012-12-03T02:12:33.750 に答える
1

私があなたを正しく理解しているなら、あなたは次のことをしたいです：

  1. 同じ名前の要素を削除します
  2. 削除された要素の子と親のリストを残りの要素にマージします
  3. 子と親のリストで、削除されたIDへの参照を残りの要素のIDに置き換えます

これらは、次のコードで実行できます。

// Find all duplicated elements and remove them
var duplicates = Elements.GroupBy(x => x.Name)
                         .Where(x => x.Count() > 1)
                         .SelectMany(x => x.OrderBy(e => e.ID)
                                           .Skip(1)
                                           .Select(e => new { Element = e, NewID = x.Min(y => y.ID) }))
                         .ToDictionary(x => x.Element.ID, x => new { x.Element, x.NewID });
Elements.ExceptWith(duplicates.Values.Select(x => x.Element));

// Update the Children and Parents of each remaining element
foreach (var element in Elements)
{
    var removed = duplicates.Where(x => x.Value.Element.Name == element.Name);

    var mergedChildren = element.Children.Union(removed.SelectMany(x => x.Value.Element.Children))
                                         .Select(x => duplicates.ContainsKey(x) ? duplicates[x].NewID : x)
                                         .Distinct().ToList();
    element.Children.Clear();
    element.Children.AddRange(mergedChildren);


    var mergedParents = element.Parents.Union(removed.SelectMany(x => x.Value.Element.Parents))
                                       .Select(x => duplicates.ContainsKey(x) ? duplicates[x].NewID : x)
                                       .Distinct().ToList();
    element.Parents.Clear();
    element.Parents.AddRange(mergedParents);
}
于 2012-12-03T08:20:17.263 に答える