有效地找到大型数组中的最低有效设置位?

2024-01-10

我有一个巨大的内存块(位向量),其大小N一个内存页内的位,考虑N平均为 5000,即 5k 位来存储一些标志信息。
在某个时间点(超频繁 - 关键),我需要找到整个大位向量中的第一个位集。现在我对每个 64 个单词执行此操作,即在__builtin_ctzll https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)。但当N增长并且搜索算法无法改进,可以通过扩展内存访问宽度来扩展此搜索。简而言之,这是主要问题

有一个汇编指令称为BSF https://www.felixcloutier.com/x86/bsf给出最高设置位的位置(GCC__builtin_ctzll())。 所以在x86-64 /questions/tagged/x86-64arch 我可以很便宜地找到 64 位字中设置的最高位。

但是通过内存宽度进行扩展又如何呢?
例如。有没有办法用 128 / 256 / 512 位寄存器有效地做到这一点?
基本上我对一些C API函数来实现这个感兴趣,但也想知道这个方法是基于什么。

UPD:至于 CPU,我对这种优化感兴趣,以支持以下 CPU 系列:
Intel Xeon E3-12XX、Intel Xeon E5-22XX/26XX/E56XX、Intel Core i3-5XX/4XXX/8XXX、Intel Core i5-7XX、Intel Celeron G18XX/G49XX(可选配 Intel Atom N2600、Intel Celeron N2807、Cortex- A53/72)

P.S.在最终位扫描之前提到的算法中,我需要求和k(平均20-40)N位向量与 CPU AND(AND 结果只是位扫描的准备阶段)。这对于内存宽度缩放也是可取的(即比每个 64 位字 AND 更有效)

另请阅读:找到第一组 https://en.wikipedia.org/wiki/Find_first_set


这个答案是不同的,但如果您事先知道您将维护 B 位的集合,并且需要能够有效地设置和清除位,同时还要弄清楚哪个位是第一个设置的位,你可能想使用像这样的数据结构范恩德博阿斯树 https://en.wikipedia.org/wiki/Van_Emde_Boas_tree or a y-快速特里 https://en.wikipedia.org/wiki/Y-fast_trie。这些数据结构旨在存储小范围内的整数,因此您可以添加或删除要设置/清除的位的索引,而不是设置或清除各个位。它们非常快 - 您可以在 O(log log B) 时间内添加或删除项目,并且它们可以让您在 O(1) 时间内找到最小的项目。如图所示,如果 B ≈ 50000,则 log log B 约为 4。

我知道这并不直接解决如何在巨大的位向量中找到最高位集。如果您的设置必须使用位向量,那么其他答案可能会更有帮助。但是,如果您可以选择以不涉及位向量搜索的方式重新构建问题,那么这些其他数据结构可能更适合。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

有效地找到大型数组中的最低有效设置位? 的相关文章

随机推荐

  • Laravel 路由重定向而不关闭路由缓存

    我的电脑上有这个代码routes php执行重定向的文件 虽然问题是每当我跑步时php artisan route cache命令 它给了我一个错误Unable to prepare route article params for ser
  • 用于网络请求的 AsyncTask 与 ThreadPoolExecutor

    我正在开发一个项目 我需要点击 Web 服务下载 JSON 数据并将其表示在列表中 所有列表项都有缩略图 URL 可以下载并显示在列表项中 我已经使用 ThreadPoolExecutor 和 AsyncTask 完成了整个调用部分 但从设
  • 在 Spring Batch 中访问步骤范围之外的 Bean

    是否可以访问步骤范围之外定义的 bean 例如 如果我定义策略 strategyA 并将其传递到作业参数中 我希望 Value 解析为strategyA bean 这可能吗 我目前正在通过从 applicationContext 手动获取
  • NPM Start 未启动本地服务器

    我正在尝试使用 webpack 制作一个 React 应用程序 当我尝试运行 npm start 时 它应该加载http localhost 3333但它说无法访问网站 这是我的 webpack 配置 module exports entr
  • 滑动视图控制器,但不使用 UISwipeGestureRecognizer

    这是我的问题 我有 5 个视图控制器 我可以使用 UISwipeGestureRecognizer 类和 xcode 的故事板通过滑动在它们之间切换 所以这可行 但是 我不喜欢幻灯片效果 我喜欢以某种方式进行制作 这样您就可以通过拖动将视图
  • Windows IoT 和 DS3231 RTC 时钟

    对于我的项目 我需要当前时间和日期 不幸的是 当 RP2 关闭时 它就会失去一切 接下来的事情是 我将没有互联网连接来使用 NTP 为此 我需要实现 DS3231 RTC 模块 所有设备的通信都通过 I2C 运行 Raspberry Ard
  • Google Admob Android:仅在一台设备上运行

    我在我的 Android 应用程序中设置了一个 admob adview 清单
  • 修改成员时不调用 C# 对象 Setter

    我有以下包装类 public class Wrapper public int Member 在一个单独的班级中 我有以下内容 public class ContainerClass private Wrapper data public
  • 我的谷歌地图被切断了,我想知道为什么? JavaScript,V

    It s kinda hard to explain so I uploaded a screen shot of the issue 正如您所看到的 尽管地图上有 div 不动产 这是实际大小 但它只显示了地图的 1 6 这个小部件可以调
  • 如何在 Java 中设置标签的颜色(彩色文本)?

    如何设置标签文本的颜色 myLabel setText Text Color Red myLabel 我可以在一个标签上使用两种不同的颜色吗 例如这里 The Text Color 变黑并且 Red 变红 对于单色前景色 label set
  • 为什么 (1 == 2 != 3) 在 Python 中计算结果为 False?

    为什么 1 2 3 评估为False在Python中 同时两者 1 2 3 and 1 2 3 评估为True 这里使用什么运算符优先级 这是由于运营商的连锁现象 https docs python org 3 reference expr
  • 为什么我可以使用类型别名声明 const 引用?

    我有一个简单的问题 据我所知 我可以声明const指向某种数据类型的指针或指向常量数据类型的指针 但我只能声明对常量数据类型的引用 而不能声明对数据类型的常量引用 事实上 引用已经是常量 因为它不能反弹到另一个对象 所以当我尝试创建一个co
  • 当多个文件作为参数传递给 perl cli 时,Perl 中文件的行号

    In awk如果我给出多个文件作为参数awk 有两个特殊变量 NR 对应于所有文件中所有行的行号 FNR 当前文件的行号 我知道在 Perl 中 对应于NR 所有文件中的行中的当前行 有什么可以媲美的FNRPerl 中的 AWK 也有吗 假
  • PBSPro qsub 输出错误文件定向到名称中包含 jobid 的路径

    我正在使用 PBSPro 并尝试使用 qsub 命令行提交作业 但似乎无法按照我想要的方式命名输出和错误文件 目前使用 qsub N subjobname short o path o PBS JOBID e path e PBS JOBI
  • VSTS 持续集成触发器不起作用

    我很确定这个设置在某一时刻对我们来说是有效的 我对我们的构建进行了一些更改以反映一些操作更改 但现在 CI git 分支触发器不起作用 我正在尝试获取它 以便当 PR 合并到 master 时它会触发发布构建 我可以手动触发此构建 但在从
  • 从 csproj 引用 ASP.NET xproj

    我正在使用 Visual Studio 中的新 类库 NuGet 包 模板之一 并且我想为其创建一个 xUnit 测试库 问题是 当我创建新的 csproj 库并尝试引用 xproj 包时 Visual Studio 说 The refer
  • 使用 c++ 中的 boost 进程库输出

    我使用升压过程并使用默认代码主要教程页面 http www highscore de boost process process tutorials html 我已经运行了这段代码 但它没有打印任何输出 include
  • BlackBerry - 在位图字段上调用单击事件

    谁能帮我解决以下问题 我正在为黑莓制作一个应用程序 从一个位图字段我必须通过单击该位图字段来调用一个新屏幕 我想要相同的代码 如何通过单击位图字段来调用新屏幕 我正在使用黑莓 JDE 4 7 尝试使 BitmapField 可聚焦 Bitm
  • Excel 中具有多个条件的 CUBESET() 函数

    我正在尝试在 Excel 中创建 CUBESET 函数 但我不知道如何使用多个条件过滤它同一维度内 这就是我迄今为止所遵循的一个标准 示例1 CUBESET ThisWorkbookDataModel Facebook Bucket C A
  • 有效地找到大型数组中的最低有效设置位?

    我有一个巨大的内存块 位向量 其大小N一个内存页内的位 考虑N平均为 5000 即 5k 位来存储一些标志信息 在某个时间点 超频繁 关键 我需要找到整个大位向量中的第一个位集 现在我对每个 64 个单词执行此操作 即在 builtin c