哈希交叉可能与redis + lua？

Question

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

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

1. arr1:一个数组,其中键是项的ID,值是它们对应的数量.这代表用户的愿望清单.
2. arr2:是相同的,arr1但它代表另一个用户的库存.
3. 我需要这个自定义交集的逻辑是,愿望清单的所有者不关心卖家是否有100个item1.如果他只想要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μsec(最差时高达266.075μsec)下计算.如果我试图从Redis获取数据到PHP,这个数字可以达到905.037μsec-3337.86μsec.

我想保持瓶颈不会将数据从redis传输到PHP,所以我想知道是否可以在lua(或者甚至是c ++)中编写这个自定义交集,如果可能的话,它是否会受到同样的影响瓶颈,因为它也从pointA到pointB获取它,或者它不会受到获取瓶颈,因为数据已经是本地的？

我不熟悉lua,但我不打算用精确的代码填充勺子.由于互联网上的lua资源与我实际想要实现的内容相关很少,我想在我搜索时首先选择一些大脑.

Answer 1

让我们来看看.首先,这是您的PHP代码直接转换为Lua.我在这里保留了相同的变量名称,但在PHP中称为"Array"的行在Lua中称为"表".

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返回字符串),我们将结果转换为字符串,因为如果我们返回浮点数,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)