Redian新闻
>
问一道(大)数据 algorithm (转载)
avatar
问一道(大)数据 algorithm (转载)# DataSciences - 数据科学
b*d
1
有个样片,newspaper发给我们看,发现脸部和背景都发黄,有大量暗影。好像白平衡
没调对。但对方说好像打出来不会有这个问题.
LD说 they are not presenting a SHARP image
instead it is an old image.
懂行的能帮忙看看吗?谢谢
avatar
w*2
2
版上懂钻石的人很多,所以我问个有个钻石的问题。据说圆形钻最亮,除了圆形钻,梨
形钻和椭圆钻哪个比较亮,如果各个参数差不多。圆钻可以用HCA来算,异性钻怎么选
啊,请大家指教一下
avatar
n*3
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.
谢谢。
avatar
b*d
4


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

avatar
d*n
5
托高一点的也比较亮,下面进光

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

avatar
w*a
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(待了几天)。

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

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

avatar
t*3
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
亮度还是要靠肉眼比较。
avatar
n*3
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 排序
: 取最相近的不同组的
: 没看见难在哪儿, 是我理解有误吗

avatar
o*g
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

avatar
m*a
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.

avatar
w*2
12

谢谢指点

【在 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

avatar
n*3
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.

avatar
m*a
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..

avatar
s*e
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
avatar
n*3
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

avatar
s*e
17
positive population.
我本来就不理解你的问题,你这一问,我更确切我误解了问题了。 我们等高人来解答
吧。
avatar
s*i
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

avatar
T*u
19
我不懂,但这是要做啥啊
avatar
d*c
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.

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

【在 s******e 的大作中提到】
: positive population.
: 我本来就不理解你的问题,你这一问,我更确切我误解了问题了。 我们等高人来解答
: 吧。

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

【在 d******c 的大作中提到】
: 看了一下他在另一个版的回帖,貌似negative population里是没有stop time的,哈哈
: 那match的标准是什么?
: 题目一直就没说明白

avatar
n*3
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
: 所以无解
: 除非是前面理解有误

avatar
T*n
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 */

avatar
n*3
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一下啊
avatar
n*3
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一下啊
avatar
s*e
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.
avatar
n*3
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.

avatar
n*3
29
length of stay(待了几天)
不是 UNIQUE 的。 很多人有一样的length of stay(待了几天)。
how to merge? many to many merge?

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.

avatar
H*H
30
题目的意思只懂个大概,你需要的应该是R里面的match() function
idx 然后你就可以用这个idx去直接提取x的信息并赋给y
y$info 向量化操作,这么点数据,应该瞬间就能完成了
avatar
n*3
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 : 向量化操作,这么点数据,应该瞬间就能完成了

avatar
H*H
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 .

avatar
m*a
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

avatar
l*s
34
其实这个不算大数据,单机可以解决,都没上million这个量级,考虑下算法优化,找
个支持多核cpu的classifier跑就行。
avatar
n*3
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跑就行。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。