lua - redis + lua 可能有哈希交集吗？

Question

我有一个用例，我需要计算很多集合之间的相似性以创建一个简单的推荐引擎。我正在查看 Jaccard 系数和其他相似系数公式，但它们之间有一个共同点:集合中的项目不能重复(如果我在这里错了请纠正我)。

我用 PHP 编写了自己的函数来执行自定义哈希交集，其逻辑是:

1. arr1:一个数组，其键是项目的id，值是它们对应的数量。这代表用户的愿望 list 。
2. arr2:与 arr1 相同，但它代表另一个用户的库存。
3. 对于此自定义交集，我需要的逻辑是愿望 list 的所有者不关心卖家是否拥有 100 件商品 1。如果他只想要其中的 4 个，则只计算 4 个。

我需要一种非常快速的方法来对集合进行求交，但通常的相似系数公式涉及集合的求交和并集，当将一个集合与 200k 其他集合进行比较时，这可能没有我想要的那么快。这是我目前所处的位置:

function my_similarity_coefficient ($arr1, $arr2) {

    $matches = 0;
    $total = 0;

    if (count($arr2) == 0)
        return 0;

    foreach ($arr1 as $id => $qty) {

        $total += $qty;

        if (!array_key_exists($id, $arr2))
            continue;

        $matches += min($qty, $arr2[$id]); // do not match more than what user wants

    }

    return $matches / $total;

}

我尝试在 PHP 中将两个红色散列相交。大小分别为 arr1[67] 和 arr2[231]。该系数是在出色的 61.98 微秒(最坏情况下高达 266.075 微秒)下计算得出的。如果我尝试将数据从 Redis 获取到 PHP，这个数字会膨胀到 905.037µsec-3337.86µsec。

我想避免将数据从 redis 传输到 PHP 的瓶颈，所以我想知道是否可以在 lua(或者甚至是 c++)中对这个自定义交集进行编程，如果可能的话，它不会受到影响吗来自相同的瓶颈，因为它也从 pointA 获取它到 pointB，或者它不会遇到获取瓶颈，因为数据已经在它的本地了吗？

我不熟悉 lua，但我不想被灌输精确的代码。由于网上关于lua的资源与我真正想要实现的相关的很少，所以我想先在这里挑几个脑筋，同时搜索。

Answer 1

让我们看看。首先，这是直接翻译成 Lua 的 PHP 代码。我在这里保留了相同的变量名，但是您在 PHP 中称为“Array”的在 Lua 中称为“Table”。

local my_similarity_coefficient = function(arr1, arr2)

  local matches = 0
  local total = 0

  if next(arr2) == nil then
    return 0
  end

  for id, qty in pairs(arr1) do

    total = total + qty

    if arr2[id] then
      matches = matches + math.min(qty, arr2[id])
    end

  end

  return matches / total

end

请注意，如果 arr1 为空，此代码可以除以零，但您的也可以。

让我们试试看:

local arr1 = {
  a = 3,
  b = 5,
  c = 8,
}

local arr2 = {
  a = 2,
  c = 10,
  d = 7,
  e = 21,
}

print(my_similarity_coefficient(arr1, arr2)) -- 0.625

现在让我们使用 Redis。首先，让我们创建测试数据。

redis 127.0.0.1:6379> hmset arr1 a 3 b 5 c 8
OK
redis 127.0.0.1:6379> hmset arr2 a 2 c 10 d 7 e 21
OK

这个脚本做你想做的，不是以最有效的方式(对 redis.call 的调用可能更少)而是以一种简单的方式，所以你可以理解它并在需要时优化它:

local k1, k2 = KEYS[1], KEYS[2]
local matches, total = 0, 0

if not redis.call("exists", k2) then return 0 end

local qty, qty2
for _, id in ipairs(redis.call("hkeys", k1)) do
  qty = tonumber(redis.call("hget", k1, id))
  total = total + qty
  qty2 = tonumber(redis.call("hget", k2, id) or 0)
  matches = matches + math.min(qty, qty2)
end

return tostring(matches / total)

我们称它为:

$ redis-cli eval "$(cat the_script.lua)" 2 arr1 arr2
"0.625"

成功!

需要注意的重点是类型转换:值(数量)使用 tonumber 转换为整数(Redis 返回字符串)，我们将结果转换为字符串，因为如果我们返回一个 float Redis 会将其截断为整数(此处为 0)。

编辑 - 好的，谈论优化而不是说如何不好，所以这是一个简单的:

local k1, k2 = KEYS[1], KEYS[2]
local matches, total = 0, 0

if not redis.call("exists", k2) then return 0 end

local t1 = redis.call("hgetall", k1)

local id, qty, qty2
for i=1,#t1,2 do
  id, qty = t1[i], tonumber(t1[i+1])
  total = total + qty
  qty2 = tonumber(redis.call("hget", k2, id) or 0)
  matches = matches + math.min(qty, qty2)
end

return tostring(matches / total)