n**x
发帖数: 606 | 1 前言：
其实问题讨论到这里已经不在是个争出个你死我活了。一开始双方的需求根本没有统一
，所以吵了半天都是你说你的，我说我的。 现在需求逐步走向统一，很多人也在群策
群力帮老魏改进优化他那个计数器。 其实大的的目的都一样，看看能不能找到一个最
简， 最优的方案。难道这不是所有码工的目标吗？
问题： 古德霸的老农民坐了一半火车需要拎着行李去找下个区段座位的问题。
我的想法是这样的：
原来老魏的计数器其的实质是一个二维数组. 1000条线，每条线20个区段，每个区段
1000个座位。 表示为 int[1000,20]即可，每个元素初始为 1000. 做减法即可。
现在要求一张票不能换座位，那其实就把这个二维数组变成了三维。 这个第三维包括
了座位号1到1000数组。 1表示有空，0表示已卖。
计算过程的本质还是inlocked加减法. 过程如下：
- 北京-〉济南 这段包括3个区段：
- 从座位号1开始遍历一直到座位号1000, 对每个座位号遍历途经的3个区段，如果该区
段该座位可用则interlocked.decrement到0（已售出). 如果每个区段该票都可用则出
票.
结论：
计数器还是计数器。只是计算增加了复杂度。 但本质还是计算，还是不带锁。老魏的
硬件足够强的话性能也是不错的。
我的分析对吗？ |
L*****e
发帖数: 8347 | 2 复杂的地方在于找座要最优，即实时碎片最小。
你的三维数组的data structure，如果座位号不能根据沿线是否此座卖出进行某种形式
的sort的话，那么worst case会是你要对19个沿途站此座是否卖出扫描，扫到最后此座
卖出，你得依次对1000个座号扫描，这就是19000次运算，即使你扫到一个满足要求的
，你也不知道是否最优，还得接着扫。。。当然，这是野蛮算法。。。
我有一个想法，把某座位号在沿途所有站是否卖出用一个20位二进制数表示，有座是1
，无座是0。然后把买票请求从拿站到哪站也用一个20位二进制数表示，经过的站的位
置用1，不经过的站是0。这样一次bitwise的运算就可以知道所要买区段该座位是否都
空，
并可以决定该次运算的结果是否可以用来更新所有的站的该座位是否卖出的情况。
如果能对这1000个二进制数跟据01分别情况做某种sort，或者引入哈嘻表，能够做最优
解的mapping，就能大大减少计算复杂度。。。
★ 发自iPhone App: ChineseWeb 8.2.2
★ 发自iPhone App: ChineseWeb 8.2.2
【在 n**x 的大作中提到】
: 前言：
: 其实问题讨论到这里已经不在是个争出个你死我活了。一开始双方的需求根本没有统一
: ，所以吵了半天都是你说你的，我说我的。 现在需求逐步走向统一，很多人也在群策
: 群力帮老魏改进优化他那个计数器。 其实大的的目的都一样，看看能不能找到一个最
: 简， 最优的方案。难道这不是所有码工的目标吗？
: 问题： 古德霸的老农民坐了一半火车需要拎着行李去找下个区段座位的问题。
: 我的想法是这样的：
: 原来老魏的计数器其的实质是一个二维数组. 1000条线，每条线20个区段，每个区段
: 1000个座位。 表示为 int[1000,20]即可，每个元素初始为 1000. 做减法即可。
: 现在要求一张票不能换座位，那其实就把这个二维数组变成了三维。 这个第三维包括
|
t**********1
发帖数: 550 | 3 多谢左眼，其实我也是要用bit map的。
但是，具体算法讨论宜粗不宜细。让人家学去了，还回头嘲笑你初中水平。
1
【在 L*****e 的大作中提到】
: 复杂的地方在于找座要最优，即实时碎片最小。
: 你的三维数组的data structure，如果座位号不能根据沿线是否此座卖出进行某种形式
: 的sort的话，那么worst case会是你要对19个沿途站此座是否卖出扫描，扫到最后此座
: 卖出，你得依次对1000个座号扫描，这就是19000次运算，即使你扫到一个满足要求的
: ，你也不知道是否最优，还得接着扫。。。当然，这是野蛮算法。。。
: 我有一个想法，把某座位号在沿途所有站是否卖出用一个20位二进制数表示，有座是1
: ，无座是0。然后把买票请求从拿站到哪站也用一个20位二进制数表示，经过的站的位
: 置用1，不经过的站是0。这样一次bitwise的运算就可以知道所要买区段该座位是否都
: 空，
: 并可以决定该次运算的结果是否可以用来更新所有的站的该座位是否卖出的情况。
|
g****t
发帖数: 31659 | 4 你没考虑系统延时吧。
简单的说，比如一个人，不停的买了退。周期性的。
另一个人不停的退了买。周期性的。
这两人到计数器的信号，分别延时t1,t2.
系统的响应好像就可以很复杂。
复杂的地方在于找座要最优，即实时碎片最小。
你的三维数组的data structure，如果座位号不能根据沿线是否此座卖出进行某种形式
的sort的话，那么worst case会是你要对19个沿途站此座是否卖出扫描，扫到最后此座
卖出，你得依次对1000个座号扫描，这就是19000次运算，即使你扫到一个满足要求的
，你也不知道是否最优，还得接着扫。。。当然，这是野蛮算法。。。
我有一个想法，把某座位号在沿途所有站是否卖出用一个20位二进制数表示，有座是1
，无座是0。然后把买票请求从拿站到哪站也用一个20位二进制数表示，经过的站的位
置用1，不经过的站是0。这样一次bitwise的运算就把所有的位置的座位情况更新了。
如果能对这1000个二进制数跟据01分别情况做某种sort，或者引入哈嘻表，能够做最优
解的mapping，就能大大减少计算复杂度。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 L*****e 的大作中提到】
: 复杂的地方在于找座要最优，即实时碎片最小。
: 你的三维数组的data structure，如果座位号不能根据沿线是否此座卖出进行某种形式
: 的sort的话，那么worst case会是你要对19个沿途站此座是否卖出扫描，扫到最后此座
: 卖出，你得依次对1000个座号扫描，这就是19000次运算，即使你扫到一个满足要求的
: ，你也不知道是否最优，还得接着扫。。。当然，这是野蛮算法。。。
: 我有一个想法，把某座位号在沿途所有站是否卖出用一个20位二进制数表示，有座是1
: ，无座是0。然后把买票请求从拿站到哪站也用一个20位二进制数表示，经过的站的位
: 置用1，不经过的站是0。这样一次bitwise的运算就可以知道所要买区段该座位是否都
: 空，
: 并可以决定该次运算的结果是否可以用来更新所有的站的该座位是否卖出的情况。
|
L*****e
发帖数: 8347 | 5 没听懂，说的是实时找座，和一个人退了买，买了退有啥关系？买和退本来就是两个不
同的transactions。。。还是你想说多线程的情况下要对bit map上锁？那是肯定的。
。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 g****t 的大作中提到】
: 你没考虑系统延时吧。
: 简单的说，比如一个人，不停的买了退。周期性的。
: 另一个人不停的退了买。周期性的。
: 这两人到计数器的信号，分别延时t1,t2.
: 系统的响应好像就可以很复杂。
:
: 复杂的地方在于找座要最优，即实时碎片最小。
: 你的三维数组的data structure，如果座位号不能根据沿线是否此座卖出进行某种形式
: 的sort的话，那么worst case会是你要对19个沿途站此座是否卖出扫描，扫到最后此座
: 卖出，你得依次对1000个座号扫描，这就是19000次运算，即使你扫到一个满足要求的
|
g****t
发帖数: 31659 | 6 回错篇了。
【在 L*****e 的大作中提到】
: 没听懂，说的是实时找座，和一个人退了买，买了退有啥关系？买和退本来就是两个不
: 同的transactions。。。还是你想说多线程的情况下要对bit map上锁？那是肯定的。
: 。。
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
g****t
发帖数: 31659 | 7 这个是对的。
要求不换座，那就把座位的信息按同样原理弄成计数器就好。
前言：
其实问题讨论到这里已经不在是个争出个你死我活了。一开始双方的需求根本没有统一
，所以吵了半天都是你说你的，我说我的。 现在需求逐步走向统一，很多人也在群策
群力帮老魏改进优化他那个计数器。 其实大的的目的都一样，看看能不能找到一个最
简， 最优的方案。难道这不是所有码工的目标吗？
问题： 古德霸的老农民坐了一半火车需要拎着行李去找下个区段座位的问题。
我的想法是这样的：
原来老魏的计数器其的实质是一个二维数组. 1000条线，每条线20个区段，每个区段
1000个座位。 表示为 int[1000,20]即可，每个元素初始为 1000. 做减法即可。
现在要求一张票不能换座位，那其实就把这个二维数组变成了三维。 这个第三维包括
了座位号1到1000数组。 1表示有空，0表示已卖。
计算过程的本质还是inlocked加减法. 过程如下：
- 北京-〉济南 这段包括3个区段：
- 从座位号1开始遍历一直到座位号1000, 对每个座位号遍历途经的3个区段，如果该区
段该座位可用则interlocked.decrement到0（已售出). 如果每个区段该票都可用则出
票.
结论：
计数器还是计数器。只是计算增加了复杂度。 但本质还是计算，还是不带锁。老魏的
硬件足够强的话性能也是不错的。
我的分析对吗？
【在 n**x 的大作中提到】
: 前言：
: 其实问题讨论到这里已经不在是个争出个你死我活了。一开始双方的需求根本没有统一
: ，所以吵了半天都是你说你的，我说我的。 现在需求逐步走向统一，很多人也在群策
: 群力帮老魏改进优化他那个计数器。 其实大的的目的都一样，看看能不能找到一个最
: 简， 最优的方案。难道这不是所有码工的目标吗？
: 问题： 古德霸的老农民坐了一半火车需要拎着行李去找下个区段座位的问题。
: 我的想法是这样的：
: 原来老魏的计数器其的实质是一个二维数组. 1000条线，每条线20个区段，每个区段
: 1000个座位。 表示为 int[1000,20]即可，每个元素初始为 1000. 做减法即可。
: 现在要求一张票不能换座位，那其实就把这个二维数组变成了三维。 这个第三维包括
|
L*****e
发帖数: 8347 | 8 互相学习。
其实如果能以初中生都懂的知识解决别人不能解决的问题，那是更牛B。乔峰用降龙十
八掌打赢鸠摩智不稀奇，用太祖长拳灭了他才牛得一塌糊涂。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 t**********1 的大作中提到】
: 多谢左眼，其实我也是要用bit map的。
: 但是，具体算法讨论宜粗不宜细。让人家学去了，还回头嘲笑你初中水平。
:
: 1
|
t**********1
发帖数: 550 | 9 本来我用的都是初中生就懂的技术，至于我们是不是说出来就是另外一回事了。
【在 L*****e 的大作中提到】
: 互相学习。
: 其实如果能以初中生都懂的知识解决别人不能解决的问题，那是更牛B。乔峰用降龙十
: 八掌打赢鸠摩智不稀奇，用太祖长拳灭了他才牛得一塌糊涂。。。
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
g****t
发帖数: 31659 | 10 如果加一条政策，网上买票的必须2小时之后才能退票。
会不会对搜索寻优有帮助？
互相学习。
其实如果能以初中生都懂的知识解决别人不能解决的问题，那是更牛B。乔峰用降龙十
八掌打赢鸠摩智不稀奇，用太祖长拳灭了他才牛得一塌糊涂。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 L*****e 的大作中提到】
: 互相学习。
: 其实如果能以初中生都懂的知识解决别人不能解决的问题，那是更牛B。乔峰用降龙十
: 八掌打赢鸠摩智不稀奇，用太祖长拳灭了他才牛得一塌糊涂。。。
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
|
|
d***a
发帖数: 13752 | 11 bitmap的办法我做了，只做票的调度，暂时不考虑联票，单线程可以达到285M/s。
1
【在 L*****e 的大作中提到】
: 复杂的地方在于找座要最优，即实时碎片最小。
: 你的三维数组的data structure，如果座位号不能根据沿线是否此座卖出进行某种形式
: 的sort的话，那么worst case会是你要对19个沿途站此座是否卖出扫描，扫到最后此座
: 卖出，你得依次对1000个座号扫描，这就是19000次运算，即使你扫到一个满足要求的
: ，你也不知道是否最优，还得接着扫。。。当然，这是野蛮算法。。。
: 我有一个想法，把某座位号在沿途所有站是否卖出用一个20位二进制数表示，有座是1
: ，无座是0。然后把买票请求从拿站到哪站也用一个20位二进制数表示，经过的站的位
: 置用1，不经过的站是0。这样一次bitwise的运算就可以知道所要买区段该座位是否都
: 空，
: 并可以决定该次运算的结果是否可以用来更新所有的站的该座位是否卖出的情况。
|
L*****e
发帖数: 8347 | 12 啥时候退票没有影响。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 g****t 的大作中提到】
: 如果加一条政策，网上买票的必须2小时之后才能退票。
: 会不会对搜索寻优有帮助？
:
: 互相学习。
: 其实如果能以初中生都懂的知识解决别人不能解决的问题，那是更牛B。乔峰用降龙十
: 八掌打赢鸠摩智不稀奇，用太祖长拳灭了他才牛得一塌糊涂。。。
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
n**x
发帖数: 606 | 13 我还没想出怎么bitwise操作，如果是要在车段见做就意味着要对车段和座位上锁。一
旦上锁性能就很难说了吧
1
【在 L*****e 的大作中提到】
: 复杂的地方在于找座要最优，即实时碎片最小。
: 你的三维数组的data structure，如果座位号不能根据沿线是否此座卖出进行某种形式
: 的sort的话，那么worst case会是你要对19个沿途站此座是否卖出扫描，扫到最后此座
: 卖出，你得依次对1000个座号扫描，这就是19000次运算，即使你扫到一个满足要求的
: ，你也不知道是否最优，还得接着扫。。。当然，这是野蛮算法。。。
: 我有一个想法，把某座位号在沿途所有站是否卖出用一个20位二进制数表示，有座是1
: ，无座是0。然后把买票请求从拿站到哪站也用一个20位二进制数表示，经过的站的位
: 置用1，不经过的站是0。这样一次bitwise的运算就可以知道所要买区段该座位是否都
: 空，
: 并可以决定该次运算的结果是否可以用来更新所有的站的该座位是否卖出的情况。
|
b*******s
发帖数: 5216 | 14 这不就是我的方案嘛
1
【在 L*****e 的大作中提到】
: 复杂的地方在于找座要最优，即实时碎片最小。
: 你的三维数组的data structure，如果座位号不能根据沿线是否此座卖出进行某种形式
: 的sort的话，那么worst case会是你要对19个沿途站此座是否卖出扫描，扫到最后此座
: 卖出，你得依次对1000个座号扫描，这就是19000次运算，即使你扫到一个满足要求的
: ，你也不知道是否最优，还得接着扫。。。当然，这是野蛮算法。。。
: 我有一个想法，把某座位号在沿途所有站是否卖出用一个20位二进制数表示，有座是1
: ，无座是0。然后把买票请求从拿站到哪站也用一个20位二进制数表示，经过的站的位
: 置用1，不经过的站是0。这样一次bitwise的运算就可以知道所要买区段该座位是否都
: 空，
: 并可以决定该次运算的结果是否可以用来更新所有的站的该座位是否卖出的情况。
|
b*******s
发帖数: 5216 | 15 compare & exchange，最直观了
【在 n**x 的大作中提到】
: 我还没想出怎么bitwise操作，如果是要在车段见做就意味着要对车段和座位上锁。一
: 旦上锁性能就很难说了吧
:
: 1
|
g****t
发帖数: 31659 | 16 性能能行吗？如果用compare &exchange
【在 b*******s 的大作中提到】
: compare & exchange，最直观了
|
L*****e
发帖数: 8347 | 17 应该影响不大，即使是多线程，不同thread可以先查不同的座位号，不用排队按同样的
顺序查。总不会有1000个线程把1000个bit map都锁住，然后后面的等待。。。而且一
个bitwise的运算也可以做个原子操作吧？
用几个thread能达到最优，可能需要调试一下才知道。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 n**x 的大作中提到】
: 我还没想出怎么bitwise操作，如果是要在车段见做就意味着要对车段和座位上锁。一
: 旦上锁性能就很难说了吧
:
: 1
|
b*******s
发帖数: 5216 | 18 原子性的，不用锁
【在 g****t 的大作中提到】
: 性能能行吗？如果用compare &exchange
|
b*******s
发帖数: 5216 | 19 先查地址（票地址由车次，车厢，座位生成），然后对一个32-bit或64bit做原子操作
【在 g****t 的大作中提到】
: 性能能行吗？如果用compare &exchange
|
L*****e
发帖数: 8347 | 20 哦，没看到啊，对不住算我剽窃了。。。大家想想怎么能一次map到最优解？或者把可
能有最优姐的范围缩小？
★ 发自iPhone App: ChineseWeb 8.2.2
【在 b*******s 的大作中提到】
: 这不就是我的方案嘛
:
: 1
|
|
|
b*******s
发帖数: 5216 | 21 不过我那个没有做座位优化，这方面你可以随便发挥
【在 L*****e 的大作中提到】
: 哦，没看到啊，对不住算我剽窃了。。。大家想想怎么能一次map到最优解？或者把可
: 能有最优姐的范围缩小？
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
b*******s
发帖数: 5216 | 22 前几天我在你一个帖子上把我那个方案的链接给你了
你找找看
【在 L*****e 的大作中提到】
: 哦，没看到啊，对不住算我剽窃了。。。大家想想怎么能一次map到最优解？或者把可
: 能有最优姐的范围缩小？
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
L*****e
发帖数: 8347 | 23 好，我找出来看看。。。水实在太大了。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 b*******s 的大作中提到】
: 前几天我在你一个帖子上把我那个方案的链接给你了
: 你找找看
|
d***a
发帖数: 13752 | 24 如果是一票一座，最优解恐怕是NP-hard的问题了。
可以做一些heuristic的优化，比如说选空闲区段最少的座位。不过，这样的话，用
bitmap方式的效率就会降下来不少，因为那个没法用bitmap来做。
【在 L*****e 的大作中提到】
: 哦，没看到啊，对不住算我剽窃了。。。大家想想怎么能一次map到最优解？或者把可
: 能有最优姐的范围缩小？
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
b*******s
发帖数: 5216 | 25 直接让乘客订票时选座就是了
【在 d***a 的大作中提到】
: 如果是一票一座，最优解恐怕是NP-hard的问题了。
: 可以做一些heuristic的优化，比如说选空闲区段最少的座位。不过，这样的话，用
: bitmap方式的效率就会降下来不少，因为那个没法用bitmap来做。
|
d***a
发帖数: 13752 | 26 乘客肯定是选比较好的座位，比如说靠窗口的。
在非高峰期，是应该让乘客来选。
【在 b*******s 的大作中提到】
: 直接让乘客订票时选座就是了
|
b*******s
发帖数: 5216 | 27 其实bitmap相对计数器有个好处，就是计数器没法估计有多少票
比如从上海到北京20个站，一个座位可以卖一张，也能卖19张
【在 d***a 的大作中提到】
: 乘客肯定是选比较好的座位，比如说靠窗口的。
: 在非高峰期，是应该让乘客来选。
|
L*****e
发帖数: 8347 | 28 没那么夸张，也就是一个P问题，暴力地和1000个bitmap比一遍，就一定知道有解无解
及最优解。也就是个O（N）的P问题而已。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 d***a 的大作中提到】
: 如果是一票一座，最优解恐怕是NP-hard的问题了。
: 可以做一些heuristic的优化，比如说选空闲区段最少的座位。不过，这样的话，用
: bitmap方式的效率就会降下来不少，因为那个没法用bitmap来做。
|
t**********1
发帖数: 550 | 29 下面是好虫的要求。我同意的。
举个例子，就是假定当前所有票的线段数是N（连着的算一段)，一个request进来，要
满足分配之后N'最小。其次，在N'一样的前提下，要从一个长度最短的线段里取。线段
长度一样可以任取一个。
这简单bruteforce最差情况是个O(N)的算法，N是座位数。
【在 d***a 的大作中提到】
: 如果是一票一座，最优解恐怕是NP-hard的问题了。
: 可以做一些heuristic的优化，比如说选空闲区段最少的座位。不过，这样的话，用
: bitmap方式的效率就会降下来不少，因为那个没法用bitmap来做。
|
b*******s
发帖数: 5216 | 30 不要自动分票，直接让用户自己选，这是最简单的实践，用户要走掉，会自己尽量填上的
用户体验还好
【在 L*****e 的大作中提到】
: 没那么夸张，也就是一个P问题，暴力地和1000个bitmap比一遍，就一定知道有解无解
: 及最优解。也就是个O（N）的P问题而已。。。
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
|
|
d***a
发帖数: 13752 | 31 啊，我说的不清楚。你和goodbug说的是从当前状态出一张票。
我想说的是，如果给出所有的M个request，要求算法出最多张的票，凭直觉说，这是个
NP-hard的问题。
【在 t**********1 的大作中提到】
: 下面是好虫的要求。我同意的。
: 举个例子，就是假定当前所有票的线段数是N（连着的算一段)，一个request进来，要
: 满足分配之后N'最小。其次，在N'一样的前提下，要从一个长度最短的线段里取。线段
: 长度一样可以任取一个。
: 这简单bruteforce最差情况是个O(N)的算法，N是座位数。
|
L*****e
发帖数: 8347 | 32 他们说的是实时最优姐，不是全局最优姐。。。
★ 发自iPhone App: ChineseWeb 8.2.2
【在 d***a 的大作中提到】
: 啊，我说的不清楚。你和goodbug说的是从当前状态出一张票。
: 我想说的是，如果给出所有的M个request，要求算法出最多张的票，凭直觉说，这是个
: NP-hard的问题。
|
d***a
发帖数: 13752 | 33 而且bitmap可以立即给出座位，也可以保证一票一座
计数器的想法新颖，只是要另一个算法来给座位
并且如goodbug所说，会出现要换座位的情况
但好处在于有可能可以出更多的票
【在 b*******s 的大作中提到】
: 其实bitmap相对计数器有个好处，就是计数器没法估计有多少票
: 比如从上海到北京20个站，一个座位可以卖一张，也能卖19张
|
d***a
发帖数: 13752 | 34 说白了就是这样。
【在 L*****e 的大作中提到】
: 他们说的是实时最优姐，不是全局最优姐。。。
:
: ★ 发自iPhone App: ChineseWeb 8.2.2
|
c****3
发帖数: 10787 | 35 好像有个简单方法，就是消耗点内存。
简单点用a-b-c-d四个区段说明，按照火车行驶方向，有a-b-c-d, a-b-c, a-b, b-c-d,
b-c, c-d, 这5个可能的区段。这5个区段每个，准备一个数组，有1000张票的空位。
每个数组有个指针，指着剩余票的尾巴。
刚开始所以票都在a-b-c-d数组里，填满这1000个位置，有1000张票。其他数组都是空
的，没有一张票。如果卖掉一张票，就把数组里剩余票尾向前移一位。如果有人买c-d
的票，先找c-d数组里有没有票，如果没有，就从a-b-c-d数组里取走一张票，因为a-b-
c是剩下的空位，把这个空位添加到a-b-c数组里去。 |
b*******g
发帖数: 603 | 36 没有那么做的，既然是抢票，就有先来后到。你实现了全局最大化反而是错的。
【在 d***a 的大作中提到】
: 啊，我说的不清楚。你和goodbug说的是从当前状态出一张票。
: 我想说的是，如果给出所有的M个request，要求算法出最多张的票，凭直觉说，这是个
: NP-hard的问题。
|
b*******g
发帖数: 603 | 37 新颖？LOL，作设计第一步，就要先想好哪些需求是可以妥协，哪些需求不可以妥协。
老弱病残抗大包这种天才想法我是没脸提。
【在 d***a 的大作中提到】
: 而且bitmap可以立即给出座位，也可以保证一票一座
: 计数器的想法新颖，只是要另一个算法来给座位
: 并且如goodbug所说，会出现要换座位的情况
: 但好处在于有可能可以出更多的票
|
d***a
发帖数: 13752 | 38 呵呵，做研究看问题的角度比较自由。明明这里有无数的研究问题，可以写N个
proposal。:)
【在 b*******g 的大作中提到】
: 没有那么做的，既然是抢票，就有先来后到。你实现了全局最大化反而是错的。
|
n*****t
发帖数: 22014 | 39 碎片最小之类的实在无聊，车站卖票的时候，票姐还拿个算盘给铁道部琢磨出哪张好？
实际情况，碎片本身就是列车长的外快来源之一。
如果纯好玩琢磨一下我没意见
【在 n**x 的大作中提到】
: 前言：
: 其实问题讨论到这里已经不在是个争出个你死我活了。一开始双方的需求根本没有统一
: ，所以吵了半天都是你说你的，我说我的。 现在需求逐步走向统一，很多人也在群策
: 群力帮老魏改进优化他那个计数器。 其实大的的目的都一样，看看能不能找到一个最
: 简， 最优的方案。难道这不是所有码工的目标吗？
: 问题： 古德霸的老农民坐了一半火车需要拎着行李去找下个区段座位的问题。
: 我的想法是这样的：
: 原来老魏的计数器其的实质是一个二维数组. 1000条线，每条线20个区段，每个区段
: 1000个座位。 表示为 int[1000,20]即可，每个元素初始为 1000. 做减法即可。
: 现在要求一张票不能换座位，那其实就把这个二维数组变成了三维。 这个第三维包括
|
n**x
发帖数: 606 | 40 这个问题是很实际的一个问题，没有火车票上印多个座位号的呀，对吧
【在 n*****t 的大作中提到】
: 碎片最小之类的实在无聊，车站卖票的时候，票姐还拿个算盘给铁道部琢磨出哪张好？
: 实际情况，碎片本身就是列车长的外快来源之一。
: 如果纯好玩琢磨一下我没意见
|
|
|
n**x
发帖数: 606 | 41 北京到上海一趟慢车有一二十个区段怎么半办那
d,
d
b-
【在 c****3 的大作中提到】
: 好像有个简单方法，就是消耗点内存。
: 简单点用a-b-c-d四个区段说明，按照火车行驶方向，有a-b-c-d, a-b-c, a-b, b-c-d,
: b-c, c-d, 这5个可能的区段。这5个区段每个，准备一个数组，有1000张票的空位。
: 每个数组有个指针，指着剩余票的尾巴。
: 刚开始所以票都在a-b-c-d数组里，填满这1000个位置，有1000张票。其他数组都是空
: 的，没有一张票。如果卖掉一张票，就把数组里剩余票尾向前移一位。如果有人买c-d
: 的票，先找c-d数组里有没有票，如果没有，就从a-b-c-d数组里取走一张票，因为a-b-
: c是剩下的空位，把这个空位添加到a-b-c数组里去。
|
n*****t
发帖数: 22014 | 42 换座当然不现实，但最优化出票更不现实。后果和前因的关系，一定要最优，只能换座。
【在 n**x 的大作中提到】
: 这个问题是很实际的一个问题，没有火车票上印多个座位号的呀，对吧
|
n**x
发帖数: 606 | 43 想通了。 你这个方法最好。 效率也很高。 人多真是力量大。
1
【在 L*****e 的大作中提到】
: 复杂的地方在于找座要最优，即实时碎片最小。
: 你的三维数组的data structure，如果座位号不能根据沿线是否此座卖出进行某种形式
: 的sort的话，那么worst case会是你要对19个沿途站此座是否卖出扫描，扫到最后此座
: 卖出，你得依次对1000个座号扫描，这就是19000次运算，即使你扫到一个满足要求的
: ，你也不知道是否最优，还得接着扫。。。当然，这是野蛮算法。。。
: 我有一个想法，把某座位号在沿途所有站是否卖出用一个20位二进制数表示，有座是1
: ，无座是0。然后把买票请求从拿站到哪站也用一个20位二进制数表示，经过的站的位
: 置用1，不经过的站是0。这样一次bitwise的运算就可以知道所要买区段该座位是否都
: 空，
: 并可以决定该次运算的结果是否可以用来更新所有的站的该座位是否卖出的情况。
|
c****3
发帖数: 10787 | 44 每个可能的区段做一个数组，所以会有几百个数组。这种方法查找的速度快，就是占内
存。
也可以用复杂一点的方法，节省点内存。每个区段数组用16个64 bit的字表示1000个座
位，1表示有空位置的票，0表示没有。然后再用一个32bit word的前16位表示那16个
64 bit 字在那个里面有空位。
原理简单，就是开始票都是从头到尾连续的。每次卖掉一张区段票，就剩下一段或者两
段，不连续的分片区段票。把这些不连续的区段票，放到相应以分片区段路线表示的数
组里。下次有人需要这些分片票，直接从这些分片区段数组里取。不用去扫所有的位置
找分片区段的票。
【在 n**x 的大作中提到】
: 北京到上海一趟慢车有一二十个区段怎么半办那
:
: d,
: d
: b-
|
n*****t
发帖数: 22014 | 45 我打算用 2 级索引队列加 bitmap，速度最快，内存反正不是问题
【在 c****3 的大作中提到】
: 每个可能的区段做一个数组，所以会有几百个数组。这种方法查找的速度快，就是占内
: 存。
: 也可以用复杂一点的方法，节省点内存。每个区段数组用16个64 bit的字表示1000个座
: 位，1表示有空位置的票，0表示没有。然后再用一个32bit word的前16位表示那16个
: 64 bit 字在那个里面有空位。
: 原理简单，就是开始票都是从头到尾连续的。每次卖掉一张区段票，就剩下一段或者两
: 段，不连续的分片区段票。把这些不连续的区段票，放到相应以分片区段路线表示的数
: 组里。下次有人需要这些分片票，直接从这些分片区段数组里取。不用去扫所有的位置
: 找分片区段的票。
|
