2

空港から空港への飛行ルートを構築するプロジェクトに取り組んでいます。たとえば、誰かが LAX から JFK に移動したい場合、LAX から JFK までのすべての可能なパス (最大 n 接続) を返したいと思います。私は、再帰 CTE を使用してこの例を MS SQL に変換する作業を行ってきました (ドキュメントの最後の例です): http://publib.boulder.ibm.com/infocenter/iseries/v5r4/index.jsp?topic= %2Fsqlp%2Frbafyrecursivequeries.htm

結果を複製することができました。最初は素晴らしかったです。ただし、約 20 のレコードに対してセット ベースの再帰を実行すると、数十万のレコード (現実世界の直行便) に対して同じタスクを実行するよりもはるかに高速です。

では、私の質問は次のとおりです。ある空港から別の空港への飛行経路を見つけるためのより高速な方法を誰かが見つけ出すのを手伝ってくれませんか? 私は MS SQL と .NET を使用してこのことをゼロから構築していますが、結果をすばやく返すために、ほぼすべてのものを使用することにオープンです (セットベースの再帰、反復 (任意の言語で) など)。

理想的には、Google フライトがデータを返すのと同じくらい早く結果が返されるようにしたいと考えています ( https://www.google.com/flights/ )。

これが、MS SQL の rCTE でこれまでに得たものです。注: ニューヨークからのすべての可能なパスを作成するだけです。ニューヨークからパリへのすべてのフライトに絞り込むには、クエリの最後の行を FROM destinations WHERE arrival = 'Paris' に変更する必要があります。

テスト テーブル FLIGHTS を作成します。

CREATE TABLE FLIGHTS (DEPARTURE nvarchar(20),
                      ARRIVAL nvarchar(20), 
                      CARRIER nvarchar(15),
                      FLIGHT_NUMBER nvarchar(5), 
                      PRICE decimal(18, 0))

テスト テーブルにデータを挿入します。

INSERT INTO FLIGHTS VALUES('New York', 'Paris', 'Atlantic', '234', 400)
INSERT INTO FLIGHTS VALUES('Chicago', 'Miami', 'NA Air', '2334', 300)
INSERT INTO FLIGHTS VALUES('New York', 'London', 'Atlantic', '5473', 350)
INSERT INTO FLIGHTS VALUES('London', 'Athens'  , 'Mediterranean', '247', 340)
INSERT INTO FLIGHTS VALUES('Athens', 'Nicosia' , 'Mediterranean', '2356', 280) 
INSERT INTO FLIGHTS VALUES('Paris', 'Madrid' , 'Euro Air',  '3256', 380)
INSERT INTO FLIGHTS VALUES('Paris', 'Cairo' , 'Euro Air', '63', 480)
INSERT INTO FLIGHTS VALUES('Chicago', 'Frankfurt', 'Atlantic', '37', 480)
INSERT INTO FLIGHTS VALUES('Frankfurt', 'Moscow', 'Asia Air', '2337', 580)
INSERT INTO FLIGHTS VALUES('Frankfurt', 'Beijing', 'Asia Air',  '77', 480) 
INSERT INTO FLIGHTS VALUES('Moscow', 'Tokyo', 'Asia Air', '437', 680)
INSERT INTO FLIGHTS VALUES('Frankfurt', 'Vienna', 'Euro Air', '59', 200)
INSERT INTO FLIGHTS VALUES('Paris', 'Rome', 'Euro Air', '534', 340)
INSERT INTO FLIGHTS VALUES('Miami', 'Lima', 'SA Air', '5234', 530)
INSERT INTO FLIGHTS VALUES('New York', 'Los Angeles', 'NA Air', '84', 330)
INSERT INTO FLIGHTS VALUES('Los Angeles', 'Tokyo', 'Pacific Air', '824', 530)
INSERT INTO FLIGHTS VALUES('Tokyo', 'Hong Kong', 'Asia Air', '94', 330)
INSERT INTO FLIGHTS VALUES('Washington', 'Toronto', 'NA Air', '104', 250)

そして、ここにrCTEがあります：

WITH

destinations (origin, departure, arrival, flight_count, itinerary) AS    
    (
        SELECT a.departure, a.departure, a.arrival, 1, CAST(a.departure + ', ' + a.arrival AS VARCHAR(2000))
                FROM [FLIGHTS] a
                WHERE a.departure = 'New York'
         UNION ALL
         SELECT r.origin, b.departure, b.arrival, r.flight_count + 1, CAST(r.itinerary + ', ' + b.arrival AS VARCHAR(2000))
                FROM destinations r, [FLIGHTS] b
                WHERE r.arrival = b.departure
                -- prevent cycles by making sure the new arrive airport is not already listed in the itinerary
                and CAST(r.itinerary AS VARCHAR(2000)) NOT LIKE '%' + b.arrival + '%'
                -- the itinerary is a csv str so we can limit the number of hops here
                and (LEN(CAST(r.itinerary AS VARCHAR(2000))) - LEN(REPLACE(CAST(r.itinerary AS VARCHAR(2000)), ',', ''))) < 3
    )

SELECT origin, departure, arrival, flight_count, itinerary 
    FROM destinations

助けてくれてありがとう！

4

1 に答える 1

3

ここにあなたのためのいくつかの些細な観察があります：

  1. 適切なインデックスを使用せずにこれを最適化することはできません。つまり、少なくともキーにインデックスを付ける必要があります。
  2. NOT LIKE '%' + b.arrival + '%'高速に動作しません (この種の式のインデックスを作成するのは困難です)。すでにリストされている空港をチェックする別の方法が必要です。たとえば、アイテムを一時テーブルに保存するなどです。
  3. ホップ数を制限する別の方法が必要です。3 つのホップが必要なだけなので、再帰の代わりに 3 つの結合を使用する方がはるかに高速になります。

リストは延々と続く可能性があります。Google フライトと同じ速さで何かを構築するのは簡単ではありません。

于 2012-11-29T03:42:22.740 に答える