给nod101一个最优化的实时分配车票座位的算法 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

给nod101一个最优化的实时分配车票座位的算法

给nod101一个最优化的实时分配车票座位的算法# Programming - 葵花宝典

x*w2014-01-13 08:01

1 楼

westwing是把它当作领先指标看得。我的看法基本相反。我坚持认为jj是比散户反映更
慢的一群资金。顶部买入底部卖出是这类资金的性质决定的。从和大盘比较来看，
7/2大盘到底，399305 7/2也到底但是7/5还画根中阴线（就ta还在跑）。
11/11大盘到顶，399305 也到顶（ta还在进的开心）
这次下跌11/17时候第一波结束，大盘收星，399305实体大阴。当然这次399305比大盘
早到底，但是今天的情形（包括周五），都是399305实体大阴，大盘微跌。jj在砸。
鉴定完毕。哈哈哈
当然王亚伟等还是很nb的。

r*e2014-01-13 08:01

2 楼

这个耳机怎么样？看了网上的一些review好像不错啊

z*y2014-01-13 08:01

3 楼

我11年1月到7月F1，
7月到10月OPT，10月之后H1b，
是填1040NR还是1040NR-EZ ？能不能用resident alien？
F1在美国第3年，
学校和公司二张W2是分开填吗？

F*e2014-01-13 08:01

4 楼

【以下文字转载自 Game 讨论区】
发信人: siliq (外F：“白人至上”，“杀人是对的”), 信区: Game
标题: 太爽了。[SC2] 7月27号免费公测台服教程！ zz
发信站: BBS 未名空间站 (Sun Jul 25 14:36:07 2010, 美东)
不知道之前有人贴过没有。。。
对于我这样一个不对战只玩单机版的，连破解都省了
唯一美中不足的是过场动画需要听湾湾的台巴式配音
================
星际争霸2的beta测试已经结束，全球玩家都在等待游戏的正式发布时间北京时间2010
年7月27日凌晨0
点到来。由于韩国和台湾地区享受暴雪的优惠，以上两个地区的玩家可以在27日0点开
始进行游戏的公
测，暨可以简单的理解为“免费玩正式版的星际争霸2”。这里为大家提供一个详细的
参与台服免费公测的
教程，以帮助大家在第一时间能够参与到星际争霸2的游戏。
1、要参加星际争霸2公测，必须下载最新的游戏版本，而之前的beta版无法参与公测，
建议大家可以删
掉了。（下载地址:http://tw.battle.net/sc2/zh/），进去之后，点击右侧的绿

T*i2014-01-13 08:01

5 楼

假定一条线路从始至终一共m个区段，n个座位。
初始化：
m个array：[0，n-1] with name SegMap
memset to 0
输入：
任何时候有人购买了区段a,b。a <= b && 0 <= a <= m - 1 && 0 <= b <= m-1。
初始化array t[0, n - 1] = sum of SeqMap[from a to b]
Search array t from 0 to n-1, find the first index with the minimum value V。
If the minimum V > 0 then repeat the algo on "subsegments with which the
seat has been taken"。
具体原则：
座位编号，每次都从第编号座位开始分配。
每次分配一个需要换座最少方案
注意，换座不可避免的。但是可证明这是实时算法中最优化的。
时间复杂度，空间复杂度：
O(m * n)
注意，本算法只能单线程实现。
但是可以scale out。对任何一个车次几百几千个座位，可以保证最差数秒钟分配完成
。因此系实时用户体验。

h*u2014-01-13 08:01

6 楼

jj搞利益输送的.这使得它的行为非常怪异.
对公, 它在高点买入社保的抛盘.
对私, 底部卖给私募,经理有大大的红包拿.

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

: westwing是把它当作领先指标看得。我的看法基本相反。我坚持认为jj是比散户反映更
: 慢的一群资金。顶部买入底部卖出是这类资金的性质决定的。从和大盘比较来看，
: 7/2大盘到底，399305 7/2也到底但是7/5还画根中阴线（就ta还在跑）。
: 11/11大盘到顶，399305 也到顶（ta还在进的开心）
: 这次下跌11/17时候第一波结束，大盘收星，399305实体大阴。当然这次399305比大盘
: 早到底，但是今天的情形（包括周五），都是399305实体大阴，大盘微跌。jj在砸。
: 鉴定完毕。哈哈哈
: 当然王亚伟等还是很nb的。

S*I2014-01-13 08:01

7 楼

1040NR/1040NR-EZ if filing as nonresident alien, OR
1040NR + 1040 if filing as dual status, which has no significant benefit
over filing as nonresident alien if you're not married

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

: 我11年1月到7月F1，
: 7月到10月OPT，10月之后H1b，
: 是填1040NR还是1040NR-EZ ？能不能用resident alien？
: F1在美国第3年，
: 学校和公司二张W2是分开填吗？

t*u2014-01-13 08:01

8 楼

不知道俄罗斯解密解的咋样了

T*i2014-01-13 08:01

9 楼

对了，这个方案在有人退票后仍然最优。

z*y2014-01-13 08:01

10 楼

H1b没超过183天也可以用dual status吗？

【在 S**I 的大作中提到】

: 1040NR/1040NR-EZ if filing as nonresident alien, OR
: 1040NR + 1040 if filing as dual status, which has no significant benefit
: over filing as nonresident alien if you're not married

T*g2014-01-13 08:01

11 楼

这个下载巨慢。。

m*j2014-01-13 08:01

12 楼

你这个想法，初看起来似乎不错。
但对于在1秒钟之内会达到几百万次的查询来说，是非常无力的。
类比为现在有1万辆车准备过河，但只有2千辆可以过河，其他的8000辆连带司机都要被
炸死。
桥只有一座，你怎么修，也没用。

V。

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

: 假定一条线路从始至终一共m个区段，n个座位。
: 初始化：
: m个array：[0，n-1] with name SegMap
: memset to 0
: 输入：
: 任何时候有人购买了区段a,b。a <= b && 0 <= a <= m - 1 && 0 <= b <= m-1。
: 初始化array t[0, n - 1] = sum of SeqMap[from a to b]
: Search array t from 0 to n-1, find the first index with the minimum value V。
: If the minimum V > 0 then repeat the algo on "subsegments with which the
: seat has been taken"。

r*a2014-01-13 08:01

13 楼

可以，但是单身的dual-staus报税的数字结果和NR一样。所以为简单起见，单身就NR
报税。

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

: H1b没超过183天也可以用dual status吗？

p*n2014-01-13 08:01

14 楼

下了9小时

2010

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

: 【以下文字转载自 Game 讨论区】
: 发信人: siliq (外F：“白人至上”，“杀人是对的”), 信区: Game
: 标题: 太爽了。[SC2] 7月27号免费公测台服教程！ zz
: 发信站: BBS 未名空间站 (Sun Jul 25 14:36:07 2010, 美东)
: 不知道之前有人贴过没有。。。
: 对于我这样一个不对战只玩单机版的，连破解都省了
: 唯一美中不足的是过场动画需要听湾湾的台巴式配音
: ================
: 星际争霸2的beta测试已经结束，全球玩家都在等待游戏的正式发布时间北京时间2010
: 年7月27日凌晨0

T*i2014-01-13 08:01

15 楼

我的系统有一个抢票核心（一串单机）来对付每秒上百万请求。
外围还有state cache server来预先过滤。基本上是unlimited scalability。
核心架构：
http://www.mitbbs.com/article/Programming/31299347_0.html
确定抢到票后。再用这个算法实时分配车票。
一趟车也就顶多上千座位，需要多长时间计算？

【在 m**********j 的大作中提到】

: 你这个想法，初看起来似乎不错。
: 但对于在1秒钟之内会达到几百万次的查询来说，是非常无力的。
: 类比为现在有1万辆车准备过河，但只有2千辆可以过河，其他的8000辆连带司机都要被
: 炸死。
: 桥只有一座，你怎么修，也没用。
:
: V。

n*12014-01-13 08:01

16 楼

O(m * n)和单线程两个限制都不是很理想. 理论上至少有O(m * log(n))的算法, 而且
可以并行, 就像qsort能并行一样.
也许还能做到O(log(m) * log(n)), 但站点一般不会太大, 暂时可以不优化.
其实用啥C++/java, 单机数据库/机群数据库都无所谓, 模型和数据结构才是最重要的.

g*g2014-01-13 08:01

17 楼

每秒百万的请求过来时，让你往单机数据库里写helloworld都得挂，算法再好有啥用。
先把scalability解决了，算法是优化的事情。没听说过架构问题能用算法解决的。

的.

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

: O(m * n)和单线程两个限制都不是很理想. 理论上至少有O(m * log(n))的算法, 而且
: 可以并行, 就像qsort能并行一样.
: 也许还能做到O(log(m) * log(n)), 但站点一般不会太大, 暂时可以不优化.
: 其实用啥C++/java, 单机数据库/机群数据库都无所谓, 模型和数据结构才是最重要的.

T*i2014-01-13 08:01

18 楼

这种算法没研究过。貌似和qsort有类似之处。
像这种m，n都比较小的，并行可能反而代价更高。而且提高复杂度，不符合够用即行的
原则。
看你帖子，似乎也没有做过多核concurrency的工作。好像你说过担心过热损坏CPU之类
的话。其实我的系统，16个core有14个常年工作在100% CPU下。故意设计成这样的。
server设计的时候已经考虑好散热的问题。增加个1-200W功耗对我们来讲不算啥。
你的见识，应该另版上某些人汗颜。

的.

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

m*j2014-01-13 08:01

19 楼

记住，你说的这个每秒上百万次的请求。
每一个单独请求被处理后，数据库内跟这个单独请求相关联的信息都是要被重新更新的。
啥网站，都得挂。

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

: 我的系统有一个抢票核心（一串单机）来对付每秒上百万请求。
: 外围还有state cache server来预先过滤。基本上是unlimited scalability。
: 核心架构：
: http://www.mitbbs.com/article/Programming/31299347_0.html
: 确定抢到票后。再用这个算法实时分配车票。
: 一趟车也就顶多上千座位，需要多长时间计算？

n*12014-01-13 08:01

20 楼

我没说过IO架构不重要, IO架构在很多不同行业里都有需求, 所以IO分布式解决方案都
很成熟了. 这方面知识已经渐渐成为IT行业基本要求了. 我并不同意老魏的单机IO打天
下在12306是最好方案, 但我不想纠结这个问题, 也不会老想证明别人是外行.
我只是认为车票分配算法是铁路行业的domain specific logic, 同样重要.而且这种东
西没法找其他行业的先例做借鉴, 所以值得深入探讨.
我只是想探讨些实际问题罢了, 没想和你打嘴仗. 还有这个贴子标题是"最优化的实时
分配车票座位的算法", 你要谈IO去其他帖子好了.

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

: 每秒百万的请求过来时，让你往单机数据库里写helloworld都得挂，算法再好有啥用。
: 先把scalability解决了，算法是优化的事情。没听说过架构问题能用算法解决的。
:
: 的.

n*12014-01-13 08:01

21 楼

你这样搞, 离socket buffer overflow只有一步之遥啊. 也许你们搞trading的整天承
受风险已经惯了, 觉得这个没啥问题, 可首长不同意啊. 你的performance per dollar
再高人家也不买帐的.
n值小的话qsort未必最好,但一列车有一两千个座位, 一秒钟有几百万个request, 单机
很玄. 我还是宁可牺牲性能, 也要上并行保证稳定性的. qsort的并行版就是现在很火
的mapreduce. 这样我就可以只专注于算法/逻辑,不用重造轮子, 也不用担心
consistency/availability.
我的见识是挺浅薄的, 也没35岁, 你要鄙视我就鄙视好了.

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

: 这种算法没研究过。貌似和qsort有类似之处。
: 像这种m，n都比较小的，并行可能反而代价更高。而且提高复杂度，不符合够用即行的
: 原则。
: 看你帖子，似乎也没有做过多核concurrency的工作。好像你说过担心过热损坏CPU之类
: 的话。其实我的系统，16个core有14个常年工作在100% CPU下。故意设计成这样的。
: server设计的时候已经考虑好散热的问题。增加个1-200W功耗对我们来讲不算啥。
: 你的见识，应该另版上某些人汗颜。
:
: 的.

b*s2014-01-13 08:01

22 楼

你们高频的比较猛，我们一般是每个core到70%左右，线程数是core数量 * 2

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

b*s2014-01-13 08:01

23 楼

老魏的单机方案可以按车次切，一样可以分布，除了联票，车次间是低耦合
联票也有办法处理

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

: 我没说过IO架构不重要, IO架构在很多不同行业里都有需求, 所以IO分布式解决方案都
: 很成熟了. 这方面知识已经渐渐成为IT行业基本要求了. 我并不同意老魏的单机IO打天
: 下在12306是最好方案, 但我不想纠结这个问题, 也不会老想证明别人是外行.
: 我只是认为车票分配算法是铁路行业的domain specific logic, 同样重要.而且这种东
: 西没法找其他行业的先例做借鉴, 所以值得深入探讨.
: 我只是想探讨些实际问题罢了, 没想和你打嘴仗. 还有这个贴子标题是"最优化的实时
: 分配车票座位的算法", 你要谈IO去其他帖子好了.

n*12014-01-13 08:01

24 楼

当然可以按车次切, 但老魏貌似现在还在坚持单机, 你确定他肯接受你的补丁?
其次, 进来的request太多, 就算是单机负责一列车也很悬的. qsort是能把一列车上的
不同座位分布到不同机器上去, 然后并行运算的, 我感觉放心点.

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

: 老魏的单机方案可以按车次切，一样可以分布，除了联票，车次间是低耦合
: 联票也有办法处理

b*s2014-01-13 08:01

25 楼

o（m*n）会有一定压力，我说的还是那种存在很多碎片的o（1）的算法
而碎片从目前实践来说，最终都被短程乘客买走了，或者被你说的站票的坐了
所以基本上这个问题我把它的优先级降低，不放在当前必备功能里

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

: 当然可以按车次切, 但老魏貌似现在还在坚持单机, 你确定他肯接受你的补丁?
: 其次, 进来的request太多, 就算是单机负责一列车也很悬的. qsort是能把一列车上的
: 不同座位分布到不同机器上去, 然后并行运算的, 我感觉放心点.

b*s2014-01-13 08:01

26 楼

另外算法的稳定性你有没有测算过？

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

n*12014-01-13 08:01

27 楼

qsort不是mapreduce里面的helloworld么(除了更简单的word count)? 你说的是哪方面
稳定性?

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

: 另外算法的稳定性你有没有测算过？

b*s2014-01-13 08:01

28 楼

worst case

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

: qsort不是mapreduce里面的helloworld么(除了更简单的word count)? 你说的是哪方面
: 稳定性?

n*12014-01-13 08:01

29 楼

O(N^2), 这个wikipedia上能搜到的.

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

: worst case

b*s2014-01-13 08:01

30 楼

我知道，我只是问，你有没有考虑过这方面因素的影响

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

: O(N^2), 这个wikipedia上能搜到的.

b*s2014-01-13 08:01

31 楼

在实际系统中，算法稳定性有时是个工程问题，不只是定性就可以的

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

: O(N^2), 这个wikipedia上能搜到的.

n*12014-01-13 08:01

32 楼

1. 实践中qsort通常是表现非常好的, 我不觉得worst case O(n^2)有啥大不了的.
2. 我举qsort最关键在于提出了并行的可能性, 从而否定必须强耦合这个假设.
3. 肯定有比qsort更适合上mapreduce的方案, 好像有个terasort就很适合hadoop.
4. sort和寻找座位空隙还不是完全对应, 要思考的还有很多. 我是希望抛砖引玉, 不
是给终极方案. 这里面的水很深的.

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

: 我知道，我只是问，你有没有考虑过这方面因素的影响

b*s2014-01-13 08:01

33 楼

你认为强耦合具体是反映在什么上面？

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

: 1. 实践中qsort通常是表现非常好的, 我不觉得worst case O(n^2)有啥大不了的.
: 2. 我举qsort最关键在于提出了并行的可能性, 从而否定必须强耦合这个假设.
: 3. 肯定有比qsort更适合上mapreduce的方案, 好像有个terasort就很适合hadoop.
: 4. sort和寻找座位空隙还不是完全对应, 要思考的还有很多. 我是希望抛砖引玉, 不
: 是给终极方案. 这里面的水很深的.

n*12014-01-13 08:01

34 楼

...
强耦合一直是老魏的假设, which comes from no where. 我现在说明了整个系统中计
算最复杂的地方能实现并行, that is it!
你对强耦合的假设怎么看?

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

: 你认为强耦合具体是反映在什么上面？

b*s2014-01-13 08:01

35 楼

我同意老魏强耦合的观点，想听听你对强耦合是哪些因素在耦合的看法
因为你似乎也把强耦合当成了一个前提条件

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

: ...
: 强耦合一直是老魏的假设, which comes from no where. 我现在说明了整个系统中计
: 算最复杂的地方能实现并行, that is it!
: 你对强耦合的假设怎么看?

n*12014-01-13 08:01

36 楼

我是说希望做到实时计算余票量, 哪里用了强耦合的假设? 能把我说的话quote以下么?
强耦合是个负担, 不是啥好东西, 我为啥要把它当前提条件?

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

: 我同意老魏强耦合的观点，想听听你对强耦合是哪些因素在耦合的看法
: 因为你似乎也把强耦合当成了一个前提条件

b*s2014-01-13 08:01

37 楼

？可能我理解错你的意思了
如果没有强耦合，12306现在的方案显然就不是个最佳了

么?

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

: 我是说希望做到实时计算余票量, 哪里用了强耦合的假设? 能把我说的话quote以下么?
: 强耦合是个负担, 不是啥好东西, 我为啥要把它当前提条件?

n*12014-01-13 08:01

38 楼

我对老魏说的强耦合理解就是:
铁道业务逻辑只能同时利用一到两个线程. 如果你用了n个线程, 那么业务逻辑会使得
其中n-2个线程处于锁定状态. 所以机群不会比单机效率高.
现在不是用了17台机子么? 虽谈不上高度decouple,但离强耦合还是差很远吧.

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

: ？可能我理解错你的意思了
: 如果没有强耦合，12306现在的方案显然就不是个最佳了
:
: 么?

T*i2014-01-13 08:01

39 楼

我感觉我们沟通有问题。
我承认实时分配车票是最复杂的。
而且我在本主题第一贴已经说明"分配车票可以scale out”。也就是扔给其他机器去做。
其实我从来没纠结什么单机。只想说明有时候单机是最优解，没法选择。
至于强耦合。能避免就避免。这个我也没意见。但是有时后不能避免。
这个应用，什么是强耦合呢？我看只有抢票。这个抢票其实也能部分scale out，使用
state cache server先过滤一下实现的。
但是地但是，抢票核心还是强耦合的。我认为还是要用单机。
至于分配车票，又能够scale out了。
这是由于数据依赖性不同决定的。不以我们的意志为转移。

么?

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

: 我是说希望做到实时计算余票量, 哪里用了强耦合的假设? 能把我说的话quote以下么?
: 强耦合是个负担, 不是啥好东西, 我为啥要把它当前提条件?

T*i2014-01-13 08:01

40 楼

大家工作的领域不一样。我理解你说的socket buffer overflow什么意思。但是我的系
统保持CPU 100%有我的道理。
强实时系统，唯一的不确定性就是memory cache miss。我的系统有很多buffer，不只
socket buffer。确保不会overflow很简单。就是确保consumer比producer消耗的快。
我的系统，consumer的速率比producer的速率高一个数量级。就是为了提供足够的余量
。因此有任何buffer overflow检测到，直接crash，因为肯定是程序写错了。
至于socket buffer，其实最容易控制。TCP本身就有flow control，UDP实现一个也简
单。实际应用中，我们的message rate的上限都是已知的。因此设计起来很容易。
至于保持CPU 100%，主要是消除context switch。这个只有我这种系统才有这种需求。
大家做事情的思路完全不一样，没有可比性。我是用效率换延迟。你们不可能这么用。
至于你的见识，我挺佩服的。

dollar

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

: 我对老魏说的强耦合理解就是:
: 铁道业务逻辑只能同时利用一到两个线程. 如果你用了n个线程, 那么业务逻辑会使得
: 其中n-2个线程处于锁定状态. 所以机群不会比单机效率高.
: 现在不是用了17台机子么? 虽谈不上高度decouple,但离强耦合还是差很远吧.

T*i2014-01-13 08:01

41 楼

事实上，堆处理器核心也是一种scale out。
摩尔定律到了极限，要继续发展，就是要堆越来越多的核心。
多核和多机有啥区别？就是通信开销不一样么！多核有QPI bus。多机是ethernet或者
InfiniBand。
我的抢票核心，完全可以用多核。其实用多机可以不可以？也应该可以。但是通信的开
销并不低，因为要有distributed transaction manager。

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

n*12014-01-13 08:01

42 楼

AIO+while loop check么? 有点像用户态自旋锁的感觉, 100%就这么来的吧

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

: 大家工作的领域不一样。我理解你说的socket buffer overflow什么意思。但是我的系
: 统保持CPU 100%有我的道理。
: 强实时系统，唯一的不确定性就是memory cache miss。我的系统有很多buffer，不只
: socket buffer。确保不会overflow很简单。就是确保consumer比producer消耗的快。
: 我的系统，consumer的速率比producer的速率高一个数量级。就是为了提供足够的余量
: 。因此有任何buffer overflow检测到，直接crash，因为肯定是程序写错了。
: 至于socket buffer，其实最容易控制。TCP本身就有flow control，UDP实现一个也简
: 单。实际应用中，我们的message rate的上限都是已知的。因此设计起来很容易。
: 至于保持CPU 100%，主要是消除context switch。这个只有我这种系统才有这种需求。
: 大家做事情的思路完全不一样，没有可比性。我是用效率换延迟。你们不可能这么用。

b*s2014-01-13 08:01

43 楼

spin lock类似，对单个任务很小能快速释放的情况是比较高效的

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

: AIO+while loop check么? 有点像用户态自旋锁的感觉, 100%就这么来的吧

z*e2014-01-13 08:01

44 楼

然

【在 m**********j 的大作中提到】

T*i2014-01-13 08:01

45 楼

基本原则是这样。

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

: AIO+while loop check么? 有点像用户态自旋锁的感觉, 100%就这么来的吧

c*32014-01-13 08:01

46 楼

> 注意，换座不可避免的。但是可证明这是实时算法中最优化的。
这种假设不合理。如果车次不变，不同区段，会给不同座号吗？如果这样，多惨呀。7
，80岁的老太太，还要每隔几个站就换个车厢座位？从北京到广州，十几个站，最坏请
况下，每一站就要拎包换座，还要把座位上的原先的人赶走，得吵多少架呀。
买一张票，就一车次，难到上面印了一串座号？
如果考虑单程单一座号，抢票系统抢到票了，座号分配系统又告知无单一座号，怎么办
？出站票？
如果能后台批处理，把当天的票统一分配座号，另外通知，似乎对系统最好。但买票体
验差了，好容易抢到票了，还要老惦记着座位还没着落。
抢票系统必须要出单一座号才行。