n*****t
发帖数: 22014 | 1 假设这趟车从 A 站到 Z 站，每个车次、座类设一组队列，以始发站做索引，A-Y。
每个队列设 n-1 个子队列，表示终点站，既 AB, AC .....
初始状态，1000 张票都在 AZ，AK 出票后，本座席移到 KZ。如果再卖了一张 MO，则
KM 和 OZ 都有这张票。考虑覆盖的情况，出票后不检查其他队列中是否需要删除，而
在取队列时核查该票的 bitmap，重新 enqueue。
这个计算应该狠简单，稍微多占点内存。 |
z*******3
发帖数: 13709 | 2 老姜，你随便找个内存db，不用你钱
开源的到处都是，别抠门了 |
n*****t
发帖数: 22014 | 3 想糙了，出票的时候直接 requeue
【在 n*****t 的大作中提到】
: 假设这趟车从 A 站到 Z 站，每个车次、座类设一组队列，以始发站做索引，A-Y。
: 每个队列设 n-1 个子队列，表示终点站，既 AB, AC .....
: 初始状态，1000 张票都在 AZ，AK 出票后，本座席移到 KZ。如果再卖了一张 MO，则
: KM 和 OZ 都有这张票。考虑覆盖的情况，出票后不检查其他队列中是否需要删除，而
: 在取队列时核查该票的 bitmap，重新 enqueue。
: 这个计算应该狠简单，稍微多占点内存。
|
n*****t
发帖数: 22014 | 4 推荐一个能卖票的呗？
【在 z*******3 的大作中提到】
: 老姜，你随便找个内存db，不用你钱
: 开源的到处都是，别抠门了
|
n*****t
发帖数: 22014 | 5 再更正，出票的时候只做 enqueue，不做 dequeue。enqueue 简单，dequeue 还得先找
到对应的 queue 再搜索到这张票，开销大，宁可下次排到这张的时候再扔出去。
【在 n*****t 的大作中提到】
: 想糙了，出票的时候直接 requeue
|
g*****y
发帖数: 7271 | 6 应该参考飞机转机，大家到一站就四处换座位，换车厢。就没这么麻烦了，哈哈
【在 n*****t 的大作中提到】
: 假设这趟车从 A 站到 Z 站，每个车次、座类设一组队列，以始发站做索引，A-Y。
: 每个队列设 n-1 个子队列，表示终点站，既 AB, AC .....
: 初始状态，1000 张票都在 AZ，AK 出票后，本座席移到 KZ。如果再卖了一张 MO，则
: KM 和 OZ 都有这张票。考虑覆盖的情况，出票后不检查其他队列中是否需要删除，而
: 在取队列时核查该票的 bitmap，重新 enqueue。
: 这个计算应该狠简单，稍微多占点内存。
|
z*******3
发帖数: 13709 | 7 飞机的联程票座位在你第一次登机时候就决定了
所以一般我会被安排到第二次飞机上的安全位
【在 g*****y 的大作中提到】
: 应该参考飞机转机，大家到一站就四处换座位，换车厢。就没这么麻烦了，哈哈
|
n*****t
发帖数: 22014 | 8 飞机最多 1-2 stop，火车 20
【在 z*******3 的大作中提到】
: 飞机的联程票座位在你第一次登机时候就决定了
: 所以一般我会被安排到第二次飞机上的安全位
|
L*****e
发帖数: 8347 | 9 这个和我昨天想的差不多。我想的是：
建一个哈希表，以20个站为key（其实19个就够，每人会在终点站买票），value是the
list of tickets which have not been sold at this (key) station.
初始时，20个key map的list都含有所有1000张票。
接到一个请求时，以请求的起点到终点之间的所有站为key查哈希表，如果任何一个的
list为空，那么说明这个请求的票卖完了，买票失败。
如果所有站对应的list都不为空，那么表示这个请求一定有票。而且这所有站中最短的
那个list的head就是最优解的票。（这点是因为这个算法保证了最碎片的票在list里总
是排在最前面，而最短的list的head才能保证所有请求中的经过站都有这个座位的票）。
现在票找到了，要把这张票从请求经过站的lists中remove掉。从所有list的头开始去
找这张票很慢。所有再给每个list里的票弄个哈希表，key为座位号，value为座位在
list里的地址，并且初建list时建double list。于是只要知道要remove掉那个座位，
就可以在各个list里立刻找到这个座位并remove掉。
抛开所占内存的因素，现在来比较下这个办法和前面提到的bitmap的办法：
每次找座bitmap要做1000次比较，哈希表法只做最多20次比较。
座位找到后bitmap法只要一次运算更新，而哈希表法要做最多20次哈希查找 + 20 次
remove a member from a list。。。
我对remove from list和bitwise运算之间的效率比没有概念，谁能给科普一下，
remove one node from a list的时间可以做多少次bitwise运算？
【在 n*****t 的大作中提到】
: 假设这趟车从 A 站到 Z 站，每个车次、座类设一组队列，以始发站做索引，A-Y。
: 每个队列设 n-1 个子队列，表示终点站，既 AB, AC .....
: 初始状态，1000 张票都在 AZ，AK 出票后，本座席移到 KZ。如果再卖了一张 MO，则
: KM 和 OZ 都有这张票。考虑覆盖的情况，出票后不检查其他队列中是否需要删除，而
: 在取队列时核查该票的 bitmap，重新 enqueue。
: 这个计算应该狠简单，稍微多占点内存。
|
n*****t
发帖数: 22014 | 10 Remove node
prev->next = next, next->prev = prev, return current->ticket;
我这个队列更直观点吧，取队首即可
Ticket = head->ticket, head = head-> next, return ticket;
反正开销都可以忽略不计。
the
【在 L*****e 的大作中提到】
: 这个和我昨天想的差不多。我想的是：
: 建一个哈希表，以20个站为key（其实19个就够，每人会在终点站买票），value是the
: list of tickets which have not been sold at this (key) station.
: 初始时，20个key map的list都含有所有1000张票。
: 接到一个请求时，以请求的起点到终点之间的所有站为key查哈希表，如果任何一个的
: list为空，那么说明这个请求的票卖完了，买票失败。
: 如果所有站对应的list都不为空，那么表示这个请求一定有票。而且这所有站中最短的
: 那个list的head就是最优解的票。（这点是因为这个算法保证了最碎片的票在list里总
: 是排在最前面，而最短的list的head才能保证所有请求中的经过站都有这个座位的票）。
: 现在票找到了，要把这张票从请求经过站的lists中remove掉。从所有list的头开始去
|
n*****t
发帖数: 22014 | 11 另外，查找票的开销大了点，事先可以把票都放进队列，开机后一次初始化就可以了，
不用临时计算。
其实铁路的方法好像也差不多，上海到苏州剩几张，窗口都是知道的，不知道分配座位
的时候神马原则。
the
【在 L*****e 的大作中提到】
: 这个和我昨天想的差不多。我想的是：
: 建一个哈希表，以20个站为key（其实19个就够，每人会在终点站买票），value是the
: list of tickets which have not been sold at this (key) station.
: 初始时，20个key map的list都含有所有1000张票。
: 接到一个请求时，以请求的起点到终点之间的所有站为key查哈希表，如果任何一个的
: list为空，那么说明这个请求的票卖完了，买票失败。
: 如果所有站对应的list都不为空，那么表示这个请求一定有票。而且这所有站中最短的
: 那个list的head就是最优解的票。（这点是因为这个算法保证了最碎片的票在list里总
: 是排在最前面，而最短的list的head才能保证所有请求中的经过站都有这个座位的票）。
: 现在票找到了，要把这张票从请求经过站的lists中remove掉。从所有list的头开始去
|
L*****e
发帖数: 8347 | 12 对于某个站，要remove的是队首，但是某些站，那张ticket在队中呀。还是说我理解错
了你的算法？
【在 n*****t 的大作中提到】
: Remove node
: prev->next = next, next->prev = prev, return current->ticket;
: 我这个队列更直观点吧，取队首即可
: Ticket = head->ticket, head = head-> next, return ticket;
: 反正开销都可以忽略不计。
:
: the
|
n*****t
发帖数: 22014 | 13 我的队列取票的时候只 remove 直接对应的，不去查间接相关的，慢
取票的时候，核实一下这张票的 bitmap，如果发现因为卖了其他区段导致无效了，直
接扔出去。bitmap mask 是固定的，and 一下就完事了。
【在 L*****e 的大作中提到】
: 对于某个站，要remove的是队首，但是某些站，那张ticket在队中呀。还是说我理解错
: 了你的算法？
|
