Browsed by
分类:程序设计

二维码的生成细节和原理

二维码的生成细节和原理

二维码又称QR Code,QR全称Quick Response,是一个近几年来移动设备上超流行的一种编码方式,它比传统的Bar Code条形码能存更多的信息,也能表示更多的数据类型:比如:字符,数字,日文,中文等等。这两天学习了一下二维码图片生成的相关细节,觉得这个玩意就是一个密码算法,在此写一这篇文章 ,揭露一下。供好学的人一同学习之。

关于QR Code Specification,可参看这个PDF:http://raidenii.net/files/datasheets/misc/qr_code.pdf 

基础知识

首先,我们先说一下二维码一共有40个尺寸。官方叫版本Version。Version 1是21 x 21的矩阵,Version 2是 25 x 25的矩阵,Version 3是29的尺寸,每增加一个version,就会增加4的尺寸,公式是:(V-1)*4 + 21(V是版本号) 最高Version 40,(40-1)*4+21 = 177,所以最高是177 x 177 的正方形。

下面我们看看一个二维码的样例:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (48 人打了分,平均分: 4.69 )
Loading...
伙伴分配器的一个极简实现

伙伴分配器的一个极简实现

(感谢网友 @我的上铺叫路遥 投稿)

提起buddy system相信很多人不会陌生,它是一种经典的内存分配算法,大名鼎鼎的Linux底层的内存管理用的就是它。这里不探讨内核这么复杂实现,而仅仅是将该算法抽象提取出来,同时给出一份及其简洁的源码实现,以便定制扩展。

伙伴分配的实质就是一种特殊的“分离适配”,即将内存按2的幂进行划分,相当于分离出若干个块大小一致的空闲链表,搜索该链表并给出同需求最佳匹配的大小。其优点是快速搜索合并(O(logN)时间复杂度)以及低外部碎片(最佳适配best-fit);其缺点是内部碎片,因为按2的幂划分块,如果碰上66单位大小,那么必须划分128单位大小的块。但若需求本身就按2的幂分配,比如可以先分配若干个内存池,在其基础上进一步细分就很有吸引力了。

可以在维基百科上找到该算法的描述,大体如是:

分配内存:

1.寻找大小合适的内存块(大于等于所需大小并且最接近2的幂,比如需要27,实际分配32)

1.如果找到了,分配给应用程序。
2.如果没找到,分出合适的内存块。

1.对半分离出高于所需大小的空闲内存块
2.如果分到最低限度,分配这个大小。
3.回溯到步骤1(寻找合适大小的块)
4.重复该步骤直到一个合适的块

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (14 人打了分,平均分: 4.79 )
Loading...
7个示例科普CPU Cache

7个示例科普CPU Cache

(感谢网友 @我的上铺叫路遥 翻译投稿)

CPU cache一直是理解计算机体系架构的重要知识点,也是并发编程设计中的技术难点,而且相关参考资料如同过江之鲫,浩瀚繁星,阅之如临深渊,味同嚼蜡,三言两语难以入门。正好网上有人推荐了微软大牛Igor Ostrovsky一篇博文《漫游处理器缓存效应》,文章不仅仅用7个最简单的源码示例就将CPU cache的原理娓娓道来,还附加图表量化分析做数学上的佐证,个人感觉这种案例教学的切入方式绝对是俺的菜,故而忍不住贸然译之,以飨列位看官。

原文地址:Gallery of Processor Cache Effects

大多数读者都知道cache是一种快速小型的内存,用以存储最近访问内存位置。这种描述合理而准确,但是更多地了解一些处理器缓存工作中的“烦人”细节对于理解程序运行性能有很大帮助。

在这篇博客中,我将运用代码示例来详解cache工作的方方面面,以及对现实世界中程序运行产生的影响。

下面的例子都是用C#写的,但语言的选择同程序运行状况以及得出的结论几乎没什么影响。

示例1:内存访问和运行

你认为相较于循环1,循环2会运行多快?

int[] arr = new int[64 * 1024 * 1024];

// Loop 1
for (int i = 0; i < arr.Length; i++) arr[i] *= 3;

// Loop 2
for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (36 人打了分,平均分: 4.31 )
Loading...
二叉树迭代器算法

二叉树迭代器算法

(感谢 @文艺复兴记(todd) 投递此文)

二叉树(Binary Tree)的前序、中序和后续遍历是算法和数据结构中的基本问题,基于递归的二叉树遍历算法更是递归的经典应用。

假设二叉树结点定义如下:

// C++
struct Node {
    int value;
    Node *left;
    Node *right;
}

中序递归遍历算法:

// C++
void inorder_traverse(Node *node) {
    if (NULL != node->left) {
        inorder_traverse(node->left);
    }
    do_something(node);
    if (NULL != node->right) {
        inorder_traverse(node->right);
    }
}

前序和后序遍历算法类似。

但是,仅有遍历算法是不够的,在许多应用中,我们还需要对遍历本身进行抽象。假如有一个求和的函数sum,我们希望它能应用于链表,数组,二叉树等等不同的数据结构。这时,我们可以抽象出迭代器(Iterator)的概念,通过迭代器把算法和数据结构解耦了,使得通用算法能应用于不同类型的数据结构。我们可以把sum函数定义为:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (16 人打了分,平均分: 4.06 )
Loading...
IoC/DIP其实是一种管理思想

IoC/DIP其实是一种管理思想

关于IoC的的概念提出来已经很多年了,其被用于一种面象对像的设计。我在这里再简单的回顾一下这个概念。我先谈技术,再说管理。

话说,我们有一个开关要控制一个灯的开和关这两个动作,最常见也是最没有技术含量的实现会是这个样子:

然后,有一天,我们发现需要对灯泡扩展一下,于是我们做了个抽象类:

但是,如果有一天,我们发现这个开关可能还要控制别的不单单是灯泡的东西,我们就发现这个开关耦合了灯泡这种类别,非常不利于我们的扩展,于是反转控制出现了。

就像现实世界一样,造开关的工厂根本不关心要控制的东西是什么,它只做一个开关应该做好的事,就是把电接通,把电断开(不管是手动的,还是声控的,还是光控,还是遥控的),而我们的造各种各样的灯泡(不管是日关灯,白炽灯)的工厂也不关心你用什么样的开关,反正我只管把灯的电源接口给做出来,然后,开关厂和电灯厂依赖于一个标准的通电和断电的接口。于是产生了IoC控制反转,如下图:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (22 人打了分,平均分: 4.59 )
Loading...
Javascript 装载和执行

Javascript 装载和执行

一两个月前在淘宝内网里看到一个优化Javascript代码的竞赛,发现有不少的人对Javascript的执行和装载的基础并不懂,所以,从那天起我就想写一篇文章,但一直耽搁了。自上篇《浏览器渲染原理简介》,正好也可以承前启后。

首先,我想说一下Javascript的装载和执行。通常来说,浏览器对于Javascript的运行有两大特性:1)载入后马上执行,2)执行时会阻塞页面后续的内容(包括页面的渲染、其它资源的下载)。于是,如果有多个js文件被引入,那么对于浏览器来说,这些js文件被被串行地载入,并依次执行。

因为javascript可能会来操作HTML文档的DOM树,所以,浏览器一般都不会像并行下载css文件并行下载js文件,因为这是js文件的特殊性造成的。所以,如果你的javascript想操作后面的DOM元素,基本上来说,浏览器都会报错说对象找不到。因为Javascript执行时,后面的HTML被阻塞住了,DOM树时还没有后面的DOM结点。所以程序也就报错了。

传统的方式

所以,当你写在代码中写下如下的代码:

<script type="text/javascript"
        src="http://coolshell.cn/asyncjs/alert.js"></script>

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (53 人打了分,平均分: 4.77 )
Loading...
无锁HashMap的原理与实现

无锁HashMap的原理与实现

 (本文由投稿)

在《疫苗:Java HashMap的死循环》中,我们看到,java.util.HashMap并不能直接应用于多线程环境。对于多线程环境中应用HashMap,主要有以下几种选择:

  1. 使用线程安全的java.util.Hashtable作为替代。
  2. 使用java.util.Collections.synchronizedMap方法,将已有的HashMap对象包装为线程安全的。
  3. 使用java.util.concurrent.ConcurrentHashMap类作为替代,它具有非常好的性能。

而以上几种方法在实现的具体细节上,都或多或少地用到了互斥锁。互斥锁会造成线程阻塞,降低运行效率,并有可能产生死锁、优先级翻转等一系列问题。

CAS(Compare And Swap)是一种底层硬件提供的功能,它可以将判断并更改一个值的操作原子化。关于CAS的一些应用,《无锁队列的实现》一文中有很详细的介绍。

Java中的原子操作

在java.util.concurrent.atomic包中,Java为我们提供了很多方便的原子类型,它们底层完全基于CAS操作。

例如我们希望实现一个全局公用的计数器,那么可以:

 

private AtomicInteger counter = new AtomicInteger(3);

public void addCounter() {
    for (;;) {
        int oldValue = counter.get();
        int newValue = oldValue + 1;
        if (counter.compareAndSet(oldValue, newValue))
            return;
    }
}

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (23 人打了分,平均分: 3.83 )
Loading...
浏览器的渲染原理简介

浏览器的渲染原理简介

看到这个标题大家一定会想到这篇神文《How Browsers Work》,这篇文章把浏览器的很多细节讲得很细,而且也被翻译成了中文。为什么我还想写一篇呢?因为两个原因,

1)这篇文章太长了,阅读成本太大,不能一口气读完。

2)花了大力气读了这篇文章后可以了解很多,但似乎对工作没什么帮助。

所以,我准备写下这篇文章来解决上述两个问题。希望你能在上班途中,或是坐马桶时就能读完,并能从中学会一些能用在工作上的东西。

浏览器工作大流程

废话少说,先来看个图:

从上面这个图中,我们可以看到那么几个事:

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (52 人打了分,平均分: 4.79 )
Loading...
疫苗:Java HashMap的死循环

疫苗:Java HashMap的死循环

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环。这个事情我4、5年前也经历过,本来觉得没什么好写的,因为Java的HashMap是非线程安全的,所以在并发下必然出现问题。但是,我发现近几年,很多人都经历过这个事(在网上查“HashMap Infinite Loop”可以看到很多人都在说这个事)所以,觉得这个是个普遍问题,需要写篇疫苗文章说一下这个事,并且给大家看看一个完美的“Race Condition”是怎么形成的。

问题的症状

从前我们的Java代码因为一些原因使用了HashMap这个东西,但是当时的程序是单线程的,一切都没有问题。后来,我们的程序性能有问题,所以需要变成多线程的,于是,变成多线程后到了线上,发现程序经常占了100%的CPU,查看堆栈,你会发现程序都Hang在了HashMap.get()这个方法上了,重启程序后问题消失。但是过段时间又会来。而且,这个问题在测试环境里可能很难重现。

我们简单的看一下我们自己的代码,我们就知道HashMap被多个线程操作。而Java的文档说HashMap是非线程安全的,应该用ConcurrentHashMap。

但是在这里我们可以来研究一下原因。

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (49 人打了分,平均分: 4.82 )
Loading...
从面向对象的设计模式看软件设计

从面向对象的设计模式看软件设计

前些天发了一篇《如此理解面向对象编程》的文章,然后引起了大家的热议。然后我在微博上说了一句——“那23个经典的设计模式和OO半毛钱关系没有,只不过人家用OO来实现罢了……OO的设计模式思想和Unix的设计思想基本没什么差别”,结果引来了一点点争议。所以,我写下这篇文章把我的观点说明一下。我希望这样可以让大家更容易地理解什么是设计模式。我顺便帮OO和 Unix/Linux搞搞基

什么是模式

在正式说明GoF的那23个经典的设计模式其实和OO关系不大并和Unix的设计思想很相似的这个观点之前,让我先来说说什么是模式?设计模式的英文是Design Pattern,模式是Pattern的汉译。所谓Pattern就是一种规则,或是一种模型,或是一种习惯。Pattern这个东西到处都是,并不只有技术圏子里才有。比如:

  • 文章有文章的Pattern。如新闻有新闻的Pattern(第一段话简述了整个新闻),诗歌总是抒情的,论文总是死板的,讲稿总是高谈的,漫画总是幽默的,……
  • 小说有小说的Pattern。比如,
    • 武侠小说必然要整个武林大会,整几个NB的武功和大师,分个正派和反派,还有一个或数个惊天阴谋,坏人总是要在一开始占尽优势,好人总是要力挽狂澜……
    • 言情小说总是要有第三者,总是要有负心人,里面的女子总是要哭得死去活来,但又痴心不改,……
  •  新闻联播的模式是:头10分钟领导很忙,中间10分钟人民很幸福,后10分钟国外很乱。中国政府官方宣传稿也模式也很明显,各种赞美,口号,胜利,总是要坚持个什么,团结个什么,迈向个什么,某某精神,某某思想,群众情绪稳定,不明真相,等等……
  • 春节的模式是,回家,吃饺子,放个鞭炮,给压岁钱,同学聚会…… 同学聚会的模式基本上都是在饭桌上回忆一下校园时光,比较一下各自的当前处境,调戏一下女同学……
  • …… ……

这就是Pattern,只要你细心观察,你会发现这世间有很多很多的Pattern。

阅读全文 Read More

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