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

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(使用前将#替换为@)

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

  • 算法 - 如何有效删除列表中的重复元素?

    有一个list L 它包含以下元素任意类型each 如何有效删除此类列表中的所有重复元素 必须保留订单 只需要一个算法 因此不允许导入任何外部库 相关问题 在Python中 从列表中删除重复项以使所有元素都是唯一的最快算法是什么在维持秩序的
  • Dijkstra 算法不生成最短路径?

    我正在使用 Dijkstra 算法解决最短路径问题 我遇到了麻烦 因为该算法应该提供最短路径 但运行该算法后 我手动得到了一条短路路径 这只是该算法的副产品吗 我尝试生成的路径是从 a gt z 这是我通过应用该算法得到的路径 在我访问的每
  • 所有可能的骑士在普罗梅拉的棋盘上移动

    是否有可能用马从初始位置 I J 绕过大小为 N N 的棋盘 并且只访问每个方格一次 define A True A I J false active proctype method bit I 4 bit J 3 bit K 1 bit
  • 用于基本要素匹配的最坏情况 NlogN 算法

    查找两个相同大小数组的元素之间的唯一映射 https stackoverflow com questions 4411940 find the unique mapping between elements of two same size
  • 识别鼠标移动的算法

    我想知道是否有任何研究 算法可以指定鼠标在识别 等字符时的偏差量使用鼠标绘制 某种光学字符识别 但可能是一个更简单的版本 是否有某种算法可以让我说用户绘制的问号确实是一个问号 而不是其他具有一定准确性的东西 就像 Windows 平板电脑软
  • Python 中的空填字游戏求解器

    我得到了一个包含填字游戏蓝图的矩阵 当然 它是空的 我们的目标是填补整个难题 这是 Checkio 的一项任务 我已经为此奋斗了相当长一段时间 根据我对复杂性的理解 这个问题没有完美的算法 不过 必须有最好的方法来做到这一点 对吧 我尝试了
  • 用ast重写代码; Python

    我正在学习 AST 它看起来很强大 但我很困惑代码去了哪里以及为什么它消失了 说我想重写 example def fake x n y useless list n return x as example def fake x n retu
  • 当平方和为N时,如何找到四个变量的所有可能值?

    A 2 B 2 C 2 D 2 N给定一个整数N 打印出整数值的所有可能组合ABCD求解方程 我猜我们可以比暴力做得更好 天真的暴力会是这样的 n 3200724 lim sqrt n 1 for a 0 a lt lim a for b
  • 神经网络的层和神经元

    我想更多地了解神经网络 我正在开发一个 C 程序来制作神经网络 但我坚持使用反向传播算法 很抱歉没有提供一些工作代码 我知道有很多库可以用多种语言创建神经网络 但我更喜欢自己制作一个 关键是我不知道要实现特定目标 例如模式识别或函数近似或其
  • 处理流星中的长服务器端计算

    我正在使用 jimp https www npmjs com package jimp https www npmjs com package jimp 在meteor JS中生成图像服务器端 换句话说 我正在使用递归算法 计算 图像的像素
  • 查找文本中所有关键字的有效算法

    我有很多字符串 其中包含许多不同拼写的文本 我通过搜索关键字来标记这些字符串 如果找到关键字 我将使用该关键字的关联文本 假设搜索字符串可以包含文本 schw schwa 和 施瓦茨 我有三个关键字 全部解析为文本 schwarz 现在我正
  • 线段树java实现[关闭]

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

    我需要创建一个民意调查 按照项目的好坏顺序创建一个排名列表 我打算向每个用户展示两个项目 让他们选择一个他们认为更好的项目 然后多次重复这个过程 它有点类似于您在社交网络电影 我应该如何根据收到的答案对项目进行排名 看着那 这ELO国际象棋
  • 关于Marching Cubes算法的澄清

    关于Marching Cubes 我对其算法和实现有一些疑问 我已经阅读了 Marching Cubes 的 Paul Bourke 优秀文章以及网站上可用的源代码 但是 我在理解以及如何以自己的方式实现算法方面仍然遇到了一些问题 问题如下
  • 什么是“朴素”算法,什么是“封闭式”解决方案?

    我有一些关于描述算法时使用的术语语义的问题 首先 朴素 算法是什么意思 这与给定问题的其他解决方案有何不同 解决方案还可以采取哪些其他形式 其次 我听到很多人提到 封闭式 解决方案 我也不知道这意味着什么 但在尝试解决递归关系时经常会出现
  • 如何求两个地点的经纬度距离?

    我有一组位置的纬度和经度 怎么找distance从集合中的一个位置到另一个位置 有公式吗 半正矢公式假定地球是球形的 然而 地球的形状更为复杂 扁球体模型会给出更好的结果 如果需要这样的精度 你应该更好地使用文森特逆公式 See http
  • 坐标算法 - 绕中心旋转

    通过查看这张图片 我想您会很好地理解我的问题 图片已删除 网址不再有效 现在返回广告 所以基本上我想要一个函数 它接受一个对象作为参数 并根据我之前添加的对象数量为该对象提供正确的坐标 假设我将所有这些对象添加到一个数组中 objectAr
  • heapq.nlargest 的时间复杂度是多少?

    我在看演讲者说 获得t列表中最大的元素n元素可以在O t n 这怎么可能 我的理解是创建堆将是O n 但是复杂度是多少nlargest本身就是O n t or O t 实际的算法是什么 在这种情况下 说话者是错误的 实际成本是O n log
  • 求先递增后递减列表的最大值和最小值

    我尝试用谷歌搜索这个问题 但没有取得太大成功 我确信这个问题或类似问题有一个技术名称 但我似乎找不到答案 给定一个列表L整数 即严格递增 然后严格递减 找到该列表的最大值和最小值 例如 L可能 1 2 3 4 5 4 3 2 or 2 4
  • 如何计算 3D Morton 数(交织 3 个整数的位)

    我正在寻找一种快速计算 3D Morton 数的方法 这个网站 http www graphics stanford edu seander bithacks html InterleaveBMN有一个基于幻数的技巧来处理 2D Morto

随机推荐