问题标签 [reduction]

我正在尝试对一个序列进行模拟，该序列的长度为 N（在 10k 和 3M 之间变化），由一个向量表示，该向量具有 n 个 1 和 s 0，其中 N = n+s。

我想将其简化为 c( 137, 278, 21271, 124162, ... ) 形式的向量，其中数字是原始向量中连续 1 的数量。因为我需要为我正在做的模拟做这大约 100,000 次，所以我正在寻找一种尽可能有效的方法！

谢谢！

马丁

如何在 Delphi 中将颜色减少到指定数字（<=256）？我不想只使用：

因为那样我无法控制颜色的数量。我不想抖动，因为我已经知道如何抖动 256 或更少颜色的图像。

我发现了这个Median Cut 实现，但它是 1990 年的纯 Pascal 并且：

1. 不能在 Delphi 中编译
2. 说它是共享软件，售价 25 德国马克
3. 看起来（不知何故）不必要的复杂

我只想减少TBitmap32（Graphics32 位图类，仅支持 32 位颜色）到 <= 8 位 bmp。我不需要减少到 15/16 位，我不需要从 24 或 15/16 位图像减少。仅 32 位 => 8 位-

我使用的德尔福：7、2005、XE3。

这是我之前的问题（在 Python 中使用随机化减少文本文件）的后续行动。正在修改以运行多个缩减，但只有第一个输出文件包含缩减，以下 3 个文件是零大小。这一定是我没有看到的明显的东西......

输出显示如下（文件 0.25-foo 包含正确的归约，其余为空）：

我刚刚开始使用 CUDA，并试图将我的大脑包裹在 CUDA 缩减算法上。就我而言，我一直在尝试获得两个矩阵的点积。但我只得到了大小为 2 的矩阵的正确答案。对于任何其他大小的矩阵，我都弄错了。

这只是测试，所以我保持矩阵大小非常小。只有大约 100 个，所以只有 1 个块可以满足所有要求。任何帮助将不胜感激。谢谢！

这是常规代码

这是我的 cuda 内核

我的完整代码： http: //pastebin.com/zS85URX5

假设我有两个 device_vector<byte> 数组，d_keys并且d_data.

例如，如果d_data是扁平的 2D 3x5 数组（例如 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3 } ）并且d_keys是一维数组大小为 5 （例如 { 1, 0, 0, 1, 1 } ），我怎么能做一个减少，如果相应的值是一个，我最终只会在每行基础上添加值d_keys（例如结束结果为 { 10, 23, 14 } )？

sum_rows.cu示例允许我在 中添加每个值d_data，但这并不完全正确。

或者，我可以在每行的基础上，使用 a并一次与一行zip_iterator组合，然后执行 a ，仅当键值为 1 时才添加，但随后我必须遍历数组。d_keysd_datatransform_reduced_data

我真正需要的是某种transform_reduce_by_key不是内置的功能，但肯定有办法实现它！

Suppose you have a graph G = (V, E) that represents the floor plan of a one-story shopping mall. The individual stores are represented by vertices, and the edges between vertices represent some arbitrary definition of stores being close to each other.

Recently, there has been an increase in the amount of shoplifting that occurs in this mall, so management decides to make it so that every store either:

• Has a security guard stationed in it

• Or is close to a store that has a security guard stationed in it

While hiring as few security guards as possible.

How would you prove this optimization problem is NP-complete? I feel like it's a simple reduction from the independent set problem, but I want to make sure.

有没有办法知道 OpenMP 中归约运算符的执行顺序？换句话说，我想知道线程是如何执行归约操作的——是从左到右吗？当有数字不是 2 的幂时会发生什么？

基本上，我正在研究物理游戏中的阻力。需要减少侧向运动（因为接近于 0，而不仅仅是带负数），但我不知道它在哪个方向行进，所以我不知道是增加阻力还是减少阻力。

（如果一个项目向右移动，它有正向力，向左移动，负向力）

现在我正在这样做：

效果很好，但我觉得肯定会有一种更时尚的方式来做到这一点。

找到一种方法来确保它不会超过 0 也无妨

我有这段并行化的代码。

据说减少会消除如果我们不使用减少可能发生的竞争条件。我仍然想知道我们是否需要为区域添加 lastprivate，因为它在并行循环之外使用并且在它之外不可见。否则减少是否也涵盖了这一点？

我在理解使用 NP 问题的减少时遇到了一些困难，希望得到澄清。考虑以下问题：

我知道关于这个主题还有其他主题，但我仍然不确定我是否理解如何进行这样的减少。

据我了解，这就是您处理此类问题的方式。

1. 假设给定的问题可以在多项式时间内解决。
2. 使用给定的问题来解决我们知道在多项式时间内是 NP-Hard 的问题
3. 这就产生了矛盾，所以假设一定是不正确的
4. 因此，给定的问题一定不能在多项式时间内解决

那么，对于这样的问题，这是一个合适的方法吗？

1. 如果我们选择 k 作为图中哈密顿循环的长度（假设有一个），这意味着这个问题可以用来在图中找到哈密顿循环。
2. 因为我们只能在 NP 时间内找到哈密顿循环，所以这个问题也必须只能在 NP 时间内解决。