问题标签 [constant-time]

我有一个可以包含多个子弹的世界，所有子弹都有一个位置（中心）。基本上是以下

我们需要在O(1)（几乎恒定的时间）内实现一个函数，它通过给出一个位置来检索世界中对应的子弹。

我试图用来HashMap存储key/value (Position/Bullet)对。但是，在更改子弹的坐标后，我无法再使用他更新的位置来检索它，例如：

null结果给出

最初，我认为问题是由我实现的 hashCode 和 equals 方法的问题引起的：

但是后来，我意识到我使用的数据结构并不适合这种问题。也就是说，PositionBullet 的 可以随时更改，但桶中的密钥不会更新。

我已经搜索了一段时间，但我找不到合适的数据结构来做到这一点。所以我想问一下是否有一个好的数据结构/实现可以用来及时解决这个问题O(1)？

为了比较两个字符串，我目前使用 strcmp 或其变体之一。但是，因为如果匹配更多字符，strcmp 需要更长的时间，因此很容易受到定时攻击。Windows 标准库中是否有常量时间字符串比较函数？

This question just went over my head:

A function G(m) is defined as below:

a) If m <= 100 then G(m) = G(G(m + 11))

b) If m > 100 then G(m) = m – 10

According to above question, how do I design a constant-time algorithm that calculates G(m)?

我正在编写一个 ProtectedPtr 类，该类使用 Windows Crypto API 保护内存中的对象，并且在创建通用常量时间比较函数时遇到了问题。我当前的代码：

getEncryptedData 函数：

问题是转换为字节*。将此类与字符串一起使用时，我的编译器抱怨无法将字符串转换为字节指针。我在想也许试图将我的函数基于 Go 的 ConstantTimeByteEq 函数，但它仍然让我回到我原来的问题，将模板类型转换为 int 或我可以执行二进制操作的东西。

Go 的 ConstantTimeByteEq 函数：

如何轻松地将模板类型转换为可以轻松执行二进制操作的东西？

更新根据 lockcmpxchg8b 的建议工作的通用常量比较函数：

在准备面试时，我遇到了一些让我质疑我对大 O 常数时间算法的理解的事情。

LeetCode 上的一个问题要求创建 LFU 缓存问题的解决方案。

有3种方法可以实现：

构造函数 - 输入：int 容量

获取 - 输入：int 键 - 输出：int

设置 - 输入：int 键，int 值

容量表示您一次可以保存的缓存键/值对的最大数量。当容量被破坏时，您必须弹出访问频率最低的对。

很明显，您必须跟踪每个项目被访问的次数。

在问题的底部，它询问您是否可以在 O(1) 时间内获取和设置。

我正在研究这个的多个提议的实现，一长串的人都同意他们是恒定时间实现的例子，但对我来说，他们看起来像 O(N)。

有关完整示例，请参见此处： https ://leetcode.com/problems/lfu-cache/discuss/94515/Java-O(1)-Accept-Solution-Using-HashMap-DoubleLinkedList-and-LinkedHashSet?page=1

但是这个例子中的相关方法在下面的代码块中。注意 valueHash 和 nodeHash 都是 java 哈希表。

方法调用 Hashtable.containsKey 和 Hashtable.get，实现线性搜索。所以最坏情况的时间复杂度是 O(N) 对吧？我错过了什么？

这个问题基本上说明了一切。假设我有一个（排序的）列表，可以包含从 1K 到 1M 的任何项目。我有一个starting index和一个ending index。如果我使用该ArrayList.sublist(start, end)方法，时间复杂度是 O(n) 还是 O(1)？我确实在这里检查了答案，因为我认为这是一个常见问题，但是虽然我找到了 LinkedList 的重复答案，但我找不到关于 ArrayList 的特定问题。感谢大家的回答！

数组中的索引（维护索引）使得O(N)Array.prototype.shift而Array.prototype.unshift不是 O(1)。

但是，如果我们只想使用 pop() / push() / shift() 和 unshift() 而从不使用索引进行查找，有没有办法实现一个省略索引的 JavaScript 数组？

我想不出办法。我能想到的唯一方法是使用数组，并且只使用 pop() / push() （因为它们是 O(1)）......但即使有多个数组，也不确定是否可能。

如果可能的话，希望使用 oa 链表来执行此操作。我用双链表实现了一个解决方案，但想知道是否可以用 oa 链表来做这个。

最终目标： 尝试创建一个所有操作都在恒定时间内的 FIFO 队列，而不使用链表。

我正在尝试运行我过去能够运行的脚本。它因错误而停止：

我最近删除了 python 3.6 并安装了 python ActiveState：

到目前为止我尝试过的事情：

重新安装密码学

重新安装密码学，但出现错误：

任何帮助将非常感激。我对python相当陌生，但我不知所措

有一个很好的解决方案：使用 itertools 的格雷码顺序的笛卡尔积？，有没有办法给这个解决方案添加一些简单的东西，以报告从一个元素到格雷码顺序的笛卡尔积的下一个元素发生变化的集合（它的索引）？也就是说， agray_code_product_with_change(['a','b','c'], [0,1], ['x','y'])会产生如下内容：

我想避免采用连续元组之间的“差异”，但要进行恒定时间更新——因此要从格雷码顺序开始。一种解决方案可能是编写一个index_changed迭代器，即返回index_changed(3,2,2)我想要的序列-1,2,1,2,0,2,1,2,0,2,1,2，但是可以将更简单的东西添加到上面的解决方案中以获得相同的结果吗？

在一个用 python 编写的机器学习项目中，我需要一个高效的循环缓冲区，collections.deque但可以持续访问任何元素，如numpy.array. 问题是 deque 显然是一个链表。请在我不知道此用例的python库中轻松实现一些有效的东西吗？

我想我可以在我的用例中简单地修改固定大小numpy.array和移动 0 索引，但这是我的 python 文化，因为这不是我第一次需要这样的东西。