免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 3905 | 回复: 20

[C++] 求教 一道外国公司的题 [复制链接]

论坛徽章:
0
发表于 2015-08-27 08:21 |显示全部楼层
本帖最后由 oov 于 2015-08-27 22:14 编辑

CodeTest.txt.zip (2.01 KB, 下载次数: 25)

论坛徽章:
14
水瓶座
日期:2014-06-10 09:51:0215-16赛季CBA联赛之江苏
日期:2017-11-27 11:42:3515-16赛季CBA联赛之八一
日期:2017-04-12 14:26:2815-16赛季CBA联赛之吉林
日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏
日期:2016-06-23 09:53:58程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏
日期:2015-12-22 09:39:36程序设计版块每日发帖之星
日期:2015-08-24 06:20:002015亚冠之德黑兰石油
日期:2015-08-07 09:57:302015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2015-08-27 09:30 |显示全部楼层
oov,星际争霸?虾米?

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2015-08-27 09:45 |显示全部楼层
看起来要你提供一个伙伴内存管理

论坛徽章:
0
发表于 2015-08-27 10:05 |显示全部楼层
本帖最后由 oov 于 2015-08-27 11:37 编辑

游戏公司可能确实需要在一点点内存里做文章,

我也感觉是内存管理,而且是只在栈内存中做的内存管理,关键是这么搞,有没有什么具体解决思路呢?

我有一个想法。

题目最大不是说可以有64个队列吗,我就直接把2048字节,分成64片,每片32字节。每组的第一个位置可以,从0*32-63*32 方便的计算下标,根据这个ID可以容易的在2048个中跳转。
题目说平均来说,只有15个左右的队列,每个80字节,那感觉我的这个分法也是凑合能应付的。

然后我把每32个字节中,拿出来2个字节,一个作为这一组queue是否使用的标志,相当于一个bool, 另一个字节作为如果30个字符不够用,那么就指向下一片的位置,比如当前是第2片不够用了,后边第10片是空的,那么我这个字节就填上10,可以直接用32*10跳转到那一片32字节中去继续添加数据。

。。。

这只是我非常粗略的想法,希望有经验的大神能给与指点下正确的做法。

回复 3# folklore


   

论坛徽章:
323
射手座
日期:2013-08-23 12:04:38射手座
日期:2013-08-23 16:18:12未羊
日期:2013-08-30 14:33:15水瓶座
日期:2013-09-02 16:44:31摩羯座
日期:2013-09-25 09:33:52双子座
日期:2013-09-26 12:21:10金牛座
日期:2013-10-14 09:08:49申猴
日期:2013-10-16 13:09:43子鼠
日期:2013-10-17 23:23:19射手座
日期:2013-10-18 13:00:27金牛座
日期:2013-10-18 15:47:57午马
日期:2013-10-18 21:43:38
发表于 2015-08-27 10:19 |显示全部楼层
大体应该是上面的方法。是否使用只需一个bit,可以跟下一空闲片位置共用1字节。另外要求能快速的push/pop,那么额外增加一个队尾位置比较好

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2015-08-27 10:47 |显示全部楼层
资源稀缺的项目,数据结构就应该专用,不去使用stl

论坛徽章:
0
发表于 2015-08-27 11:34 |显示全部楼层
用bit来作为标示位,确实更好。

目前我的想法是先1个字节作为是否这一片被使用的标志对付着,大体功能完成了再用bit试着更优化一点。

遇到几个问题。

1)用什么表示当前节点位置是空的? 我一开始用把没用过得char赋值'\0' , 这样检测到为0的char就作为空位置,可以插入数据。
但是很快就发现,题目给出的测试用例中,也会直接插入0作为一个char的值,这就带来一个麻烦。例如,
往一个空队列中push插入1,2,3,是没问题的,但是一旦第四个插入0,等第5个插入的时候,怎么判断第4个是空的,还是插入过一个数0的?
pop也有类似的问题,由于是数组,比如1,2,3,弹出第一个后,就成了0,2,3,未来也会陷入,0,2,3,这个0到底有没弹出的困境。
目前也没想出来啥好办法,估计还是要再分出来两个字节,专门作为指针,指着头和尾位置,才知道0到底是个数还是一个空位置。
这样岂不是,就要拿出来4个字符用了,每一小片只能保存28个字节。

2)如果拿出来4个字符,2个作为头尾指针,1个作为next节点的指针,还剩1个作为当前这一片32个字符是否使用过的标志,没有这个,一旦一片32个字节被pop成空的后,无法知道这一片是用过的,还是没用过的,如果是用过的,这一片可能还会被调用程序拿去重新push数据,没用过的才能释放回2048中,给新建立的队列用。这是挺大的区别,所以这个字段也该保留。

问题是,想到这些,我怎么隐隐觉得已经进入歧途了。。。哪位大神再指点指点。。

回复 5# hellioncu


   

论坛徽章:
323
射手座
日期:2013-08-23 12:04:38射手座
日期:2013-08-23 16:18:12未羊
日期:2013-08-30 14:33:15水瓶座
日期:2013-09-02 16:44:31摩羯座
日期:2013-09-25 09:33:52双子座
日期:2013-09-26 12:21:10金牛座
日期:2013-10-14 09:08:49申猴
日期:2013-10-16 13:09:43子鼠
日期:2013-10-17 23:23:19射手座
日期:2013-10-18 13:00:27金牛座
日期:2013-10-18 15:47:57午马
日期:2013-10-18 21:43:38
发表于 2015-08-27 12:00 |显示全部楼层
oov 发表于 2015-08-27 11:34
用bit来作为标示位,确实更好。

目前我的想法是先1个字节作为是否这一片被使用的标志对付着,大体功能完 ...


按64每片,最小分配单位64,每个队列由N个分片组成

每片需要3字节用作标志,实际使用18bits

每片第0字节:
  最高位:已分配标志
  5bits:本分片的尾节点
第1字节(6bits):
  Next分片编号,等于本片编号表示无
第2字节(6bits):
  Prev分片编号,等于本片编号表示本片是队列的头分片

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2015-08-27 12:36 |显示全部楼层
基本思路:
1. 用伙伴算法, 因为经常增加、删除,非伙伴系统很难对应这种要求。
2. 用空闲链表算法, 这样可以最大限度使用内存

最小要分配内存为2Btyes(不含Header2Bytes),最高为2046Bytes(不含Header2Bytes)
Header低12位表示分配的内存大小,
高4位用来表示含Header及内部未使用内存的内存块大小(实际大小2^n)
Handler直接为内存地址就可以了。

这样,事实上无需64块的限制。但题目要求最大64, 所以
在YourType* aPointerOnYourType上做文件
将其定义为 INT(32)位, 低12位表示空闲列表头, -1为无空闲块, 高16Bit用来计数限制最大64块

在空闲表时, 因为有4个字节可以用, 4个字节可用来放向前向后指针及本块大小(共需 12(前指针)+12(后指针)+4(块大小)=28Bit)。

论坛徽章:
0
发表于 2015-08-27 12:40 |显示全部楼层
我觉得头尾位置该都要知道。。。
每个分片,都是一小片数组,比如1234567,在pop几次后,就变成了0004567这样,那还是需要一个头指针用来指出头的位置在4这个样子,否则一旦有个0被push进来后,就容易引发混乱,pop和push时候,不知道头尾位置在哪里了。

回复 8# hellioncu


   
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP