一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 317|回复: 1
收起左侧

Vertica的 assignment

[复制链接] |试试Instant~ |关注本帖
爱吃肉的羊 发表于 2015-2-20 04:16:42 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Vertica - 校园招聘会 - 校园招聘会 |Other

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
题目是有两个很大的xml 需要分析,一个user, 一个post 其实就是相当于两个数据库的表,现在让我从这个xml里读取top 10发帖最多的user, 其实就是相当于join两个table 然后拿出top 10。 要求是尽量减少空间、时间复杂度,群里的大大有什么思路吗?
ourlord 发表于 2015-10-6 05:38:27 | 显示全部楼层
啊我也刚面过,当时我自己想的太复杂了,于是后来貌似没跑好吧,反正挂了。.1point3acres缃

交完第二天我自己想了一想觉得很简单的其实. 1point3acres.com/bbs

需要一个这样的数据结构
struct Recorder
{int post; int answer;}. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
std::vector<Recorder>          (或者用map更好,我只是懒得用c++11,所以开了个够大的vector,想想世界上人口也才6b,你开个1b存3个int也就是几MB的事情)

然后跑xml的每一行,更新这个vector或者map就是了,角标是userid,post对应帖子数,answer是回答数. visit 1point3acres.com for more.

然后排序来了,用std::set就可以了,for一记之前的vector,然后这么操作
Wrapper
{int userid; int count;}. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
重载operator<,让根据count来排序
std::set<Wrapper> posts, answers;
for (auto &v : vector)
{
     posts.insert(v);
     answers.insert(v);
     if (posts.size() > 10) posts.erase(posts.begin());
     if (answers.size() > 10) answers.erase(answers.begin());
}

最后再把这20个userid去小的xml里找一下用户名就可以了。
这样肯定跑的出,而且不用很多内存,那个vector真的没啥内存,用map就更少了。但其实这个数据结构有个前提是post_id是primary key,意思是不能有重复的。。。但给的数据其实可以发现这一点,我觉得最好还是说一下比较好。

如果还要optimize的话可以在读数据的时候mutltithread一下,但是数据容易跑花,我自己随便实现了一下发现不太可靠,后来也没有再去想这个问题....
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 06:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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