Clever Geek Handbook

オフラむンおよびオンラむン2GIS補品での単䞀ルヌティングの䜜成

他の誰かが知らない堎合、 2GISは郜垂地図を持぀組織の無料ディレクトリです。 たた、ディレクトリに぀いお倚くのこずがすでに曞かれおいる堎合、マップずその機胜に関する情報は少なくなりたす。 そしお、䌝えるべきこずがありたす。 たずえば、ルヌティングに぀いお-既存の゜リュヌションを採甚しなかったのに、独自の゜リュヌションを䜜成したのか、さたざたな補品で統䞀された構築アルゎリズムが必芁なのか。









2012幎の初めに、最初に問題が発生したした。以前はデスクトップバヌゞョンで䜿甚されおいた゚ンゞンがリ゜ヌスを必芁ずするため、モバむルデバむスでは䜿甚できたせん。 䜕かをする必芁がありたした。



既補の゜リュヌションを䜜っおみたせんか



ルヌティング゚ンゞンは、実装の埮劙な点で䞍可胜なタスクであるずいう意芋がありたす。 ブヌスト::グラフに入らないかのように、それを撮るべきではありたせん映画は撮圱されおいない、知らないはずです、はい。既補の゜リュヌションを芋぀けるのは簡単です。 おそらく、しかし私たちの堎合はそうではありたせん。



この蚘事からそれが明らかになるこずを願っおいたす-垞識、ちょっずした冒険䞻矩、そしおすべおのための既補のガむドがどんな問題も解決するでしょう。



公平を期すために、グラフでの怜玢〜5,000䞇頂点の経隓がすでにあるこずに泚意する必芁がありたす。



はじめに



  1. サヌバヌバヌゞョンでは、同じコヌドが機胜するはずですが、蚭定は異なりたす。
  2. パスの構築は、劥圓な時間内に携垯電話で機胜するはずです。
  3. アセットには、準備ができた怜蚌枈みの道路グラフがありたす。 既成の゜リュヌションを怜玢しお研ぐよりもはるかに簡単/䟿利/安䟡であるこずがわかりたした。




基本的な そしお、䞀般的な、䞀般的な 原則を瀺したす



  1. ストレヌゞ構造はシンプルでなければなりたせん。
  2. リンクの局所性を刺激するず䟿利です。 デヌタが物理的に近いたずえばグラフの頂点を参照しおいる堎合、可胜であればディスク䞊の近くに配眮する必芁がありたす。
  3. ディスク䞊のグラフ芁玠に䞀床に1぀ず぀アクセスしおはならず、読み取りはバッチでのみ実行されたす。
  4. 䜎レベルのキャッシュはほずんど圹に立たないので、「高䟡な」オブゞェクトのみを凊理する必芁がありたす。 たずえば、ディスクコヌルを盎接キャッシュするのではなく、アルゎリズム的にその数を最小限に抑えるように泚意するこずをお勧めしたす。
  5. グラフ内の怜玢ロゞックは、可胜な堎合は単玔化する必芁がありたす。これは、「パむプラむンが砎損した堎合」C
  6. ディスク䞊のデヌタを圧瞮するのは良いこずです。
  7. パフォヌマンスを優先しお粟床を無芖するこずは非難できたせん。




䞻なアむデア



  1. ラティスに頂点の座暙を眮きたす。 ぀たり 浮動小数点座暙を敎数に倉換したす。 ラティスはかなり粗くするこずができ、頂点が互いにくっ぀くたで、たたはさらに悪いこずに長されロの゚ッゞが圢成されるたで、ステップを増やしたす。 私たちを怜玢するずき、座暙は最終およびデバッグたでの残りの距離を掚定するために必芁であり、栌子がフィニッシュラむンの近くで倧きく増加するず、アルゎリズムは奇劙な動䜜を開始したす。

    グレヌティングが粗いほど、ディスク䞊のデヌタ量が少なくなるため、本圓に必芁な堎合は、繰り返し遞択するこずができたす。 グリッドピッチは1メヌトルです。







    これは、グリッド䞊に怍えられたグラフの断片のようです。
  2. 粟神的にグラフの範囲を、栌子を圢成するいく぀かの長方圢のタむルに分割したす。 この栌子は、ピヌクでその副栌子である必芁はありたせん。
  3. タむルは、ディスクからの同時読み蟌みずキャッシュの察象ずなる論理ナニットです。 これには、すべおの頂点ず出力アヌク぀たり、この頂点が最初の頂点にあるアヌクが含たれたす。 プラス関連情報ある堎合。







    モスクワの道路グラフの断片の䟋による、1぀のタむルに陥る゚ッゞの䟋。
  4. タむルのサむズは、グラフのサむズに基づいお遞択する必芁がありたす。 ディスクから䜕かをロヌドするため、読み取られる情報の合蚈量がディスクバッファのサむズに芋合ったものになるのは劥圓です。 ディスクアクセスの圢匏で重い砲を䜿甚しお、100バむトに収たるいく぀かのピヌクにアクセスするのは奇劙です。 もちろん、グラフは均䞀に配眮されおいたせんが、平均倀をアピヌルできたす。たずえば、グラフはディスク䞊で20 MBを消費したす。 2500 8Kペヌゞ。したがっお、グラフの範囲は50×50の郚分に分割されたすsqrt2500。 ここでは、タむルに関するすべおの情報が1぀の堎所にあるず暗黙的に想定されおいたす。 そうでない堎合は、適切な修正を行う必芁がありたす。
  5. タむルをキャッシュするこずは理にかなっおいたす。
  6. メモリたたはその䞀郚に読み蟌たれるグラフは、倚数の小さなオブゞェクトです。 倧量の小さなオブゞェクトを隔離しお免陀するこずはできたせん。 したがっお、可胜な限りセッションベヌスのペヌゞアロケヌタを䜿甚したす。 これにより、速床ず倧幅に少ないメモリの断片化に加えお、デヌタブロックのプロロヌグず゚ピロヌグ二重ラベルアルゎリズムが節玄されたす。

    ペヌゞアロケヌタは、それに属する固定サむズのペヌゞからメモリを分配し可胜な堎合、必芁に応じおシステムに芁求したす。 デストラクタですべおのメモリのみがすぐに解攟されたす。
  7. タむルには必然的にそのようなアロケヌタヌがあり、ロヌド時に目立぀ものはすべおタむルから取埗され、キャッシュから匷制的に削陀されるずタむルずずもに消滅したす。
  8. ペヌゞアロケヌタヌを䜿甚する別の候補は実際の怜玢です。この方法でグラフの枡された郚分に関する情報を保存するず䟿利です
  9. 実際には怜玢アルゎリズム。 単䞀の「波」で通垞のA *を䜿甚し、移動距離たたは時間ず残りの掚定倀の合蚈の圢匏で頂点倀を掚定したす。
  10. A *-なぜなら 元のダむクストラアルゎリズムず比范しお、通過するピヌクの数を枛らすこずができたす。
  11. 1぀の波で-2぀の理由。 第䞀に、2぀の波を互いに向けお発射するず、グラフの通過郚分が枛りたすが、停止基準が耇雑になりたす。 2぀の波が衝突したかどうかを垞に確認する必芁がありたす。 そしお、これには、動的な䞀連のピヌクの各波のコンテンツ、たたは盎接読み蟌たれたタむルの倉曎が必芁です。
  12. 第二の理由-近づいおくる波の存圚は、䟋えばmental骚に粟神的に到達するたでに亀通状況が倉化するため、rib骚のコストに動的に圱響を䞎えるこずはできたせん。
  13. 䞉角圢の䞍等匏に違反しない限り、残りのパスのコストの掚定倀はどれでもかたいたせん。 たずえば、正盎なナヌクリッド距離たたはチェビシェフ距離を䜿甚できたす。




゜ヌスデヌタ



  1. グラフの頂点-座暙ず識別子を持぀構造
  2. ゚ッゞには、開始頂点ず終了頂点の識別子、長さ、タむプ、および識別子が含たれたす。 すべおのリブは䞀方向です。
  3. 制限-゚ッゞのペア、その間の遷移は䞍可胜です。 制玄は、䞡方の゚ッゞに共通する特定の頂点に関連付けられおいたす。 このようなかなり切り捚おられた制限に぀いお説明したすが、必芁に応じお読者は簡単に䞀般化できたす。




前凊理



  1. グラフの包括的な範囲を芋぀けたす。
  2. 座暙グリッドで決定されたす。
  3. タむルのグリッドを決定したす。 各タむルには識別子が割り圓おられたす。 識別子は、スむヌプ曲線の結果ずしお増加する数倀です。 このような曲線には、氎平スキャンむグルヌ、ヒルベルト曲線、たたはビットむンタヌリヌビング曲線zorderがありたす。 抂しお、タむルがポむントの座暙に該圓するポむントを特定できるこずだけが重芁です。 たた、スむヌプ曲線の遞択は、デヌタの圧瞮胜力にのみ圱響したす。
  4. 各頂点を特定のタむルに割り圓おたす。 同時に、各頂点にタむルのシリアル番号を割り圓おたす。これは圧瞮にも圹立ちたす。
  5. ゚ッゞごずに、どのタむルからどのタむルを取埗するか、および発信ポむントず着信ポむントの内郚番号を決定したす。




ディスクストレヌゞ



デヌタ自䜓はBツリヌに栌玍され、より正確にはその皮類の1぀に栌玍されたす。

デヌタりェアハりスから、䞊べ替えられたN-ok配列を保存し、それらの間隔をすばやく読み取る機胜が必芁です。



抂しお、ストレヌゞの遞択は基本的なものではなく、Bツリヌを遞択したした。



  1. 理解ずデバッグが簡単
  2. 詳现に瞛られるこずなくデヌタを圧瞮できたす
  3. 最も重芁なのは、実装が手元でテストされたこずです。




したがっお、いく぀かのツリヌがありたす。



1. ピヌクのツリヌ。 このツリヌのN-kaは4぀の芁玠で構成されおいたす。







2. rib骚の朚 、圌の鍵は7぀の芁玠で構成されおいたす。







3. 識別子のツリヌ。 倖の䞖界ず通信するのに圹立ちたす。 キヌには5぀の芁玠が含たれたす。







4.長さ4のキヌを持぀制限ツリヌ







思慮深い読者は次のように蚀うでしょう。 1぀のタむルに関するすべおの情報を読み取るには、ツリヌ䞊で3行を実行する必芁がありたす。 すべおをBLOBにたずめお䞀気に持ち䞊げる方が良いのではないでしょうか」読み取り専甚デヌタの堎合は、もちろん、速床ず圧瞮品質の䞡方が優れおいたす。 しかし、これは远加の䜜業であり、远加のテストです。 さらに、プロファむリングは、実際には、方向を怜玢するずきにデヌタの読み取りがボトルネックではないこずを瀺したした。



動的に倉化する可胜性のあるデヌタに぀いお話しおいる堎合、Bツリヌは競合を超えおいたす。 独自のツリヌの実装は必芁ありたせん。SQLストレヌゞを䜿甚でき、䞊蚘の゚ンティティは、1぀の䞻キヌのみで構成されるテヌブルずしお定矩できたす。 したがっお、説明されおいる゚ンゞンの前身の1぀は、テヌブル自䜓がツリヌのように配眮されおいるOpenLink Virtuoso DBMSに基づいお構築されおおり、この堎合、デヌタ自䜓の重耇はありたせんむンデックス内のテヌブルのデヌタの重耇を意味したす。



メモリ内のグラフの衚珟



このセクションでは、アンパックされたグラフがメモリ内でどのように芋えるかを説明したす。



1.メモリ内のグラフ党䜓が存圚しない堎合がありたす。 すでに述べたように、誰かがこのグラフの䞀郚を必芁ずするずきに、タむルにロヌドされたす。



2.したがっお、タむルのキャッシュずこのキャッシュのホルダヌがありたす。 キャッシング戊略は任意です。 このLRULeast Recent Usedがありたす。



3.メモリにロヌドされたタむル-その領域に萜ちたデヌタに関するすべおの情報が含たれたす。 既に述べたように、このためのすべおのメモリは、タむルに属するアロケヌタから割り圓おられ、タむルが消滅するず解攟されたす。 すなわち 



struct vertex_t {int x_; int y_; const link_t*links_; };  ,   ..     .  links_      ,    . struct link_t { int64_tfid_; //    int len_; //  int class_; //  int vert_id_; //   , >0,      union { const vertex_t *vertex_; //         int tile_id_; //    }; const link_t *next_; //   }; struct restriction_t {uint64_t from_; uint64_t to_;};   .         ,   ( )         . ,   .




4.したがっお、メモリ内のタむルは、すぐに䜿甚できるグラフの䞀郚です。







実際に怜玢



1.怜玢を開始する前に、グラフに添付する必芁がありたす。 ぀たり 倖郚では、2セットのポむント-゜ヌスず゚ンドを取埗したす。 各ポむントの説明は、その倖郚グラプッゞ識別子ず倀で構成されたす。 開始点に぀いおこの゚ッゞの開始点に到達するコスト、および終了点に぀いお゚ッゞの終了点から最終点たでのパスのコスト。 だから



2.識別子のツリヌを䜿甚しお、゚ッゞの識別子をグラフの゚ントリポむントに倉換したすconst vertex_t *。 これを行うには、タむルキャッシュホルダヌに連絡しお必芁なものをロヌドする必芁がありたす。

オブゞェクトが必芁です-タむル識別子ず頂点番号を含む、最終に関する情報の保持者。 このオブゞェクトが持぀別の有甚な情報は、フィニッシュラむンの幟䜕孊的䜍眮です。 明瀺的に蚭定できたすが、たずえば、最終ポむントの重心ずしお蚈算できたす。 アルゎリズムAの到達ピヌクのコストの掚定郚分を蚈算するには、この点が必芁です*



3.ここで、「りェヌブ」ホルダヌが必芁です。 次のもので構成されたす。



a。 アロケヌタヌ、たあ、圌なしで。

b。 ロヌドされたタむルのセット。 適切なサむズのグラフの堎合、ビットマスクで十分です。 ぀たり、最初にタむルをヒットしたずきに、このマスクの察応するビットをマヌクし、そのリンクのカりンタヌを増やしたす。 このマスクに焊点を合わせお怜玢を完了した埌、リンクカりントをロヌルバックしたす。 同時に、カりンタヌがれロにリセットされたタむルは、将来キャッシュから飛び出す可胜性がありたす。

c。 優先キュヌ。 バむナリ゜ヌトヒヌプを䜿甚したす。 候補を衚瀺したす。 たずえば、開始点はここからたっすぐ進みたす。 キヌは、移動距離たたは費やされた時間です。 そしお、倀は枡されたポむントの蚘述子ぞのポむンタです

d。 枡されたポむントのセット。 そのような各ポむントは、構造によっお蚘述されたす。 



 struct vertex_ptr_t { int64_t fid_; //   ,      //     0 const vertex_t *ptr_; //      const vertex_ptr_t *prev_; //      size_t cost_len_; //      size_t cost_time_; //      };


もちろん、これらの構造はアロケヌタヌずしお際立っおいたす。



4.したがっお、開始点ごずに蚘述子を䜜成し、ヒヌプに配眮したす。 これで、怜玢を開始する準備が敎いたした。



5.ヒヌプ内に䜕かが存圚する間および、既に芋぀かった候補よりも朜圚的に優れおいる間、その䞭から最も安䟡な芁玠を遞択し、以䞋を実行したす。



a。 発信゚ッゞのリストに沿っお実行し、それぞれに぀いお



I.前の゚ッゞからこの゚ッゞに切り替える可胜性を確認したす。

II。 この゚ッゞが指すグラフの頂点を芋぀ける。 おそらくこれは新しいタむルをロヌドし、このポむントはそこにありたす。

III。この新しいポむントを達成するためのコストを蚈算したす。 これを行うには



  1. 蓄積されたパスず時間を取る
  2. 珟圚の゚ッゞの長さでパスを芁玄したす
  3. 珟圚の長さ、タむプ、その他に応じお、珟圚の時間を克服するために必芁な量だけ時間を増やしたす
  4. 残りのパスの掚定倀を蚈算しお远加したす-absdx+ absdy、ここでdxずdyはそれぞれ経床ず緯床の差です
  5. 残りのパス、時刻、平均速床の掚定倀に基づいお、フィニッシュラむンたでの残り時間の掚定倀を蚈算しお远加したす
  6. 合栌したステヌゞなど




IV。 枡された頂点の蚘述子を䜜成しお塗り぀ぶしたす

V.この点が最終的​​なものではないか確認する

VI。 これがフィニッシュラむンの堎合、前のリストを巻き戻したす

vertex_ptr_t :: prev_ 、このポむントから始たり、0に達するたで、

぀たり 開始したす。 匕き枡しの完成した候補は次のずおりです。

VII。 䜜成された蚘述子をヒヌプに配眮したす



結果



広倧な祖囜の銖郜の道路グラフの䟋で、この行為の結果を評䟡しおみたしょう。











青は最適なルヌトを瀺し、赀は「波」を瀺したす。











前ず同じように、青は最適なルヌトを瀺し、赀は「波」を瀺したす。

怜玢がグラフの実際の、暗黙の階局構造を明らかにし、それを䜿甚し始めた様子を芳察するのは面癜い











合蚈



ご芧のずおり、このような単玔なデヌタ構造ず説明されおいるアルゎリズムにより、通垞のスマヌトフォンで倧郜垂の単䞀レベルのグラフを操䜜できたす。 たた、たずえば、サヌバヌの堎合にRAMがタむルキャッシュのサむズを増やすこずを蚱可する堎合は、グラフ党䜓をメモリに栌玍し、すぐに䜿甚できる衚珟で䜜業したす。 これはパフォヌマンスに有益な効果がありたす。



亀通状況、その予枬、階局グラフを考慮に入れるなど、意図的に特定のポむントに觊れたせんでした。これはたったく別の話です。



それはすべおの人々です


More articles:


All Articles