问题标签 [reduction]

我正在尝试开发一个在彩虹表生成器中使用的缩减函数。

归约函数背后的基本原理是它接受一个散列，执行一些计算，并返回一个特定长度的字符串。

目前我正在使用 SHA1 哈希，我需要返回一个长度为 3 的字符串。我需要由以下任意三个随机字符组成的字符串：

我面临的主要问题是我编写的任何归约函数总是返回已经生成的字符串。一个好的归约函数很少会返回重复的字符串。

任何人都可以就实现这一目标的方式提出任何想法吗？或者任何关于哈希到字符串操作的建议都会很棒。

提前致谢

乔什

任何人都知道我将如何减少我的以下代码行？我在objective-c / cocos2D 上还是相当新的，我的以下代码看起来像火车残骸。如果是 PHP，我可以轻松地创建一个循环来获取所有这些内容，但我对 obj-c 还不够熟悉，还没有弄清楚。

非常感谢任何输入！

如果我有布尔变量 a_1、a_2、..、a_n。如何使用多项式大小布尔表达式来表达设置为 true 的布尔变量的数量大于一些 k 的事实？（指数很容易 - 只需编写 newton(n,k) 表达式）。

我必须使用许多不同的键对数组进行键控减少，这些键只在一段时间内重复一次：

使用thrust::reduce_by_key（或任何其他分段缩减方法）在这里并不是最快的选择，因为大多数操作实际上只是从一个数组复制到另一个数组。

解决这个问题的更好方法是什么？

大家好，

我有一个类和一个属性，并且我有该类的三个实例。

现在在某个时刻，我需要比较这三个属性值，并验证它们是否相等，以得到最少的值。

所以如果我有

在 magic_function_call 之后，我应该得到 3 和 5。

如果我有

在 magic_function_call 之后，我应该得到 2。

尽管这本身很简单，并且可以根据需要通过尽可能多的 IF 检查来解决，但我想知道哪种方法是最快或更有效的方法，特别是考虑到我可能需要添加另一个变量到将来的检查。

事实上，我想知道是否有可以执行的按位运算可以优雅而快速地解决这个问题。

或者，是否有可用于实现相同目标的数组操作？我试过寻找“减少”或“压缩”，但这些关键字似乎并没有朝着正确的方向发展。

提前致谢。

我有一个表情，假设，

我希望它减少到，

有没有人有什么建议？指向任何算法的指针？

Nota Bene：我相信，卡诺图或 Quine-McCluskey 不是这里的选择。因为这些方法不处理灰色情况。我的意思是，表达只能减少到像 A 或 A' 或什么都没有，或者说是黑色或白色或无色的情况。但是在这里我有灰色阴影，正如你们所看到的。

解决方案：我已经在 Clojure 中为此编写了程序。我使用包含函数作为值的地图的地图。这很方便，只需几个组合的一些规则，你就很好。感谢您提供有用的答案。

减少很多个，是不对称的。我试图证明这一点，但效果并不好。

给定两种语言 A 和 B ，其中 A 定义为

和B=A_TM，其中 A_TM 不可判定但图灵可识别！

鉴于以下减少：

（请原谅我没有使用 Latex ，我没有使用它的经验）

正如我所看到的，从 A <= B（从 A 到 A_TM）的减少是可能的，并且效果很好。但是，我不明白为什么 B <= A 是不可能的。

你能澄清和解释一下吗？

谢谢罗恩

我一直在考虑如何使用归约在 CUDA 上执行此操作，但我对如何完成它有点茫然。C代码如下。要记住的重要部分——变量precalculatedValue取决于两个循环迭代器。此外，变量ngo对m的每个值都不是唯一的……例如m = 0,1,2 可能有ngo = 1，而m = 4,5,6,7,8 可能有ngo = 2，等等。我已经包含了循环迭代器的大小，以防它有助于提供更好的实现建议。

在之前的案例中，当precalculatedValue只是内部循环变量的函数时，我将值保存在唯一的数组索引中，并在事后通过并行归约（推力）添加它们。但是，这种情况让我很困惑：m的值并没有唯一地映射到ngo的值。因此，我看不出有一种方法可以使此代码高效（甚至可行）以使用减少。任何想法都是最受欢迎的。

我必须在 GPU 上解决一个非常标准的问题，但我对实用的 GPGPU 还是很陌生，所以我正在寻找解决这个问题的想法。

我在 3 空间中有很多点被分配给极少数的组（每个点属于一个组），在这种情况下特别是 15 个（永远不会改变）。现在我想计算所有组的均值和协方差矩阵。所以在CPU上它大致相同：

由于组的数量非常少，最后一步可以在 CPU 上完成（无论如何，我需要 CPU 上的这些值）。第一步实际上只是分段缩减，但分段分散。

所以我想出的第一个想法是首先按他们的组对点进行排序。我考虑了一个简单的桶排序，atomic_inc用于计算桶大小和每点重定位索引（对排序有更好的想法？，原子可能不是最好的想法）。之后，它们按组排序，我可能会想出此处介绍的分段扫描算法的改编版。

但是在这种特殊情况下，我每点获得大量数据（9-10 个浮点数，如果需要，甚至可能翻倍），因此使用每个线程共享内存元素和每个点线程的标准算法可能会产生问题将每个多处理器资源视为共享内存或寄存器（好吧，计算能力 1.x 比 2.x 更多，但仍然如此）。

由于组的数量非常少且固定，我认为可能有更好的方法。也许已经存在适合此类标准问题的这些特定属性的想法。或者，也许我的一般方法还不错，并且您有改进各个步骤的想法，例如适用于非常少量键的良好排序算法或某些分段缩减算法，以最大限度地减少共享内存/寄存器的使用。

我正在寻找通用方法并且不想使用外部库。FWIW 我正在使用 OpenCL，但这并不重要，因为 GPU 计算的一般概念在主要框架上并没有真正的不同。

我需要执行并行缩减以找到 CUDA 设备上数组的最小值或最大值。我为此找到了一个很好的库，称为 Thrust。您似乎只能对主机内存中的数组执行并行缩减。我的数据在设备内存中。是否可以减少设备内存中的数据？我不知道该怎么做。这是 Thrust 的文档：http ://code.google.com/p/thrust/wiki/QuickStartGuide#Reductions 。谢谢大家。