Redis+Lua可以实现哈希交集吗？

2013-11-6 0:39:8
收藏：0
阅读：64
评论：1

我有一个用例，需要计算很多集合之间的相似度，以创建一个简单的推荐引擎。我看了一下杰卡德系数和其他相似系数公式，但它们之间有一个共同点：集合内部的项目不能重复（如果我理解不正确，请纠正我）。

我在 PHP 中编写了自己的函数来进行自定义哈希交集，逻辑是：

1.**arr1**：一个数组，其键是项目的 id，值是它们对应的数量。这代表用户的心愿清单。 2. **arr2**：与arr1相同，但它代表另一个用户的库存。 3. 我需要的这个自定义交集的逻辑是心愿清单的所有者不在乎卖家是否有100个item1，如果他只想要4个，那么只计算4个。

我需要一个非常快的方法来相交这些集合，但通常的相似度系数公式涉及集合的相交和并集，在比较一个集合与其他200k个集合时，可能不会像我想的那么快。目前的状态如下：

```function my_similarity_coefficient ($arr1，$arr2) {

$matches = 0;
$total = 0;

如果（count($arr2)==0）
    返回0;

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

    $total += $qty;

    如果！array_key_exists($id，$arr2)
        继续;

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

}

返回$matches / $total;

} ```

我尝试在 PHP 中交集两个红色哈希。它们的大小分别为 arr1[67] 和 arr2[231]。系数在不到61.98微秒（最多266.075微秒）的时间内被计算出来。如果我尝试将数据从Redis传输到PHP，则此数字会膨胀到905.037µsec-3337.86µsec。

我想远离从Redis传输数据到PHP的瓶颈，所以我想知道是否可能在lua（甚至c++）中编写此自定义交集程序，如果可能的话，它是否会遭受与获取数据从点A到点B相同的瓶颈？还是不会遭受获取瓶颈，因为数据已经在本地？

我不熟悉lua，但我不想要完整的代码。因为与我实际想要实现的相关的互联网资源很少，所以在我搜索时我想首先在这里请教一些人。

点赞
用户204011
用户204011

让我们来看一下。首先，这里是将您的 PHP 代码直接翻译为 Lua 的结果。我保留了相同的变量名，但是 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 返回字符串），并将结果转换为字符串，因为如果我们返回浮点数，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)
2013-11-06 10:19:48

作者:

用户504941

用户504941
推荐文章