座位优化有多难？难于上青天？ - 未名空间MITBBS历史存档

座位优化有多难？难于上青天？# Programming - 葵花宝典

T*r2014-02-07 08:02

1 楼

tl 原文
http://www.teamliquid.net/forum/viewmessage.php?topic_id=164267
附我的rep
http://www.megaupload.com/?d=AVNUUFTL
被骚了，但是最后对a的时候人口差不多。主要想知道要造什么组合，特别是在我已经
造了一些飞龙的情
况下。当然，我最后没有高magic box 是个失误，是不是应该搞多一些飞龙和毒爆，还
是用roach +
hydra？

f*k2014-02-07 08:02

2 楼

有些电影，周围的人都没看过或者不喜欢，没有人可以交流，发在这个版上又肯定被人
骂装@#%￥%。
我先开个头吧：
所有看过的电影里，我最喜欢的就是《the big lebowski》，Jeff Bridges演的。看了
没有50遍
也有40遍了，台词都背下来了。
不知道为什么喜欢，就是喜欢那个调调，90年代初的美国就是那个样子么？好想永远回
到那个年代。

h*o2014-02-07 08:02

3 楼

1.免费的100刀 Chase SapphireSM Card 只需消费一笔无年费-- 年度最受欢迎信用卡
http://bankingbonus.spaces.live.com/blog/
最近申请chase家的这个信用卡会弹出一个页面，写着Before you go…We hope you
will reconsider 难不成他们家最近被人拿太多这个100刀了！不用对它客气，赶
紧点击Return&Apply，拿到落袋为安。
2.免费的250刀 Chase SapphireSM Preferred Card 需要满足这个offer的条件
http://bankingbonus.spaces.live.com/blog/
3.免费的12000mile from Miles Card by Discover
http://bankingbonus.spaces.live.com/blog/cns!E581C466612AE7F!305.entry
首个礼品卡 drugstore.com giftcard code 7c49792fdf251(已用) 7v93d5dcd

t*12014-02-07 08:02

4 楼

下面是好虫的要求：
举个例子，就是假定当前所有票的线段数是N（连着的算一段)，一个request进来，要
满足分配之后N'最小。其次，在N'一样的前提下，要从一个长度最短的线段里取。线段
长度一样可以任取一个。
这是一个全局搜索算法的问题。复杂度至少O(n)，n是总座位数。
好虫的要求是20个区段，每个区段每个等级车票1000个座位。那是什么概念呢？就是每
次要考虑20X1000个全局座位的优化。
最难的是有时间要求。比如我赌气地提出1MM出票每秒。好虫竟然还不乐意，妄图无耻
地讨价还价为1MM transaction每秒。
现在就假定我们只优化一个座位。假定有上帝之手帮你优化好了，用的是全体平行宇宙
的超级量子计算机。用时为0。结果返回到一个数据结构如下：
struct SeatRank {
public:
short _seatNum;
short _rank;
};
_rank表示座位的优化等级，越高，则表示此座位越应该采用。
你要做的就是把1000个座位扫描一遍，找到一个优化等级最高的采用：
SeatRank seats[1000];
int bestIndex = 0;
short bestRank = seats[0]._rank;
for (int j=1; j<1000; j++) {
short curRank = seats[j]._rank;
if (curRank > bestRank) {
bestRank = curRank;
bestIndex = j;
}
}
这个过程要多久呢？在我的2.9G Sandy Bridge Server上，gcc -O3编译，循环100万次
要超过0.9s。
也就是说，你啥都不干，假定结果都算好了，你光扫描一遍找一个最好的，出票1MM每
秒都勉强。
所以说，迄今各位提出来的算法都不可能达到1MM/s的出票。
这不是他妈的根本不可能么？跟各位说实话，我觉得我还有很大机会。玩极限才刺激么！
可惜，再讨论下去，总会有无聊的人来影响我的兴致。

m*d2014-02-07 08:02

5 楼

空投自爆毁灭MM。。。

s*a2014-02-07 08:02

6 楼

natural born killers

【在 f******k 的大作中提到】

: 有些电影，周围的人都没看过或者不喜欢，没有人可以交流，发在这个版上又肯定被人
: 骂装@#%￥%。
: 我先开个头吧：
: 所有看过的电影里，我最喜欢的就是《the big lebowski》，Jeff Bridges演的。看了
: 没有50遍
: 也有40遍了，台词都背下来了。
: 不知道为什么喜欢，就是喜欢那个调调，90年代初的美国就是那个样子么？好想永远回
: 到那个年代。

n*t2014-02-07 08:02

7 楼

遍历比较慢，老魏你看看我的 2 级队列可行不可行
http://www.mitbbs.com/article_t/Programming/31318275.html

【在 t**********1 的大作中提到】

: 下面是好虫的要求：
: 举个例子，就是假定当前所有票的线段数是N（连着的算一段)，一个request进来，要
: 满足分配之后N'最小。其次，在N'一样的前提下，要从一个长度最短的线段里取。线段
: 长度一样可以任取一个。
: 这是一个全局搜索算法的问题。复杂度至少O(n)，n是总座位数。
: 好虫的要求是20个区段，每个区段每个等级车票1000个座位。那是什么概念呢？就是每
: 次要考虑20X1000个全局座位的优化。
: 最难的是有时间要求。比如我赌气地提出1MM出票每秒。好虫竟然还不乐意，妄图无耻
: 地讨价还价为1MM transaction每秒。
: 现在就假定我们只优化一个座位。假定有上帝之手帮你优化好了，用的是全体平行宇宙

R*o2014-02-07 08:02

8 楼

阿凡达。一说就被批判不会欣赏没深度。

t*12014-02-07 08:02

9 楼

老姜，你回帖太快了。
再读一下我的帖子，循环1000次，啥都不干，找一个最大的，就要0.9us了。
肯定地讲，你那个还是太慢。

【在 n*****t 的大作中提到】

: 遍历比较慢，老魏你看看我的 2 级队列可行不可行
: http://www.mitbbs.com/article_t/Programming/31318275.html

d*z2014-02-07 08:02

10 楼

CHINAMAN

【在 f******k 的大作中提到】

: 有些电影，周围的人都没看过或者不喜欢，没有人可以交流，发在这个版上又肯定被人
: 骂装@#%￥%。
: 我先开个头吧：
: 所有看过的电影里，我最喜欢的就是《the big lebowski》，Jeff Bridges演的。看了
: 没有50遍
: 也有40遍了，台词都背下来了。
: 不知道为什么喜欢，就是喜欢那个调调，90年代初的美国就是那个样子么？好想永远回
: 到那个年代。

n*t2014-02-07 08:02

11 楼

线段长度在队列里是已知的，等于已经 sort 过了，只要从相应队列里面随便拿一个出
来就可以了，不用比较了吧？关键是没那么多优化等级

【在 t**********1 的大作中提到】

: 老姜，你回帖太快了。
: 再读一下我的帖子，循环1000次，啥都不干，找一个最大的，就要0.9us了。
: 肯定地讲，你那个还是太慢。

G*o2014-02-07 08:02

12 楼

what is this？

CHINAMAN

【在 d****z 的大作中提到】

: CHINAMAN

t*12014-02-07 08:02

13 楼

而且你那个不满足goodbug的要求。
你看看他的需求。还要求线段最少加长度最短。

【在 t**********1 的大作中提到】

: 老姜，你回帖太快了。
: 再读一下我的帖子，循环1000次，啥都不干，找一个最大的，就要0.9us了。
: 肯定地讲，你那个还是太慢。

v32014-02-07 08:02

14 楼

haha

【在 R***o 的大作中提到】

: 阿凡达。一说就被批判不会欣赏没深度。

n*t2014-02-07 08:02

15 楼

我琢磨一下，基本上我是打算用索引表

【在 t**********1 的大作中提到】

: 而且你那个不满足goodbug的要求。
: 你看看他的需求。还要求线段最少加长度最短。

d*z2014-02-07 08:02

16 楼

就是OP说的那个电影啊，故事一开始就是“CHINAMAN"到人家袭击还在地毯上撒了泡尿
，整个电影就是
这么开始的...

【在 G*********o 的大作中提到】

: what is this？
:
: CHINAMAN

t*12014-02-07 08:02

17 楼

你还要考虑退票怎么办？
重新sort的代价？
优化等级无所谓，只要有2级就可能要扫描整个1000个座位。你扫描一次就别干别的了。

【在 n*****t 的大作中提到】

: 线段长度在队列里是已知的，等于已经 sort 过了，只要从相应队列里面随便拿一个出
: 来就可以了，不用比较了吧？关键是没那么多优化等级

b*n2014-02-07 08:02

18 楼

hang over.

n*t2014-02-07 08:02

19 楼

比如一趟车 A - Z，我预设队列 AB AC ....... YZ
卖 AB 票就直接从 AB 队列取，有票的话，总线段数 N 减一，满足要求。AB 无票，取
AC，N 不变，长度最短，这样满足了？

【在 t**********1 的大作中提到】

: 而且你那个不满足goodbug的要求。
: 你看看他的需求。还要求线段最少加长度最短。

B*r2014-02-07 08:02

20 楼

school of rock
怕别人说幼稚。。。

i*i2014-02-07 08:02

21 楼

这就是单机的牛逼之处． goodbug的方案没有这个问题，因为想都不用想．

v*t2014-02-07 08:02

22 楼

无极
黄金甲

【在 f******k 的大作中提到】

: 有些电影，周围的人都没看过或者不喜欢，没有人可以交流，发在这个版上又肯定被人
: 骂装@#%￥%。
: 我先开个头吧：
: 所有看过的电影里，我最喜欢的就是《the big lebowski》，Jeff Bridges演的。看了
: 没有50遍
: 也有40遍了，台词都背下来了。
: 不知道为什么喜欢，就是喜欢那个调调，90年代初的美国就是那个样子么？好想永远回
: 到那个年代。

n*t2014-02-07 08:02

23 楼

退票不用 sort，直接 enqueue。初始状态是都在 AZ，出票的时候调整队列，重新
enqueue

了。

【在 t**********1 的大作中提到】

: 你还要考虑退票怎么办？
: 重新sort的代价？
: 优化等级无所谓，只要有2级就可能要扫描整个1000个座位。你扫描一次就别干别的了。

H*r2014-02-07 08:02

24 楼

SM porn

t*12014-02-07 08:02

25 楼

goodbug的理由：
1. 实时没有用，而且一无是处，预订才是牛逼
2. 我做不了实时，12306每秒最多10K是实时，我希望每秒1MM不是实时

【在 i**i 的大作中提到】

: 这就是单机的牛逼之处． goodbug的方案没有这个问题，因为想都不用想．

n*t2014-02-07 08:02

26 楼

其实抢票成功后，选座位可以放到外围计算最优，如果真的有必要的话，每个车次安排
一台机器总行了吧，反正跟别的车次不相干

【在 t**********1 的大作中提到】

: goodbug的理由：
: 1. 实时没有用，而且一无是处，预订才是牛逼
: 2. 我做不了实时，12306每秒最多10K是实时，我希望每秒1MM不是实时

t*12014-02-07 08:02

27 楼

老姜，
定了某个区段的票，可能有些座位线段数量没增加，有些座位线段数量加2，有些座位
线段数量反而减一。
这些你的算法考虑了么？

【在 n*****t 的大作中提到】

: 退票不用 sort，直接 enqueue。初始状态是都在 AZ，出票的时候调整队列，重新
: enqueue
:
: 了。

t*12014-02-07 08:02

28 楼

不行，这样会有振荡。
因为有些请求不能分配座位，会失败。但是这个过程中保留的座位会影响其他请求。
必须串行实时处理。

【在 n*****t 的大作中提到】

: 其实抢票成功后，选座位可以放到外围计算最优，如果真的有必要的话，每个车次安排
: 一台机器总行了吧，反正跟别的车次不相干

n*t2014-02-07 08:02

29 楼

比如只有 AZ 票，非卖 KO，那就多出一段了，这个没办法优化。否则就是从 KP KQ KR
IO JO 队列里取票。如果这类队列都没有，就向两端扩展范围，最坏扫描 200 个队列
。其实 2 级队列是否有票也可以用 bitmap 表示。

【在 t**********1 的大作中提到】

: 老姜，
: 定了某个区段的票，可能有些座位线段数量没增加，有些座位线段数量加2，有些座位
: 线段数量反而减一。
: 这些你的算法考虑了么？

n*t2014-02-07 08:02

30 楼

前端抢票前先到分座鸡查询，拿到票后让分座鸡计算，分座失败后记录索引表，下次这
个段就
不用抢了，有退票就先更新分座鸡的索引表

【在 t**********1 的大作中提到】

: 不行，这样会有振荡。
: 因为有些请求不能分配座位，会失败。但是这个过程中保留的座位会影响其他请求。
: 必须串行实时处理。

t*12014-02-07 08:02

31 楼

反正1000次循环比较就勉强1MM/s了。
还要完全满足goodbug的优化要求。算线段数量，算长度。
这个算是比较困难的题目了。
呵呵，这个要是有一个1MM 的方案出来如何？
其实说出来初中生也都能理解。

KR

【在 n*****t 的大作中提到】

: 比如只有 AZ 票，非卖 KO，那就多出一段了，这个没办法优化。否则就是从 KP KQ KR
: IO JO 队列里取票。如果这类队列都没有，就向两端扩展范围，最坏扫描 200 个队列
: 。其实 2 级队列是否有票也可以用 bitmap 表示。

t*12014-02-07 08:02

32 楼

还是不行。这是优化问题。
只要有一个组合是最坏情况，人家可以不停地买票退票折腾你的benchmark。
我的要求是，不论怎么折腾，performance都要稳定。
而且，latency也会导致振荡。不能claim 100%优化稳定。

【在 n*****t 的大作中提到】

: 前端抢票前先到分座鸡查询，拿到票后让分座鸡计算，分座失败后记录索引表，下次这
: 个段就
: 不用抢了，有退票就先更新分座鸡的索引表

n*t2014-02-07 08:02

33 楼

我这个是看一下对应队列是否有票，看一下 20x20 的队列 bitmap就可以了，大多数情
况下读一次 memory ，cmp 10 来次可以了，极端情况 cmp 200 次，比遍历快。老魏还
有啥更优姐，能不能拿出来分享分享？
不过我估计古德八连我这个蓝翔技校算法都没考虑过，就是暴力堆机器算，LOL

【在 t**********1 的大作中提到】

: 反正1000次循环比较就勉强1MM/s了。
: 还要完全满足goodbug的优化要求。算线段数量，算长度。
: 这个算是比较困难的题目了。
: 呵呵，这个要是有一个1MM 的方案出来如何？
: 其实说出来初中生也都能理解。
:
: KR

n*t2014-02-07 08:02

34 楼

我觉得差不多吧，如果 KO 肯定无法出票，人还是可以不断查询这张来折腾你，区别就
是把压力放在分票鸡还是抢票鸡

【在 t**********1 的大作中提到】

: 还是不行。这是优化问题。
: 只要有一个组合是最坏情况，人家可以不停地买票退票折腾你的benchmark。
: 我的要求是，不论怎么折腾，performance都要稳定。
: 而且，latency也会导致振荡。不能claim 100%优化稳定。

i*i2014-02-07 08:02

35 楼

贪心算法如何？
做索引：
（方向，时间段，可用站数，开始站，结束站，票）
方向：京沪，京广等铁路线
可用站数：当前一个座位空闲的站数．
比如：
（京广，2/7 6:00am-8:00pm,3, 廊坊，保定)
来一个请求，查表看方向，看开车时间, "找"合适的站数， "找"合适的起始站．
退票时要插入相应的索引．
（实现起来是很无趣，很麻烦．）

n*t2014-02-07 08:02

36 楼

我们先假设要求的车次、日期是固定的，不然太无聊了，上海到苏州一天几百趟车，全
查一遍就是深井冰
车次固定了，我觉得索引队列勉强符合要求了。

【在 i**i 的大作中提到】

: 贪心算法如何？
: 做索引：
: （方向，时间段，可用站数，开始站，结束站，票）
: 方向：京沪，京广等铁路线
: 可用站数：当前一个座位空闲的站数．
: 比如：
: （京广，2/7 6:00am-8:00pm,3, 廊坊，保定)
: 来一个请求，查表看方向，看开车时间, "找"合适的站数， "找"合适的起始站．
: 退票时要插入相应的索引．
: （实现起来是很无趣，很麻烦．）

L*e2014-02-07 08:02

37 楼

吼吼，我刚把我昨天的想法打出来，大家就已经纷纷出招了。。。
大家批评一下我的算法？
http://www.mitbbs.com/article/Programming/31318459_0.html

【在 t**********1 的大作中提到】

: 下面是好虫的要求：
: 举个例子，就是假定当前所有票的线段数是N（连着的算一段)，一个request进来，要
: 满足分配之后N'最小。其次，在N'一样的前提下，要从一个长度最短的线段里取。线段
: 长度一样可以任取一个。
: 这是一个全局搜索算法的问题。复杂度至少O(n)，n是总座位数。
: 好虫的要求是20个区段，每个区段每个等级车票1000个座位。那是什么概念呢？就是每
: 次要考虑20X1000个全局座位的优化。
: 最难的是有时间要求。比如我赌气地提出1MM出票每秒。好虫竟然还不乐意，妄图无耻
: 地讨价还价为1MM transaction每秒。
: 现在就假定我们只优化一个座位。假定有上帝之手帮你优化好了，用的是全体平行宇宙

t*12014-02-07 08:02

38 楼

请左眼以及各位详查。
goodbug要求类似俄罗斯方块。要求尽量填补空隙。所以还要看前后站的票状态。
如果多个空隙都最优，还要尽量把人往一起凑。

【在 L*****e 的大作中提到】

: 吼吼，我刚把我昨天的想法打出来，大家就已经纷纷出招了。。。
: 大家批评一下我的算法？
: http://www.mitbbs.com/article/Programming/31318459_0.html

L*e2014-02-07 08:02

39 楼

我说的方法应该是可以满足实时gap最小，也就是尽量填补空隙的。。。
没太明白什么是“如果多个空隙都最优，还要尽量把人往一起凑。”是在说要尽量让卖
出去的座位都挨着？
真够麻烦的，不玩了。。。

【在 t**********1 的大作中提到】

: 请左眼以及各位详查。
: goodbug要求类似俄罗斯方块。要求尽量填补空隙。所以还要看前后站的票状态。
: 如果多个空隙都最优，还要尽量把人往一起凑。

t*12014-02-07 08:02

40 楼

GAP不能看数量，还要看位置。
而且位置更重要。
我说的不对，不是尽量让卖出去的座位都挨着。
而是尽量提高车厢的利用率。

【在 L*****e 的大作中提到】

: 我说的方法应该是可以满足实时gap最小，也就是尽量填补空隙的。。。
: 没太明白什么是“如果多个空隙都最优，还要尽量把人往一起凑。”是在说要尽量让卖
: 出去的座位都挨着？
: 真够麻烦的，不玩了。。。

n*t2014-02-07 08:02

41 楼

那就是按车厢车座 sorted queue，应该还好，队列最长只有 1000 张票

【在 t**********1 的大作中提到】

: GAP不能看数量，还要看位置。
: 而且位置更重要。
: 我说的不对，不是尽量让卖出去的座位都挨着。
: 而是尽量提高车厢的利用率。

c*32014-02-07 08:02

42 楼

就像前面说的，这种复杂算法其实只有在Web GUI上搞trick最好。
某个车次那些区段票被卖了，就是个内存bitmap，很容易sync到前端的，在GUI上显示
车次空座位，让用户自己选。如果买的时刻被别人抢走了，算他活该。重新再抢，他也
没有话说。

n*t2014-02-07 08:02

43 楼

艾玛，古德八这变态有没有具体规则啊，一次弄完整了，省得重新一次次设计

【在 t**********1 的大作中提到】

: GAP不能看数量，还要看位置。
: 而且位置更重要。
: 我说的不对，不是尽量让卖出去的座位都挨着。
: 而是尽量提高车厢的利用率。

t*12014-02-07 08:02

44 楼

呵呵，你这个肯定不对。
因为对于不同的请求，sort的结果是不一样的。因为和GAP的位置有关。

【在 n*****t 的大作中提到】

: 那就是按车厢车座 sorted queue，应该还好，队列最长只有 1000 张票

c*32014-02-07 08:02

45 楼

在Web GUI上搞trick，抢票软件也基本废了。
抢票软件的弱点是图像识别能力差，智能差，现在人工智能就是这样低水平。

n*t2014-02-07 08:02

46 楼

不太明白这个到底是啥要求啊？

【在 t**********1 的大作中提到】

: 呵呵，你这个肯定不对。
: 因为对于不同的请求，sort的结果是不一样的。因为和GAP的位置有关。

p*o2014-02-07 08:02

47 楼

这玩艺每趟车就是一个register allocation问题，文献里随便翻个算法比如left-edge
之类的都不会太离谱，那个线段数最小也不一定是个好的目标函数。
问题是要scale out，一个机器别处理太多。机器间加锁是不行的，一个黄牛党反复刷票
你的系统就瘫了。还是得上STM之类的基于事务的算法。

【在 t**********1 的大作中提到】

: 下面是好虫的要求：
: 举个例子，就是假定当前所有票的线段数是N（连着的算一段)，一个request进来，要
: 满足分配之后N'最小。其次，在N'一样的前提下，要从一个长度最短的线段里取。线段
: 长度一样可以任取一个。
: 这是一个全局搜索算法的问题。复杂度至少O(n)，n是总座位数。
: 好虫的要求是20个区段，每个区段每个等级车票1000个座位。那是什么概念呢？就是每
: 次要考虑20X1000个全局座位的优化。
: 最难的是有时间要求。比如我赌气地提出1MM出票每秒。好虫竟然还不乐意，妄图无耻
: 地讨价还价为1MM transaction每秒。
: 现在就假定我们只优化一个座位。假定有上帝之手帮你优化好了，用的是全体平行宇宙

t*12014-02-07 08:02

48 楼

现在说别的都没用，目标是单机1MM/s。还要带其他各种overhead。
其实我还要考虑将来的scalability，比如在4/8 CPU架构上性能能加倍。

edge
刷票

【在 p***o 的大作中提到】

: 这玩艺每趟车就是一个register allocation问题，文献里随便翻个算法比如left-edge
: 之类的都不会太离谱，那个线段数最小也不一定是个好的目标函数。
: 问题是要scale out，一个机器别处理太多。机器间加锁是不行的，一个黄牛党反复刷票
: 你的系统就瘫了。还是得上STM之类的基于事务的算法。

c*32014-02-07 08:02

49 楼

还有一种办法。几千个客户端到服务器的TCP连接，你不可能用单线程处理吧？
收到请求后，先在处理socket的线程算座位，因为是在一个机器，你可以从内存读到最
新座位分配，然后把请求加上座位号，放到FIFO的queue里。让那个计数器线程处理。

【在 t**********1 的大作中提到】

: 现在说别的都没用，目标是单机1MM/s。还要带其他各种overhead。
: 其实我还要考虑将来的scalability，比如在4/8 CPU架构上性能能加倍。
:
: edge
: 刷票

L*e2014-02-07 08:02

50 楼

哦，以下面的为例子，座位1和2的0部分是已经卖掉了，1部分表示还要票，现在来了个
请求要求买000011000（1的地方是这个请求的上车站和下车站），好虫要求的最优解是
卖座位2比卖座位1优？因为卖2的碎片集中在一个位置。。。
1. 000111100
2. 001111000
卖座位1的结果是：000100100
卖座位2的结果是：001100000
如果一个结果是0011001100，另一个结果是00111000100，哪个结果更优？第二个？因
为在可能的情况下使得碎片更集中化？

【在 t**********1 的大作中提到】

: GAP不能看数量，还要看位置。
: 而且位置更重要。
: 我说的不对，不是尽量让卖出去的座位都挨着。
: 而是尽量提高车厢的利用率。

t*12014-02-07 08:02

51 楼

这个socket确实单线程处理最快。
虽然counter intuitive但是事实。

【在 c****3 的大作中提到】

: 还有一种办法。几千个客户端到服务器的TCP连接，你不可能用单线程处理吧？
: 收到请求后，先在处理socket的线程算座位，因为是在一个机器，你可以从内存读到最
: 新座位分配，然后把请求加上座位号，放到FIFO的queue里。让那个计数器线程处理。

c*32014-02-07 08:02

52 楼

你这种情况，还用单线程处理几百，上千个socket数据接收，再去算计数器，可能够呛。

【在 t**********1 的大作中提到】

: 这个socket确实单线程处理最快。
: 虽然counter intuitive但是事实。

t*12014-02-07 08:02

53 楼

呵呵，接收到以后就要给别的线程了。
这就是窍门。

呛。

【在 c****3 的大作中提到】

: 你这种情况，还用单线程处理几百，上千个socket数据接收，再去算计数器，可能够呛。

n*t2014-02-07 08:02

54 楼

先抢票再算座位比较好

【在 c****3 的大作中提到】

: 还有一种办法。几千个客户端到服务器的TCP连接，你不可能用单线程处理吧？
: 收到请求后，先在处理socket的线程算座位，因为是在一个机器，你可以从内存读到最
: 新座位分配，然后把请求加上座位号，放到FIFO的queue里。让那个计数器线程处理。

t*12014-02-07 08:02

55 楼

对
这个结果怎么得来的？这种情况按照好虫规则任选。

【在 L*****e 的大作中提到】

: 哦，以下面的为例子，座位1和2的0部分是已经卖掉了，1部分表示还要票，现在来了个
: 请求要求买000011000（1的地方是这个请求的上车站和下车站），好虫要求的最优解是
: 卖座位2比卖座位1优？因为卖2的碎片集中在一个位置。。。
: 1. 000111100
: 2. 001111000
: 卖座位1的结果是：000100100
: 卖座位2的结果是：001100000
: 如果一个结果是0011001100，另一个结果是00111000100，哪个结果更优？第二个？因
: 为在可能的情况下使得碎片更集中化？

c*32014-02-07 08:02

56 楼

那你可以把请求多传递几次。收到请求，给某个线程算座位，算好座位，把请求加上座
位号，放到FIFO的Queue里。
计数器线程只管从FIFO Queue的头读请求，它读到的请求，已经包含座位号。
FIFO多线程访问，可以用lock-free的算法，就是用atomic operation做的lock-free的
Queue。

【在 t**********1 的大作中提到】

: 呵呵，接收到以后就要给别的线程了。
: 这就是窍门。
:
: 呛。

n*t2014-02-07 08:02

57 楼

出票 KO 优先找 K 打头和 O 结尾的，没有再逐步像两端扩散。
111 - 1 vs 11 - 11 哪个更优我觉得无意义，谁知道下一张出啥票啊？

【在 L*****e 的大作中提到】

: 哦，以下面的为例子，座位1和2的0部分是已经卖掉了，1部分表示还要票，现在来了个
: 请求要求买000011000（1的地方是这个请求的上车站和下车站），好虫要求的最优解是
: 卖座位2比卖座位1优？因为卖2的碎片集中在一个位置。。。
: 1. 000111100
: 2. 001111000
: 卖座位1的结果是：000100100
: 卖座位2的结果是：001100000
: 如果一个结果是0011001100，另一个结果是00111000100，哪个结果更优？第二个？因
: 为在可能的情况下使得碎片更集中化？

L*e2014-02-07 08:02

58 楼

你说的好虫的要求我的算法是满足的，我的算法和老姜的本质上一样。。。
不过因为上面的提示，才想到结果为000100100和结果为001100000确实是有优劣之分的
，因为结果一里的碎片票再也没法卖出，而结果二里的碎片还有可能被卖出。。。
然后同理，0011001100该座位还有两张票可能被卖出，而00111000100只有一张票可能
被卖出。。。
完了，好虫看到这个条件后，估计又要给你加码了。。。

【在 t**********1 的大作中提到】

:
: 对
: 这个结果怎么得来的？这种情况按照好虫规则任选。

L*e2014-02-07 08:02

59 楼

当然有意义了，111 - 1最多可能再卖出一张票，11 - 11可能再卖出两张票把碎片全部
填补。。。

【在 n*****t 的大作中提到】

: 出票 KO 优先找 K 打头和 O 结尾的，没有再逐步像两端扩散。
: 111 - 1 vs 11 - 11 哪个更优我觉得无意义，谁知道下一张出啥票啊？

n*t2014-02-07 08:02

60 楼

啥，坐一站车的人肯定没有摸？

【在 L*****e 的大作中提到】

: 当然有意义了，111 - 1最多可能再卖出一张票，11 - 11可能再卖出两张票把碎片全部
: 填补。。。

a*a2014-02-07 08:02

61 楼

好虫那就是典型的水平不够的程序员，连基本的需求分析都没做好
实际上完全可以先出票，再选座位
丫非要放一起处理，完全就证明丫对整个案例的基本需求不了解
也就一帮水平不够的烂java程序员在互相吹捧

【在 t**********1 的大作中提到】

: 下面是好虫的要求：
: 举个例子，就是假定当前所有票的线段数是N（连着的算一段)，一个request进来，要
: 满足分配之后N'最小。其次，在N'一样的前提下，要从一个长度最短的线段里取。线段
: 长度一样可以任取一个。
: 这是一个全局搜索算法的问题。复杂度至少O(n)，n是总座位数。
: 好虫的要求是20个区段，每个区段每个等级车票1000个座位。那是什么概念呢？就是每
: 次要考虑20X1000个全局座位的优化。
: 最难的是有时间要求。比如我赌气地提出1MM出票每秒。好虫竟然还不乐意，妄图无耻
: 地讨价还价为1MM transaction每秒。
: 现在就假定我们只优化一个座位。假定有上帝之手帮你优化好了，用的是全体平行宇宙

L*e2014-02-07 08:02

62 楼

哦，是我想错了，汗。。。

【在 n*****t 的大作中提到】

: 啥，坐一站车的人肯定没有摸？

L*e2014-02-07 08:02

63 楼

因为要必须保证不能换座，所以先出票再选座位不可行，不能出了票结果发现没有满足
要求的座位。。。

【在 a****a 的大作中提到】

: 好虫那就是典型的水平不够的程序员，连基本的需求分析都没做好
: 实际上完全可以先出票，再选座位
: 丫非要放一起处理，完全就证明丫对整个案例的基本需求不了解
: 也就一帮水平不够的烂java程序员在互相吹捧

n*t2014-02-07 08:02

64 楼

有些人打小就是三好学生，上课认真记笔记，考试前熬夜复习，找工作认真刷题，上班
了用好每个轮子。这些人从没想过发明轮子，也不敢发明轮子，更不信你也能发明轮子。

★ 发自iPhone App: ChineseWeb 8.6

【在 a****a 的大作中提到】

: 好虫那就是典型的水平不够的程序员，连基本的需求分析都没做好
: 实际上完全可以先出票，再选座位
: 丫非要放一起处理，完全就证明丫对整个案例的基本需求不了解
: 也就一帮水平不够的烂java程序员在互相吹捧

w*z2014-02-07 08:02

65 楼

你买过火车票？哪有买火车票，先出票，再选座位的？

【在 a****a 的大作中提到】

: 好虫那就是典型的水平不够的程序员，连基本的需求分析都没做好
: 实际上完全可以先出票，再选座位
: 丫非要放一起处理，完全就证明丫对整个案例的基本需求不了解
: 也就一帮水平不够的烂java程序员在互相吹捧

q*c2014-02-07 08:02

66 楼

不过你要明白发明轮子得， 99.9% 发明得轮子一般都会害人害己，只是大家都看着那
0.1% 得好轮子而已。
当然讨论新轮子是很好得，但是要是讨论现实实现方案，那是能用旧轮子，绝对别
去发明新轮子－哪怕新轮子有可能强 1000 倍。
只有旧轮子完全不行，才只好上新轮子。

子。

【在 n*****t 的大作中提到】

: 有些人打小就是三好学生，上课认真记笔记，考试前熬夜复习，找工作认真刷题，上班
: 了用好每个轮子。这些人从没想过发明轮子，也不敢发明轮子，更不信你也能发明轮子。
:
: ★ 发自iPhone App: ChineseWeb 8.6

L*e2014-02-07 08:02

67 楼

理论问题和实际问题还是要分开谈。早就说过，实际中首发站是先开始售票的，然后途
经站再依次售票，根本就不存在这个座位优化问题。。。

【在 w**z 的大作中提到】

: 你买过火车票？哪有买火车票，先出票，再选座位的？

q*c2014-02-07 08:02

68 楼

BTW...说个跟这个主题没关系得话，和大家没关系，就是这个bbs 上太常见得个例和
惯例得问题。
比如这个三好学生，这个世界没有毁灭，没有变成人吃人得世界，中流砥柱就是这
些三好学生。发明轮子得人， 0.1% 成了千古流芳的牛屄人物， 0.1% 成了遗臭万年
的祸害人物。还有 99.8% 在大街上找饭吃。。。
所以你不能隐含鄙视这些三好学生，实际上他们的选择是最理性合理的选择。那些发
明轮子的人选择是非理性选择。当然这些非理性也是需要的，否则没了活力。但是
提倡就要坏事。

子。

【在 n*****t 的大作中提到】

: 有些人打小就是三好学生，上课认真记笔记，考试前熬夜复习，找工作认真刷题，上班
: 了用好每个轮子。这些人从没想过发明轮子，也不敢发明轮子，更不信你也能发明轮子。
:
: ★ 发自iPhone App: ChineseWeb 8.6

a*a2014-02-07 08:02

69 楼

飞机票就可以，火车票一样可以
实际上你去买火车票，也并不是说你可以挑座位
完全可以先完成 transaction，把你的票 reserve了，然后后台分配座位，然后再出票
，想连几个座位在一起都没问题，反正具体的座位你只有出票的时候才能看见
这样有足够的缓冲时间，也不会对负责transaction的服务器造成太大负担
所以说你们这些人水平不够，动不动就是上平台啊，换架构啊，堆 server啊没法实时
啊
纯粹都是脑子有水

【在 w**z 的大作中提到】

: 你买过火车票？哪有买火车票，先出票，再选座位的？

q*c2014-02-07 08:02

70 楼

那是过去，没有网络，不得不通过浪费，降低效率，解决这个问题。
现在有了计算机网络，优化是可以实现的，而且可以相当程度提高运力。这个对于
中国这种车少的局面很有意义。

【在 L*****e 的大作中提到】

: 理论问题和实际问题还是要分开谈。早就说过，实际中首发站是先开始售票的，然后途
: 经站再依次售票，根本就不存在这个座位优化问题。。。

n*t2014-02-07 08:02

71 楼

可以先抢票再分座，如果发现无法满足不换座了，负责分票的发消息通知抢票机这个区
间不要出票了，同时回馈客户无票

★ 发自iPhone App: ChineseWeb 8.6

【在 L*****e 的大作中提到】

: 因为要必须保证不能换座，所以先出票再选座位不可行，不能出了票结果发现没有满足
: 要求的座位。。。

a*a2014-02-07 08:02

72 楼

这种三好学生拿着自己可怜的见识反对别人发明轮子你怎么说
更何况，真的算三好学生吗
三好学生连个需求分析都做不好？
扯淡吧
那种的就是标准的读书不求甚解的，应用只会照虎画猫的，你教他 1＋1=2 2+2=4，
然后问他 1+1+2等于啥他就傻乐得

【在 q*c 的大作中提到】

: BTW...说个跟这个主题没关系得话，和大家没关系，就是这个bbs 上太常见得个例和
: 惯例得问题。
: 比如这个三好学生，这个世界没有毁灭，没有变成人吃人得世界，中流砥柱就是这
: 些三好学生。发明轮子得人， 0.1% 成了千古流芳的牛屄人物， 0.1% 成了遗臭万年
: 的祸害人物。还有 99.8% 在大街上找饭吃。。。
: 所以你不能隐含鄙视这些三好学生，实际上他们的选择是最理性合理的选择。那些发
: 明轮子的人选择是非理性选择。当然这些非理性也是需要的，否则没了活力。但是
: 提倡就要坏事。
:
: 子。

q*c2014-02-07 08:02

73 楼

别急着下结论脑子有水什么的。世界不不止你一个聪明人。
火车比飞机复杂多了，沿线可以加车厢，可是还是同一车次，就是说车次的运力在
不同站不同，飞机能加挂座位？
这种情况下，根据先后不同，你完全可能 ab, bc, cd 都有票，但是就是没有一张
座位不变的 abcd 的票。春云大家都做过的，我没有几次是从门里面进进的。叫人换
座打架是最轻的结果。
这里就需要 transaction.

【在 a****a 的大作中提到】

:
: 这种三好学生拿着自己可怜的见识反对别人发明轮子你怎么说
: 更何况，真的算三好学生吗
: 三好学生连个需求分析都做不好？
: 扯淡吧
: 那种的就是标准的读书不求甚解的，应用只会照虎画猫的，你教他 1＋1=2 2+2=4，
: 然后问他 1+1+2等于啥他就傻乐得

n*t2014-02-07 08:02

74 楼

很多 open source 一开始都是烂得不行不行的，就因为一帮人闲得蛋疼慢慢变成了
linux。
这个版上讨论 12306 的有哪个是红三代太子党吗？既然都是蛋疼，何必限制自己的思
路，更何况还是有几个人发明过类似的轮子

★ 发自iPhone App: ChineseWeb 8.6

【在 q*c 的大作中提到】

: 不过你要明白发明轮子得， 99.9% 发明得轮子一般都会害人害己，只是大家都看着那
: 0.1% 得好轮子而已。
: 当然讨论新轮子是很好得，但是要是讨论现实实现方案，那是能用旧轮子，绝对别
: 去发明新轮子－哪怕新轮子有可能强 1000 倍。
: 只有旧轮子完全不行，才只好上新轮子。
:
: 子。

q*c2014-02-07 08:02

75 楼

不是这样不行，而且这种补丁越开越多，系统稳定性就越来越低。 oracle 为了
transaction 的代价很大，你现在无非是自己在慢慢实现 transaction, 不停的发现
问题再重走别人的老路而已。
等你补的稳定可靠了，我估计你的 perf 还比不了 oracle.

【在 n*****t 的大作中提到】

: 可以先抢票再分座，如果发现无法满足不换座了，负责分票的发消息通知抢票机这个区
: 间不要出票了，同时回馈客户无票
:
: ★ 发自iPhone App: ChineseWeb 8.6

a*a2014-02-07 08:02

76 楼

实际上都不需要
完全可以把一列车的票全部抢完，然后重排，抢完票之后发个comfirmation,然后等十
分钟出票
这样根本不可能存在不满足不换座的行为
因为实际上一票对应一座
而且最简单的是，就算有少量冲突，完全可以人与人在车上自行讨论解决，程序完全不
需要那么robost
所谓的不能换座就是个伪需求，丫自己造出来的伪概念，纯粹的机械唯物主义

【在 n*****t 的大作中提到】

: 可以先抢票再分座，如果发现无法满足不换座了，负责分票的发消息通知抢票机这个区
: 间不要出票了，同时回馈客户无票
:
: ★ 发自iPhone App: ChineseWeb 8.6

q*c2014-02-07 08:02

77 楼

你说的对啊，这不就是前面古德霸的异步批处理嘛. 我觉得这才是正道。
看来你是没看前面。

【在 a****a 的大作中提到】

: 实际上都不需要
: 完全可以把一列车的票全部抢完，然后重排，抢完票之后发个comfirmation,然后等十
: 分钟出票
: 这样根本不可能存在不满足不换座的行为
: 因为实际上一票对应一座
: 而且最简单的是，就算有少量冲突，完全可以人与人在车上自行讨论解决，程序完全不
: 需要那么robost
: 所谓的不能换座就是个伪需求，丫自己造出来的伪概念，纯粹的机械唯物主义

n*t2014-02-07 08:02

78 楼

瑞士军刀好不好？当然好，但特定场合就是比不上糙快猛的螺丝刀。而且说实话，老魏
的方案迄今为止都不是啥新轮子，都是在业界早就在用的技术，只是很多普通程序员没
接触过，觉得不可思议。
不是说不停的打补丁，是需求一直在变，在适应新的要求，框架始终没动。又不是交标
书，谁也不给钱，凭啥我一开始就给你上个大宝剑啊

★ 发自iPhone App: ChineseWeb 8.6

【在 q*c 的大作中提到】

: 不是这样不行，而且这种补丁越开越多，系统稳定性就越来越低。 oracle 为了
: transaction 的代价很大，你现在无非是自己在慢慢实现 transaction, 不停的发现
: 问题再重走别人的老路而已。
: 等你补的稳定可靠了，我估计你的 perf 还比不了 oracle.

a*a2014-02-07 08:02

79 楼

我怎么觉得我说的是魏老师的做法呢
整个售票过程的核心环节就是抢票一段，你抓不住这一段，说别的有意义吗
抢票这一段用高性能单机做，这基本上是这几年业界的常识，尤其是这种带有强耦合性
质的交易
好虫所谓的堆Queue，堆服务器，实际上是增加难度的，因为过分增加了 lock的难度
现在铁道部的做法实际上就是魏老师的做法，所以我不明白你在吵什么
按好虫的办法，12306现在那17组 xeon肯定是不够的

【在 q*c 的大作中提到】

: 你说的对啊，这不就是前面古德霸的异步批处理嘛. 我觉得这才是正道。
: 看来你是没看前面。

n*t2014-02-07 08:02

80 楼

异步批处理是伪科学，是古德八无力实现实时处理

★ 发自iPhone App: ChineseWeb 8.6

【在 q*c 的大作中提到】

: 你说的对啊，这不就是前面古德霸的异步批处理嘛. 我觉得这才是正道。
: 看来你是没看前面。

L*e2014-02-07 08:02

81 楼

嗯，如果不需要满足某几张票必须坐一起之类的要求，最后做全局调整座位可以保证不
需要换座位。
如果条件是：实时出票，但是座位号随后确定，老魏搞定应该没问题。。。

【在 a****a 的大作中提到】

: 实际上都不需要
: 完全可以把一列车的票全部抢完，然后重排，抢完票之后发个comfirmation,然后等十
: 分钟出票
: 这样根本不可能存在不满足不换座的行为
: 因为实际上一票对应一座
: 而且最简单的是，就算有少量冲突，完全可以人与人在车上自行讨论解决，程序完全不
: 需要那么robost
: 所谓的不能换座就是个伪需求，丫自己造出来的伪概念，纯粹的机械唯物主义

a*a2014-02-07 08:02

82 楼

所以我说他们连需求都没搞清楚
魏老师那方案一看就是做过案例的，知道实际情况是什么样，主要矛盾在哪里

【在 L*****e 的大作中提到】

: 嗯，如果不需要满足某几张票必须坐一起之类的要求，最后做全局调整座位可以保证不
: 需要换座位。
: 如果条件是：实时出票，但是座位号随后确定，老魏搞定应该没问题。。。

w*z2014-02-07 08:02

83 楼

折腾半天，又变回异步了。
你要人车上自己解决？你搞笑？一趟车，好几千人，要出人命的。

【在 a****a 的大作中提到】

: 实际上都不需要
: 完全可以把一列车的票全部抢完，然后重排，抢完票之后发个comfirmation,然后等十
: 分钟出票
: 这样根本不可能存在不满足不换座的行为
: 因为实际上一票对应一座
: 而且最简单的是，就算有少量冲突，完全可以人与人在车上自行讨论解决，程序完全不
: 需要那么robost
: 所谓的不能换座就是个伪需求，丫自己造出来的伪概念，纯粹的机械唯物主义

w*z2014-02-07 08:02

84 楼

魏老师买卖股票的，不是火车票，拍马屁，不是这种拍法的。

【在 a****a 的大作中提到】

:
: 所以我说他们连需求都没搞清楚
: 魏老师那方案一看就是做过案例的，知道实际情况是什么样，主要矛盾在哪里

L*e2014-02-07 08:02

85 楼

不叫做连需求都没搞清楚，是各坚持各的需求，从一开始就没统一过。具体到最近这个
就是应不应该实时分配座位且达到实时优化。。。

【在 a****a 的大作中提到】

:
: 所以我说他们连需求都没搞清楚
: 魏老师那方案一看就是做过案例的，知道实际情况是什么样，主要矛盾在哪里

L*e2014-02-07 08:02

86 楼

但全局分配的一个缺陷是，你不知道最后票什么时候卖完，没有拿到所有最后能够出票
的请求，也就没法做全局分配。那到底等到啥时候再确定座位呢？继续等，还是根据现
有的分配？根据现有的分配就会有可能将来产生conflicts或者又得重新分配。。。

【在 a****a 的大作中提到】

:
: 所以我说他们连需求都没搞清楚
: 魏老师那方案一看就是做过案例的，知道实际情况是什么样，主要矛盾在哪里

q*c2014-02-07 08:02

87 楼

离线异步枪啥，交易请求排好队，后台单线程顺序执行飞快又没错，各种优化都能
做，有限 delay.
你说的就是我们说的办法，和老魏实时抢票不同。几百上千的文章你没看完。lol

【在 a****a 的大作中提到】

:
: 所以我说他们连需求都没搞清楚
: 魏老师那方案一看就是做过案例的，知道实际情况是什么样，主要矛盾在哪里

b*g2014-02-07 08:02

88 楼

需求以12306为准。我说的每个需求，你到是说说那个要求不是基本要求可以妥协？
我让他做两张票已经是看他可怜。
http://www.12306.cn/mormhweb/kyfw/question/201112/t20111220_672
在12306.cn网站购票一个身份证可以购多少张票？一笔订单是否有购票张数限制？
一个有效身份证件同一乘车日期同一车次限购一张车票（但使用同行成年人的有效
身份证件信息为乘车儿童购买儿童票的除外）。一笔订单不能超过5张票，12306.cn网
站可根据具体情况做适当限制。

【在 L*****e 的大作中提到】

: 不叫做连需求都没搞清楚，是各坚持各的需求，从一开始就没统一过。具体到最近这个
: 就是应不应该实时分配座位且达到实时优化。。。

f*52014-02-07 08:02

89 楼

其实还隐含这这几张票最好要挨着。消除很多所谓优化的讨论。

【在 b*******g 的大作中提到】

: 需求以12306为准。我说的每个需求，你到是说说那个要求不是基本要求可以妥协？
: 我让他做两张票已经是看他可怜。
: http://www.12306.cn/mormhweb/kyfw/question/201112/t20111220_672
: 在12306.cn网站购票一个身份证可以购多少张票？一笔订单是否有购票张数限制？
: 一个有效身份证件同一乘车日期同一车次限购一张车票（但使用同行成年人的有效
: 身份证件信息为乘车儿童购买儿童票的除外）。一笔订单不能超过5张票，12306.cn网
: 站可根据具体情况做适当限制。

b*g2014-02-07 08:02

90 楼

我是真没难为他。事实上这种出票，就算没要求挨着至少也要求同车厢。所有这些要求
都会增加算法的复杂度。系统设计要留有余量，是基本素养。

【在 f*******5 的大作中提到】

: 其实还隐含这这几张票最好要挨着。消除很多所谓优化的讨论。

b*g2014-02-07 08:02

91 楼

真是不知天高地厚，你来吧。
发信人: goodbug (好虫), 信区: Programming
标题: 再举个测试用例。
发信站: BBS 未名空间站 (Wed Feb 5 04:17:26 2014, 美东)
假定一趟车经过ABCD四个地方，为简单举例，假定只有一个100人的车厢。在B加挂一个
200人的车厢，到C后撤掉。
最后客满，得ABC 票100张，BCD票100张，BC票100张。
A B C D
100 100 100
200
按照太监只管抢票不分座位的策略，请给个出票不用换座位的方案吧。别跟我说一个车
次还俩号。

【在 a****a 的大作中提到】

: 好虫那就是典型的水平不够的程序员，连基本的需求分析都没做好
: 实际上完全可以先出票，再选座位
: 丫非要放一起处理，完全就证明丫对整个案例的基本需求不了解
: 也就一帮水平不够的烂java程序员在互相吹捧

n*t2014-02-07 08:02

92 楼

12306 是一天卖 5M 票还是处理 5M 订单

【在 b*******g 的大作中提到】

: 需求以12306为准。我说的每个需求，你到是说说那个要求不是基本要求可以妥协？
: 我让他做两张票已经是看他可怜。
: http://www.12306.cn/mormhweb/kyfw/question/201112/t20111220_672
: 在12306.cn网站购票一个身份证可以购多少张票？一笔订单是否有购票张数限制？
: 一个有效身份证件同一乘车日期同一车次限购一张车票（但使用同行成年人的有效
: 身份证件信息为乘车儿童购买儿童票的除外）。一笔订单不能超过5张票，12306.cn网
: 站可根据具体情况做适当限制。

L*e2014-02-07 08:02

93 楼

这个问题我早就有态度，我很早就表明老魏的东西不能算是一个完整的系统方案，如果
要替代整个系统还有很多很多要做。我觉得他现在做的只是解决一个系统中的一个非常
具体的一个功能的问题。我甚至都在那篇“作为一个有买票体验的用户”的帖子里表明
我觉得抢票不是解决网上买票问题的方向（一开始的设定就错了）。。。
但是我还是很有兴趣看看，老魏的方案能在他所能满足的条件下performance能达到多
少。至于你加的条件或者说你认为本来就应该有的条件之类，我真的不care，这些不过
是些干扰因素使得你们的赌赢或输的概率增大一点变小一点而已（如果发现有什么基本
功能对performance有指数级影响的，我愿意听一听，linear的就算了）。。。
老霸你也是网上的老江湖了，BBS上的输赢真的有那么重要？

【在 b*******g 的大作中提到】

: 需求以12306为准。我说的每个需求，你到是说说那个要求不是基本要求可以妥协？
: 我让他做两张票已经是看他可怜。
: http://www.12306.cn/mormhweb/kyfw/question/201112/t20111220_672
: 在12306.cn网站购票一个身份证可以购多少张票？一笔订单是否有购票张数限制？
: 一个有效身份证件同一乘车日期同一车次限购一张车票（但使用同行成年人的有效
: 身份证件信息为乘车儿童购买儿童票的除外）。一笔订单不能超过5张票，12306.cn网
: 站可根据具体情况做适当限制。

t*12014-02-07 08:02

94 楼

再留余量也经不住你的无耻指标。
按照transaction来算。动不动可以降上千倍，没见过这么无耻的要求。
而且，关键功能都有了，大家就是定格指标看看能不能实现，有必要再返回万阴的么？
又不是赢房子赢的。
为了你的那点脸，就不管不顾别的网友了。你还有脸么？

【在 b*******g 的大作中提到】

: 我是真没难为他。事实上这种出票，就算没要求挨着至少也要求同车厢。所有这些要求
: 都会增加算法的复杂度。系统设计要留有余量，是基本素养。

b*g2014-02-07 08:02

95 楼

卖5M人次的票，问题是不成功的订单可以有10-1000倍。刚开始抢得时候峰值能有1M/s。

【在 n*****t 的大作中提到】

: 12306 是一天卖 5M 票还是处理 5M 订单

n*t2014-02-07 08:02

96 楼

你是不是要在订票的时候再加 100 单查询，然后查询也不给工分啊？
先说好了啊

【在 b*******g 的大作中提到】

: 卖5M人次的票，问题是不成功的订单可以有10-1000倍。刚开始抢得时候峰值能有1M/s。

b*g2014-02-07 08:02

97 楼

他那个是个不可行的方案，至于一个抢座位算法，能优化到什么程度，实在不是我关心
的问题。
我是做架构的，做算法我不专业。人贵有自知之明。
还是那句话，装逼被雷劈呀。

【在 L*****e 的大作中提到】

: 这个问题我早就有态度，我很早就表明老魏的东西不能算是一个完整的系统方案，如果
: 要替代整个系统还有很多很多要做。我觉得他现在做的只是解决一个系统中的一个非常
: 具体的一个功能的问题。我甚至都在那篇“作为一个有买票体验的用户”的帖子里表明
: 我觉得抢票不是解决网上买票问题的方向（一开始的设定就错了）。。。
: 但是我还是很有兴趣看看，老魏的方案能在他所能满足的条件下performance能达到多
: 少。至于你加的条件或者说你认为本来就应该有的条件之类，我真的不care，这些不过
: 是些干扰因素使得你们的赌赢或输的概率增大一点变小一点而已（如果发现有什么基本
: 功能对performance有指数级影响的，我愿意听一听，linear的就算了）。。。
: 老霸你也是网上的老江湖了，BBS上的输赢真的有那么重要？

b*g2014-02-07 08:02

98 楼

你做不了，我做的了，算什么无耻？谁规定12306必须实时了吗？

【在 t**********1 的大作中提到】

: 再留余量也经不住你的无耻指标。
: 按照transaction来算。动不动可以降上千倍，没见过这么无耻的要求。
: 而且，关键功能都有了，大家就是定格指标看看能不能实现，有必要再返回万阴的么？
: 又不是赢房子赢的。
: 为了你的那点脸，就不管不顾别的网友了。你还有脸么？

b*g2014-02-07 08:02

99 楼

查询倒是容易，不需要实时更新，也做不到，snapshot就行，对系统性能影响有限。

【在 n*****t 的大作中提到】

: 你是不是要在订票的时候再加 100 单查询，然后查询也不给工分啊？
: 先说好了啊

n*t2014-02-07 08:02

100 楼

又扯了，查询的时候就要计算有没有可能不换座，跟出票几乎没区别

【在 b*******g 的大作中提到】

: 查询倒是容易，不需要实时更新，也做不到，snapshot就行，对系统性能影响有限。

L*e2014-02-07 08:02

101 楼

查询时稍微简单点，一个是查询有延时，二是查询只要告诉你满足你要求的票有没有，
不需要把座位号确定出来。。。

【在 n*****t 的大作中提到】

: 又扯了，查询的时候就要计算有没有可能不换座，跟出票几乎没区别

b*g2014-02-07 08:02

102 楼

查询就是查询个当前余票而已，还不要求实时准确，反正准确了也没用。你对做这种系
统完全没概念。

【在 n*****t 的大作中提到】

: 又扯了，查询的时候就要计算有没有可能不换座，跟出票几乎没区别

b*g2014-02-07 08:02

103 楼

下单的时候再告诉你卖不了是完全可以的，有人就是木瓜脑袋呀。

【在 L*****e 的大作中提到】

: 查询时稍微简单点，一个是查询有延时，二是查询只要告诉你满足你要求的票有没有，
: 不需要把座位号确定出来。。。

n*t2014-02-07 08:02

104 楼

在我的设计里没区别，队列有票就有，座位号只不过是 queue->head->ticketid

【在 L*****e 的大作中提到】

: 查询时稍微简单点，一个是查询有延时，二是查询只要告诉你满足你要求的票有没有，
: 不需要把座位号确定出来。。。

n*t2014-02-07 08:02

105 楼

操，那我是不是告诉你都有票啊？

【在 b*******g 的大作中提到】

: 下单的时候再告诉你卖不了是完全可以的，有人就是木瓜脑袋呀。

z*32014-02-07 08:02

106 楼

老姜你现在argue的是你自己的设计么？

【在 n*****t 的大作中提到】

: 操，那我是不是告诉你都有票啊？

f*52014-02-07 08:02

107 楼

有没有票会变的，不是一次把票放完。

【在 n*****t 的大作中提到】

: 操，那我是不是告诉你都有票啊？

n*t2014-02-07 08:02

108 楼

我的设计 open source

【在 z*******3 的大作中提到】

: 老姜你现在argue的是你自己的设计么？

b*g2014-02-07 08:02

109 楼

我那个设计，不告诉你余票让你发单都行。告诉你一个余票的大概数据就是让你有个概
念，
还有多少余票，前面有多少人等着处理。没戏了就别排队了，大家都省时间。

【在 n*****t 的大作中提到】

: 操，那我是不是告诉你都有票啊？

n*t2014-02-07 08:02

110 楼

所以你连查询都不做了，好么
咱不说废话，查询算不算 TPS

【在 b*******g 的大作中提到】

: 我那个设计，不告诉你余票让你发单都行。告诉你一个余票的大概数据就是让你有个概
: 念，
: 还有多少余票，前面有多少人等着处理。没戏了就别排队了，大家都省时间。

L*e2014-02-07 08:02

111 楼

我不是说算法，我是说查询的需求，延迟个把秒钟不成问题，谁先做个查询，然后看到
结果后1毫秒内下单啊？所有查询做到实时没有意义。。。

【在 n*****t 的大作中提到】

: 在我的设计里没区别，队列有票就有，座位号只不过是 queue->head->ticketid

n*t2014-02-07 08:02

112 楼

那我也不能胡给结果是不是？而且他这边查完了还不算 TPS，玩啊

【在 L*****e 的大作中提到】

: 我不是说算法，我是说查询的需求，延迟个把秒钟不成问题，谁先做个查询，然后看到
: 结果后1毫秒内下单啊？所有查询做到实时没有意义。。。

b*g2014-02-07 08:02

113 楼

查询算不算，要看你怎么实现的。在我的实现里，是不算的。因为我查询的是cache，
根本不过DB。
现在的问题是怎么处理百万次的订单，能还是不能，你怎么算TPS，没啥意义。如果处
理百万订单，你自己的定义需要10M TPS，那你就得支持10M tps.

【在 n*****t 的大作中提到】

: 所以你连查询都不做了，好么
: 咱不说废话，查询算不算 TPS

L*e2014-02-07 08:02

114 楼

哦，没看上下文，不知道你么争的是什么，我退出。。。

【在 n*****t 的大作中提到】

: 那我也不能胡给结果是不是？而且他这边查完了还不算 TPS，玩啊

b*g2014-02-07 08:02

115 楼

总之，百万订单是用户发起的，你跟他们争对不对有用吗？

n*t2014-02-07 08:02

116 楼

简单说，查询不算你就别给我发包，发了就算。

【在 b*******g 的大作中提到】

: 查询算不算，要看你怎么实现的。在我的实现里，是不算的。因为我查询的是cache，
: 根本不过DB。
: 现在的问题是怎么处理百万次的订单，能还是不能，你怎么算TPS，没啥意义。如果处
: 理百万订单，你自己的定义需要10M TPS，那你就得支持10M tps.