范围信息的简单表示和计算在本文中，笔者基于12306余票查询问题的需求和启发，提出了一种对范围数据进行转换和处理的技术方
概述
如果笔者是标题党，这篇文章的标题应该是这样的： 《12306的余票查询世纪难题，被我解决了！！》。
笔者还没有自大到这个程度。本文其实只是主要提出了一种用于高效进行范围干涉计算的技术方案，可能有机会并运用到如铁路售票的余票检查和管理的应用场景当中。实际的数据库实现和结构，也是笔者自己构想的，也许就算12306要参考实现，也会受到很多的限制，并需要进行很多调整。
但是，无论是否适合12306的应用场景，本文讨论的内容其实具有一定的普遍性和通用性，应当不妨碍给系统开发者一些有用的信息和启示，让他们考虑可以运用相关的知识和技术，来解决实际业务和工作中遇到的问题。
在讨论12306的解决方案之前，笔者想要先从一个技术化的概念，就是从“范围”(Range)开始。它是一种典型的数据和信息组织的方式。常见的使用场景包括一天中的温度变化，价格波动，还有就是列车运行的区间都可以用范围的形式进行表示。在信息处理方面，就可以围绕着范围的信息和数据进行相关的处理和分析。笔者称其为范围计算。
但再深入思考一下，就可以发现，虽然都是范围，但其实它们还是有很大的不同的(从数据处理的角度)。大致可以分为数值范围和数组范围。比如温度变化的范围，它是一个连续的区域，可能需要两个数值(浮点数)来表示这个范围。而列车运行的区间，它虽然也可以用两个整数(线路中站点的序号)来表示，但实际上这个范围，是一个连续的、有序的、离散的，可以使用数组来表示，可能更容易处理。
为了简化讨论，特别是针对列车运行的站点区间这个场景，我们在本文中只讨论后者，就是范围计算的一个子集或者特例：数组的片段和范围计算。
实例和需求
为了更好的表述和说明这个问题，笔者想结合一个实际用例进行展开。
前面已经简单提到，这种模式的一个经典的用例，就是列车运行的站点区间的计算。为什么要进行这个计算，当然是为了解决一个实际的问题，就是更好的进行分区间的座次和车票的销售。大家都坐过火车，就知道，一趟列车的运行过程，是由很多列车在一系列车站中运行的区间构成的。一个特定的座次(铺位)，由于旅客实际上可能只需要在区间中使用，其实是可以“重复”销售的。这样，通过合理的规划区间和销售，就可以使列车的运力充分的利用，提高运营的经济效益。
在没有信息系统的日子里，这种处理是由人工或者简单的计划来实现的。一种简单粗暴的方式，就是在计划和销售的时候，给特定的车站(通常是大站)预留一些座位(甚至是为了方便管理，预留整个车厢)来进行销售，那个车站的旅客可以购买从那个车站开始的运行区间。还有一种方式是由列车长在车上才进行处理，就是一个旅客在运行中间车站下车之后，列车长现场销售空出来的坐席和后续区间的车票。这些处理模式，本质上是因为信息的不完整和不通畅而造成的，而在有了信息计算之后，通过快速的统计和查询，可以在销售的时候实时确定，从而在管理上更加精细和高效。
我们下面来以一个具体的实例来展开说明，并做一些初始的设定。这里是一趟由福田开往北京西的G336次列车的运行时刻表：
| 序号 | 编码 | 车站 | 时刻 |
|---|---|---|---|
| 1 | NZQ | 福田 | 400 |
| 2 | IZQ | 广州南 | 38 |
| 3 | IIQ | 英德西 | 78 |
| 4 | SNQ | 韶关 | 100 |
| 5 | ICQ | 郴州西 | 133 |
| 6 | ZAQ | 株洲西 | 191 |
| 7 | CWQ | 长沙南 | 210 |
| 8 | MQQ | 汨罗东 | 242 |
| 9 | YIQ | 岳阳东 | 267 |
| 10 | WHN | 武汉 | 320 |
| 11 | OYN | 信阳东 | 368 |
| 12 | MDN | 明港东 | 387 |
| 13 | ZLN | 驻马店西 | 406 |
| 14 | LBN | 漯河西 | 430 |
| 15 | ZAF | 郑州东 | 472 |
| 16 | EGF | 新乡东 | 498 |
| 17 | HPP | 邯郸东 | 538 |
| 18 | EDP | 邢台东 | 556 |
| 19 | SJP | 石家庄 | 601 |
| 20 | BXP | 北京西 | 678 |
如何表达这个列车的运行区间呢？简单的方式，可以使用一个车站编码的数组，而且，如果只分析区间，其实是可以不需要时刻信息的，只保留序列就可以了。这样，这个车次的运行区间就可以这样表达：
"NZQ,IZQ,IIQ,SNQ,ICQ,ZAQ,CWQ,MQQ,YIQ,WHN,OYN,MDN,ZLN,LBN,ZAF,EGF,HPP,EDP,SJP,BXP".split(",");
[
'NZQ', 'IZQ', 'IIQ', 'SNQ',
'ICQ', 'ZAQ', 'CWQ', 'MQQ',
'YIQ', 'WHN', 'OYN', 'MDN',
'ZLN', 'LBN', 'ZAF', 'EGF',
'HPP', 'EDP', 'SJP', 'BXP'
]
为了方便编辑，我们使用一个字符串，并很容易的就可以将其转换为一个数组来表示。
然后，一个旅客A，购买了一张车票，坐席是A1，区间是从“福田”到“武汉”，当然可以使用两个代码来表示，但实际上我们更关心他在这趟列车中的区间，参考时刻表倒查车站的序号，我们就可以表示成为：1-10 (两个整数，表示从第一站到第十站)。
我们的问题是，如果另一个旅客B，需要从长沙到北京，是否可以将同样的座位销售给他呢？ 或者如果他是从郑州到北京呢？作为人类，有了这个时刻表，这个问题当然可以很快的得到这个答案。从长沙到北京，旅客B上车时，显然旅客A还在车上(到武汉才下)，所以无法将A1坐席销售给B；而从郑州到北京，上车时座位已经空出来了(旅客A已经在武汉下车)，就可以进行销售。
这样，我们就有了基本的设定和需求，下面就可以来探讨，如何使用程序进行处理。
程序化解决方案
为了简化问题，我们先假设只有一个座次，那么输入的信息就是这个车次的运行区间，和一系列旅客旅行的区间，输出是检查这些旅客的区间是否冲突，这个信息将用于决定是否可以将这个座次销售给后来的旅客。在前面的问题中，如果用序号来表示，长沙到北京就是7-20，武汉到北京就是15-20。用范围检查，显然前者和1-10冲突(7-10重叠了)，而后者不冲突。
这个数字化的思维过程明确之后，就可以考虑将其程序化了。我们首先比较容易想到的，有以下几种解决方案。
数值对比
要将上面的范围冲突检查判断，转换为数值比较的话，可以使用下面的方式。
在经典和一般的编程语义中，是没有“范围(Range)”这种数据结构的，只能用已经存在的数据结构比如结构体来表示。这里使用一个对象，来表示起点和终点。这样，所谓的A和B两个范围有冲突，就是A的最小值，如果比B的最小值小，那么A的最大值，应该比B的最小值要大，否则(就是如果A的最小值比B的最小值大的话)，B的最小值，应该小于A的最大值。
根据上述构想，实现的参考数据和测试代码如下：
let
A = { start: 1, end: 10},
B = { start: 7, end: 20},
C = { start: 15, end: 20};
D = { start: 10, end: 15};
const vcheck = (range1,range2)=>(range1.start < range2.start) ? range1.end > range2.start : vcheck(range2, range1);
const check = ()=>{
// A vs B
console.log("A vs B", vcheck(A,B)); // true
console.log("B vs A", vcheck(B,A));
// A vs C
console.log("A vs C", vcheck(A,C)); // false
console.log("C vs A", vcheck(C,A));
// A vs D
console.log("A vs D", vcheck(A,D)); // false
console.log("D vs A", vcheck(D,A));
}; check();
在定义好范围的对象结构后，编写检查代码非常简单，就是做两个判断而已。
数组比较
前面我们已经提到，列车的车站序列，可以使用一个数组来表示。同样的，一个旅行区间，也可以使用一个数组来表示。这样，区间和范围的冲突，就可以转换成为数组交集检查的计算。根据这一思维方式，实现的测试代码如下：
let
ALL = "NZQ,IZQ,IIQ,SNQ,ICQ,ZAQ,CWQ,MQQ,YIQ,WHN,OYN,MDN,ZLN,LBN,ZAF,EGF,HPP,EDP,SJP,BXP".split(","),
A = ALL.slice(0,9),
B = ALL.slice(6,19),
C = ALL.slice(14,19),
D = ALL.slice(9,14);
const acheck = (arr1, arr2)=> arr1.some(v => arr2.includes(v));
const check = ()=>{
console.log("A vs B", acheck(A,B)); // true
console.log("A vs C", acheck(A,C)); // false
console.log("A vs D", acheck(A,D)); // false
}; check();
由于旅客区间都是车次区间的严格子序列，内部的元素和次序都是严格相同的，所以只需要检查两个数组是否有相同的元素即可。
数组转化数值比较
前面的两种方式，特别是数组的方法，都需要进行一些数值比较的操作，稍显麻烦。其实仔细思考一下，我们会发现其实我们并不关心在数组中的车站的代码，其实关心的是代码在区间中的序号和整个区间之间的关系。笔者就想到可以使用位图和相关的操作来进行处理，这部分内容较多，其实也是本文的核心和重要内容，笔者在下面专门的章节中展开讨论。
范围转化为数值
还是以前面的数据为例，在去除了编码之后，我们可以使用下面数组的方式，来表达旅行区间的信息，更加抽象(和车次和车站完全无关)和直观：
// 当前车次 完整20站
"####################"
// 福田-武汉
"##########XXXXXXXXXXX"
// 长沙-北京
"XXXXXX##############"
// 郑州-北京
"XXXXXXXXXXXXXX#####"
进一步可以发现，这就是典型的位图的方式，因为数组中只有两个类型的数据，完全可以使用二进制字符串来表示，而二进制字符串也可以简单的转化为一个数组。也就是说，其实我们可以使用一个整数，来表达区间的信息。
笔者先例举相关的代码示例，然后进行分析和说明：
const
SLENGTH = 24,
rangeInt = (istart, iend, ilen = iend)=> {
// start
let iresult = 1 << (istart-1);
for(let i = istart; i < iend; i++) iresult += (1 << i);
return iresult;
},
intRange = (ivalue)=> {
if (ivalue <=0 ) return [0,0];
let istart =1, iend = 0;
do {
iend++;
if ((ivalue & 1) == 0) istart++;
} while(ivalue >>= 1);
return [istart, iend];
},
blength = (ivalue)=>{
let ilen = 0;
do { if (ivalue & 1) ilen++ } while(ivalue >>=1);
return ilen;
};;
const doTest = ()=>{
let i1 = rangeInt(2,5,SLENGTH);
let i2 = rangeInt(3,6,SLENGTH);
let i3 = rangeInt(6,7,SLENGTH);
console.log("i1, 2 - 5:",i1, i1.toString(2).padStart(SLENGTH,"0"));
// should be 30 000000000000000000011110
console.log("i2, 3 - 6:",i2, i2.toString(2).padStart(SLENGTH,"0"));
// should be 60 000000000000000000111100
console.log("i3, 6 - 7:",i3, i3.toString(2).padStart(SLENGTH,"0"));
// should be 96 000000000000000001100000
console.log("i1 & i2", i1 & i2);
// i1 & i2 28
console.log("i2 & i3", i2 & i3);
// i2 & i3 32
console.log("i1 & i3", i1 & i3);
// i1 & i3 0
console.log("Range: ", i1, intRange(i1)); // [2,5]
console.log("Range: ", i2, intRange(i2)); // [3,6]
console.log("Range: ", i3, intRange(i3)); // [6,7]
}
在这段代码中，笔者定义了两个函数，可以将一个范围(起点和终点序号，从1开始)转换成为一个整数，以及反向操作。例如，从第二站广州，到第五站郴州，就可以表示为30。
需要注意的是，在本示例中，起点的记录是从低位开始的，这一可以有效利用整数的位进行操作和存储。要转成完整的字符串形式，也比较简单，在左侧加零补全即可。
在将区间范围转换成为数字之后，要进行两个区间的冲突检查，就可以使用整数的与(&)计算，大于零，就表示有区间冲突(两个整数的二进制表达有重叠的部分)，同时这个计算结果，其实还能得到冲突的范围大小(位上为1的长度，可以使用blength计算)。
经过上面的讨论，我们就可以知晓，是可以将一个范围，通过位图的形式，表达成为一个正整数字的；反之亦可。然后，可以使用简单的数字的与计算，就可以检查其所代表的范围是否冲突，而且由于简单的使用位运算，可以保证这些操作的效率。
Postgres中的操作
前面的工作，已经为具体问题的解决打下了一个很好的基础。让我们将相关的工作，搬到数据库系统之中，来支持更加现实的应用开发。
Postgres函数实现
我们先使用文中前面的相同的方式，先定义相关的操作方法，几乎完全照搬JS的定义和实现过程。
-- 范围转整数函数
CREATE FUNCTION
x_rangeInt(istart INT, iend INT)
RETURNS INT AS $$
DECLARE
iresult INT;
iloop INT;
BEGIN
IF (istart =0 or iend =0) THEN
return 0;
END IF;
iloop = istart;
iresult := 1 << (istart-1);
WHILE iloop < iend LOOP
iresult := iresult + (1 << iloop);
iloop := iloop + 1;
END LOOP;
return iresult;
END;
$$ LANGUAGE plpgsql;
-- 检查功能和数据
defaultdb=> select x_rangeInt(3,5) & x_rangeInt(4,10);
?column?
----------
24
(1 row)
类似的，可以实现上述转换的的逆操作，但基于使用简便的考虑，定义了两个函数，分别获取范围的起始和结束数值。
-- 起始序号
CREATE FUNCTION x_intRange_start(irange INT)
RETURNS INT AS $$
DECLARE
iloop INT;
istart INT := 1;
-- iend INT := 0;
BEGIN
IF (irange <= 0) THEN
RETURN 0;
END IF;
iloop = irange;
WHILE iloop > 0 LOOP
IF (iloop & 1) = 0 THEN
istart = istart + 1;
END IF;
iloop = iloop >> 1;
END LOOP;
return istart;
END;
$$ LANGUAGE plpgsql;
-- 结束序号
CREATE FUNCTION x_intRange_end(irange INT)
RETURNS INT AS $$
DECLARE
iloop INT;
iend INT := 0;
BEGIN
IF (irange <= 0) THEN
RETURN 0;
END IF;
iloop = irange;
WHILE iloop > 0 LOOP
iend = iend+1;
iloop = iloop >> 1;
END LOOP;
return iend;
END;
$$ LANGUAGE plpgsql;
-- 测试执行
defaultdb=> select x_intRange_start(30) || '-' || x_intRange_end(30);
?column?
----------
2-5
(1 row)
在实现了范围数值转换的相关函数，就可以方便的基于数据库中的信息和数据，进行范围相关的操作和查询，特别是干涉性检查了。而且基于其运行和实现的原理，它可以在数据库内部执行，并且非常高效。
Postgres Range类型应用
前面讨论的内容，都是基于使用整数来表示范围的解决方法。Postgres中，也原生支持了Range数据类型，从功能上也能够解决类似的需求。
针对以上的问题，其基本方式和过程是，先将所有的已预定的坐席，对应的发到站转换成为一个序号的范围，作为一个数据库字段保存这个范围；然后如果有新的预定请求，则需要使用其发到站范围，在已有记录中进行包含性搜索，不能匹配的坐席记录，就可以作为可销售的坐席(余票)了。
这里使用的Postgres技术主要包括Range的数据类型， int4range数据范围构造函数，和 包含计算(@>)操作符，这些都是Postgres系统原生提供的。后面有更详细的代码和示例说明。
使用Range数据类型的处理更加直观和方便，但受到数据库技术支持条件的限制。而使用整数来表示和操作，通用性更好，理论上可以适用于任意的数据库系统。
余票检查的用例和流程
上面两种表达和操作区间信息的技术方案，应该都可以很好的运用到铁路客票的销售过程当中的余票和状态检查操作当中。基本的构想如下(以单个车次的坐席为例)：
- 在发售前，产生车次的基本坐席数据，包括车次日期，坐席编号，类型，状态，始到站信息(0)，订单编号等信息
- 旅客购票的时候，根据购票的车次日期、始到站和类型等信息，搜索可用的坐席，并进行选择和锁定
- 另一个旅客进行购票的时候，就可以基于区间冲突检查的策略，查找可用的坐席
- 购票系统优先选择和呈现已有订票的坐席给新的区间不冲突的购票申请
- 购票系统也可以根据区间快速查询和统计可用销售的客票数量
- 购票订单确认后，如果当前坐席是初始状态，则直接更新当前坐席记录数据
- 如果坐席已销售，但可以销售更多区间，则增加一条坐席+新区间的记录
- 坐席记录的区间字段，都由确定后的区间范围转换而来，同理，也可以反向转换查找对应的车站
在这个流程中，核心的区间数据和状态的查询问题都已经解决了，也没有现实的应用需求，上面的思想流程和实验应该已经能够说明问题，笔者就不再做具体的数据库设计和测试实现了。这里只做一个简单的数据库实现的核心操作和代码的展示：
defaultdb=> with
O( seat, istart, iend, status ) as (values
('A1', 2,5, 1),
('A2', 0,0, 0),
('A3', 5,6, 1)),
O1 as (select seat, int4range(istart, iend) trange , x_rangeint(istart,iend) irange, status from O)
select 'range ',* from O1 where not O1.trange::int4range @> int4range(2,3)
union all
select 'interge', * from O1 where irange & x_rangeint(2,3) = 0;
?column? | seat | trange | irange | status
----------+------+--------+--------+--------
range | A2 | empty | 0 | 0
range | A3 | [5,6) | 48 | 1
interge | A2 | empty | 0 | 0
interge | A3 | [5,6) | 48 | 1
(4 rows)
代码中先构造了三个坐席和状态的数据，其中两个都已经有旅客购买。然后如果有另外一个旅客，基于其购票意向2~3，可以在当前的记录中，检查可以预定和使用的坐席。代码中展示了分别由Postgres Range类型和范围整数实现的余票和可用座位的查询方式。这里范围整数的操作，使用了前面定义的x_rangeint方法，它可以将一个车次区间，转换称为一个整数用于后续的可用空位查询。
其他相关信息，欢迎访问笔者的另一个博客系列，起始文章是：
小结
在本文中，笔者基于12306余票查询问题的需求和启发，提出了一种对范围数据进行转换和处理的技术方案，并提出了相关的处理方法和代码，以及相关的应用分析。
转载自:https://juejin.cn/post/7408462655944474635