代码之家 › 专栏 › 技术社区 › Gdeglin

通过连接表查找相似用户的算法

algorithm ruby sql

4

Gdeglin · 技术社区 · 16 年前

我有一个应用程序,用户可以从大约300种可能的兴趣中选择多种兴趣。每个选定的兴趣都存储在一个包含列user\u id和interest\u id的联接表中。

典型的用户会从300种兴趣中选择50种左右。

我想建立一个系统,用户可以找到前20名的用户有最共同的兴趣与他们。

SELECT i2.user_id, count(i2.interest_id) AS count 
  FROM interests_users as i1, interests_users as i2
    WHERE i1.interest_id = i2.interest_id AND i1.user_id = 35
  GROUP BY i2.user_id
  ORDER BY count DESC LIMIT 20;

但是,对于连接表中的10000个用户和500000行,执行此查询大约需要500毫秒。所有索引和数据库配置设置都已尽我所能进行了优化。

我还尝试使用以下查询避免使用连接:

select user_id,count(interest_id) count
  from interests_users
    where interest_id in (13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,508)
  group by user_id 
  order by count desc 
  limit 20;

我曾考虑过将这些数据放入Neo4j这样的图形数据库,但我不确定这是不是最简单的解决方案,或者它是否比我目前所做的还要快。

4 回复 | 直到 16 年前

1

Marc-André Lafortune 16 年前

您作为答案发布的代码不正确。通过将计数存储在散列中,您将忘记许多用户,因为每个总数只保留一个用户。例如,如果两个用户具有相同的兴趣(或者至少与当前用户具有相同数量的匹配兴趣),则 t 变量将是相同的,第一个变量将被第二个变量覆盖。

true 和 false 而不是 1 0 .

USERS_COUNT = 10_000
INTERESTS_COUNT = 500

users = Array.new(USERS_COUNT) { rand(100000)+100000 }

table = Array.new(INTERESTS_COUNT) do
  Array.new(USERS_COUNT) { rand(10) == 0 }
end

s = Time.now
cur_user = 0
cur_interests = table.each_index.select{|i| table[i][cur_user]}

scores = Array.new(USERS_COUNT) do |user|
  nb_match = cur_interests.count{|i| table[i][user] }
  [nb_match, users[user]]
end

scores.sort!

puts Time.now.to_f - s.to_f

顺便说一句,你可以通过调换 table

2

1

Matthieu M. 16 年前

你所说的叫做集群。

集群是一个困难的问题,动态计算它需要的资源恐怕比我们希望的要多,因为一个完整的计算是O(N) ²

但是,我可以找出如何缓存结果!

UserId*  |  LinkedUserId*  |  Count
35       |  135            |  47
35       |  192            |  26

(一个索引用于UserId,另一个索引用于LinkedUserId,unicity的限制是不应该有两行具有相同的UserId/LinkedUserId对)

无论何时需要获取此用户的组,请首先查阅缓存表。

现在,我们还需要不时地使一些缓存条目无效:每次用户添加或删除一个兴趣,那么它就可能影响所有链接到她的用户。

老实说,我不确定它会表现得更好。

3

1

Theofanis Pantelides 16 年前

SELECT DISTINCT TOP 20 b.user_id, SUM(1) OVER (PARTITION BY b.user_id) AS match
  FROM interests_users a
  LEFT OUTER JOIN interests_users b ON a.interest_id = b.interest_id AND b.user_id <> 35
 WHERE a.user_id = 35 AND b.user_id IS NOT NULL
 ORDER BY 2 DESC

如果你建立了很好的索引,你应该很好。

4

1

Gdeglin 16 年前

首先,我创建一个二维数组,其中每列是一个用户,每行是一个兴趣点。数组中的每个值都是0或1,具体取决于当前用户是否感兴趣。此数组存储在内存中,并带有用于添加或修改行和列的函数。

然后,当我想计算与当前用户兴趣相似的用户时,我将当前用户的列设置为“1”的每一行的所有列相加。这意味着我需要遍历10000列,平均每列运行50个加法操作,最后执行排序操作。

您可能会猜到这需要很长时间,但实际上在我的机器上大约需要50-70毫秒(core2duo,3ghz)。Ruby 1.9.1),在我们的生产服务器上大约110毫秒。好在我甚至不需要限制结果集。

USERS_COUNT = 10_000
INTERESTS_COUNT = 500

users = []
0.upto(USERS_COUNT) { |u| users[u] = rand(100000)+100000 }

a = []
0.upto(INTERESTS_COUNT) do |r|
  a[r] = []
  0.upto(USERS_COUNT) do |c|
    if rand(10) == 0 # 10% chance of picking an interest
      a[r][c] = 1
    else
      a[r][c] = 0
    end
  end  
end

s = Time.now

countable_rows = []

a.each_index { |i| countable_rows << i unless a[i][0].zero? }

b = {}
0.upto(USERS_COUNT) do |c|
  t = 0
  countable_rows.each { |r| t+= a[r][c] }
  b[t] = users[c]
end
b = b.sort {|x,y| y[0] <=> x[0] }

puts Time.now.to_f - s.to_f

前几行用于创建模拟的二维阵列。程序的其余部分运行我上面描述的算法。

上述算法在一段时间内可以很好地扩展。显然,它不适合50000多个用户,但是由于我们的产品将社区划分为更小的组,这种方法工作得非常好(而且比SQL快得多)。

任何关于如何调整它以获得更好性能的建议都是欢迎的。