标签: reduction

这是个问题.我想知道是否有明确有效的证据:

顶点覆盖:输入无向G,整数k> 0.是否有顶点S的子集,| S | <= k,覆盖所有边？

支配集:输入无向G,整数k> 0.是否有一个顶点S的子集,| S | <= k,它支配所有顶点？

顶点覆盖了它的入射边缘,并支配它的邻居和自身.

假设VC是NPC,证明DS是NPC.

我想对我的内核代码(1维数据)应用reduce:

__local float sum = 0;
int i;
for(i = 0; i < length; i++)
  sum += //some operation depending on i here;

我想要有n个线程(n =长度),最后有1个线程来计算总和,而不是只有1个线程执行此操作.

在伪代码中,我希望能够写出这样的东西:

int i = get_global_id(0);
__local float sum = 0;
sum += //some operation depending on i here;
barrier(CLK_LOCAL_MEM_FENCE);
if(i == 0)
  res = sum;

有办法吗？

我总和有竞争条件.

我联系您,以便了解"如何将流水车间调度问题转换为布尔可满足性".

我已经为N*N Sudoku,N-queens和Class调度问题做了这样的减少,但是我对如何将Flow shop转换为SAT有一些问题.

SAT问题看起来像这样:

目标是:使用不同的布尔变量,找到每个变量的效果,以使"句子"成立.(如果可以找到解决方案).

我使用遗传算法创建自己的求解器,能够找到解决方案并证明什么时候没有.现在,我尝试不同的NP问题,比如Flow Shop.

流水车间调度问题是车间或集团车间的一类调度问题,其中流量控制应能够为每个作业进行适当的排序,并在一组机器或其他资源上进行处理1,2,...,m符合给定的处理订单.

特别是在最小的空闲时间和最少的等待时间的情况下,期望保持连续的处理任务流.

Flow shop调度是作业车间调度的一个特例,其中对所有作业执行所有操作的严格顺序.

流水车间调度也可以应用于计算设计的生产设施.

(http://en.wikipedia.org/wiki/Flow_shop_scheduling)

结果是一系列工作将经历每个研讨会,图形结果将如下所示:

所以为了表示flow-shop实例,在输入中我有这样的文件:

2 4
4 26 65 62 
63 83 57 9 

这个文件意味着我有2个商店和4个工作,每个工作的每个工作的持续时间都是.

目标:找到最小化C_max的序列,如果您愿意,可以找到最后一台机器上最后一个作业的结束日期.

我的Flow-Shop现在非常简单,但我不知道如何将它们形式化以便创建一个CNF文件来执行我的SAT求解器.

如果你们其中一个有一些想法:文章？一个想法的开始？

这个问题的下一部分:Flow/Job Shop到布尔可满足性[多项式时间缩减]第2部分

我试图通过使用Openmp使这个for循环并行化,我认识到在这个循环中减少了所以我添加了"#pragma omp parallel for reduction(+,ftab)",但它没有用,它给了我这个错误:错误:找不到'ftab'的用户定义缩减.

   #pragma omp parallel for reduction(+:ftab)
    for (i = 1; i <= 65536; i++) ftab[i] += ftab[i-1];

我有一个平面数组b：

a = numpy.array([0, 1, 1, 2, 3, 1, 2])

以及c标记每个“块”开始的索引数组：

b = numpy.array([0, 4])

我知道我可以使用归约找到每个“块”中的最大值：

m = numpy.maximum.reduceat(a,b)
>>> array([2, 3], dtype=int32)

但是...有没有一种方法可以通过向量化操作（无列表、循环）找到<edit>块内最大值的索引</edit>（例如）？numpy.argmax

我想让这段代码并行:

std::vector<float> res(n,0);
std::vector<float> vals(m);
std::vector<float> indexes(m);
// fill indexes with values in range [0,n)
// fill vals and indexes
for(size_t i=0; i<m; i++){
  res[indexes[i]] += //something using vas[i];
}

在这个文章它的建议使用:

#pragma omp parallel for reduction(+:myArray[:6])

在这个问题中,评论部分提出了相同的方法.

我有两个问题:

1. 我不知道m在编译时,从这两个例子看来,它似乎是必需的.是这样吗？或者,如果我可以在这种情况下使用它,我需要?在以下命令中替换#pragma omp parallel for reduction(+:res[:?])什么？m还是n？
2. 难道是相关的指标for是相对于indexes和vals,而不是res,尤其是考虑到reduction是在后者做了什么？

但是,如果是这样,我该如何解决这个问题呢？

从OpenMP 4.0开始,支持用户定义的缩减.所以我在这里完全定义了C++中std :: vector的减少.它适用于GNU/5.4.0和GNU/6.4.0,但它使用intel/2018.1.163返回减少的随机值.

这是一个例子:

#include <iostream>
#include <vector>
#include <algorithm>
#include "omp.h"

#pragma omp declare reduction(vec_double_plus : std::vector<double> : \
                              std::transform(omp_out.begin(), omp_out.end(), omp_in.begin(), omp_out.begin(), std::plus<double>())) \
                    initializer(omp_priv = omp_orig)

int main() {

    omp_set_num_threads(4);
    int size = 100;
    std::vector<double> w(size,0);

#pragma omp parallel for reduction(vec_double_plus:w)
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < w.size(); ++j)
            w[j] += 1;

    for(auto i:w)
        if(i != 4)
            std::cout << i << std::endl;

    return 0; …

我正在修改即将到来的Haskell考试,我不理解过去论文中的一个问题.谷歌没有任何用处

fst(x, y) = x
square i = i * i

i)源减少,使用Haskells懒惰评估,表达式:

fst(square(3+4), square 8)

ii)使用严格的评估,源减少相同的表达式

iii)说明懒惰评估的一个优点和严格评估的一个优点

我不明白什么是源减少？

什么是还原变量？有人能给我一些例子吗？

我有一个Java bean,就像

class EmployeeContract {
    Long id;
    Date date;
    getter/setter
}

如果有一个很长的列表,我们在id中有重复但有不同的日期,例如:

1, 2015/07/07
1, 2018/07/08
2, 2015/07/08
2, 2018/07/09

如何减少此类列表仅保留最近日期的条目,例如:

1, 2018/07/08
2, 2018/07/09

？最好使用Java 8 ...

我从一开始就开始:

contract.stream()
         .collect(Collectors.groupingBy(EmployeeContract::getId, Collectors.mapping(EmployeeContract::getId, Collectors.toList())))
                    .entrySet().stream().findFirst();

这给了我各个组内的映射,但是我被困在如何将其收集到结果列表中 - 我的流不是太强我害怕...