草庐IT

Redis ZRANGEBYLEX 命令复杂度

coder 2023-07-18 原文

根据 ZRANGEBYLEX command 的文档部分, 有以下信息。如果将键存储在零分的有序集中，则可以按字典顺序检索后面的键。 ZRANGEBYLEX 操作复杂度为 O(log(N)+M)，其中 N 是元素总数，M 是结果集大小。文档有一些关于字符串比较的信息，但没有说明将存储元素的结构。

但经过一些实验和阅读之后source code ，这可能是 ZRANGEBYLEX 操作具有线性时间搜索的原因，此时 ziplist 中的每个元素都将与请求匹配。如果是这样，复杂度将比上面描述的更大——大约 O(N)，因为 ziplist 中的每个元素都将被扫描。

用gdb调试后，很明显ZRANGEBYLEX命令在genericZrangebylexCommand中实现了功能。控制流在 eptr = zzlFirstInLexRange(zl,&range); 处继续，因此元素检索的主要工作将在 zzlFirstInLexRange 处执行。功能。所有命名和后续控制流都考虑使用ziplist结构，所有与输入操作数的比较都是逐个元素顺序进行的。
在 redis 存储中插入众所周知的键后通过分析检查内存，似乎 ZSET 元素确实存储在 ziplist 中 - 与 gauge 逐字节比较确认一下。

那么问题 - 文档怎么会出错并在出现线性复杂度的地方传播对数复杂度？或者 ZRANGEBYLEX 命令的工作方式略有不同？提前致谢。

最佳答案

how can documentation be wrong and propagate logarithmic complexity where linear one appears?

该文档多次出错，但这是一项持续的开源工作，您可以通过存储库 (https://github.com/antirez/redis-doc) 为之做出贡献。

Or maybe ZRANGEBYLEX command works slightly different?

从某种意义上说，您的结论是正确的，因为当使用 Ziplist 对其进行编码时，排序集搜索操作(无论是否按字典顺序)都表现出线性时间复杂度。

但是。

Ziplists 是一种更喜欢 CPU 而不是内存的优化，这意味着它适用于小集合(即低 N 值)。它通过配置进行控制(参见 zset-max-ziplist-entries 和 zset-max-ziplist-value 指令)，一旦数据增长超过指定阈值ziplist 编码转换为 skip list .

因为 ziplist 很小(小 N)，它们的复杂度可以假设为常数，即 O(1)。另一方面，由于它们的性质，跳跃列表表现出对数搜索时间。 IMO 这意味着文档的完整性保持不变，因为它提供了最坏情况下的复杂性。

关于Redis ZRANGEBYLEX 命令复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47871402/

ZRANGEBYLEXRediscodenoreferrertime-complexity

有关Redis ZRANGEBYLEX 命令复杂度的更多相关文章

  1. ruby - 在 Ruby 中编写命令行实用程序 - 2

    我想用ruby​​编写一个小的命令行实用程序并将其作为gem分发。我知道安装后，Guard、Sass和Thor等某些gem可以从命令行自行运行。为了让gem像二进制文件一样可用，我需要在我的gemspec中指定什么。 最佳答案 Gem::Specification.newdo|s|...s.executable='name_of_executable'...endhttp://docs.rubygems.org/read/chapter/20 关于ruby-在Ruby中编写命令行实用程序

  2. ruby-on-rails - rbenv:从 RVM 移动到 rbenv 后，在 Jenkins 执行 shell 中找不到命令 - 2

    我从Ubuntu服务器上的RVM转移到rbenv。当我使用RVM时，使用bundle没有问题。转移到rbenv后，我在Jenkins的执行shell中收到“找不到命令”错误。我内爆并删除了RVM，并从~/.bashrc'中删除了所有与RVM相关的行。使用后我仍然收到此错误:rvmimploderm~/.rvm-rfrm~/.rvmrcgeminstallbundlerecho'exportPATH="$HOME/.rbenv/bin:$PATH"'>>~/.bashrcecho'eval"$(rbenvinit-)"'>>~/.bashrc.~/.bashrcrbenvversions

  3. ruby - 使用 AES 的 Rails 加密，过于复杂 - 2

    我在加密来self正在使用的第三方供应商的值时遇到问题。他们的指令如下:1)Converttheencryptionpasswordtoabytearray.2)Convertthevaluetobeencryptedtoabytearray.3)Theentirelengthofthearrayisinsertedasthefirstfourbytesontothefrontofthefirstblockoftheresultantbytearraybeforeencryption.4)EncryptthevalueusingAESwith:1.256-bitkeysize,2.25

  4. ruby - 从 Ruby : capturing the output while displaying the output? 运行 shell 命令 - 2

    我有一个问题。我想从另一个ruby​​脚本运行一个ruby​​脚本并捕获它的输出信息，同时让它也输出到屏幕。亚军#!/usr/bin/envrubyprint"Enteryourpassword:"password=gets.chompputs"Hereisyourpassword:#{password}"我运行的脚本文件:开始.rboutput=`runner`putsoutput.match(/Hereisyour(password:.*)/).captures[0].to_s正如您在此处看到的那样，存在问题。在start.rb的第一行，屏幕是空的。我在运行程序中看不到“输入您的密

  5. ruby - 是否有将图像文件转换为 ASCII 艺术的命令行程序或库？ - 2

    有这样的事吗？我想在Ruby程序中使用它。 最佳答案 试试这个http://csl.sublevel3.org/jp2a/此外，Imagemagick可能还有一些东西 关于ruby-是否有将图像文件转换为ASCII艺术的命令行程序或库？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/6510445/

  6. ruby - 测试一个复杂的方法 - 2

    我正在开发西洋跳棋实现，其中有许多易于测试的方法，但我不确定如何测试我的主要#play_game方法。我的大多数方法都可以很容易地确定输入和输出，因此也很容易测试，但这种方法是多方面的，实际上并没有容易辨别的输出。这是代码:defplay_gameputs@gui.introwhile(game_over?==false)message=nil@gui.render_board(@board)@gui.move_requestplayer_input=getscoordinates=UserInput.translate_move_request_to_coordinates(play

  7. ruby - 在 Ruby 的 if 语句中检查 bash 命令 - 2

    如何在Ruby的if语句中检查bash命令的返回值(true/false)。我想要这样的东西，if("/usr/bin/fswscell>/dev/null2>&1")has_afs="true"elsehas_afs="false"end它会提示以下错误含义，它总是返回true。(irb):5:warning:stringliteralincondition正确的语法是什么？更新:/usr/bin/fswscell寻找afs安装和运行状态。它会抛出这样的字符串，Thisworkstationbelongstocell如果afs没有运行，命令以状态1退出 最

  8. ruby - 是否有用于复杂比较的漂亮语法？ - 2

    方法应返回-1,0或1分别表示“小于”、“等于”和“大于”。对于某些类型的可排序对象，通常将排序顺序基于多个属性。以下是可行的，但我认为它看起来很笨拙:classLeagueStatsattr_accessor:points,:goal_diffdefinitializepts,gd@points=pts@goal_diff=gdenddefothercompare_pts=pointsother.pointsreturncompare_ptsunlesscompare_pts==0goal_diffother.goal_diffendend尝试一下:[LeagueStats.new(

  9. ruby - 可以正常中断的来自 Rake 的长时间运行的 shell 命令？ - 2

    在几个项目中，我希望有一个类似rakeserver的rake任务，它将通过任何需要的方式开始为该应用程序提供服务。这是一个示例:task:serverdo%x{bundleexecrackup-p1234}end这行得通，但是当我准备停止它时，按Ctrl+c并没有正常关闭；它中断了Rake任务本身，它说rakeaborted!并给出堆栈跟踪。在某些情况下，我必须执行Ctrl+c两次。我可能可以用Signal.trap写一些东西来更优雅地中断它。有没有更简单的方法？ 最佳答案 trap('SIGINT'){puts"Yourmessa

  10. ruby - Capistrano 中的执行、测试和捕获命令有什么区别？ - 2

    关于SSHkit-Github它说:Allbackendssupporttheexecute(*args),test(*args)&capture(*args)来自SSHkit-Rubydoc,我明白execute实际上是test的别名？test之间有什么区别？,execute,capture在Capistrano/SSHKit中我应该什么时候使用？ 最佳答案 执行只是执行命令。使用非0退出引发错误。测试方法的行为与execute完全相同，但是它返回bool值(true如果命令以0退出，而false否则)。它通常用于控制任务中的流程

随机推荐