0

假设我有一大组坐标

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 设计外部索引是一种选择，就像数据库所做的那样。还有其他想法吗？

4

1 回答 1

2

The first three operations you can be easily solved if you create a hash table with the user_id being the key. This will reduce the complexity of the operations to amortized O(1).

The last operation is a bit ambiguous: what should the method return if there is more than one user in the range? Will it be an array of users? Given your sub-optimal solution, I assume you are interested in all users in the range. This can never be improved in worst case, because the answer itself might be all n users (thus complexity of O(n)).

The act of finding all points within given rectangle is called spatial indexing. One of the most commonly used solutions for such query is the Quad Tree. Still, my note for the worst case scenario holds true for sure, whatever structure you choose to use.

As I mentioned in the comment below, you need not worry for the fact I mention two different structures for implementing the different operations. It is very often that you use more than one representation of the same data set in order to get all operations optimal.

于 2012-11-14T14:46:36.587 回答