您所在的位置： 首页 > 最新热文 > 计算机探索

    扩展独特的元组找到重新$ P $的关系由BDD psented独特、关系、psented、BDD

    2023-09-11 04:38:54 作者：△爱在老地方

    考虑{＆LT; 1,2>，＆LT; 1,3>，＆LT; 1,7>，＆LT; 0,4>}为一组关系的元组R.现在考虑R是再$ psented（通过其成员函数）p $由BDD。也就是说，该BDD重新presentingř取决于变量{X1，X2，Y1，Y2，Y3}其中{X1，X2}被用于重新present每一元组的第一个元素和{Y1，Y2 ，Y3}被用于重新present第二元件。

    现在，考虑寻找该组具有在其第一元件的唯一值的元组的问题。对于上面这组关系是{＆LT; 0,4>}。所有其他元素被丢弃，因为它们是一个以上的值具有1中的第一组分

    1,2>，＆所述; 1,3>，＆所述; 1,7>，＆所述; 2,3>，＆所述;

    作为第二示例与元组的集合{＆所述考虑的关系2,5>， ＆LT; 0,4>}。在这种情况下，预期的结果仍是{＆LT; 0,4>}为2不止一次出现的第一个元素

    。

    的问题也可以看作是抽象掉变量{Y1，Y2，Y3}，使得对于{X1，X2}只有唯一值保持。通过该结果，预期关系可以通过计算所得的BDD的结合输入1被重建。

    在综上所述，问题是：它们是必须对R的重新presentation进行，得到的BDD仅用唯一的元组BDD中操作。

    我们的简历泄露问题还有救吗

    请注意，这就是一个genralization question

    修改1： 下面code反映了执行我到目前为止。不过，我想知道是否有可能得到一个更有效的版本。为了简单起见，我故意省略计算表的处理（关键，以获得更好的时间复杂度）。此外，我使用及放大器;，|和 ！来表示的同时，析取和上BDDS补充操作

      BDD uniqueAbstract（BDD楼BDD立方体）{
  如果（（f.IsZero（）|| f.IsOne（））及＆安培;！cube.IsOne（））
    返回零（）;
  BDD T =高（F）;
  BDD E =低（F）;
  如果（级（F）==级别（C））{//当前变种是抽象
    BDD uniqueThen = uniqueAbstract（T，高（C））;
    BDD existElse = existAbstract（E，高（C））;

    BDD existThen = existAbstract（T，高（C））;
    BDD uniqueElse = uniqueAbstract（E，高（C））;

    返回（uniqueThen＆安培; existElse！）| （uniqueElse＆安培;！existThen）
  } 其他 {
    BDD uniqueThen = uniqueAbstract（T，C）;
    BDD uniqueElse = uniqueAbstract（E，C）;
    返回ITE（顶部（F），uniqueThen，uniqueElse）;
  }
}

    EDIT2：在尝试三种不同的实现仍存在一些性能问题。让我描述他们三人。

    AC执行我的方法，让我把它的参考实现 4 。 在接受的答案 3 建议用户meolic的实现。 两个和可用 2 之间的混合方式。

    该更新的目的是分析了一下，结果使用了三种方法。随着时间的措施似乎误导性在这个时候判断出来，我决定来评估一套不同的措施的实施。

    在递归调用 缓存命中 摘要简单。次数的函数调用得到解决，而无需存在抽象。 摘要复杂：次函数调用得到解决，需要存在抽象的数量。 存在摘要：调用存在抽象的数

    结果执行1：（21123毫秒）：     独特的抽象的统计数据：         递归调用：1728549.000000         高速缓存命中：638745.000000         非摘要：67207.000000         摘要简单：0.000000         摘要复杂：0.000000         存在摘要：1593430.000000

    结果执行2：（运行时间：54727毫秒）     独特的抽象的统计数据：         递归调用：191585.000000         高速缓存命中：26494.000000         摘要简单：59788.000000         摘要复杂：12011.000000         存在摘要：24022.000000

    结果执行3：（运行时间：20215毫秒）     独特的抽象的统计数据：         递归调用：268044.000000         高速缓存命中：30668.000000         摘要简单：78115.000000         摘要复杂：46473.000000         存在摘要：92946.000000

    编辑3：以下结果执行在ITE 5 的术语的每个逻辑运算之后获得

    uniqueAbstractRecRef（21831毫秒） 独特的抽象的统计数据： 总电话：1723239 优化呼叫：0 总存在抽象的电话：30955618 独特的抽象要求存在摘要：2385915 总ITE电话：3574555 出的总时间，uniqueAbstractRecRef需要4001毫秒（12.4％）

    uniqueAbstractSERec（56761毫秒） 独特的抽象的统计数据： 总电话：193627 优化呼叫：60632 总存在抽象的电话：16475806 独特的抽象要求存在摘要：24304 总ITE电话：1271844 出的总时间，uniqueAbstractSERec花费33918毫秒（51.5％）

    uniqueAbstractRec（20587毫秒） 独特的抽象的统计数据： 总电话：270205 优化呼叫：78486 总存在抽象的电话：13186348 独特的抽象要求存在摘要：93060 总ITE电话：1256872 出的总时间，uniqueAbstractRec需要3354毫秒（10.6％）

    解决方案

    下面是我的实现。我研究的作者提出的解决方案，并在我看来，这是最好的，如果不是随心所欲的乱堆乱放的只有简单的BDD为基础的解决方案。然而，可能有一些改善，如果该算法在我的方式 - 请检查实施。我用我自己的包装上BDD包，但你不应该有任何麻烦去了解它。

    编辑：我已经简化了解决方案，功能Bdd_GetVariableChar（）不再使用

    FOR问题

      / *测试解决方案堆栈溢出* /
/ * bdd_termFalse，bdd_termTrue：布尔常量* /
/ * Bdd_isTerminal（F）：检查是否f是布尔常量* /
/ * Bdd_Low（F），Bdd_​​High（F）：'别人'和'然后'子函数* /
/ * Bdd_Top（F）：F的*文字的功能重新presenting topvar /
/ * Bdd_IsSmaller（F，G）：检查如果f topvar以上的G * topvar /
/ * existentialAbstraction（F，立方体）：\立方体*存在VF的所有V /

Bdd_Edge specialAbstraction（Bdd_Edge楼Bdd_Edge立方体）{
  如果（Bdd_isTerminal（立方体））返回F;
  如果（Bdd_isTerminal（F））返回bdd_termFalse;
  如果（Bdd_IsSmaller（F，立方体））{
    Bdd_Edge E，T;
    E = specialAbstraction（Bdd_Low（F），立方体）;
    T = specialAbstraction（Bdd_High（F），立方体）;
    返回Bdd_ITE（Bdd_Top（F），T，E）;
  }否则，如果（Bdd_IsSmaller（立方体，F））{
    返回bdd_termFalse;
  } 其他 {
    Bdd_Edge E，T;
    立方= Bdd_High（立方体）;
    E = Bdd_Low（F）;
    T = Bdd_High（F）;
    如果（Bdd_isEqv（E，bdd_termFalse））{
      返回specialAbstraction（T，立方体）;
    }否则，如果（Bdd_isEqv（T，bdd_termFalse））{
      返回specialAbstraction（E，立方体）;
    } 其他 {
      Bdd_Edge EX，TX，R;
      EX = existentialAbstraction（E，立方体）;
      TX = existentialAbstraction（T，立方体）;
      如果（Bdd_isEqv（EX，TX））返回bdd_termFalse;
      R = Bdd_ITE（Bdd_ITE（EX，bdd_termFalse，T）
                  bdd_termTrue，
                  Bdd_ITE（德克萨斯州，bdd_termFalse，E））;
      返回specialAbstraction（R，立方体）;
    }
  }
}

    和，是的，如果变量排序是固定的上述X Y，该算法能够真正有效得多 - 你可以从最复杂的'其他'块中删除所有的计算，只是返回0

    下面是一些测试运行：

      CUBE（以防万一你不熟悉的BDD算法）
  + Y1 Y2 Y3 Y4 Y5

ORIGINAL（排序，上述X Y）
  + * X1 * X2 X3 * X4 X5 Y1 * Y2 Y3 Y4 Y5
  + * X1 X2 * X3 * X4 * X5 Y1 Y2 * Y3 Y4 Y5
  + * X1 X2 * X3 * X4 X5 * Y1 Y2 * Y3 Y4 Y5
  + * X1 X2 * X3 X4 * X5 Y1 * Y2 Y3 * Y4 * Y5
  + * X1 X2 X3 * X4 X5 * Y1 * Y2 * Y3 * Y4 Y5
  + * X1 X2 X3 * X4 X5 * Y1 Y2 Y3 * Y4 * Y5
  X1 + X2 * * * X3 X4 * X5 Y1 Y2 Y3 Y4 * Y5
  + X1 X2 * X3 X4 X5 * Y1 * Y2 * Y4 * Y5
  + X1 X2 X3 * X4 * X5 * Y1 * Y2 * Y3 Y4 * Y5

ABSTRACTION
  + * X1 * X2 X3 * X4 X5
  + * X1 X2 * X3 * X4
  + * X1 X2 * X3 X4 * X5
  X1 + X2 * * * X3 X4 * X5
  + X1 X2 X3 * X4 * X5

ORIGINAL（订购Ÿ以上X）
  + * Y1 * Y2 * Y3 * Y4 * Y5 X1 X2 * X3 X4 X5
  + * Y1 * Y2 * Y3 * Y4 Y5 * X1 X2 X3 * X4 X5
  + * Y1 * Y2 * Y3 Y4 * Y5 X1 X2 X3 * X4 * X5
  + * Y1 * Y2 Y3 * Y4 * Y5 X1 X2 * X3 X4 X5
  + * Y1 Y2 * Y3 Y4 Y5 * X1 X2 * X3 * X4 X5
  + * Y1 Y2 Y3 * Y4 * Y5 * X1 X2 X3 * X4 X5
  + Y1 * Y2 Y3 * Y4 * Y5 * X1 X2 * X3 X4 * X5
  + Y1 * Y2 Y3 Y4 Y5 * X1 * X2 X3 * X4 X5
  + Y1 Y2 * Y3 Y4 Y5 * X1 X2 * X3 * X4 * X5
  + Y1 Y2 Y3 Y4 * Y5 X1 * X2 * X3 * X4 * X5

ABSTRACTION
  + * X1 * X2 X3 * X4 X5
  + * X1 X2 * X3 * X4
  + * X1 X2 * X3 X4 * X5
  X1 + X2 * * * X3 X4 * X5
  + X1 X2 X3 * X4 * X5

ORIGINAL（MIXED ORDER）
  + * X1 * X2 Y1 * Y2 Y3 Y4 Y5 X3 * X4 X5
  + * X1 X2 * Y1 * Y2 * Y3 * Y4 Y5 X3 * X4 X5
  + * X1 X2 * Y1 Y2 * Y3 Y4 Y5 * X3 * X4 X5
  + * X1 X2 * Y1 Y2 Y3 * Y4 * Y5 X3 * X4 X5
  + * X1 X2 Y1 * Y2 Y3 * Y4 * Y5 * X3 X4 * X5
  + * X1 X2 Y1 Y2 * Y3 Y4 Y5 * X3 * X4 * X5
  X1 + X2 * Y1 Y2 Y3 Y4 Y5 * * * X3 X4 * X5
  + X1 X2 * Y1 * Y2 * Y3 * Y4 * Y5 * X3 X4 X5
  + X1 X2 * Y1 * Y2 * Y3 Y4 * Y5 X3 * X4 * X5
  + X1 X2 * Y1 * Y2 Y3 * Y4 * Y5 * X3 X4 X5

ABSTRACTION
  + * X1 * X2 X3 * X4 X5
  + * X1 X2 * X3 * X4
  + * X1 X2 * X3 X4 * X5
  X1 + X2 * * * X3 X4 * X5
  + X1 X2 X3 * X4 * X5

    Consider {<1,2>, <1,3>, <1,7>, <0,4>} as the set of tuples of a relation R. Now consider that R is represented (via its membership function) by a BDD. That is, The BDD representing R depends on variables {x1,x2, y1, y2, y3} where {x1, x2} are used to represent the first element of every tuple and {y1, y2, y3} are used to represent the second element.

    Now, consider the problem of finding the set of tuples that have unique values in its first element. For the relation above that set would be {<0,4>}. All the other elements are discarded as they are more than one value having 1 in the first component.

    As a second example consider the relation with set of tuples {<1,2>, <1,3>, <1,7>, <2,3>, <2,5>, <0,4>}. In such a case the expected result is still {<0,4>} as 2 appears more than once as first element.

    The problem can be also seen as abstracting away the variables {y1,y2,y3} such that only unique values for {x1,x2} remain. With this result, the expected relation can be reconstructed by computing the conjunction of the resulting BDD with the input one.

    In summary, the the question is: which are the BDD operations that have to be performed on The representation of R to obtain the BDD with only the unique tuples.

    Notice that this is a genralization of this question

    EDIT 1: The following code reflects the implementation I have so far. However, I am wondering if it is possible to get a more efficient version. For simplicity I intentionally omit the handling of the computed table (crucial to get better time complexity). Additionally, I use &, | and ! to denote the conjunction, disjunction and complement operations on BDDs.

    BDD uniqueAbstract(BDD f, BDD cube) {
  if ((f.IsZero() || f.IsOne()) && !cube.IsOne())
    return zero();
  BDD T = high(f);
  BDD E = low(f);
  if(level(f) == level(c)) { // current var is abstracted
    BDD uniqueThen = uniqueAbstract(T, high(c));
    BDD existElse = existAbstract(E, high(c));

    BDD existThen = existAbstract(T, high(c));
    BDD uniqueElse = uniqueAbstract(E, high(c));

    return (uniqueThen & !existElse) | (uniqueElse & !existThen)
  } else {
    BDD uniqueThen = uniqueAbstract(T,c);
    BDD uniqueElse = uniqueAbstract(E,c);
    return ite(top(f), uniqueThen, uniqueElse);
  }
}

    EDIT2: After trying three different implementations there are still some performance issues. Let me describe the three of them.

    A C implementation of my approach, let me call it the reference implementation4. The implementation proposed by user meolic in the accepted answer3. A hybrid approach between the two and available2.

    The goal of this update is to analyze a bit the results from using the three approaches. As time measures seem misleading at this time to judge them, I decided to evaluate the implementations on a different set of measures.

    Recursive calls Cache hits Abstract simple. Number of times the function call was solved without requiring existential abstraction. Abstract complex: Number of times the function call was solved requiring existential abstraction. Exist abstract: Number of calls to the existential abstraction.

    The results for implementation 1: (21123 ms): Unique abstraction statistics: Recursive calls: 1728549.000000 Cache hits: 638745.000000 Non abstract: 67207.000000 Abstract simple: 0.000000 Abstract complex: 0.000000 Exist abstract: 1593430.000000

    Results for implementation 2: (run time: 54727 ms) Unique abstraction statistics: Recursive calls: 191585.000000 Cache hits: 26494.000000 Abstract simple: 59788.000000 Abstract complex: 12011.000000 Exist abstract: 24022.000000

    Results for implementation 3: (run time: 20215 ms) Unique abstraction statistics: Recursive calls: 268044.000000 Cache hits: 30668.000000 Abstract simple: 78115.000000 Abstract complex: 46473.000000 Exist abstract: 92946.000000

    EDIT 3: The following results were obtained after implementing every logical operation in terms of ITE5.

    uniqueAbstractRecRef (21831 ms) Unique abstraction statistics: Total calls: 1723239 Optimized calls: 0 Total exist abstract calls: 30955618 Unique abstract calls to exist abstract: 2385915 Total ite calls: 3574555 Out of the total time, uniqueAbstractRecRef takes 4001 ms (12.4%)

    uniqueAbstractSERec (56761 ms) Unique abstraction statistics: Total calls: 193627 Optimized calls: 60632 Total exist abstract calls: 16475806 Unique abstract calls to exist abstract: 24304 Total ite calls: 1271844 Out of the total time, uniqueAbstractSERec takes 33918 ms (51.5%)

    uniqueAbstractRec (20587 ms) Unique abstraction statistics: Total calls: 270205 Optimized calls: 78486 Total exist abstract calls: 13186348 Unique abstract calls to exist abstract: 93060 Total ite calls: 1256872 Out of the total time, uniqueAbstractRec takes 3354 ms (10.6%)

    解决方案

    Here is my implementation. I have studied author's proposed solution and it seems to me that it is the best if not the only simple BDD-based solution for arbitrary ordering. However, there may be some improvements if the algorithm is implemented in my way- PLEASE CHECK. I am using my own wrapper over BDD package but you should not have any troubles to understand it.

    EDITED: I have simplified the solution, function Bdd_GetVariableChar() is not used anymore.

    /* TESTING SOLUTION FOR QUESTION ON STACK OVERFLOW */
/* bdd_termFalse,bdd_termTrue: Boolean constants */
/* Bdd_isTerminal(f): check if f is Boolean constant */
/* Bdd_Low(f),Bdd_High(f): 'else' and 'then' subfunction */
/* Bdd_Top(f): literal function representing topvar of f */
/* Bdd_IsSmaller(f,g): check if topvar of f is above topvar of g */
/* existentialAbstraction(f,cube): \exist v.f for all v in cube */

Bdd_Edge specialAbstraction(Bdd_Edge f, Bdd_Edge cube) {
  if (Bdd_isTerminal(cube)) return f;
  if (Bdd_isTerminal(f)) return bdd_termFalse;
  if (Bdd_IsSmaller(f,cube)) {
    Bdd_Edge E,T;
    E = specialAbstraction(Bdd_Low(f),cube);
    T = specialAbstraction(Bdd_High(f),cube);
    return Bdd_ITE(Bdd_Top(f),T,E);
  } else if (Bdd_IsSmaller(cube,f)) {
    return bdd_termFalse;
  } else {
    Bdd_Edge E,T;
    cube = Bdd_High(cube);
    E = Bdd_Low(f);
    T = Bdd_High(f);
    if (Bdd_isEqv(E,bdd_termFalse)) {
      return specialAbstraction(T,cube);
    } else if (Bdd_isEqv(T,bdd_termFalse)) {
      return specialAbstraction(E,cube);
    } else {
      Bdd_Edge EX,TX,R;
      EX = existentialAbstraction(E,cube);
      TX = existentialAbstraction(T,cube);
      if (Bdd_isEqv(EX,TX)) return bdd_termFalse;
      R = Bdd_ITE(Bdd_ITE(EX,bdd_termFalse,T),
                  bdd_termTrue,
                  Bdd_ITE(TX,bdd_termFalse,E));
      return specialAbstraction(R,cube);
    }
  }
}

    And, yes, if variable ordering is fixed with x above y, the algorithm can really be much more efficient - you can remove all the calculations from the most complex 'else' block and just return 0.

    Here are some testing runs:

    CUBE (JUST IN CASE YOU ARE NOT FAMILIAR WITH BDD ALGORITHMS)
  +  y1 y2 y3 y4 y5

ORIGINAL (ORDERED WITH X ABOVE Y)
  +  *x1 *x2 x3 *x4 x5 y1 *y2 y3 y4 y5
  +  *x1 x2 *x3 *x4 *x5 y1 y2 *y3 y4 y5
  +  *x1 x2 *x3 *x4 x5 *y1 y2 *y3 y4 y5
  +  *x1 x2 *x3 x4 *x5 y1 *y2 y3 *y4 *y5
  +  *x1 x2 x3 *x4 x5 *y1 *y2 *y3 *y4 y5
  +  *x1 x2 x3 *x4 x5 *y1 y2 y3 *y4 *y5
  +  x1 *x2 *x3 *x4 *x5 y1 y2 y3 y4 *y5
  +  x1 x2 *x3 x4 x5 *y1 *y2 *y4 *y5
  +  x1 x2 x3 *x4 *x5 *y1 *y2 *y3 y4 *y5

ABSTRACTION
  +  *x1 *x2 x3 *x4 x5
  +  *x1 x2 *x3 *x4
  +  *x1 x2 *x3 x4 *x5
  +  x1 *x2 *x3 *x4 *x5
  +  x1 x2 x3 *x4 *x5

ORIGINAL (ORDERED WITH Y ABOVE X)
  +  *y1 *y2 *y3 *y4 *y5 x1 x2 *x3 x4 x5
  +  *y1 *y2 *y3 *y4 y5 *x1 x2 x3 *x4 x5
  +  *y1 *y2 *y3 y4 *y5 x1 x2 x3 *x4 *x5
  +  *y1 *y2 y3 *y4 *y5 x1 x2 *x3 x4 x5
  +  *y1 y2 *y3 y4 y5 *x1 x2 *x3 *x4 x5
  +  *y1 y2 y3 *y4 *y5 *x1 x2 x3 *x4 x5
  +  y1 *y2 y3 *y4 *y5 *x1 x2 *x3 x4 *x5
  +  y1 *y2 y3 y4 y5 *x1 *x2 x3 *x4 x5
  +  y1 y2 *y3 y4 y5 *x1 x2 *x3 *x4 *x5
  +  y1 y2 y3 y4 *y5 x1 *x2 *x3 *x4 *x5

ABSTRACTION
  +  *x1 *x2 x3 *x4 x5
  +  *x1 x2 *x3 *x4
  +  *x1 x2 *x3 x4 *x5
  +  x1 *x2 *x3 *x4 *x5
  +  x1 x2 x3 *x4 *x5

ORIGINAL (MIXED ORDER)
  +  *x1 *x2 y1 *y2 y3 y4 y5 x3 *x4 x5
  +  *x1 x2 *y1 *y2 *y3 *y4 y5 x3 *x4 x5
  +  *x1 x2 *y1 y2 *y3 y4 y5 *x3 *x4 x5
  +  *x1 x2 *y1 y2 y3 *y4 *y5 x3 *x4 x5
  +  *x1 x2 y1 *y2 y3 *y4 *y5 *x3 x4 *x5
  +  *x1 x2 y1 y2 *y3 y4 y5 *x3 *x4 *x5
  +  x1 *x2 y1 y2 y3 y4 *y5 *x3 *x4 *x5
  +  x1 x2 *y1 *y2 *y3 *y4 *y5 *x3 x4 x5
  +  x1 x2 *y1 *y2 *y3 y4 *y5 x3 *x4 *x5
  +  x1 x2 *y1 *y2 y3 *y4 *y5 *x3 x4 x5

ABSTRACTION
  +  *x1 *x2 x3 *x4 x5
  +  *x1 x2 *x3 *x4
  +  *x1 x2 *x3 x4 *x5
  +  x1 *x2 *x3 *x4 *x5
  +  x1 x2 x3 *x4 *x5

    上一篇：在正克，它是最常见者一切的字中它是、最常、见者

    下一篇：鉴于整数0-9的股票，什么是我可以写之前，我跑了一些整数的最后一个数字？整数、跑了、数字、股票

    相关推荐
     
    猜您喜欢
    火山涌现最早时候摸索 洪量奇形怪状壁绘引人沉思

    火山涌现最早时候摸索 洪量奇形怪状壁绘

    精彩图集
    精彩推荐
    图片推荐

    探秘家（tanmijia.com），深层探秘世界自然奇观未解之谜，揭秘宇宙空间、人类、生物未解之谜,世界传闻、奇闻异事ufo未解之谜。有效真实科学探索天下奇观猎奇世界。

    © 2016-2021 探秘家. All Rights Reserved 浙ICP备20029812号-3