问一道(大)数据 algorithm (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>DataSciences - 数据科学

问一道(大)数据 algorithm (转载)

问一道(大)数据 algorithm (转载)# DataSciences - 数据科学

b*d2015-03-22 07:03

1 楼

有个样片，newspaper发给我们看，发现脸部和背景都发黄，有大量暗影。好像白平衡
没调对。但对方说好像打出来不会有这个问题.
LD说 they are not presenting a SHARP image
instead it is an old image.
懂行的能帮忙看看吗？谢谢

w*22015-03-22 07:03

2 楼

版上懂钻石的人很多，所以我问个有个钻石的问题。据说圆形钻最亮，除了圆形钻，梨
形钻和椭圆钻哪个比较亮，如果各个参数差不多。圆钻可以用HCA来算，异性钻怎么选
啊，请大家指教一下

n*32015-03-22 07:03

3 楼

【以下文字转载自 JobHunting 讨论区】
发信人: nacst23 (cnc), 信区: JobHunting
标题: 问一道(大)数据 algorithm
发信站: BBS 未名空间站 (Sun Mar 22 00:11:01 2015, 美东)
请教大家一下：
两组人， POSITIVE 和 Negative ，
say
POSITIVE 100K ppl，
Negative 900K ppl.
基本的数据结构是人的 ID 和 length of stay（待了几天）。
ID length of stay(days)
ppl-0000001 8
ppl-0000002 10
...
目的是 sample Negative 组出来 100K 人 ,
which one-to-one match the Positive 组人
的 length of stay（待了几天），
这样 match 完, 两组人的 100K 个 length of stay（待了几天）
完全一样.
当然如果 negative
组人有多个 match 一个 POSITIVE 组人，任取一个就好了。
想用 c++ 写，use STL／Map hash，
不知有没好的算法哦，
or 更好的 STL 数据结构／算法可用？
因为是准备写成 RCPP for R, 现在不考虑用
并行 Solution.
谢谢。

b*d2015-03-22 07:03

4 楼

【在 b*****d 的大作中提到】

: 有个样片，newspaper发给我们看，发现脸部和背景都发黄，有大量暗影。好像白平衡
: 没调对。但对方说好像打出来不会有这个问题.
: LD说 they are not presenting a SHARP image
: instead it is an old image.
: 懂行的能帮忙看看吗？谢谢

d*n2015-03-22 07:03

5 楼

托高一点的也比较亮，下面进光

【在 w*****2 的大作中提到】

: 版上懂钻石的人很多，所以我问个有个钻石的问题。据说圆形钻最亮，除了圆形钻，梨
: 形钻和椭圆钻哪个比较亮，如果各个参数差不多。圆钻可以用HCA来算，异性钻怎么选
: 啊，请大家指教一下

w*a2015-03-22 07:03

6 楼

没完全明白你想干啥, 没理解错的话
将两组数据放一块, 同时标记好POSITIVE 和 Negative
然后按 length of stay 排序
取最相近的不同组的
没看见难在哪儿, 是我理解有误吗

【在 n*****3 的大作中提到】

: 【以下文字转载自 JobHunting 讨论区】
: 发信人: nacst23 (cnc), 信区: JobHunting
: 标题: 问一道(大)数据 algorithm
: 发信站: BBS 未名空间站 (Sun Mar 22 00:11:01 2015, 美东)
: 请教大家一下：
: 两组人， POSITIVE 和 Negative ，
: say
: POSITIVE 100K ppl，
: Negative 900K ppl.
: 基本的数据结构是人的 ID 和 length of stay（待了几天）。

l*s2015-03-22 07:03

7 楼

这是因为8bit或以上色彩的图被转成256色或256色一下的图了，丢失了很多色彩信息，
打印出来也是这样。

【在 b*****d 的大作中提到】

t*32015-03-22 07:03

8 楼

从对称性考虑，亮度顺序是Round，Oval，Pear，取决于具体几何参数。
Pear一端是圆形，比较亮，另一端是尖形，亮度降低。Oval和Pear的中心部分容易出现
暗区，因为复杂的几何结构阻碍了反光。Pear的尖形部分要注意保护。Pear容易显现钻
石本色，对Color的选择要求高。
HCA只能用于Round。一般来说，比较理想的Oval，Pear参数是
table 55-60%
crown height 12-15%
girdle thinkness 0.4%-5.5%
total depth 59-63%
length/width ratios: Oval 1.33-1.66;Pear 1.5-1.75
亮度还是要靠肉眼比较。

n*32015-03-22 07:03

9 楼

the for loop will take a long of time to complete...
want to find out some good algorithms for this.

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

: 没完全明白你想干啥, 没理解错的话
: 将两组数据放一块, 同时标记好POSITIVE 和 Negative
: 然后按 length of stay 排序
: 取最相近的不同组的
: 没看见难在哪儿, 是我理解有误吗

o*g2015-03-22 07:03

10 楼

好贴,收入精华区了

【在 t***3 的大作中提到】

: 从对称性考虑，亮度顺序是Round，Oval，Pear，取决于具体几何参数。
: Pear一端是圆形，比较亮，另一端是尖形，亮度降低。Oval和Pear的中心部分容易出现
: 暗区，因为复杂的几何结构阻碍了反光。Pear的尖形部分要注意保护。Pear容易显现钻
: 石本色，对Color的选择要求高。
: HCA只能用于Round。一般来说，比较理想的Oval，Pear参数是
: table 55-60%
: crown height 12-15%
: girdle thinkness 0.4%-5.5%
: total depth 59-63%
: length/width ratios: Oval 1.33-1.66;Pear 1.5-1.75

m*a2015-03-22 07:03

11 楼

you can use MapReduce
Use days as key
Positive, negative marker as value
one job to get it done
if your data is too large
In non-distributed version
you could loop your positive first, for example
build a map, then go to loop your negative, get the match.

【在 n*****3 的大作中提到】

: the for loop will take a long of time to complete...
: want to find out some good algorithms for this.

w*22015-03-22 07:03

12 楼

谢谢指点

【在 t***3 的大作中提到】

n*32015-03-22 07:03

13 楼

no distributed version for now, thanks for the tips.
go through the loop can be very time consuming, wish can find a
better approach..

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

: you can use MapReduce
: Use days as key
: Positive, negative marker as value
: one job to get it done
: if your data is too large
: In non-distributed version
: you could loop your positive first, for example
: build a map, then go to loop your negative, get the match.

m*a2015-03-22 07:03

14 楼

I want to learn the better approach too,
if there is any
without loop the data

【在 n*****3 的大作中提到】

: no distributed version for now, thanks for the tips.
: go through the loop can be very time consuming, wish can find a
: better approach..

s*e2015-03-22 07:03

15 楼

1. keep estimate histogram in positive set util convergence
after scanning first 1000 records in positive, if lucky, k-s test shows no
difference with previous histogram,which is estimated for the first 900
records.
2.build a hash, key is stay days, value is count
3.keep scan negative set util find 100K record

n*32015-03-22 07:03

16 楼

先估计分布，再 hash then scan，
省得时间是估计分布 vs scan positive population；
hash table is for positive polulation or negative population?
thanks.

no

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

: 1. keep estimate histogram in positive set util convergence
: after scanning first 1000 records in positive, if lucky, k-s test shows no
: difference with previous histogram,which is estimated for the first 900
: records.
: 2.build a hash, key is stay days, value is count
: 3.keep scan negative set util find 100K record

s*e2015-03-22 07:03

17 楼

positive population.
我本来就不理解你的问题，你这一问，我更确切我误解了问题了。我们等高人来解答
吧。

s*i2015-03-22 07:03

18 楼

试着回答一下。。。
用hive作的假设有2个table: tempp=positive and tempn=negative
column=id,ls
select a3.* from
(select rank() over (partition by a2.aid order by rand()) as rank, a2.aid,
a2.bid, a2.als
from (select a.id as aid,a.ls as als,b.id as bid from tempp a left join
tempn b on (a.ls=b.ls)) a2) a3
where a3.rank<=1
;
但是这样做有缺点就是重复sample,
i.e.会出现
u1,11,u11
u2,11,u11
u3,11,u11
这样地，虽然几率会很小如果negative很大的话
求高人解答。。。
-------
PS 好像partition那里直接by length of stay再改改就可以了。。。

【在 n*****3 的大作中提到】

: 先估计分布，再 hash then scan，
: 省得时间是估计分布 vs scan positive population；
: hash table is for positive polulation or negative population?
: thanks.
:
: no

T*u2015-03-22 07:03

19 楼

我不懂，但这是要做啥啊

d*c2015-03-22 07:03

20 楼

一般matlab或者R里不推荐for loop，是因为系统函数进行了优化，很多时候能并行处
理，或者vectorized。
你用c++又不用for loop，还不并行，是到底想干什么？该有的计算是免不了的
另外你题目也没说明白，match的定义是什么？

【在 n*****3 的大作中提到】

: the for loop will take a long of time to complete...
: want to find out some good algorithms for this.

d*c2015-03-22 07:03

21 楼

看了一下他在另一个版的回帖，貌似negative population里是没有stop time的，哈哈
那match的标准是什么？
题目一直就没说明白

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

: positive population.
: 我本来就不理解你的问题，你这一问，我更确切我误解了问题了。我们等高人来解答
: 吧。

m*a2015-03-22 07:03

22 楼

感觉他/她好像是要作一个MATCH SAMPLE
得运算快
并且既不能用分布式计算
又不能用LOOP - 任何LOOP
所以无解
除非是前面理解有误

【在 d******c 的大作中提到】

: 看了一下他在另一个版的回帖，貌似negative population里是没有stop time的，哈哈
: 那match的标准是什么？
: 题目一直就没说明白

n*32015-03-22 07:03

23 楼

谢谢大家的会贴啊，很感谢！！
其实就是match sample，
分布式以后下一个stage 用，
不是说不可以Loop，只是希望尽量快。
下面抛砖一下：这 loop 不需每次全scan，
用两个indicator 往下走。
／*** assume f[] g[] are all sorted!!!!! ***/
int match(int f[], int g[], int m, int n)
{
int index_f, index_g; /* subscripts for f and g */
int m,n /* length of each group **/
int count; /* equal pair counter */
count = index_f = index_g = 0;
while (index_f < m && index_g < n)
if (f[index_f] < g[index_g]) /* if f[] is less */
index_f++; /* then move f */
else if (f[index_f] > g[index_g]) /* if f[] > */
index_g++; /* then move g */
else
count++, index_f++, index_g++; /* EQUAL */
return count;
}

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

: 感觉他/她好像是要作一个MATCH SAMPLE
: 得运算快
: 并且既不能用分布式计算
: 又不能用LOOP - 任何LOOP
: 所以无解
: 除非是前面理解有误

T*n2015-03-22 07:03

24 楼

至少先sort一下啊

【在 n*****3 的大作中提到】

: 谢谢大家的会贴啊，很感谢！！
: 其实就是match sample，
: 分布式以后下一个stage 用，
: 不是说不可以Loop，只是希望尽量快。
: 下面抛砖一下：这 loop 不需每次全scan，
: 用两个indicator 往下走。
: ／*** assume f[] g[] are all sorted!!!!! ***/
: int match(int f[], int g[], int m, int n)
: {
: int index_f, index_g; /* subscripts for f and g */

n*32015-03-22 07:03

25 楼

first line
／*** assume f[] g[] are all sorted!!!!! ***/
I sort them in the R part, before passing them to RCPP.
In general, I think R vectorized operating is fast
enough.

【在 T**n 的大作中提到】

: 至少先sort一下啊

n*32015-03-22 07:03

26 楼

／*** assume f[] g[] are all sorted!!!!! ***/
I sort them in the pure R section first; vectorized operation like data.
table/setkey is very fast already. Try to keep the RCPP as mini as possible.

【在 T**n 的大作中提到】

: 至少先sort一下啊

s*e2015-03-22 07:03

27 楼

still confused.
you are looking for algorithm which is better then O(n). if sorting is only
for match sample, it is bad. sorting is kind of O(nlogn), I could be wrong
, if R uses bucket sort in this case.
assuming data was sorted already for other purpose, merge join is fast.
otherwise, I would use hash join.

n*32015-03-22 07:03

28 楼

good point;
if everything in c/c++, I bet there is better solution;
but here I just want to speed up a small, but very time consuming(big loop)
part ,
in R.
Sure I can use std::sort to sort them in the RCPP code instead of using R/
data.table/setkey.
BTW do you have better algorithm for this? my solution is just for 抛砖引玉.

only
wrong

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

: still confused.
: you are looking for algorithm which is better then O(n). if sorting is only
: for match sample, it is bad. sorting is kind of O(nlogn), I could be wrong
: , if R uses bucket sort in this case.
: assuming data was sorted already for other purpose, merge join is fast.
: otherwise, I would use hash join.

n*32015-03-22 07:03

29 楼

length of stay（待了几天）
不是 UNIQUE 的。很多人有一样的length of stay（待了几天）。
how to merge? many to many merge?

only
wrong

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

H*H2015-03-22 07:03

30 楼

题目的意思只懂个大概，你需要的应该是R里面的match() function
idx 然后你就可以用这个idx去直接提取x的信息并赋给y
y$info 向量化操作，这么点数据，应该瞬间就能完成了

n*32015-03-22 07:03

31 楼

Thanks , but match() is kind of very slow ah..
for the R help:
"Matching for lists is potentially very slow and best avoided except in
simple cases."
our first stage data is about 60G txt file, not too smart for R .

【在 H*H 的大作中提到】

: 题目的意思只懂个大概，你需要的应该是R里面的match() function
: idx : 然后你就可以用这个idx去直接提取x的信息并赋给y
: y$info : 向量化操作，这么点数据，应该瞬间就能完成了

H*H2015-03-22 07:03

32 楼

你这不是100k个ID match另外100K个ID吗？不大明白为什么会涉及list。要是原始数据
存在list里面的，你可以把他们的id提取出来存放在vector里，然后match。照你这么
一说，你的code慢主要就是因为list操作，跟match基本没啥关系。

【在 n*****3 的大作中提到】

: Thanks , but match() is kind of very slow ah..
: for the R help:
: "Matching for lists is potentially very slow and best avoided except in
: simple cases."
: our first stage data is about 60G txt file, not too smart for R .

m*a2015-03-22 07:03

33 楼

I do not think sort is needed.
So now, first loop either positive or negative sample - the small size one
build histogram with days, then normalize it
then loop the other sample, do sampling with acceptance/rejection method
until the same number records collected

)
玉.

【在 n*****3 的大作中提到】

: good point;
: if everything in c/c++, I bet there is better solution;
: but here I just want to speed up a small, but very time consuming(big loop)
: part ,
: in R.
: Sure I can use std::sort to sort them in the RCPP code instead of using R/
: data.table/setkey.
: BTW do you have better algorithm for this? my solution is just for 抛砖引玉.
:
: only

l*s2015-03-22 07:03

34 楼

其实这个不算大数据，单机可以解决，都没上million这个量级，考虑下算法优化，找
个支持多核cpu的classifier跑就行。

n*32015-03-22 07:03

35 楼

你说的对，这不是大数据。
因为在modeling training stage，用 R 跑prototype system，
R itself 不方便并行。下一阶段会上 spark／hadoop。
继续抛砖引玉一下。下面的 CPP file 跑得还行。用 sourceRCPP call
就可。看看有什么可以改进的，
再次谢谢大家 all
#include
using namespace Rcpp;
using namespace std;
// Below is a the balancing C++ function to R. You can
// source this function into an R session using the Rcpp::sourceCpp
// function (or via the Source button on the editor toolbar)
// For more on using Rcpp click the Help button on the editor toolbar
// [[Rcpp::export]]
DataFrame ba(DataFrame ng, DataFrame ps) {
int ng_nrows = ng.nrows();
int ps_nrows = ps.nrows();
// int nCols = ng.size();
cout << " neg nRows is " << neg_nrows << endl;
cout << " pos nRows is " << pos_nrows << endl;
int count = 0;
std::vector ps_ls =Rcpp::as > (ps[0]);
std::vector ng_ls =Rcpp::as > (ng[1]);
std::vector::const_iterator i = ps_ls.begin();
std::vector:: iterator j = ng_ls.begin();
// while( (i ! ps_ls.end() ) && (j ! ng_los.end() ) )
while( (i != ps_ls.end() ) )
{if ( *i < *j)
i++ ;
else if (*i > *j)
j++;
else
{ count++;
std::cout << "the *i is " << *i <endl;
*j = (*j) + 5000;
i++; j++; }
}
// for( std::vector::const_iterator k = ng_ls.begin(); k != ng_
ls.end(); ++i)
// std::cout << *k << ' ' << endl;
cout << " total matached # is " << count << endl;
return ng_ls;
}

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

: 其实这个不算大数据，单机可以解决，都没上million这个量级，考虑下算法优化，找
: 个支持多核cpu的classifier跑就行。