go

golang md5计算

消息摘要算法(message degist)

md5是经典的“消息摘要”算法之一,也就是生成一段文本的一个 hash 值,位数固定 128 位(16个字节)。消息摘要算法的几个特点:

  1. 单向不可逆:根据文本很容易计算hash值,但是根据hash值很难反推出文本;
  2. 反碰撞:给出既定的hash值,很难找到一段文本也是同一个hash值;

golang 计算 md5 方法甚是简单,可以看下面的 demo:

Tags: 

golang list sort

golang 的序列化容器有数组、slice 和 list,前两个是语言内置的,后一个是标准库提供的。用数组的场景并不多,因为其最大缺点是 —— 长度固定,所以我们更倾向于会动态增加长度的 slice 和 list。slice 底层是数组,所以是连续存储的结构;list 底层是链表,非连续存储结构。slice/list 相当于 java 中的 ArrayList/LinkedList ,或是 c++ 中的 vector/list。不同的储存结构结果就决定了它们的优缺点:

  • slice:特点:连续存储;优点:访问(第i个元素)方便,直接访问;缺点:删除和添加(第i个)元素不方便,需要大量移动数据;
  • list:特点:非连续存储;优点:删除和添加元素方便,不需要大量移动数据;缺点:访问(第i个元素)不方便,线性复杂度;

前面都是在说废话,现在入正题。排序算法很多:冒泡排序、希尔排序、堆排序、快速排序以及基数排序等。一般语言都提供快速排序 quicksort/qsort/sort 算法,其平均时间复杂度为 O(nlogn),采用的是递归分治的思想。关于快速排序可以看这篇文章

Tags: 

golang时间处理

时间处理是每一门语言的必备技能。关于时间处理其实有两部分,一个是日期相关的,一个是时间间隔相关。首先我们看下如何获取时间间隔,因为对于一个号称高性能的语言来说,对每一个 feature 的执行时间进行统计分析是非常重要的。

Tags: 

golang单例模式

单例模式(singleton)是设计模式的一种,其定义是:

Ensure a class has one instance, and provide a global point of access to it.也就是:保证类只有一个实例,而且有一个全局访问点。

go支持部分的 oo 编程,但不支持不支持构造/析构函数,也不支持 static 参数,所以 oo 中常用的单例模式的实现 go 中是不行的。然而 go 有自己的方式:

Tags: 

go的类型以及方法

go自称是一门简单安全的语言,是新时代的 c 语言, not c++ 。

声明新的类型

go 除了内置的整型、浮点型、复数和字符串之外,还可以灵活定义其他类型,方式也很简单:

Tags: 

堆排序、优先级队列以及相关复杂度分析

堆(heap)是一种特殊的数据结构,主要用途是排序,以及构造优先级队列。

什么是堆?

堆首先是一棵完全二叉树,结点从上到下、从左到右依次排列下来,中间没有空隙结点。完全二叉树有几个重要性质,下面的算法以及复杂度分析会用到:

  • 结点数量为 n 的完全二叉树的高度为:[log2n]+1
  • 第 i 层有 2i-1个结点;也就是每层结点数量是 q = 2 的等比数列;
  • 第 i 个结点的子结点编号是 2*i 和 2*i +1 ;

其次,堆有一个重要性质:每个结点的值都小于(或是大于)其子结点。如果是小于的话,那么树的根节点是最小元素,这样的堆是小顶堆;如果是大于的话,那么根结点是最大元素,这样的堆是大顶堆。下面均以小顶堆为例进行分析。

堆排序

Tags: 

球面两点距离计算公式

两点之间的距离怎么定义?距离,就是路径的长度。显然从一点到另一点有无数条路径,而每一条路径都有一个长度,那么我们用哪一条路径的长度来定义两点之间距离呢?毫无疑问,“最短长度”!为什么?因为它特殊,最短!

小时候我们就知道了,“平面上,两点之间直线最短”。平面上的两点距离可以用欧氏距离公式 √x2+y2 表示。不过我们现在关心的是地球上两点之间的距离。不幸的是地球近似一个球形(R ≈ 6378137m),表面近似一个球面,并不是一个平面。我们不能用欧式的直线距离,那样我们会是穿过地球内部从一点达到另外一点。(至于直线为嘛会穿过地球内部?因为球面是一个凸面!) 那球面上的最短距离是什么呢?

球面上的最短距离,也就是测地线距离,是两点与球心确定的大圆在球面上划过的弧的长度。

Tags: 

go语言的排序和搜索

晚上准备动手写点 go 的程序的时候,想起 go 如何排序的问题。排序 sort 是个基本的操作,当然搜索 search 也是。c 提供一个 qsort 和 bsearch,一个快排一个二分查找,不过是使用起来都不方便; c++ 中的 sort 貌似很不错,因为 c++ 支持泛型(或是说模板),所以很多东西使用起来很方便。go 是通过 sort 包提供排序和搜索,因为 go 暂时不支持泛型(将来也不好说支不支持),所以,go 的 sort 和 search 使用起来跟类型是有关的,或是需要像 c 一样写比较函数等,稍微显得也不是很方便。

补注: 近来又看 go 的排序, 发现以前对 go 的排序理解的有点浅了。 go 的排序思路和 c 和 c++ 有些差别。 c 默认是对数组进行排序, c++ 是对一个序列进行排序, go 则更宽泛一些,待排序的可以是任何对象, 虽然很多情况下是一个 slice (分片, 类似于数组),或是包含 slice 的一个对象。

排序(接口)的三个要素:

Tags: 

Go的内存模型

Golang 官网有一个单独的页面介绍 —— Go的内存模型。me 这里算是将它翻译一下,然后配几个小程序,再加点(个人)说明。me 表示对某些东西也不是太懂,赶脚有些地方有些模糊,甚至有些奇怪。翻译水平有限,不要骂 me,O__O"…

Tags: 

若干个神奇的程序

有时候程序神奇怪,很 bt,很不合逻辑,但是就是那么回事。前几天在 oschina 上就看到一个“平方根倒数速算法”的程序。

Tags: 

Pages