algorithm - 大規模プロジェクトのスペースの複雑さに近づく

Question

スタートアップでこの質問をされた

Bing Mapsのようなマップを設計するように求められた場合、スペースの複雑さをどのように見積もりますか？

地図について考えられる唯一の答えは、スペースは一定でしたが、正しい方向に進んだかどうかはよくわかりませんでした。

そのような質問にどのようにアプローチするのですか？

Answer 1

マップサービスの詳細を確認すると、いくつかのレイヤーがあることがわかります。各レイヤーについて、ソースデータの解像度と、それらがカバーする領域に基づいてサイズを見積もることができます。

size = sum(foreach layer: layer.area * (layer.resolution)^2 * layer.elementsize)

衛星画像は、基本的な解像度レベルで世界中をカバーする必要があるため、計算が最も簡単です。ただし、航空写真など、関心のある領域に焦点を当てたソース資料が期待できます。これらはおそらくより高い解像度になりますが、総面積は小さくなります。

ズームアウトされた表示を便利に提供するために、フル解像度データの縮小バージョンを保存することをお勧めします。ただし、これは、フル解像度データに必要なスペースのごく一部を占めるにすぎません。画像サイズを2分の1に縮小すると、追加データのサイズが4分の1に縮小されます。2倍の画像ピラミッドの追加サイズは、フル解像度データの1/3になります。

最後に、道路、地理的地域、関心のあるポイントなどの地理情報も必要になります。このデータのサイズは当然非常に弾力性がありますが、特定の都市の商業地理データベースのサイズを評価し、人口ごとにスケーリングすることで、ある種の大まかな見積もりを得ることができます。

Answer 2

ズーム0（惑星全体が見える場所）で地図を見て、地図がX画像に分割されているとしましょう。

次に、1にズームすると、現在の領域を表示するための同じX画像が作成されますが、これはマップの一部にすぎません。惑星全体を「カバー」するには、ズーム1でYパーツを表示する必要があるとします。これは、X*Y画像を表示する必要があることを意味します。Bing Mapsには約21のズームレベルがあるため、X * 1 + X * Y + X * Y ^ 2 + ... + X * Y ^ 21 = X *（1 + Y + Y ^2+。。 。+Y^ 21）そしてこの結果はO（X * Y ^ 21）を推定します。

さらに、住所、道路、交通状況を説明するために必要なデータを考慮する必要があります。これは、いくつかの統計データを使用して、おおよそ計算できます。