天天看點

機票分享第二篇 機票計算過程及時間複雜度(國内篇)

機票搜尋過程:按照請求的條件,取得對應的運價、規則、座位,三者比對并計算出票價,排序選擇優先價格并展示。主要代價花在其中的比對步驟,也是本篇介紹的重點。比對和計算都位于計算層。

一、國内機票單程

1、三層循環做運價*規則*座位的笛卡爾積來實作比對,并計算代理商機票銷售價

機票分享第二篇 機票計算過程及時間複雜度(國内篇)

2、時間複雜度

選取B2C運價(此外還有管道運價、B2B運價)的計算節點為例

機票分享第二篇 機票計算過程及時間複雜度(國内篇)

指定出發、到達下的計算次數 ∝ 運價數*規則數*座位數

運價數 ∝ 代理商總數

規則放大的倍數 ∝ 規則基于機場、航班的細分(不同返點、留錢)程度

座位放大的倍數 ∝ 航班數

二、國内機票往返

1、基于兩個單程結果拼接

機票分享第二篇 機票計算過程及時間複雜度(國内篇)

時間複雜度:拼接步驟所消耗時間占比可忽略不計(由于合并後的結果數量級遠低于合并前),等于單程。

2、基于往返打包運價計算

往返打包運價*往返規則*去程航班*返程航班的笛卡爾積來實作比對,并計算代理商機票銷售價

機票分享第二篇 機票計算過程及時間複雜度(國内篇)

時間複雜度:當打包運價數遠低于單程運價數時,時間占比可忽略;否則為單程複雜度*單個航司下的平均航班數。

3、兩類結果合并後為最終結果

兩類結果可以并行計算,合并消耗時間占比很小

總時間複雜度:與單程相當,或大一個數量級。

繼續閱讀