ruby - 对于一大组坐标，如何快速插入/更新/删除/fetch_by_range到这个集合

Question

假设我有一大组坐标

all_users = [{:user_id=>1,:x=>100,:y=>100}, {:user_id=>2,:x=>120,:y=>120}, ...]

这里有几个操作:

• 插入

  一个玩家上线，报告他当前的坐标

  all_users << {:user_id=>3,:x=>150,:y=>150}

• 通过 user_id 更新坐标

  玩家移动到一个新的坐标

  user = all_users.detect {|u| u[:user_id] == current_user_id }

  user.update :x => new_x, :y => new_y if user

• 按user_id删除

  玩家退出

  all_users.delete_if {|u| u[:user_id] == current_user_id }

• 按坐标范围查找

  找到我周围的用户，+-100 说。

  all_users.select {|u| u[:user_id] != current_user_id && (u[:x] - me[:x]).abs <= 100 && (u[:y] - me[:y]).abs <= 100 }

虽然如您所见，更新/删除/查找操作都是 O(n)，我认为我可以做得更好，也许为 user_id & x & y 设计外部索引是一种选择，就像什么数据库呢。还有其他想法吗？

Answer 1

如果您创建一个以user_id 为键的哈希表，您可以轻松解决前三个操作。这会将操作的复杂性降低到分摊的 O(1)。

最后一个操作有点模棱两可:如果范围内有多个用户，该方法应该返回什么？它会是一组用户吗？鉴于您的次优解决方案，我假设您对该范围内的所有用户都感兴趣。这在最坏的情况下永远无法改进，因为答案本身可能是所有 n 个用户(因此复杂度为 O(n))。

在给定矩形内找到所有点的行为称为空间索引。此类查询最常用的解决方案之一是 Quad Tree .不过，无论您选择使用什么结构，我对最坏情况的说明都适用。

正如我在下面的评论中提到的，您不必担心我提到了两种不同的结构来实现不同的操作。为了使所有操作都达到最佳，您经常使用同一数据集的多种表示形式。