部分多键映射的数据结构?

2024-03-10

我的数据由映射到值的键组成,如下所示:

---------------------
Key          | Value
---------------------
(0, 0, 0, 0) | a
(0, 0, 0, 1) | b
(0, 1, 0, 1) | c
(0, 1, 1, 0) | d
....

我正在寻找一种可以有效地对键执行搜索查询的数据结构,其中查询可以是完整或部分指定键。例如:

(0, 0, 0, 1) -> a
(0, *, *, *) -> [a, b, c, d]
(0, 1, *, *) -> [c, d]

The idea that I've right now is to implement this using a regular tree, similar to this: tree Leaves nodes represent the values and non-leaves nodes are parts of the key (i.e. w,x,y and z nodes are first, second, third and forth part of the key, respectively.). A simple BFS algorithm could be used to answer any query. But the problem is that this tree is growing exponentially with each new part of the key.

什么数据结构/算法更适合解决这个问题?请注意,关键部分可以是数字或字符串。


数组。对真的!您将没有空间开销,没有“指针追逐”开销,并且计算索引只需要一点位数学,而处理器在这方面确实相当擅长。

假设您获得部分密钥作为mask and bits哪里的mask通配符位为 0,其他位为 1,并且bits通配符为 0,非通配符为任意值。

收集具有与该模式匹配的键的所有项目的算法是:

int key = bits;
do {
    yield items[key];
    key = (key | mask) + 1 & ~mask | bits;
} while (key != bits);

That key = (key | mask) + 1 & ~mask | bits这部分看起来很有趣,这就是它的工作原理。

The |(按位或)使所有非通配符为 1。这可确保增量继续携带非通配符的位。添加之后,本应“固定”的位被破坏(如果进位通过它们,则为 0,否则为 1),因此必须将它们屏蔽掉(& ~mask),然后设置回正确的值(| bits)。运算符的优先级使得它基本上可以在没有括号的情况下编写。您也可以将其写为

key = (((key | mask) + 1) & (~mask)) | bits;

这适用于任何类型的模式。如果您只需要“最后 x 位是可变的”,您可以进行一些优化:

int wildcards = 0;
int invmask = ~mask;
do {
    yield items[wildcards++ | bits];
} while (wildcards & invmask);

That just runs from 0 to 2number-of-wildcards and then puts in the fixed bits in the top.

非二进制密钥

In the simplest non-binary case, the parts of the key are still some integral number of bits, that is, they range from 0 to 2n-1. You can use exactly the same code in that case, but the interpretation of the mask is different: instead of having a single 0 bit for a wildcard or a single 1 bit for a non-wildcard, it would have some other number of bits (corresponding to the width in bits of a key-part).

对于非二的幂,需要更多的技巧。问题在于,为了满足关键部分小于某个值的约束,必须比正常情况更早地生成进位。

例如,如果所有关键部分都可以是 0、1 或 2(但不能是 3),则可以执行以下操作(未测试):

int key = bits;
int increment = (0x55555555 & ~mask) + 1;
do {
    yield items[key];
    int temp = (key | mask) + increment & ~mask;
    int fix = (temp | (temp >> 1)) & 0x55555555;
    key = temp - fix | bits;
} while (key != bits);

额外的increment是 1 加上“最接近的 2 次方与关键部分最大值之差”的掩码,在本例中,每个关键部分都是 1,因此每个“槽”(槽)中都有一个 1是 2 位宽,这是在这种情况下它们可以达到的最窄宽度)。它仅在通配符位置具有那些“偏移量”。

偏移关键部分,使其最高允许值映射到“全一”,确保进位通过它们传播。然而,这意味着它们通常处于无效状态(除非它接收到进位并变为零)。那么烦人的部分就来了:必须撤消偏移only对于没有归零的关键部分。

所以有fix它计算不为零的关键部分的掩码。如果关键部分更宽,那就更烦人了,如果关键部分的尺寸不一样,那就更糟糕了。

然后最后一部分,key = temp - fix | bits,撤消偏移并将非通配符放回原位。该减法不会破坏任何内容,因为仅从至少为 1 的 2 位组中减去 1,因此进位永远不会留下关键部分。

当然,这种索引方式确实浪费了一些空间,与二次幂的情况不同,因为数组中存在您永远无法索引的“洞”。

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

部分多键映射的数据结构? 的相关文章

  • 对相当大的整数的大集合的操作的快速实现

    描述 我实现了以下类 LabSetInt64 参见下面的代码 这里的目标是尽可能快地操作大量大整数 最多 10M 的值 我的主要要求集中在 至关重要 尽快获取集合的大小 基数 重要 能够非常快速地迭代一组集合 所以 从下面的实现开始 我还有
  • 如何计算python 2D散点占用面积

    我使用 matplotlib 绘制了这两个 2000 个点的序列 从图片上看 前2000点占用的面积比后2000点要小 但如果我想定量计算2000个点的第一序列和第二序列占用了多少面积 该怎么办 我真的很感谢任何帮助 建议或意见 非常感谢
  • Numpy:具有特定条件的线性系统。无负解

    我正在使用 numpy 编写 Python 代码 在我的代码中 我使用 linalg solve 来求解 n 个变量中的 n 个方程的线性系统 当然 解决方案可以是积极的 也可以是消极的 我需要做的是始终有正解或至少等于 0 为此 我首先希
  • 数组中的重复元素[重复]

    这个问题在这里已经有答案了 这有点与this https stackoverflow com questions 2605766 how to find a duplicate element in an array of shuffled
  • 我的程序替换了链表中所有节点中的所有字符串数据类型

    我有一个程序 基本上将历史记录 节点 添加到员工记录 链接列表 中 这是我的代码 include
  • 从列表中获取数组而不进行堆分配

    我有一个列表 我想将其数组分配给一个属性 public void BuildMesh List
  • 快速排序应用程序中这些交换代码行的目的是什么?

    我试图理解快速排序的实现或应用程序以找到第 k 个最小元素 这是我试图理解的代码 public int quicksort int a int start int end int k if start lt end int pivot pa
  • 用于计算三角函数、对数或类似函数的算法。仅限加减法

    我正在修复 Ascota 170 古董机械可编程计算机 它已经开始工作了 现在我正在寻找一种算法来展示其功能 例如计算三角或对数表 或类似的东西 不幸的是 从数学运算来看 计算机只能进行整数的加减法 从 1E12到1E12的55个寄存器 甚
  • 如何在单向链表(一次遍历中)中从尾部获取第 n 个节点?

    所以我在一次考试中得到了这个问题 如何从单链表的尾部获取第 n 个节点 每个节点都有一个值和一个下一个 指向下一个值的指针 我们得到这个 getNodeFromTail Node head int x 所以我的做法是通过遍历一次来求出列表的
  • 在 3d 网格中转发(绘制)线

    我需要类似 Bresenham 算法的东西 但是 对于 3d 网格空间来说不完全是这样 我需要 3d 单元网格 边缘尺寸 1 0 从 S 点开始 前进到 K 点 接触 该线接触的所有单元格 即使只有边缘 点被触摸我需要触摸所有 8 个单元
  • 序列和与 GCD

    大约一个月前 我在编程挑战中遇到了这个问题 但社论尚未发布 所以我在这里问 有一个大小为 N 的数组 A 求 A 的 K 个长度子序列的总和 GCD Example 如果 A 1 2 3 且 K 2 1 2 3 总和 1 GCD 3 1 3
  • 如何在 JavaScript 中构建树模式匹配算法?

    好吧 这是一个有点复杂的问题 但是 tl dr 基本上是如何使用 模式树 解析 实际树 如何检查特定的树实例是否与特定的模式树匹配 首先 我们有我们的结构模式树 模式树通常可以包含以下类型的节点 sequence节点 匹配一系列项目 零个或
  • 线段树java实现[关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 你知道 二进制 的良好实现吗线段树 http en wikipedia org wiki Segmen
  • 自动跟踪算法

    我正在尝试写一个simple跟踪例程来跟踪电影中的某些点 本质上我有一系列 100 帧长的电影 在黑暗背景上显示一些亮点 我每帧有大约 100 150 个点 它们在电影的过程中移动 我想跟踪它们 所以我正在寻找一些有效的 但可能不会过度实施
  • 数独算法,暴力破解[关闭]

    这个问题不太可能对任何未来的访客有帮助 它只与一个较小的地理区域 一个特定的时间点或一个非常狭窄的情况相关 通常不适用于全世界的互联网受众 为了帮助使这个问题更广泛地适用 访问帮助中心 help reopen questions 我正在尝试
  • 分而治之算法找到两个有序元素之间的最大差异

    给定一个整数数组 arr 找出任意两个元素之间的差异 使得较大的元素出现在 arr 中较小的数字之后 Max Difference Max arr x arr y x gt y 例子 如果数组是 2 3 10 6 4 8 1 7 那么返回值
  • 在任意时间范围内找到最佳日/月/年间隔的算法?

    如果您有时间表 请说 March 19 2009 July 15 2011 是否有一种算法可以将该时间范围分解为 March 19 2009 March 31 2009 complete days April 1 2009 December
  • 如何将多边形放入另一个多边形内[关闭]

    Closed 这个问题需要多问focused help closed questions 目前不接受答案 我有两个多边形 如下图所示 左边是 粗多边形 右边是 最终多边形 现在 我正在寻找算法来将 最终多边形 拟合到 粗糙多边形 内 并具有
  • 是否有一种算法可以在线性时间内计算数组反转?

    我知道有多少倒转 en wikipedia org wiki Inversion 28discrete mathematics 29 in an n 元素数组可以在 O n log n 操作使用增强型归并排序 http www geeksf
  • 如何在 C# 中以编程方式创建柔和的颜色?

    根据所需的颜色数量均匀分布地生成它们 如果指定的计数为 8 则看起来像这样 List

随机推荐