DIV CSS 佈局教程網

用 JavaScript 模擬火車票訂票與退票:二進位位元字串的售票模型
編輯:JavaScript基礎知識     

先前讀過有人分析 12306 後台設計的文章,其中一個觀點讓我印象很深:火車票的銷售邏輯,和一般電商的下單完全不是一回事。

難點在哪裡

最麻煩的地方在於,一張票並不是不可分割的整體。以北京到上海為例,沿途停靠許多站,旅客可以買北京到濟南、濟南到南京、徐州到南京……種種區段。也就是說,同一個座位在不同區段上可以重複賣給不同的人。想用「庫存數量加一減一」這種最直白的做法,是行不通的。

用位元字串描述一張票

網路上看過一個相當漂亮的思路:把一張票表示成一段二進位字串,每一位對應一個行車區段。假如北京到上海一共 10 站,那麼這張票的初始狀態就是:

'1111111111'

1 代表該區段還可賣,0 代表已被佔用。接著看幾個操作:

  • 賣出一張全程票,這張票變成 '0000000000'。
  • 賣出一張北京到濟南的票(第 1 站到第 3 站),票變成 '0011111111'。
  • 再賣出一張徐州到南京的票(第 6 站到第 9 站),同一張票變成 '0011100011'。

退票就是買票的逆向運算

退票時,從票池裡找出第一張「沒辦法賣出這個區段」的票,把它還原回去就好。例如要退徐州到南京,找到上面那張 '0011100011',退票後它又變回 '0011111111'。買票用的是 AND,退票用的是 OR,兩者互為反操作。

為什麼要這麼設計

12306 面臨的是多入口並行、資料必須強一致的環境,查票、買票、退票都得有極致的效率。據說高峰期每秒有二十萬量級的請求,因此票的資料結構是放在記憶體中運算的,而不是每次都回到資料庫。在這種前提下,一個小而精悍的資料結構就顯得格外關鍵——位元運算正好符合這個要求。

參考實作

function Server(){
  var self = this;

  self.ticketsPool = [];

  self._init = function(number){
    if(typeof(number) != 'number')
      throw ('type error');
    for(i=0; i<number; i++){
      self.ticketsPool.push(new Ticket());
    }
  };

  // 判斷一張票是否可以賣出,透過位元運算完成。
  // 訂單 o 為北京-濟南(0011111111),某張票為(0000000011)(已賣出北京-南京),回傳 false
  // 訂單 o 為北京-濟南(0011111111),某張票為(1111100011)(已賣出徐州-南京),回傳 true
  self.canBuy = function(o, t){
    var _o = '';
    for(j=0; j<o.length; j++){
      _o += o[j]=='0' ? 1 : 0;
    }
    var r1 = (parseInt(t.tic,2) | parseInt(o,2)) & parseInt(_o,2);
    var r2 = parseInt(_o,2);
    return r1 == r2;
  };

  // 賣出一張票
  self.pop1Ticket = function(o){
    for(i=0; i < self.ticketsPool.length; i++){
      if(self.canBuy(o, self.ticketsPool[i])){
        self.buy(self.ticketsPool[i], o);
        return i;
      }
    };
    return -1;
  };

  // 賣出票的實作:以 AND 改寫位元字串,例如 '1111111111' -> '0011111111'
  self.buy = function(t, o){
    t.tic = (parseInt(t.tic,2) & parseInt(o,2)).toString(2);
  };

  // 查詢餘票
  self.remainTics = function(o){
    var count = 0;
    for(i=0; i < self.ticketsPool.length; i++){
      count += self.canBuy(o, self.ticketsPool[i]) ? 1 : 0;
    };
    return count;
  };

  // 退票:以 OR 還原區段
  self.refund = function(o){
    for(i=0; i < self.ticketsPool.length; i++){
      if(!self.canBuy(o, self.ticketsPool[i])){
        var _o = '';
        for(j=0; j<o.length; j++){
          _o += o[j]=='0' ? 1 : 0;
        }
        self.ticketsPool[i].tic =
          (parseInt(self.ticketsPool[i].tic,2) | parseInt(_o,2)).toString(2);
        return i;
      }
    };
    return -1;
  };
}

// 資料模型:票
function Ticket(){
  var self = this;
  self.tic = '1111111111'; // 初始為全程票
}

// 資料模型:訂單
function Order(from, to){
  var s = '';
  for(i=0; i<10; i++){
    s += (i>=from && i<to) ? 0 : 1;
  }
  return s;
}

Server = new Server();
Server._init(400); // 初始票池:400 張全程票

這段程式碼的重點不在語法,而在於思維方式:當業務的複雜度來自「區段可重疊」時,把狀態壓縮成位元,再靠位元運算完成比對,往往比直覺的計數器方案乾淨得多。當然,這只是教學用的簡化模型,真正的售票系統還要處理座位選擇、連線併發、異步一致性等一大堆問題。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved