📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3049| 回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

Google : Re-order data packets

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
应用程序的re-order的buffer的设计,如果满了可以丢弃
大概是应用程序需要in order的数据包,但是收到的数据可能是乱序的
(类似于IP分片,每一个数据片有一个序列号,但是不同的数据片
到达应用程序的顺序可能和发送的顺序不一样,引起乱序, 但是不会太夸张的乱序, 第一个数据包不会跑到第一万个以后)。如何设计算法通过这个buffer
把数据片变成有序。

上一篇:《编译原理》到底是做什么的?
下一篇:Google : Combine intervals
🔗
 楼主| wwwyhx 2011-9-12 02:54:57 | 只看该作者
全局:
最小堆(序号)装buffer, 每次把buffer放进去, 然后一个个的顺序取序号最小的buffer, 不知道有没有更好的解
回复

使用道具 举报

🔗
yjyongz 2011-12-12 04:14:36 | 只看该作者
全局:
感觉用bucket sort 比较好
因为这个到达的id的 顺序跟 发送的顺序接近。。
所以 要发 N*M个包的话。。我们 构造 M个 bucket 每个bucket 容纳 N个
1~N 第一个桶 N+1~2N 第二个桶。。。。
一旦packet到达之后 如果某个桶塞满了。。立即做quicksort。。直到所有的桶排序完毕后 concatenate即可
空间复杂度是  packet的#的数量
时间复杂度是 (N*logN) 因为先满 先sort。。所以是N*logN
回复

使用道具 举报

🔗
3vilCoder 2011-12-14 09:21:24 | 只看该作者
全局:
我怎么感觉是insertion sort,既然说乱序不会太夸张,那么insertion sort的时间复杂度应该是O(nk),k为乱序的元素与它应该在的位置的最大距离。
回复

使用道具 举报

🔗
nooneknow 2011-12-14 12:29:38 | 只看该作者
全局:
最小堆(序号)装buffer, 每次把buffer放进去, 然后一个个的顺序取序号最小的buffer, 不知道有没有更好的解
wwwyhx 发表于 2011-9-12 02:54


heap很多时候都挺好的,不过这个可以更优化。

假设packet乱序最远的距离是K。用一个大小为K的circular queue。
假设packet no为A或者之前的packets都已经收到。下一个expected subsequent packet 是A+1。

那么这个circular queue从头到尾应该存A+1 到 A+K。
如果收到A+i,直接存到对应的位置。

如果已经A+1收到,输出A+1,并令A=A+1。

几乎是把circular queue当hash table在用。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表