Browsed by
分类: 程序设计

Go 语言简介(上)— 语法

Go 语言简介(上)— 语法

周末天气不好,只能宅在家里,于是就顺便看了一下Go语言,觉得比较有意思,所以写篇文章介绍一下。我想写一篇你可以在乘坐地铁或公交车上下班时就可以初步了解一门语言的文章。所以,下面的文章主要是以代码和注释为主。只需要你对C语言,Unix,Python有一点基础,我相信你会在30分钟左右读完并对Go语言有一些初步了解的。

Hello World

//文件名:hello.go
package main //声明本文件的package名

import "fmt" //import语言的fmt库——用于输出

func main() {
    fmt.Println("hello world")
}

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (39 人打了分,平均分: 4.38 )
Loading...
TF-IDF模型的概率解释

TF-IDF模型的概率解释

(感谢 @猫叔shiro(以前的todd) 投递此文)

信息检索概述

信息检索是当前应用十分广泛的一种技术,论文检索、搜索引擎都属于信息检索的范畴。通常,人们把信息检索问题抽象为:在文档集合D上,对于由关键词w[1] … w[k]组成的查询串q,返回一个按查询q和文档d匹配度relevance(q, d)排序的相关文档列表D’。

对于这一问题,先后出现了布尔模型、向量模型等各种经典的信息检索模型,它们从不同的角度提出了自己的一套解决方案。布尔模型以集合的布尔运算为基础,查询效率高,但模型过于简单,无法有效地对不同文档进行排序,查询效果不佳。向量模型把文档和查询串都视为词所构成的多维向量,而文档与查询的相关性即对应于向量间的夹角。不过,由于通常词的数量巨大,向量维度非常高,而大量的维度都是0,计算向量夹角的效果并不好。另外,庞大的计算量也使得向量模型几乎不具有在互联网搜索引擎这样海量数据集上实施的可行性。

tf-idf模型

目前,真正在搜索引擎等实际应用中广泛使用的是tf-idf模型。tf-idf模型的主要思想是:如果词w在一篇文档d中出现的频率高,并且在其他文档中很少出现,则认为词w具有很好的区分能力,适合用来把文章d和其他文章区分开来。该模型主要包含了两个因素:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (21 人打了分,平均分: 3.71 )
Loading...
Bret Victor – Learnable Programming

Bret Victor – Learnable Programming

大家是否还记得之前酷壳向大家介绍的苹果设计师Bret Victor一种可视编程的视频《Bret Victor – Inventing on Principle》,最近,他写了一篇文章—— Learnable Programming,写这篇文章的原因是因为“可汗学院(Khan Academy)”近期上线的一个在线编程环境,根据他的演讲提供了一堆基于Javascript的“实时编程”的环境,因为这个环境是引用了他的想法,所以,他有必要出来喷两句。

这篇文章的开头就是一个问题——“How do we get people to understand programming?”,我们怎么让人们懂得编程?

然后,他说了两条——

  • 编程是一种思考,而不是一种死记硬背的技能!你学会了“for循环”并不是说你就学会了编程,这就好像你知道有铅笔这个东西,但是你对绘画还是什么不懂。(对于这一条,正好这两天我在微博上和人辩论“基础算法面试题是否好”(还有微博一微博二),而且我以前也写过一篇《为什么我反对纯算法面试》,这里借用Bret的话再加强一下我的观点——“我们一方面在骂中国的应试教育毁了学生,另一方面我们又在把我们的面试变成“考八股文”式的考试!  你会qsort有什么用?你只不过是会用一支高级铅笔而已罢了。”)
  • 人只有看得见,才能理解。如果一个程序员不能看到他的程序在干什么,那么她就不能理解程序。(对于这一条,让我想到了Donald Knuth的话——“An algorithm must be seen to be believe!”)

所以,Bret 觉得编程软件的目标是——

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (24 人打了分,平均分: 3.92 )
Loading...
无锁队列的实现

无锁队列的实现

————注:本文于2019年11月4日更新————

关于无锁队列的实现,网上有很多文章,虽然本文可能和那些文章有所重复,但是我还是想以我自己的方式把这些文章中的重要的知识点串起来和大家讲一讲这个技术。下面开始正文。

关于CAS等原子操作

在开始说无锁队列之前,我们需要知道一个很重要的技术就是CAS操作——Compare & Set,或是 Compare & Swap,现在几乎所有的CPU指令都支持CAS的原子操作,X86下对应的是 CMPXCHG 汇编指令。有了这个原子操作,我们就可以用其来实现各种无锁(lock free)的数据结构。

这个操作用C语言来描述就是下面这个样子:(代码来自Wikipedia的Compare And Swap词条)意思就是说,看一看内存*reg里的值是不是oldval,如果是的话,则对其赋值newval

int compare_and_swap (int* reg, int oldval, int newval)
{
  int old_reg_val = *reg;
  if (old_reg_val == oldval) {
     *reg = newval;
  }
  return old_reg_val;
}

我们可以看到,old_reg_val 总是返回,于是,我们可以在 compare_and_swap 操作之后对其进行测试,以查看它是否与 oldval相匹配,因为它可能有所不同,这意味着另一个并发线程已成功地竞争到 compare_and_swap 并成功将 reg 值从 oldval 更改为别的值了。

这个操作可以变种为返回bool值的形式(返回 bool值的好处在于,可以调用者知道有没有更新成功):

bool compare_and_swap (int *addr, int oldval, int newval)
{
  if ( *addr != oldval ) {
      return false;
  }
  *addr = newval;
  return true;
}

与CAS相似的还有下面的原子操作:(这些东西大家自己看Wikipedia,也没什么复杂的)

注:在实际的C/C++程序中,CAS的各种实现版本如下:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (53 人打了分,平均分: 4.21 )
Loading...
K Nearest Neighbor 算法

K Nearest Neighbor 算法

K Nearest Neighbor算法又叫KNN算法,这个算法是机器学习里面一个比较经典的算法, 总体来说KNN算法是相对比较容易理解的算法。其中的K表示最接近自己的K个数据样本。KNN算法和K-Means算法不同的是,K-Means算法用来聚类,用来判断哪些东西是一个比较相近的类型,而KNN算法是用来做归类的,也就是说,有一个样本空间里的样本分成很几个类型,然后,给定一个待分类的数据,通过计算接近自己最近的K个样本来判断这个待分类数据属于哪个分类。你可以简单的理解为由那离自己最近的K个点来投票决定待分类数据归为哪一类

Wikipedia上的KNN词条中有一个比较经典的图如下:

从上图中我们可以看到,图中的有两个类型的样本数据,一类是蓝色的正方形,另一类是红色的三角形。而那个绿色的圆形是我们待分类的数据。

  • 如果K=3,那么离绿色点最近的有2个红色三角形和1个蓝色的正方形,这3个点投票,于是绿色的这个待分类点属于红色的三角形。
  • 如果K=5,那么离绿色点最近的有2个红色三角形和3个蓝色的正方形,这5个点投票,于是绿色的这个待分类点属于蓝色的正方形。

我们可以看到,机器学习的本质——是基于一种数据统计的方法!那么,这个算法有什么用呢?我们来看几个示例。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (24 人打了分,平均分: 3.83 )
Loading...
K-Means 算法

K-Means 算法

最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问题讲得很全面很清楚的文章,所以,把我的学习笔记记录下来,分享给大家。

在数据挖掘中, k-Means 算法是一种 cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。

问题

K-Means算法主要解决的问题如下图所示。我们可以看到,在图的左边有一些点,我们用肉眼可以看出来有四个点群,但是我们怎么通过计算机程序找出这几个点群来呢?于是就出现了我们的K-Means算法(Wikipedia链接

K-Means 要解决的问题

算法概要

这个算法其实很简单,如下图所示:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (22 人打了分,平均分: 4.18 )
Loading...
性能调优攻略

性能调优攻略

关于性能优化这是一个比较大的话题,在《由12306.cn谈谈网站性能技术》中我从业务和设计上说过一些可用的技术以及那些技术的优缺点,今天,想从一些技术细节上谈谈性能优化,主要是一些代码级别的技术和方法。本文的东西是我的一些经验和知识,并不一定全对,希望大家指正和补充

在开始这篇文章之前,大家可以移步去看一下酷壳以前发表的《代码优化概要》,这篇文章基本上告诉你——要进行优化,先得找到性能瓶颈! 但是在讲如何定位系统性能瓶劲之前,请让我讲一下系统性能的定义和测试,因为没有这两件事,后面的定位和优化无从谈起。

一、系统性能定义

让我们先来说说如何什么是系统性能。这个定义非常关键,如果我们不清楚什么是系统性能,那么我们将无法定位之。我见过很多朋友会觉得这很容易,但是仔细一问,其实他们并没有一个比较系统的方法,所以,在这里我想告诉大家如何系统地来定位性能。 总体来说,系统性能就是两个事:

  1. Throughput ,吞吐量。也就是每秒钟可以处理的请求数,任务数。
  2. Latency, 系统延迟。也就是系统在处理一个请求或一个任务时的延迟。

一般来说,一个系统的性能受到这两个条件的约束,缺一不可。比如,我的系统可以顶得住一百万的并发,但是系统的延迟是2分钟以上,那么,这个一百万的负载毫无意义。系统延迟很短,但是吞吐量很低,同样没有意义。所以,一个好的系统的性能测试必然受到这两个条件的同时作用。 有经验的朋友一定知道,这两个东西的一些关系:

  • Throughput越大,Latency会越差。因为请求量过大,系统太繁忙,所以响应速度自然会低。
  • Latency越好,能支持的Throughput就会越高。因为Latency短说明处理速度快,于是就可以处理更多的请求。

二、系统性能测试

经过上述的说明,我们知道要测试系统的性能,需要我们收集系统的Throughput和Latency这两个值。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (47 人打了分,平均分: 4.28 )
Loading...
Lisp的永恒之道

Lisp的永恒之道

感谢 Todd投递本文 – 微博帐号:weidagang

Lisp之魅

长久以来,Lisp一直被许多人视为史上最非凡的编程语言。它不仅在50多年前诞生的时候带来了诸多革命性的创新并极大地影响了后来编程语言的发展,即使在一大批现代语言不断涌现的今天,Lisp的诸多特性仍然未被超越。当各式各样的编程语言摆在面前,我们可以从运行效率、学习曲线、社区活跃度、厂商支持等多种不同的角度进行评判和选择,但我特别看中的一点在于语言能否有效地表达编程者的设计思想。学习C意味着学习如何用过程来表达设计思想,学习Java意味着学习如何用对象来表达设计思想,而虽然Lisp与函数式编程有很大的关系,但学习Lisp绝不仅仅是学习如何用函数表达设计思想。实际上,函数式编程并非Lisp的本质,在已经掌握了lambda、高阶函数、闭包、惰性求值等函数式编程概念之后,学习Lisp仍然大大加深了我对编程的理解。学习Lisp所收获的是如何“自由地”表达你的思想,这正是Lisp最大的魅力所在,也是这门古老的语言仍然具有很强的生命力的根本原因。

Lisp之源

Lisp意为表处理(List Processing),源自设计者John McCarthy于1960年发表的一篇论文《符号表达式的递归函数及其机器计算》。McCarthy在这篇论文中向我们展示了用一种简单的数据结构S表达式(S-expression)来表示代码和数据,并在此基础上构建一种完整的语言。Lisp语言形式简单、内涵深刻,Paul Graham在《Lisp之根源》中将其对编程的贡献与欧几里德对几何的贡献相提并论。

Lisp之形

然而,与数学世界中简单易懂的欧氏几何形成鲜明对比,程序世界中的Lisp却一直是一种古老而又神秘的存在,真正理解其精妙的人还是少数。从表面上看,Lisp最明显的特征是它“古怪”的S表达式语法。S表达式是一个原子(atom),或者若干S表达式组成的列表(list),表达式之间用空格分开,放入一对括号中。“列表“这个术语可能会容易让人联想到数据结构中的链表之类的线形结构,实际上,Lisp的列表是一种可嵌套的树形结构。下面是一些S表达式的例子:

foo

()

(a b (c d) e)

(+ (* 2 3) 5)

(defun factorial (N)
    (if (= N 1)
        1
        (* N (factorial (- N 1)))
    )
)

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (27 人打了分,平均分: 4.33 )
Loading...
Huffman 编码压缩算法

Huffman 编码压缩算法

前两天发布那个rsync算法后,想看看数据压缩的算法,知道一个经典的压缩算法Huffman算法。相信大家应该听说过 David Huffman 和他的压缩算法—— Huffman Code,一种通过字符出现频率,Priority Queue,和二叉树来进行的一种压缩算法,这种二叉树又叫Huffman二叉树 —— 一种带权重的树。从学校毕业很长时间的我忘了这个算法,但是网上查了一下,中文社区内好像没有把这个算法说得很清楚的文章,尤其是树的构造,而正好看到一篇国外的文章《A Simple Example of Huffman Code on a String》,其中的例子浅显易懂,相当不错,我就转了过来。注意,我没有对此文完全翻译。

我们直接来看示例,如果我们需要来压缩下面的字符串:

 “beep boop beer!” 

首先,我们先计算出每个字符出现的次数,我们得到下面这样一张表 :

字符 次数
‘b’ 3
‘e’ 4
‘p’ 2
‘ ‘ 2
‘o’ 2
‘r’ 1
‘!’ 1


然后,我把把这些东西放到Priority Queue中(用出现的次数据当 priority),我们可以看到,Priority Queue 是以Prioirry排序一个数组,如果Priority一样,会使用出现的次序排序:下面是我们得到的Priority Queue:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (24 人打了分,平均分: 4.17 )
Loading...
rsync 的核心算法

rsync 的核心算法

rsync是unix/linux下同步文件的一个高效算法,它能同步更新两处计算机的文件与目录,并适当利用查找文件中的不同块以减少数据传输。rsync中一项与其他大部分类似程序或协定中所未见的重要特性是镜像是只对有变更的部分进行传送。rsync可拷贝/显示目录属性,以及拷贝文件,并可选择性的压缩以及递归拷贝。rsync利用由Andrew Tridgell发明的算法。这里不介绍其使用方法,只介绍其核心算法。我们可以看到,Unix下的东西,一个命令,一个工具都有很多很精妙的东西,怎么学也学不完,这就是Unix的文化啊。

本来不想写这篇文章的,因为原先发现有很多中文blog都说了这个算法,但是看了一下,发现这些中文blog要么翻译国外文章翻译地非常烂,要么就是介绍这个算法介绍得很乱让人看不懂,还有错误,误人不浅,所以让我觉得有必要写篇rsync算法介绍的文章。(当然,我成文比较仓促,可能会有一些错误,请指正)

问题

首先, 我们先来想一下rsync要解决的问题,如果我们要同步的文件只想传不同的部分,我们就需要对两边的文件做diff,但是这两个问题在两台不同的机器上,无法做diff。如果我们做diff,就要把一个文件传到另一台机器上做diff,但这样一来,我们就传了整个文件,这与我们只想传输不同部的初衷相背。

于是我们就要想一个办法,让这两边的文件见不到面,但还能知道它们间有什么不同。这就出现了rsync的算法。

算法

rsync的算法如下:(假设我们同步源文件名为fileSrc,同步目的文件叫fileDst

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (37 人打了分,平均分: 4.49 )
Loading...