2

次のような入力データ構造があります。

{
 { {x1,y1,z1,p1}, {x1,y2,z1,p1}, {x1,y3,z1,p1}, {x1,y4,z1,p1} },
 { {x1,y1,z2,p2}, {x1,y2,z2,p2}, {x1,y3,z2,p2}, {x1,y4,z2,p2} },
 { {x1,y1,z3,p3}, {x1,y2,z3,p3}, {x1,y3,z3,p3}, {x1,y4,z3,p3} }
}

質問を完全に理解するために、各項目はブール式 (型付きの ITree) です (例: nn < 42)。

最終的に知りたいのは、各場所がどこにあるかを示す木の数です。

トップツリー:

                根
                  | |
                 x1
            / | \
           z1 z2 z3
            | | | | | |
           あ(0) あ(4) あ(8)

ツリー a:

               ルート (オフセット) - オフセット = o
            / / \ \
           y1 y2 y3 y4
           | | | | | | | |
         b(o) b(o+1) b(o+2) b(o+3)

ツリー b:

               ルート (オフセット) - オフセット = o
            / | \
           p1 p2 p3
           | | | | | |
           o o+1 o+2

したがって、{x1,y2,z1,p1} が true と評価される値を含むリストがある場合、これがセル 1 (実際には 0,1) にあり、{x1, y2,z1,p2} どのセルにもありません。

機能的な実装を構築しましたが、非常に遅いです:

public MultiIfTreeList Compile(List<List<ITree>> input, out List<MultiIfTreeList> all, out List<int> orderOfLeafs ) {
  //{ { {x,y} }, { {z} } } -> {0:{x.ToString:x, y.ToString:y}, 1:{z.ToString:z}}
  List<Tuple<int, Dictionary<string, ITree>>> andList = ConvertToDictionaryAndFlatten(input);

  orderOfLeafs = new List<int>();
  all = new List<MultiIfTreeList>();
  return BuildIfTree(andList, orderOfLeafs, all);
}

  private MultiIfTreeList BuildIfTree(List<Tuple<int, Dictionary<string, ITree>>> andList, List<int> orderOfLeafs, List<MultiIfTreeList> all)
  {
     if (andList.Count == 0)
        return null;
     var children = new List<MultiIfTree>();

     while (andList.Count > 0)
     {
        //count number of occurances of each statement, ie x1=5 and x2=3 and find the highest one
        Dictionary<string, int> counts = new Dictionary<string, int>();
        foreach (var exp1 in andList.SelectMany(exp => exp.Item2.Keys))
           if (!counts.ContainsKey(exp1))
              counts[exp1] = 1;
           else
              counts[exp1]++;

        var maxcount = counts.Max(x => x.Value);

        if (maxcount == 1) //OPTIMIZATION: then all are different and we can just do them one at a time
        {
           foreach (var lst in andList)
           {
              var item = lst.Item2.First();
              lst.Item2.Remove(item.Key);
              var idx = orderOfLeafs.Count;
              children.Add(
                 new MultiIfTree
                 {
                    Value = item.Key,
                    Ast = item.Value,
                    LeafsThis = 0,
                    Children = BuildIfTree(new List<Tuple<int, Dictionary<string, ITree>>> { lst }, orderOfLeafs, all),
                    ExpireCountWithChildren = orderOfLeafs.Count - idx,
                 });
           }
           andList.Clear();
        }
        else
        {
           //Make lists of where each statement can be found
           foreach (var kvp in counts.Where(x => x.Value == maxcount))
           {
              var max = kvp.Key;
              var expireindex = expire.Count;
              ITree exp = null;
              var listWithMax = new List<Tuple<int, Dictionary<string, ITree>>>();
              var listWithoutMax = new List<Tuple<int, Dictionary<string, ITree>>>();
              foreach (var lst in andList)
              {
                 var copy = new Dictionary<string, ITree>(lst.Item2);
                 var item = new Tuple<int, Dictionary<string, ITree>>(lst.Item1, copy);
                 if (copy.ContainsKey(max))
                 {
                    exp = copy[max];
                    copy.Remove(max);
                    if (copy.Count == 0)
                       expire.Add(lst.Item1);
                    else
                       listWithMax.Add(item);
                 }
                 else
                    listWithoutMax.Add(item);
              }
              if (exp != null)
                 children.Add(
                    new MultiIfTree
                    {
                       Value = max,
                       Ast = exp,
                       LeafsThis = orderOfLeafs.Count - idx,
                       Children = BuildIfTree(listWithMax, expire, all),
                       LeafCountWithChildren = orderOfLeafs.Count - idx,
                    });
              andList = listWithoutMax;
           }
        }
     }
     var tree = new MultiIfTreeList(children);
     all.Add(tree);
     return tree;
  }

それぞれ 4 つの式のリストが 25008 個ある入力では、私のマシンでは約 800 ミリ秒かかります。

編集1： 実際にトップツリーaとbを取得するには、それらをハッシュするだけです.25008 * 4の私の特定のケースでは、最終的に24000のツリーになり、760の一意のツリーにハッシュされます. この部分はわずか21ミリ秒かかります

4

0 に答える 0