-
网易2017春招笔试真题编程题集合题解
前言 想想已经有一年多没有接触算法题了，忙活了一年多没什么用的东西，才陡然发现自己竟然就要毕业了，然而审视了下自己的水平估计还达不到大一的程度，甚是惊恐。于是下定决心开始刷一点题，打好基本功。正好有同学在做网易笔试题的时候来向我问问题，我看了看有12道，好像也不多，于是就顺便刷了刷。本以为会是一帆风顺的，可是事实是，我果然还是太菜了。。。 双核处理 题目 一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，…
-
Linux-C简单多线程编程分析
我们都知道多线程可以提高程序运行的速度，但是至于能够提高多少却一直没有一个直观的印象，下面就用Linux C的多线程编程技术，简要分析下多线程的运行效率。 测试代码 下面就用1000*1000的矩阵之间的乘法来做一个实验，我们分别用单线程和多线程分别实现，算法都采用$O(n^3)$的朴素算法。测试代码如下： #include
#include #include #include #define LEN 1000 #define MAXNUM 1000 #define MAXTH …
-
常见的距离测度
在对向量进行相似度计算的时候经常需要纠结的是用什么测度来衡量相似度。经常听到的距离测度无非是欧氏距离、曼哈顿距离、切比雪夫距离、闵科夫斯基距离、海明距离、编辑距离、余弦距离、杰卡德距离这么几个，稍微生僻点的再加上什么标准化欧氏距离、卡方距离、马哈拉诺比斯距离、巴塔恰里雅距离、皮尔逊距离。前面说的那些距离大都是一回事，掌握了初中左右的知识基本都能理解，而后面说的这些距离就相对复杂很多了，得有离散统计线性代数这类的扎实功底才能吃透。。。这里就稍微介绍下概念上距离测度的定义，以及简单的距离测度。…
-
面向最小哈希签名的LSH
LSH 我们知道最小哈希签名能够把一篇较大的文档压缩成一个较短的签名并且不影响文档间的Jaccard相似度。很多情况下，我们用最小哈希签名的目的就是为了方便的对文档进行存储，并且对于给定的文档，能在大量的文档中快速的查找相似的文章。现在我们能做到快速的对两篇文章进行相似度比较，但是当总的文档数目比较大的时候，比较所有文档的最小哈希签名仍然是一个非常耗时耗力的事。而我们知道，对于给定的文档而言，文档库中的绝大多数文档其实都没有比较的意义，如果能有一个方法能过滤掉不需要比较的大量文档，那么显然就能…
-
最小哈希签名（MinHash）简述
最小哈希签名(minhashing signature)解决的问题是，如何用一个哈希方法来对一个集合（集合大小为n）中的子集进行保留相似度的映射（使他在内存中占用的字节数尽可能的少）。 其实哈希本身并不算难，难的是怎么保留两个子集的相似度的信息。所谓保留相似度，就是说我们能十分直观的从两个子集的哈希结果中看出他们的相似度。当然，朴素的办法就用是一个长度为n的二进制数的每个位来分别对应集合中的每个元素。不过当n比较大而待hash的集合的数目比较小的时候，这种方法的效率就太低了。这时候最常用的方法…
-
相似度度量标准之Jaccard相似度
定义 Jaccard相似度(杰卡德相似度)是一个用于衡量两个集合相似程度的度量标准，他的定义如下：给定两个集合$S,T$，那么我们记这两个集合的Jaccard相似度$SIM(S,T)$为: $$SIM(S,T)=|S\cap T|/|S\cup T|$$ 也就是两个集合交集的大小除以两个集合并集的大小。显然他的取值在[0,1]区间。 扩展 原始的Jaccard相似度定义的仅仅是两个集合(set)之间的相似度，而实际上更常见的情况是我们需要求两个包(bag,multiset)的相似度，即每…
-
QR二维码植入图片方法简析
我们平时都经常见到二维码，用手机扫一扫就会显示当中的内容，内容大多是url的格式，方便人们访问站点。不过对于人来说，直接看二维码却并没有任何良好的印象。因此很多商家为了让自家的二维码更加形象，会想方设法地让自家的二维码更加形象生动，于是也就诞生出了很多种图像植入的方法。今天就把这些方法稍微汇总一下。 二维码 二维码可以说是现今人们生活中经常接触到的东西，简单的讲其实就是把条形码中的竖线变成点，从而增加一个数据维度，达到增加数据内容的目的。事实上二维码的种类有很多，曾经流行的二维码规范大概有…
-
伽罗华域性质简析
伽罗华（伽罗瓦）域名字听起来挺酷的，其实就是有限域。域这个东西由于他能够进行满足加减乘除四则运算，在加密解密、编码解码当中应用非常广泛。但是我们常见的实数域却无法直接在计算机中精确的保存，因此有限域这类能够支持四则运算而且能够用有限的编码精确保存的东西就非常有用了。 （顺带提一句，伽罗瓦这个人的生平很有意思，如果他活久点，说不能成为跟高斯、欧拉一样档次的人。。。） 域 域的定义在各种与离散数学相关的地方都能看到，看上去定义的十分啰嗦，说白了其实就是从有理数抽象出来的一种集合，能加能减能乘…
-
Reed-Solomon纠删码简析
Reed-Solomon编码（又叫RS编码、里德-所罗门编码）作为一种前向纠错编码，是一种很常见的数据冗余技术，也就是通过对数据增加冗余部分来保证当数据丢失时能够在一定程度上进行恢复。最典型的应用就是在现在最流行的QR二维码的编码设计中。 实现功能 他所解决的问题是：给定$n$个数据块$(d_1,d_2,d_3,...,d_n)$，对于一个确定的正整数$m$， RS编码能够根据这$n$个数据块生成$m$个校验块， $(c_1, c_2,..., c_m)$。 我们能够做到，从这$m+n$…
-
幂定律和齐夫定律
幂定律 幂定律又叫幂律，大量的事实表明，很多现象都服从类似于幂函数$y=cx^a$的形式，其中$a$是幂，而且通常是负数。 幂定律可以非常直观的用马太效应(Matthew effect)解释，说白了其实就是所谓的“富者越富，穷者越穷”。例如图书的销售，本来销售好的图书可能会发布更多的广告，做更多的营销从而导致销量更多。这样如果将图书销售量按照名次排列下来就会发现图书销量会随着名次的提高而指数性的提高。 齐夫定律 齐夫定律(Zipf's Law)其实可以说是幂定律的一种形式，只是由于在曾…