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 の外部インデックスを設計することもオプションの 1 つかもしれません。他の考えはありますか？

4

1 に答える 1

2

最初の 3 つの操作は、 をキーにしてハッシュ テーブルを作成すると簡単に解決できますuser_id。これにより、操作の複雑さが amortized に軽減されO(1)ます。

最後の操作は少しあいまいです: 範囲内に複数のユーザーがいる場合、メソッドは何を返す必要がありますか? ユーザーの配列になりますか？準最適なソリューションを考えると、範囲内のすべてのユーザーに関心があると思います。回答自体がすべてのユーザーである可能性があるため、最悪の場合、これを改善することはできませんn(したがって の複雑さO(n))。

与えられた四角形内のすべての点を見つける行為は、空間インデックス付けと呼ばれます。このようなクエリで最も一般的に使用されるソリューションの 1 つはQuad Treeです。それでも、最悪のシナリオに対する私のメモは、どのような構造を使用する場合でも、確かに当てはまります。

以下のコメントで述べたように、異なる操作を実装するための 2 つの異なる構造について言及しているという事実について心配する必要はありません。すべての操作を最適化するために、同じデータ セットの複数の表現を使用することがよくあります。

于 2012-11-14T14:46:36.587 に答える