问题标签 [stream-compaction]

我对执行以下操作的最佳方法有点困惑：

假设我有以下排序的键值对

(K:V) (0 : .5)(0 : .7)(0 : .9) (1 : .2) (1 : .6) (1 : .8)

等等..

我想删除复制每个键的最小值，所以我会有 2 个结果

按键最小值

(0 : .5)(1 : .2)

其余的

(0 : .7)(0 : .9)(1 : .6)(1 : .8)

推力::unique_by_key_copy 似乎能够通过键给我最小值，因为 (K:V) 已排序。但是我不确定如何删除从原始中选择的那些以获得剩余的。

非常感谢任何想法或建议

我正在制作一个 python“脚本”，它将一个字符串发送到一个 web 服务（在 C# 中）。我需要压缩或压缩这个字符串，因为带宽和 MB 数据是有限的（是的，大写，因为它非常有限）。

我正在考虑将其转换为文件，然后压缩文件。但我正在寻找一种直接压缩字符串的方法。

如何压缩或压缩字符串？

给定一个带有行分隔 JSON 记录的文件：

我想通过仅保留 id 的最后一条记录来压缩这样的文件，例如对于上面的示例，我希望将其作为输出：

tldr; 是否有uniq适用于行分隔的 JSON（并且速度很快）？

输入文件可能包含 10 亿条记录，其中可能有 10-20% 的记录可以丢弃。

我尝试了各种方法：

1. 看过的id

   在内存中保留一组“已见”的 ID。这会耗尽内存。

2. 排序和唯一

   首先按“id”对文件进行排序（使用稳定的排序，因此保留顺序）。然后再次运行文件，只保留最后一条记录。这就像通常的 unixsort | uniq方法。排序在这里很昂贵，而且可能工作量太大。

3. 提取偏移量和长度信息

   从文件中提取偏移量和长度信息以及 id，例如

   /li>

并找出哪些记录属于压缩集。然后查找并阅读该文件。此信息的提取速度相当快，但数百万次搜索和读取以提取记录会减慢这种方法的速度。

有什么更好、更快（或最快）的方法？是否有解决此类问题的现有工具？

我正在尝试使用 CUDA 构建一个并行算法，该算法采用整数数组并删除所有0's，无论是否保持顺序。

例子：

全局内存：{0, 0, 0, 0, 14, 0, 0, 17, 0, 0, 0, 0, 13}

主机内存结果：{17, 13, 14, 0, 0, ...}

最简单的方法是使用主机及时删除0's O(n)。但考虑到我有周围的1000元素，将所有内容留在 GPU 上并在发送之前先压缩它可能会更快。

首选的方法是创建一个设备上的堆栈，这样每个线程都可以弹出并（以任何顺序）推入或推出堆栈。但是，我认为 CUDA 没有实现这一点。

一个等效（但慢得多）的方法是继续尝试写入，直到所有线程都完成写入：

这种方法的唯一好处是我们可以O(f(x))及时执行，其中f(x)是数组中非零值的平均数量（f(x) ~= ln(n)对于我的实现，因此O(ln(n))是时间，但具有很高的O常数）

最后，诸如快速排序或归并排序之类的排序算法也可以解决该问题，并且实际上确实在O(ln(n))相对时间中运行。我认为甚至可能有比这更快的算法，因为我们不需要浪费时间排序（交换）零零元素对和非零非零元素对（不需要保持顺序）。

所以我不太确定哪种方法最快，我仍然认为有更好的方法来处理这个问题。有什么建议么？

我在 Kafka 0.8.1.1 中的 server.properties 文件中进行了更改，即添加log.cleaner.enable=true并cleanup.policy=compact在创建主题时启用。现在，当我测试它时，我将以下消息推送到带有以下（键，消息）的主题。

• 偏移量：1 - (123, abc);
• 偏移量：2 - (234, def);
• 偏移量：3 - (345, ghi);
• 偏移量：4 -（123，已更改）

现在，我使用与先前输入相同的键推送第四条消息，但更改了消息。这里应该出现日志压缩。使用 Kafka 工具，我可以看到主题中的所有 4 个偏移量。我如何知道日志压缩是否有效？是否应该删除较早的消息，或者在推送新消息时日志压缩工作正常。它与log.retention.hoursor topic.log.retention.hoursorlog.retention.size配置有什么关系吗？这些配置在日志压缩中的作用是什么。PS - 我已经彻底阅读了 Apache 文档，但仍然不清楚。

我有一个浮点数组，我想对其执行 stram 压缩操作，就像这里介绍的那样：Parallel Prefix Sum (Scan) with CUDA，然后根据值和地址或原始元素应用转换。

例如，我有一个值为 {10,-1, -10, 2} 的数组，我想返回绝对值大于 5 的所有元素，并应用一个转换来获取该值及其在大批。这里的结果是 {transform(10,0),transform(-10,2)}。

我正在尝试对此使用推力，但此代码将经常在大型数组上运行，因此理想情况下它不会使用缓冲区和数组的多次遍历。

是否可以在不分配辅助数组并进行多次遍历的情况下做我想做的事情？如果是，这样的代码是否存在于野外？或者至少有人知道我可以编写哪些推力函数或任何其他库来达到我的目标吗？

git 版本控制系统，是一种分布式日志（在概念上与 raft 共识协议有一些相似之处）。

Raft 和其他一些系统都有log compaction的概念，所以新客户端不需要遍历整个 change set 来应用更改。

我的问题是：git 有日志压缩的概念吗？

作为一个学校项目，我们 4 正在使用 OpenCL 开发并行光线追踪器。这是我们第一个使用 OpenCL 的项目，所以我们可能对它有一些不理解。

我们正在尝试实现并行缓冲区压缩以删除完成的光线，或者没有与任何东西碰撞的光线，以便下一次迭代处理更少的数据。基本上，我们有一个缓冲区，可以s_ray_states根据需要进行渲染、跟踪、获取碰撞数据、压缩缓冲区，这样就只有与其中的对象发生碰撞的光线，然后对它们进行着色。

所以我们有一个缓冲区uint *prefix_sum，其中包含每个s_ray_state必须移动到缓冲区中的索引，s_ray_state *ray_states以减少发送到着色内核的光线数量，以及跟踪/着色内核的下一次迭代。

可悲的是，ray_sort下面的内核似乎无法正常工作，我们验证了输入prefix_sum数据，这是 100% 正确的，对于ray_states缓冲区也是如此，但我们在输出中得到了不需要的数据。

我们正在启动一个工作组（全局工作大小 = 局部工作大小），光线总是在缓冲区中移动到比其原始索引更小的索引。我们设置了障碍，并且正在使用s_ray_state *tmp缓冲区来防止并行执行写入彼此的数据，但它似乎不起作用，即使移除障碍我们也会得到相同的结果。

我们俩都在努力了 4 天，已经向其他学生寻求帮助，但似乎没有人能够弄清楚哪里出了问题。我们可能对障碍/内存栅栏的理解不足以确保这实际上可以工作。

我们已经尝试让单个工作组中的单个工作项对整个数组进行排序，这很有效，甚至可以提供更好的性能。

下面的代码应该工作吗？以我们对 OpenCL 的理解，它应该可以工作，我们做了很多研究，但从未真正得到任何明确的答案。

ray_states长度是ray_states_size

prefix_sum包含每个ray_states元素必须移动到的索引

tmp是大小的本地缓冲区local_work_size

local_work_size=global_work_size

did_hit()如果射线击中一个物体，则返回 1，否则返回 0

我们期望ray_states元素被移动到包含在prefix_sum

示例：每个都ray_states[id]被移动到prefix_sum[id]索引中 ray_states

prefix_sum: 0 | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 4

did_hit(ray_states[id]): 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0

did_hit(output[id]): 1 | 1 | 1 | 1 | X | X | X | X | X

Xs 可以是任何东西

我有一个启用了酸的、分区的、分桶的配置单元表，我正在使用流式客户端对其进行写入。我看到在将记录写入分区时创建了几个增量文件。我想启用自动压缩并尝试了以下基本参数和特定参数：

和，

我做了上述工作，希望能够实现 主要的压缩。但是我看到主要压缩只自动触发一次。即，主要压缩运行一次并创建一个基本文件。一旦为该分区中的许多 delta 文件创建了基本文件，尽管此后有更多的 delta 文件流入该分区，但不会进一步安排主要压缩。如何为表启用自动主要压缩？以前有没有人遇到过类似的问题？

我正在尝试使用 AArch64 SVE（或SVE2）实现 SIMD 算法，该算法采用元素列表并仅选择满足特定条件的元素。它通常被称为 Left Packing ( SSE/AVX/AVX-512 ) 或 Stream Compaction ( CUDA )？

是否可以使用 SVE 对该操作进行矢量化？

等效的 SQL 和标量代码可能如下所示：

可以使用 AVX-512 在 SIMD 中对其进行矢量化

如何使用 AArch64 SVE 实现它？有没有类似 AVX-512 compress_store的函数来压缩稀疏数据？

注意：SVE 既有 collect 也有scatter，详情请参阅SVE 的简短介绍。但我找不到等效的 SVE / 2 指令来保持元素的相对顺序。