算法以随机顺序存储列表的元素在没有定义顺序的密钥/值存储中,但要检索最大/min值
在执行相关应用程序(一个区块链节点,但无论如何)时,随着时间的流逝,每个新块都有与之关联的数字。该数字称为“链条”;这是一个具有自定义比较功能(不是C ++本地)的256位号码。
与以前的块的值相比,与新块相关的链条可以具有任何值。因为有太多的块,假设我们不想将所有块(甚至它们的链条)存储在内存中,那么我们必须将它们存储在持久存储中。
唯一可用的存储是一个密钥/值存储,不能保证这些数字是按顺序存储的。甚至没有预定义的存储顺序(将其视为哈希地图)。
问题:我们需要将这些数字存储在该持久存储中,但是只能检索with will
问题:是否有一种方法或算法可以使其成为可能为了获得在任何时间点可用的链条值的最大值(以及与之相关的一些信息),前提是我们可以存储任何需要的额外信息来帮助从未分类容器中检索最大值?换句话说,是否有一种方法可以合理地牺牲存储,以便为这个问题获得更好的复杂性,而不必用O(n)循环循环所有链条值?
如果您需要任何其他信息,请继续询问。
编辑:跟踪最大值不起作用,因为有时可以删除最大值,因此需要对所有值进行重新循环。我忘了提到这一点,但在评论中出现了。道歉。
While executing the application in question (a blockchain node, but regardless), every new block that comes over time has a number associated with it; The number is called "ChainWork"; it's a 256-bit number with a custom comparison function (not native to C++).
The ChainWork associated with new blocks can theoretically have any value compared to the previous blocks' values. Because there are way too many blocks, assuming we don't want to store all the blocks (or even their ChainWork) in memory, we have to store them in a persistent storage.
The only storage available is a key/value store that does not guarantee that these numbers are stored in order. There is not even a pre-defined storage order (think of it as a hash map).
The problem: We need to store these numbers in that persistent storage, but retrieve only the maximum value at will
The question: Is there a way or algorithm that can make it possible to get the maximum value of the ChainWork values available at any point in time (and some associated information with them), provided that we can store any extra information required to help in retrieving the maximum value from the unsorted container? In other word, is there a way to reasonably sacrifice storage to get better complexity for this problem, instead of having to loop over all the ChainWork values, with O(N)?
If you require any additional information, please go ahead and ask.
EDIT: Keeping track of the max does not work because the max can be removed at times, so a re-loop over all the values would be required. I forgot to mention this point, but it came up in the comments. Apologies.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论