Redis和Ruby中的ZRANGEBYSCORE

Question

我试图在Ruby中的Redis代码中优化ZRANGEBYSCORE。

具体来说，Redis网站(http://redis.io/commands/zrangebyscore)指出：

时间复杂度: O(log(N)+M)，N是排序集中的元素数，M是返回的元素数。如果M是常数(例如总是要求前10个元素有极限)，你可以认为它是O(log(N))。

因此，正如我所读到的，只要我使用的限制，大号(O)应该是常数在O(log(N) )，无论限制设置为48或6。然而，我的基准似乎是相反的。

require 'redis'

def bench(descr)
    start = Time.now
    yield
    puts "#{descr} #{Time.now-start} seconds"
end

def with_pipelining_48
    id = 26053643
    @@redis.pipelined {
        1000.times {
            @@redis.zrevrangebyscore("key:#{id}", "+inf", "-inf", :limit => [0, 48],:with_scores => true)
        }
    }
end

def with_pipelining_24
    id = 26053643
    @@redis.pipelined {
        1000.times {
            @@redis.zrevrangebyscore("key:#{id}", "+inf", "-inf", :limit => [0, 24],:with_scores => true)
        }
    }
end

def with_pipelining_12
    id = 26053643
    @@redis.pipelined {
        1000.times {
            @@redis.zrevrangebyscore("key:#{id}", "+inf", "-inf", :limit => [0, 12],:with_scores => true)
        }
    }
end

def with_pipelining_6
    id = 26053643
    @@redis.pipelined {
        1000.times {
            @@redis.zrevrangebyscore("key:#{id}", "+inf", "-inf", :limit => [0, 6],:with_scores => true)
        }
    }
end

bench("with pipelining_48") {
    with_pipelining_48
}
bench("with pipelining_24") {
    with_pipelining_24
}
bench("with pipelining_12") {
    with_pipelining_12
}
bench("with pipelining_6") {
    with_pipelining_6
}

返回以下结果：

with pipelining_48 1.709097 seconds
with pipelining_24 0.930054 seconds
with pipelining_12 0.801045 seconds
with pipelining_6 0.633037 seconds

我的结果似乎与Redis文档不一致。有人能说明一下造成这些差异的原因吗？

Answer 1

因此，首先，对于一个真正的基准，您应该在剔除异常值之后取您操作的平均值。所有这些操作之间的区别都是以毫秒为单位的，所以如果您只是有一个微小的网络问题，或者在您的盒子上发生了一些奇怪的事情，它就会把数字扔掉。如果你这样做，你的数字可能会看起来不一样。

第二，当您对Redis运行一个操作时，发生的不仅仅是操作成本。与Redis的连接需要与其他相关的启动成本一起进行。数据也需要传输，而且还会有网络来回传输。你所要做的不仅仅是手术的成本，还包括所有这些辅助成本。这些也将是非线性的，因为保存数据的不同格式可能会根据数据大小而使用。总之，主要的观点是zrevrangebyscore是O(log(n)+m)，但在操作中也涉及辅助成本，而且在低操作成本(通常是Redis的情况下)，这些成本与实际操作成本相形见绌。这是件好事。

Answer 2

我相信你误解了大(O)的意思。Big(O)是一种复杂性度量，正如Redis的文档所述，通过保持M不变，您可以放弃它对复杂性的“贡献”(基本上，O(常数)= O(1))。这意味着，如果你比较这样的运算，只要M保持不变，只有N起作用。

然而，这并不意味着性能是相同的。返回6个元素或24个元素不同，因为您正在移动不同数量的数据(不管复杂程度如何)。