存档

‘Algorithm’ 分类的存档
1月
02

推荐系统实践

s10213357两个多月前刚从香港团建回来就被扔去广州参与个实时推荐系统的设计,由于这个工作和以前的工作内容差别略大,就花了点时间把《推荐系统实践》这本书给啃了,确实是本好书,对于我这种初心者而言满满的都是实用的干货,整本书都做了详细的笔记,也把知识点整理在了印象笔记,然后觉得闲着无聊,就写了段小代码把markdown转成博客可以发表的格式来水一篇(我知道有工具,但是我就是想自己写着玩。。),好,为什么有这篇东西的背景介绍完了。。

虽然此趟主要是设计算法(因为业务原因通用推荐框架不太方便直接套进来用),开发有专业人士帮我们完成,不过这两个多月的研究,最大的一点感悟就是,比起像学术论文一样研究改进推荐系统的召回率啊准确率什么的,工业界的推荐系统反而会把算法看的很轻很轻,而设计算法是重点会往业务和场景上靠拢;也就是你必须根据你的业务,结合用户所处的场景给他进行推荐,而且分得越细可能越好。另外很多论文虽然号称表现得很不错,但是实际上在大数据的情况下,实现起来都是不是很现实的(不是不能,而是代价太大)。。。

阅读全文...

3月
24

直方图下最大矩形面积问题【算法优化向】

histogram_area好像好久没写算法问题了。。。。上一次写好像是。。额。。大概是去年的事了吧。。。以前还兴致勃勃的狂写Euler Project的个人解答系列,但是后来发现官方有说,请不要在互联网上直接贴关于解答的代码,额,然后他这么一说,这个系列我就不怎么想弄了。。除了一方面不想做这些会被官方讨厌的事情外,其次是。。。懒。。。自己做完题还要花时间上来写思路,各种分析,敲数学公式什么的。。

唉,不管怎么说,研究算法和学习前端那些“不误正业”的东西的时候总是很“忘我”————忘记我™还要靠光子学和水声的东西毕业啊!!!!!然后这两天又跑到两个以前没去过的OJ网站上玩了,一个是51nod,还有一个leetcode OJ,昨晚就一直刷题玩到半夜三点多。。 阅读全文...

3月
11

井字过三关·变种游戏

最近我好像对这个游戏的执念很深啊。。

这篇博文的起因是这个样子的,上次我在到处跟别人“调研”井字过三关(如若不清楚这个游戏,请查看上一篇博文)名字问题的时候,有个朋友提到了一种井字过三关的变种玩法,觉得很有趣,最近出差回来有点闲情,就做来玩了一下。。

传统的井字过三关(是不是叫井字游戏更加大众化。。)作为一个游戏本身,有一个致命的缺陷,单局游戏时长太短,走完不到9格就结束了,完成一局几乎花不了10秒,而且,对于稍有常识的玩家来说,平局率太高,95%都有了吧。。再其次,局面变化太少,就算不玩,你枚举也可以枚举完所有的可能的局面;

规则

鉴于此,出现了本文中的这个游戏,最基本的规则和传统的一样,A,B两人轮流在3×3的棋局上打圈圈(○)和叉叉(×),先让自己的符号连成一条线的玩家胜利,包括纵,横,斜对角都可以。

下面是变种游戏的附加规则:场面上最多只能容纳6个棋子,也就是说下了第七个棋子的时候,第一个棋子会消失;下第八个的时候第二个会消失,如此类推

另外还需补充说明的一点是:判断胜负要在下子后,处理完棋子的消失问题后才可以进行。 阅读全文...

分类: 博弈 标签: , ,
3月
02

所以这个世界就没人知道井字过三关了么?!

之前忘了是什么事儿,看到一道博弈题,然后想着想着就想到了井字过三关,然后又想到了以前有人跟我说过:其实很多人并不清楚井字过三关的正确走法。。于是我就想问一下实验室的人验证一下这句话,对L某说:“你玩井字过三关一般是怎么玩的?”;

L某回答说“井字过三关是啥?”

“什么,你居然不知道井字过三关?!!”

“你说一下规则来听听?”

于是我简单讲了一下“就是那个XXXXXX的游戏啊!!”

然后L某还是很冷漠的说“没听过。。”;

这个时候我对有人不知道井字过三关表示高度震惊!!正在说着“你没童年”的时候,实验室Q某装完水走进来了,为了扳回一局,我马上问到“你玩过井字过三关没”,之后。。标准结局。。。在我解释完规则后Q某终于表示:“啊,这个啊,听过,没玩过。。”,然后L某很得意的对我嘲讽地说“打脸了吧~”。。

之后我又问了实验室Z某。。。然后晚上回来问舍友。。。。结局就是。。。难道就没人玩过井字过三关么!!!这不科学!!经过再三地跟不同的人打听,得知除了好一部分人真的不知道这个游戏,还有一些人是把井字过三关叫做别的名字,比如冰果游戏,打井(游戏),OX游戏,圈叉游戏【这两个名字。。。】。。。 阅读全文...

分类: 博弈 标签: , ,
1月
11

卫星云图定风向——光流法

前言

好吧,我是强迫症发作来刷出在感的,因为我发现当年写博文的时候,乱开Categories,导致现在博客很多Categories下只有一篇博文,强迫症患者表示,必须至少两篇,所以我最近就来慢慢填这些坑好了。。所以今天填的是第一个坑——计算机视觉。。。【好吧,其实我不搞DIP很久了。。。

作为一个从大四毕设开始就基本没研究过图像处理的人来说,要写一篇算法的科普文,虽然不是不可以,但是你会发现和网上很多人写的差不多【好吧,一般都是别人写的比我好。。】,所以我就决定写一篇关于去年(好吧,前年)研究生数模比赛的某道题的博文好了【一直觉得那道题很适合拿来水一篇博文。。】;

当年赛题发下来时,要做的第一件事自然就是选题,我把几道题都瞄了一下,然后基本马上下定了“嗯,就做这道题吧!!”的决心;因为那道题其中最核心的一问我已经有十足的信心可以“秒杀”了!!

那道题目的大概意思我也就不说了,我说说那核心的一问吧,假如你有以下三幅卫星云图(为了让大家看的比较清楚区别,我将其转为gif了),然后你就需要估算出各个地方的风速和风向【也叫风矢场或者云导风】;
阅读全文...

12月
15

关于正弦调频的信号频谱的理解

简短地记载一下之前师兄问的一个问题的探讨。

是这样子的,实验室一个师兄之前要做一个仿真,里面需要仿一个信号源,这个信号源的频率要随正弦变换,也就是时频图如下图所示的那种信号:QQ20131126195718 阅读全文...

12月
08

Euler Project之Retraction【算法优化向】

pe_banner_light好吧,其实我是在新博客这边练习敲公式来着。。。

题目来源还是是Euler Project,之前官方连续公布了三道类似的题目,都是基于一种叫做Retraction数的东西,它的定义是:

对于所有整数\(n>1\),定义一族函数\(f_{n,a,b}(x)=mod(ax+b,n)\)\(x,a,b\)均为整数,且满足0<\(n\)<\(a\),\(0\leq b < n\),\(0\leq x < n\)
如果对所有\(x\)均有:

\(f_{n,a,b}(f_{n,a,b}(x))=mod(f_{n,a,b}(x),n)\)

那么,我们管\(f_{n,a,b}(x)=mod(ax+b,n)\)叫做一个Retraction;
我们需要计算的是\(R(n)\),定义为包含\(n\)的Retraction的个数。

阅读全文...

11月
24

快速傅里叶变换幅度与加窗の研究

几个月前写过一篇关于分析用傅里叶变换来计算频率与选取正弦波周期数的关系的博文,今天来讨论一下计算幅度的问题。

不过在此之前还是请让我重述一下下面这两个已经老生常谈的东西(写毕业论文不就是这样么,前面都是一大堆本科生都懂的常识性东西。。):

一,对于离散序列的连续时间傅里叶变换DTFT,得到的结果是一个连续的,以2\(\pi\)为周期的函数。而FFT,是快速傅里叶变换的英文简称,它所做的,不是离散时间傅里叶变换DTFT,而是离散傅里叶变换DFT,也就是说,它把一个离散序列变换完,得到的是一个离散的序列,那么这个离散的序列和DTFT得到的连续周期函数有什么关系呢?我们可以认为它是后者的一个周期的采样的结果。

二,理论上来说正弦函数sin(ωt)的傅里叶变换结果应该是两个无穷细的冲激函数,但是FFT出来的结果应该是如下图所示,原因吉布斯(振铃)现象在之前那篇博文里面已经解释过了,这里就不累述了! 阅读全文...

11月
22

互质数倒数乘积之和の研究【算法优化向】

pe_banner_light上周开始一直在Euler Project上面刷题,玩得不亦乐乎,那种面对千奇百怪的问题,可以用自己手边的各种工具来“玩弄”的感觉真是让人欲罢不能,其实手头上也就4套工具,C++,Python,Matlab,Mathematica,主要用得最多的也就Mathematica,Python。

好吧,讲正事,上周遇到一道题,可算把我两天给送进去了。。。。

题目链接可以参见这里,翻译过来是这样的:

对于任意整数M,我们定义R(M)是符合下面条件的整数p,q的乘积的倒数1/(p·q)的和,
1.1≤p<q≤M
2.p+q≥M
3.p和q互质
然后我们定义S(N)表示R(i)的和,2≤i<N

求:S(107)精确到小数点后4位

我开始用python试测了一下这个暴算的复杂度,直接跪了,所以我马上转战C++。。

首先我们可以根据题目表面要求写出第一套可以预知不可能成功的程序: 阅读全文...

11月
10

Prony谱分析研究

这是最近研究的一个很有意思的东西~

之前发了一篇笔记式的AR谱分析算法的东西,当时说了,AR模型是谱分析里面最最最基础的模型算法,它的思想就是通过一个采样得到的信号x[n],算出一系列AR参数ai来,使得下式重构出来的信号与原来的信号误差最小:

\(x_{re}[n]=-\sum_{i=1}^{p}a_ix[n-i]\)

或者说计算出一系列AR参数ai来,使得\(x[n]=-\sum_{i=1}^{p}a_ix[n-i]\)成立!

其中ai的个数,也就是上式中的p,就是AR模型的阶数,之前那篇博文就列举和对比了几种计算ai的算法及仿真。

然后就是今天的主角,Prony模型,如果要阅读下去,首先要对上面的那几行要有所理解,因为Prony是基于AR模型来求解的!!

首先什么是Prony模型呢?Prony模型就是说,我们把原来的信号分解成下式:

\(x(t)=\sum A_ie^{(\alpha_i+j\omega_i)t}\)

说明几点,首先就是说,上面的式子表示,Prony模型构建思想就是把原始信号x(t)分解成一系列的不同幅度,不同衰减系数,不同频率的信号的叠加。就好像傅里叶变换是把原始信号分解成一系列不同频率幅度的正弦信号的和一样,只是我们这里多了个衰减系数αi,其他参数也解释一下,ωi就是每个子信号的频率,Ai是信号的幅度,必须一提的是,Ai可以是个复数,什么意思?就是说每个子信号还可以有一定的初始相位,懂?

哦,对,另外一点就是,离散信号的话,就是把上式的t变成nΔt就行了嘛。

然后Prony模型要干的事自然就是把这个振幅相位频率衰减全部给求解出来啦~没错,Prony模型就是根据采样得到的信号x[n]把每个子信号上述三个参数给解出来!! 阅读全文...