求审稿－－表观遗传和发育方向 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Biology - 生物学

求审稿－－表观遗传和发育方向

求审稿－－表观遗传和发育方向# Biology - 生物学

z*e2013-01-22 08:01

1 楼

其实我觉得design问题是划分等级的重要一环，决定senior/junior的关键。
anyway，问题是这样：
某网站要记录用户访问数据，每次用户访问会生成三个数据：customer_id, page_id,
date.
现在要找访问过至少两个不同网页(page）并且至少在不同的date中访问的所有
customer，设计相关数据结构和算法，并实现（date可以简单处理成integer或者
whatever).
解决并不难，但是要用尽可能优化的数据结构，并分析memory cost和相关time
complexity.

k*a2013-01-22 08:01

2 楼

看了一部电影，里面有个情节，是用电脑摄像头监控家里。
请问有这样的软件吗？
谢谢！

b*e2013-01-22 08:01

3 楼

有意者，请pm站内

j*u2013-01-22 08:01

4 楼

难道不是一次map reduce吗？(in-memory hash同理)
3个int有什么可优化的？除了mapper先做local reduce

,

【在 z***e 的大作中提到】

: 其实我觉得design问题是划分等级的重要一环，决定senior/junior的关键。
: anyway，问题是这样：
: 某网站要记录用户访问数据，每次用户访问会生成三个数据：customer_id, page_id,
: date.
: 现在要找访问过至少两个不同网页(page）并且至少在不同的date中访问的所有
: customer，设计相关数据结构和算法，并实现（date可以简单处理成integer或者
: whatever).
: 解决并不难，但是要用尽可能优化的数据结构，并分析memory cost和相关time
: complexity.

d*e2013-01-22 08:01

5 楼

facetime? skype? hangout?

【在 k****a 的大作中提到】

: 看了一部电影，里面有个情节，是用电脑摄像头监控家里。
: 请问有这样的软件吗？
: 谢谢！

x*y2013-01-22 08:01

6 楼

How about, for each customer, building two structures(could be map, hash,
trie or B+ tree for large set of data), one for page and one for date.
Whenever a new record needs to be put in, check whether the page field is in
structure 1 and whether the date field is in struct 2. Only neither of them
exists, we will add the date field and page field to the corresponding
structure respectively.

,

【在 z***e 的大作中提到】

c*n2013-01-22 08:01

7 楼

casm
可以设置敏感度超过范围拍照发email提醒你
吃包子

z*e2013-01-22 08:01

8 楼

1. map reduce不过是把大量数据hash后对每个hash set进行reduce，那么，你要对哪
个进行hash，之后又怎么reduce...
2. 这三个数据是相互关联的，你的local reduce又怎么做？你可以对每个customer的
数据并行处理，问题并不在于这点，而在于你怎么处理customer的数据并用合适的数据
结构存贮（比如，每个人访问的日期和该日期访问的page，你打算分开各存一个list/
hashtable，还是用日期做key，然后再存访问的pages？或者其他方式？每个方式有何
优缺点？）
3. 回到最初问题，原始数据你需要如何存储？用什么数据格式存储？如果只有1000个
customer，你也打算去map reduce？
呵呵，我不是map reduce专家，你可以说说吧。

【在 j*****u 的大作中提到】

: 难道不是一次map reduce吗？(in-memory hash同理)
: 3个int有什么可优化的？除了mapper先做local reduce
:
: ,

E*a2013-01-22 08:01

9 楼

iSpy

z*e2013-01-22 08:01

10 楼

嗯，我差不多就是这样做的，想知道有没有其他更有效的做法。
不过你这个还是有问题“ Only neither of them　exists, we will add the date
field and page field to the corresponding structure respectively”，这个似乎
不对（如果我理解没错）。比如customer在day 1访问了page2，我们有了<1, 2>（分在
两个set里面)，然后又在同一天day1访问了page 3，那么对记录<1,3>“neither of
them exists”就不成立因为day1已经记录了，但是实际上我们要把page 3也记录下来
，所以在记录的时候，我是对date/page分开处理，各自记录。

in
them

【在 x***y 的大作中提到】

: How about, for each customer, building two structures(could be map, hash,
: trie or B+ tree for large set of data), one for page and one for date.
: Whenever a new record needs to be put in, check whether the page field is in
: structure 1 and whether the date field is in struct 2. Only neither of them
: exists, we will add the date field and page field to the corresponding
: structure respectively.
:
: ,

g*s2013-01-22 08:01

11 楼

what do u mean by "至少两个不同网页(page）并且至少在不同的date中访问"?
say, (p1, d1), (p2, d2) satisfies the condition iff p1 != p2 && d1 != d2?

,

【在 z***e 的大作中提到】

x*y2013-01-22 08:01

12 楼

You're right. I think probably only 1 structure is needed for each customer.
It's like for each date, we only keep each page, visited in this date, once
(using hash or map or...) Then, if one date has at least two different
pages, and another date is not empty, then the customer qualifies; otherwise
, if all the unempty dates only have 1 page, the customer qualifies as long
as any two of dates have different pages.

【在 z***e 的大作中提到】

: 嗯，我差不多就是这样做的，想知道有没有其他更有效的做法。
: 不过你这个还是有问题“ Only neither of them　exists, we will add the date
: field and page field to the corresponding structure respectively”，这个似乎
: 不对（如果我理解没错）。比如customer在day 1访问了page2，我们有了<1, 2>（分在
: 两个set里面)，然后又在同一天day1访问了page 3，那么对记录<1,3>“neither of
: them exists”就不成立因为day1已经记录了，但是实际上我们要把page 3也记录下来
: ，所以在记录的时候，我是对date/page分开处理，各自记录。
:
: in
: them

z*e2013-01-22 08:01

13 楼

yes

【在 g*********s 的大作中提到】

: what do u mean by "至少两个不同网页(page）并且至少在不同的date中访问"?
: say, (p1, d1), (p2, d2) satisfies the condition iff p1 != p2 && d1 != d2?
:
: ,

j*u2013-01-22 08:01

14 楼

俺也不是砖家
先回答3，怎么存储一般改变不了，log的format已经固定好了，通常就是txt file。如
果数据量小了可以in memory hash，方法等同map reduce
1, 2：
mapper：emit >，以customer_id为key hash
local reducer和global reducer 相同的code：
可以sort也可以hash，以date和page其中之一为key，比如date
Dictionary> dict;
while (reducing a customer)
{
dict[date].Add(page);
if (dict.Count > 1 && (any_page_set.Count > 1 || any_two_page_set[0]_are_
different)))
emit customer_id and terminate reducing;
}

【在 z***e 的大作中提到】

: 1. map reduce不过是把大量数据hash后对每个hash set进行reduce，那么，你要对哪
: 个进行hash，之后又怎么reduce...
: 2. 这三个数据是相互关联的，你的local reduce又怎么做？你可以对每个customer的
: 数据并行处理，问题并不在于这点，而在于你怎么处理customer的数据并用合适的数据
: 结构存贮（比如，每个人访问的日期和该日期访问的page，你打算分开各存一个list/
: hashtable，还是用日期做key，然后再存访问的pages？或者其他方式？每个方式有何
: 优缺点？）
: 3. 回到最初问题，原始数据你需要如何存储？用什么数据格式存储？如果只有1000个
: customer，你也打算去map reduce？
: 呵呵，我不是map reduce专家，你可以说说吧。

z*e2013-01-22 08:01

15 楼

这有点像我刚听到这个问题时的解法，但是浪费了memory.
Dictionary> dict ----如果一个用户在day 1 visit了page1,然后
day2又visit了page1,那么你在对day1和day2的两个set里面都要加入page1，这就是不
必要的。

【在 j*****u 的大作中提到】

: 俺也不是砖家
: 先回答3，怎么存储一般改变不了，log的format已经固定好了，通常就是txt file。如
: 果数据量小了可以in memory hash，方法等同map reduce
: 1, 2：
: mapper：emit >，以customer_id为key hash
: local reducer和global reducer 相同的code：
: 可以sort也可以hash，以date和page其中之一为key，比如date
: Dictionary> dict;
: while (reducing a customer)
: {

j*u2013-01-22 08:01

16 楼

okay，这个optimization make sense，但问题是值不值得？
let's do the math，假设这个用户十年如一日，每天都只访问同一个page然后走人
假设该网站有1M个user，有1/10都是这类用户
假设我们起1k个reducer，不考虑local reducer
浪费了多少memory？10 * 365 * 4byte * 1M * 1/10 * 1/1000 = 1.5MB
这是hash-reduce，如果考虑local reduce或者用merge-reduce的话memory就少更多了
为了这个写tricky的code我觉得不值得，cluster里再差的机器也得有4GB的memory吧。。

【在 z***e 的大作中提到】

: 这有点像我刚听到这个问题时的解法，但是浪费了memory.
: Dictionary> dict ----如果一个用户在day 1 visit了page1,然后
: day2又visit了page1,那么你在对day1和day2的两个set里面都要加入page1，这就是不
: 必要的。

w*a2013-01-22 08:01

17 楼

这道题扩展一下就是两个以上DC，10亿个以上用户。。>100个DB server。hoho

s*k2013-01-22 08:01

18 楼

能否每个custom hash 一个value，这个value有两个指针和两个int，分别是date和
page的链表头，以及date和page的count。对于任何新的访问，先hash到这个custom的
value，如果有新的date或者page，那么就insert，更新对应count，否则discard。最
后只需要看两个count都大于1的custom就可以了。不过如果某个链表很长，比如一个
custom经常访问上百网页，这个效率不是很高，是否可以考虑再 hash一次？

【在 z***e 的大作中提到】

s*k2013-01-22 08:01

19 楼

补充了一下，觉得设计还是要针对具体问题，如果是1个million的用户，每个每天就访
问几个网页，访问的天数也不多，这个方法还是比较有效，但是如果100用户，但是每
个用户每天访问上千网页，可能数据结构就要重新设计了。设计之前应该先统计下访问
习惯

【在 s********k 的大作中提到】

: 能否每个custom hash 一个value，这个value有两个指针和两个int，分别是date和
: page的链表头，以及date和page的count。对于任何新的访问，先hash到这个custom的
: value，如果有新的date或者page，那么就insert，更新对应count，否则discard。最
: 后只需要看两个count都大于1的custom就可以了。不过如果某个链表很长，比如一个
: custom经常访问上百网页，这个效率不是很高，是否可以考虑再 hash一次？