Posted Updated 2 hours read (About 14663 words)

从头编写一款时间序列数据库

本文转自 从头编写一款时间序列数据库 （翻译：Colstuwjx），请支持原作者。

我从事监控方面的工作。尤其是专注在 Prometheus，一款内置了自己定制的时间序列数据库的监控系统，以及它和 Kubernetes 的集成工作。

从很多方面来说，Kubernetes 表现出了一切 Prometheus 专门设计的东西。它使得持续部署，自动扩缩，以及高度动态环境的其他功能更易于实现。它的查询语言和操作模型，还有许多其他概念方面的决策使得 Prometheus 尤其适合这样的环境。然而，如果被监控的工作负载变得更加显著动态的话，这也会给监控系统本身带来新的压力。基于这一点的考虑，与其再次回顾 Prometheus 已经很好解决的问题，还不如专注于在这样一个高度动态或短生命周期服务的环境里提高它的性能。

Prometheus 的存储层在历史上有着惊人的性能表现，一个单台服务器每秒可以摄取多达 100 万个采样，数百万个时间序列，同时仅占用令人惊叹的少量磁盘空间。尽管当前的存储已经给我们提供了不错的服务，笔者构思了一个新设计的存储子系统用来纠正现有解决方案的一些短板，并且可以用来配备支撑下一代的集群规模。

Read more
Posted Updated 18 minutes read (About 2628 words)

引用计数与垃圾收集之比较

原文地址：http://blog.codingnow.com/2008/06/gc.html

本质上来说，引用计数策略和垃圾收集策略都属于资源的自动化管理。所谓自动化管理，就是在逻辑层不知道资源在什么时候被释放掉，而依赖底层库来维持资源的生命期。

而手工管理，则是可以准确的知道资源的生命期，在准确的位置回收它。在 C++ 中，体现在析构函数中写明 delete 用到的资源，并由编译器自动生成的代码析构基类和成员变量。

所以，为 C++ 写一个垃圾收集器，并不和手工管理资源冲突。自动化管理几乎在所有有点规模的 C++ 工程中都在使用，只不过用的是引用计数的策略而非垃圾收集而已。也就是说，我们使用 C++ 或 C 长期以来就是结合了手工管理和自动管理在构建系统了。无论用引用计数，还是用垃圾收集，软件实现的细节上，该手工管理的地方我们依旧可以手工管理。

为什么要用资源生命期自动管理？

Read more
Posted Updated 18 minutes read (About 2680 words)

Makefile 简易教程

Makefile 简介

在软件开发中，make通常被视为一种软件构建工具。该工具主要经由读取一种名为“makefile”或“Makefile”的文件来实现软件的自动化建构。它会通过一种被称之为“target”概念来检查相关文件之间的依赖关系，这种依赖关系的检查系统非常简单，主要通过对比文件的修改时间来实现。在大多数情况下，我们主要用它来编译源代码，生成结果代码，然后把结果代码连接起来生成可执行文件或者库文件。

优点与缺点

与大多数古老的Unix工具一样，make也分别有着人数众多的拥护者和反对者。它在适应现代大型软件项目方面有着许许多多的问题。但是，依然有很多人坚定地认为（包括我）它能应付绝大多数常见的情况，而且使用非常的简单，功能强大，表达清楚。无论如何，make如今仍然被用来编译很多完整的操作系统，而且它的那些“更为现代”的替代品们在基本操作上与它没有太大差别。

当然，随着现代的集成开发环境（IDE）的诞生，特别是非Unix的平台上，很多程序员不再手动管理依靠关系检查，甚至不用去管哪些文件是这个项目的一部分，而是把这些任务交给了他们的开发环境去做。类似的，很多现代的编程语言有自己专属的、能高效配置依赖关系的方法（譬如Ant）。

主要版本

make程序经历过各方多次的改写与重写，各方都依据自己的需要做了一些特定的改良。目前市面上主要流行有以下几种版本：

  • GNU make： GNU make对make的标准功能（通过clean-room工程）进行了重新改写，并加入作者自认为值得加入的新功能，常和GNU编译系统一起被使用，是大多数GNU Linux默认安装的工具。

  • BSD make： 该版本是从Adam de Boor制作的版本上发展起来的。它在编译目标的时有并发计算的能力。主要应用于FreeBSD，NetBSD和OpenBSD这些系统。

  • Microsoft nmake： 该版本主要用于微软的Windows系统中，需要注意的是，微软的nmake与Unix项目中的nmake是两种不同的东西，千万不要混淆。

从一个简单的例子开始

我们可以用K&R C中4.5那个例子来做个说明。在这个例子中，我们会看到一份主程序代码 main.c、三份函数代码 getop.c、stack.c、getch.c以及一个头文件 calc.h。通常情况下，我们需要这样编译它：

1
gcc -o calc main.c getch.c getop.c stack.c

如果没有makefile，在开发+调试程序的过程中，我们就需要不断地重复输入上面这条编译命令，要不就是通过终端的历史功能不停地按上下键来寻找最近执行过的命令。这样做两个缺陷：

一旦终端历史记录被丢失，我们就不得不从头开始；

任何时候只要我们修改了其中一个文件，上述编译命令就会重新编译所有的文件，当文件足够多时这样的编译会非常耗时。

那么 Makefile 又能做什么呢？我们先来看一个最简单的 makefile 文件：

1
2
calc: main.c getch.c getop.c stack.c
    gcc -o calc main.c getch.c getop.c stack.c

现在你看到的就是一个最基本的Makefile语句，它主要分成了三个部分，第一行冒号之前的 calc，我们称之为目标（target），被认为是这条语句所要处理的对象，具体到这里就是我们所要编译的这个程序 calc。冒号后面的部分（main.c getch.c getop.c stack.c），我们称之为依赖关系表，也就是编译calc所需要的文件，这些文件只要有一个发生了变化，就会触发该语句的第三部分，我们称其为命令部分，相信你也看得出这就是一条编译命令。现在我们只要将上面这两行语句写入一个名为Makefile或者makefile的文件，然后在终端中输入make命令，就会看到它按照我们的设定去编译程序了。

请注意，在第二行的“gcc”命令之前必须要有一个tab缩进。语法规定Makefile中的任何命令之前都必须要有一个tab缩进，否则make就会报错。

接下来，让我们来解决一下效率方面的问题，先初步修改一下上面的代码：

1
2
3
4
5
6
cc = gcc
prom = calc
source = main.c getch.c getop.c stack.c

$(prom): $(source)
    $(CC) -o $(prom) $(source)

如你所见，我们在上述代码中定义了三个常量 cc、prom 以及 source。它们分别告诉了make我们要使用的编译器、要编译的目标以及源文件。这样一来，今后我们要修改这三者中的任何一项，只需要修改常量的定义即可，而不用再去管后面的代码部分了。

请注意，很多教程将这里的 cc、prom 和 source 称之为变量，个人认为这是不妥当的，因为它们在整个文件的执行过程中并不是可更改的，作用也仅仅是字符串替换而已，非常类似于C语言中的宏定义。或者说，事实上它就是一个宏。

但我们现在依然还是没能解决当我们只修改一个文件时就要全部重新编译的问题。而且如果我们修改的是 calc.h 文件，make就无法察觉到变化了（所以有必要为头文件专门设置一个常量，并将其加入到依赖关系表中）。下面，我们来想一想如何解决这个问题。考虑到在标准的编译过程中，源文件往往是先被编译成目标文件，然后再由目标文件连接成可执行文件的。我们可以利用这一点来调整一下这些文件之间的依赖关系：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
cc = gcc
prom = calc
deps = calc.h
obj = main.o getch.o getop.o stack.o

$(prom): $(obj)
    $(CC) -o $(prom) $(obj)

main.o: main.c $(deps)
    $(CC) -c main.c

getch.o: getch.c $(deps)
    $(CC) -c getch.c

getop.o: getop.c $(deps)
    $(CC) -c getop.c

stack.o: stack.c $(deps)
    $(CC) -c stack.c

这样一来，上面的问题显然是解决了，但同时我们又让代码变得非常啰嗦，啰嗦往往伴随着低效率，是不祥之兆。经过再度观察，我们发现所有.c都会被编译成相同名称的 .o 文件。我们可以根据该特点再对其做进一步的简化：

1
2
3
4
5
6
7
8
9
10
cc = gcc
prom = calc
deps = calc.h
obj = main.o getch.o getop.o stack.o

$(prom): $(obj)
    $(CC) -o $(prom) $(obj)

%.o: %.c $(deps)
    $(CC) -c $< -o $@

在这里，我们用到了几个特殊的宏。首先是 %.o:%.c，这是一个模式规则，表示所有的.o目标都依赖于与它同名的 .c 文件（当然还有deps中列出的头文件）。再来就是命令部分的 $< 和 $@，其中$<代表的是依赖关系表中的第一项（如果我们想引用的是整个关系表，那么就应该使用 $^），具体到我们这里就是%.c。而$@代表的是当前语句的目标，即 %.o。这样一来，make命令就会自动将所有的 .c 源文件编译成同名的 .o 文件。不用我们一项一项去指定了。整个代码自然简洁了许多。

到目前为止，我们已经有了一个不错的makefile，至少用来维护这个小型工程是没有什么问题了。当然，如果要进一步增加上面这个项目的可扩展性，我们就会需要用到一些Makefile中的伪目标和函数规则了。例如，如果我们想增加自动清理编译结果的功能就可以为其定义一个带伪目标的规则；

1
2
3
4
5
6
7
8
9
10
11
12
13
cc = gcc
prom = calc
deps = calc.h
obj = main.o getch.o getop.o stack.o

$(prom): $(obj)
    $(CC) -o $(prom) $(obj)

%.o: %.c $(deps)
    $(CC) -c $< -o $@

clean:
    rm -rf $(obj) $(prom)

有了上面最后两行代码，当我们在终端中执行 make clean 命令时，它就会去删除该工程生成的所有编译文件。

另外，如果我们需要往工程中添加一个 .c 或 .h，可能同时就要再手动为 obj 常量再添加第一个 .o 文件，如果这列表很长，代码会非常难看，为此，我们需要用到Makefile中的函数，这里我们演示两个：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
cc = gcc
prom = calc
deps = $(shell find ./ -name "*.h")
src = $(shell find ./ -name "*.c")
obj = $(src:%.c=%.o) 

$(prom): $(obj)
    $(CC) -o $(prom) $(obj)

%.o: %.c $(deps)
    $(CC) -c $< -o $@

clean:
    rm -rf $(obj) $(prom)

其中，shell 函数主要用于执行shell命令，具体到这里就是找出当前目录下所有的 .c 和 .h 文件。而 $(src:%.c=%.o) 则是一个字符替换函数，它会将 src 所有的 .c 字串替换成 .o，实际上就等于列出了所有 .c 文件要编译的结果。有了这两个设定，无论我们今后在该工程加入多少 .c 和 .h 文件，Makefile都能自动将其纳入到工程中来。

到这里，我们就基本上将日常会用到的Makefile写法介绍了一遍。如果你想了解更多关于makefile和make的知识，请参考 GNU Make Manual。

原文地址：http://www.epubit.com.cn/article/546

Posted Updated 29 minutes read (About 4361 words)

协程的历史，现在和未来

原文地址：http://blog.youxu.info/2014/12/04/coroutine/

本文原发于《程序员》2014年11月刊，发表时略有修改。

计算机科学是一门应用科学，几乎所有概念都是为了理解或解决实际问题而生的。协程 (Coroutine) 的出现也不例外。协程的概念，最早可以追溯到写作 COBOL 语言编译器中的技术难题。

Read more
Posted Updated 11 minutes read (About 1600 words)

IO 设计模式：Reactor 和 Proactor 对比

原文地址：https://segmentfault.com/a/1190000002715832
Posted by: 大CC | 28APR,2015
博客：blog.me115.com [订阅]
微博：新浪微博

平时接触的开源产品如Redis、ACE，事件模型都使用的Reactor模式；而同样做事件处理的Proactor，由于操作系统的原因，相关的开源产品也少；这里学习下其模型结构，重点对比下两者的异同点；

反应器Reactor

Reactor模式结构

Read more
Posted Updated 24 minutes read (About 3667 words)

如何在 Git 里撤销（几乎）任何操作

任何版本控制系统的一个最有的用特性就是“撤销 (undo)”你的错误操作的能力。在 Git 里，“撤销” 蕴含了不少略有差别的功能。

当你进行一次新的提交的时候，Git 会保存你代码库在那个特定时间点的快照；之后，你可以利用 Git 返回到你的项目的一个早期版本。

在本篇博文里，我会讲解某些你需要“撤销”已做出的修改的常见场景，以及利用 Git 进行这些操作的最佳方法。

撤销一个“已公开”的改变

场景： 你已经执行了 git push, 把你的修改发送到了 GitHub，现在你意识到这些 commit 的其中一个是有问题的，你需要撤销那一个 commit.

方法： git revert <SHA>

原理： git revert 会产生一个新的 commit，它和指定 SHA 对应的 commit 是相反的（或者说是反转的）。如果原先的 commit 是“物质”，新的 commit 就是“反物质” — 任何从原先的 commit 里删除的内容会在新的 commit 里被加回去，任何在原先的 commit 里加入的内容会在新的 commit 里被删除。

这是 Git 最安全、最基本的撤销场景，因为它并不会改变历史 — 所以你现在可以 git push 新的“反转” commit 来抵消你错误提交的 commit。

修正最后一个 commit 消息

场景： 你在最后一条 commit 消息里有个笔误，已经执行了 git commit -m "Fxies bug #42"，但在 git push 之前你意识到消息应该是 "Fixes bug #42"。

方法： git commit --amend 或 git commit --amend -m "Fixes bug #42"

原理： git commit --amend 会用一个新的 commit 更新并替换最近的 commit ，这个新的 commit 会把任何修改内容和上一个 commit 的内容结合起来。如果当前没有提出任何修改，这个操作就只会把上次的 commit 消息重写一遍。

撤销“本地的”修改

场景： 一只猫从键盘上走过，无意中保存了修改，然后破坏了编辑器。不过，你还没有 commit 这些修改。你想要恢复被修改文件里的所有内容 — 就像上次 commit 的时候一模一样。

方法： git checkout -- <bad filename>

原理： git checkout 会把工作目录里的文件修改到 Git 之前记录的某个状态。你可以提供一个你想返回的分支名或特定 SHA ，或者在缺省情况下，Git 会认为你希望 checkout 的是 HEAD，当前 checkout 分支的最后一次 commit。

记住： 你用这种方法“撤销”的任何修改真的会完全消失。因为它们从来没有被提交过，所以之后 Git 也无法帮助我们恢复它们。你要确保自己了解你在这个操作里扔掉的东西是什么！（也许可以先利用 git diff 确认一下）

重置“本地的”修改

场景： 你在本地提交了一些东西（还没有 push），但是所有这些东西都很糟糕，你希望撤销前面的三次提交 — 就像它们从来没有发生过一样。

方法： git reset <last good SHA> 或 git reset --hard <last good SHA>

原理： git reset 会把你的代码库历史返回到指定的 SHA 状态。 这样就像是这些提交从来没有发生过。缺省情况下，git reset 会保留工作目录。这样，提交是没有了，但是修改内容还在磁盘上。这是一种安全的选择，但通常我们会希望一步就“撤销”提交以及修改内容 — 这就是 --hard 选项的功能。

在撤销“本地修改”之后再恢复

场景： 你提交了几个 commit，然后用 git reset --hard 撤销了这些修改（见上一段），接着你又意识到：你希望还原这些修改！

方法： git reflog 和 git reset 或 git checkout

原理： git reflog 对于恢复项目历史是一个超棒的资源。你可以恢复几乎 任何东西 — 任何你 commit 过的东西 — 只要通过 reflog。

你可能已经熟悉了 git log 命令，它会显示 commit 的列表。git reflog 也是类似的，不过它显示的是一个 HEAD 发生改变的时间列表.

一些注意事项：

  • 它涉及的只是 HEAD 的改变。在你切换分支、用 git commit 进行提交、以及用 git reset 撤销 commit 时，HEAD 会改变，但当你用 git checkout -- <bad filename>撤销时（正如我们在前面讲到的情况），HEAD 并不会改变 — 如前所述，这些修改从来没有被提交过，因此 reflog 也无法帮助我们恢复它们。
  • git reflog 不会永远保持。Git 会定期清理那些 “用不到的” 对象。不要指望几个月前的提交还一直躺在那里。
  • 你的 reflog 就是你的，只是你的。你不能用 git reflog 来恢复另一个开发者没有 push 过的 commit。

reflog

那么…你怎么利用 reflog 来“恢复”之前“撤销”的 commit 呢？它取决于你想做到的到底是什么：

  • 如果你希望准确地恢复项目的历史到某个时间点，用 git reset --hard <SHA>
  • 如果你希望重建工作目录里的一个或多个文件，让它们恢复到某个时间点的状态，用 git checkout <SHA> -- <filename>
  • 如果你希望把这些 commit 里的某一个重新提交到你的代码库里，用 git cherry-pick <SHA>

利用分支的另一种做法

场景： 你进行了一些提交，然后意识到你开始 check out 的是 master 分支。你希望这些提交进到另一个特性（feature）分支里。

方法： git branch feature, git reset --hard origin/master, and git checkout feature

原理： 你可能习惯了用 git checkout -b <name> 创建新的分支 — 这是创建新分支并马上 check out 的流行捷径 — 但是你不希望马上切换分支。这里， git branch feature 创建一个叫做 feature 的新分支并指向你最近的 commit，但还是让你 check out 在 master 分支上。

下一步，在提交任何新的 commit 之前，用 git reset --hard 把 master 分支倒回 origin/master 。不过别担心，那些 commit 还在 feature 分支里。

最后，用 git checkout 切换到新的 feature 分支，并且让你最近所有的工作成果都完好无损。

及时分支，省去繁琐

场景： 你在 master 分支的基础上创建了 feature 分支，但 master 分支已经滞后于 origin/master 很多。现在 master 分支已经和 origin/master 同步，你希望在 feature 上的提交是从现在开始，而不是也从滞后很多的地方开始。

方法： git checkout feature 和 git rebase master

原理： 要达到这个效果，你本来可以通过 git reset (不加 --hard, 这样可以在磁盘上保留修改) 和 git checkout -b <new branch name> 然后再重新提交修改，不过这样做的话，你就会失去提交历史。我们有更好的办法。

git rebase master 会做如下的事情：

  • 首先它会找到你当前 check out 的分支和 master 分支的共同祖先。
  • 然后它 reset 当前 check out 的分支到那个共同祖先，在一个临时保存区存放所有之前的提交。
  • 然后它把当前 check out 的分支提到 master 的末尾部分，并从临时保存区重新把存放的 commit 提交到 master 分支的最后一个 commit 之后。

大量的撤销/恢复

场景： 你向某个方向开始实现一个特性，但是半路你意识到另一个方案更好。你已经进行了十几次提交，但你现在只需要其中的一部分。你希望其他不需要的提交统统消失。

方法： git rebase -i <earlier SHA>

原理： -i 参数让 rebase 进入“交互模式”。它开始类似于前面讨论的 rebase，但在重新进行任何提交之前，它会暂停下来并允许你详细地修改每个提交。

rebase -i 会打开你的缺省文本编辑器，里面列出候选的提交。如下所示：

rebase-interactive1

前面两列是键：第一个是选定的命令，对应第二列里的 SHA 确定的 commit。缺省情况下， rebase -i 假定每个 commit 都要通过 pick 命令被运用。

要丢弃一个 commit，只要在编辑器里删除那一行就行了。如果你不再需要项目里的那几个错误的提交，你可以删除上例中的1、3、4行。

如果你需要保留 commit 的内容，而是对 commit 消息进行编辑，你可以使用 reword 命令。 把第一列里的 pick 替换为 reword (或者直接用 r)。有人会觉得在这里直接重写 commit 消息就行了，但是这样不管用 rebase -i 会忽略 SHA 列前面的任何东西。它后面的文本只是用来帮助我们记住 0835fe2 是干啥的。当你完成 rebase -i 的操作之后，你会被提示输入需要编写的任何 commit 消息。

如果你需要把两个 commit 合并到一起，你可以使用 squash 或 fixup 命令，如下所示：

rebase-interactive2

squash 和 fixup 会“向上”合并 — 带有这两个命令的 commit 会被合并到它的前一个 commit 里。在这个例子里， 0835fe2 和 6943e85 会被合并成一个 commit， 38f5e4e 和 af67f82 会被合并成另一个。

如果你选择了 squash， Git 会提示我们给新合并的 commit 一个新的 commit 消息； fixup 则会把合并清单里第一个 commit 的消息直接给新合并的 commit 。 这里，你知道 af67f82 是一个“完了完了….” 的 commit，所以你会留着 38f5e4e as的 commit 消息，但你会给合并了 0835fe2 和 6943e85 的新 commit 编写一个新的消息。

在你保存并退出编辑器的时候，Git 会按从顶部到底部的顺序运用你的 commit。你可以通过在保存前修改 commit 顺序来改变运用的顺序。如果你愿意，你也可以通过如下安排把 af67f82 和 0835fe2 合并到一起：

rebase-interactive3

修复更早期的 commit

场景： 你在一个更早期的 commit 里忘记了加入一个文件，如果更早的 commit 能包含这个忘记的文件就太棒了。你还没有 push，但这个 commit 不是最近的，所以你没法用 commit --amend.

方法： git commit --squash <SHA of the earlier commit> 和 git rebase --autosquash -i <even earlier SHA>

原理： git commit --squash 会创建一个新的 commit ，它带有一个 commit 消息，类似于 squash! Earlier commit。 (你也可以手工创建一个带有类似 commit 消息的 commit，但是 commit --squash 可以帮你省下输入的工作。)

如果你不想被提示为新合并的 commit 输入一条新的 commit 消息，你也可以利用 git commit --fixup 。在这个情况下，你很可能会用 commit --fixup ，因为你只是希望在 rebase 的时候使用早期 commit 的 commit 消息。

rebase --autosquash -i 会激活一个交互式的 rebase 编辑器，但是编辑器打开的时候，在 commit 清单里任何 squash 和 fixup 的 commit 都已经配对到目标 commit 上了，如下所示：

rebase-autosquash

在使用 --squash 和 --fixup 的时候，你可能不记得想要修正的 commit 的 SHA 了— 只记得它是前面第 1 个或第 5 个 commit。你会发现 Git 的 ^ 和 ~ 操作符特别好用。HEAD^ 是 HEAD 的前一个 commit。 HEAD~4 是 HEAD 往前第 4 个 – 或者一起算，倒数第 5 个 commit。

停止追踪一个文件

场景： 你偶然把 application.log 加到代码库里了，现在每次你运行应用，Git 都会报告在 application.log 里有未提交的修改。你把 *.login 放到了 .gitignore 文件里，可文件还是在代码库里 — 你怎么才能告诉 Git “撤销” 对这个文件的追踪呢？

方法： git rm --cached application.log

原理： 虽然 .gitignore 会阻止 Git 追踪文件的修改，甚至不关注文件是否存在，但这只是针对那些以前从来没有追踪过的文件。一旦有个文件被加入并提交了，Git 就会持续关注该文件的改变。类似地，如果你利用 git add -f 来强制或覆盖了 .gitignore， Git 还会持续追踪改变的情况。之后你就不必用 -f 来添加这个文件了。

如果你希望从 Git 的追踪对象中删除那个本应忽略的文件， git rm --cached 会从追踪对象中删除它，但让文件在磁盘上保持原封不动。因为现在它已经被忽略了，你在 git status 里就不会再看见这个文件，也不会再偶然提交该文件的修改了。

这就是如何在 Git 里撤销任何操作的方法。要了解更多关于本文中用到的 Git 命令，请查看下面的有关文档：

原文地址：https://github.com/blog/2019-how-to-undo-almost-anything-with-git
译文地址：http://blog.jobbole.com/87700/

Posted Updated 15 minutes read (About 2261 words)

mmap 详解

共享内存可以说是最有用的进程间通信方式，也是最快的 IPC 形式, 因为进程可以直接读写内存，而不需要任何数据的拷贝。对于像管道和消息队列等通信方式，则需要在内核和用户空间进行四次的数据拷贝，而共享内存则只拷贝两次数据: 一次从输入文件到共享内存区，另一次从共享内存区到输出文件。实际上，进程之间在共享内存时，并不总是读写少量数据后就解除映射，有新的通信时，再重新建立共享内存区域。而是保持共享区域，直到通信完毕为止，这样，数据内容一直保存在共享内存中，并没有写回文件。共享内存中的内容往往是在解除映射时才写回文件的。因此，采用共享内存的通信方式效率是非常高的。

一、传统文件访问

UNIX访问文件的传统方法是用 open 打开它们, 如果有多个进程访问同一个文件，则每一个进程在自己的地址空间都包含有该文件的副本，这不必要地浪费了存储空间。下图说明了两个进程同时读一个文件的同一页的情形。系统要将该页从磁盘读到高速缓冲区中，每个进程再执行一个存储器内的复制操作将数据从高速缓冲区读到自己的地址空间。

二、共享存储映射

现在考虑另一种处理方法：进程 A 和进程 B 都将该页映射到自己的地址空间，当进程 A 第一次访问该页中的数据时，它生成一个缺页中断。内核此时读入这一页到内存并更新页表使之指向它。以后，当进程 B 访问同一页面而出现缺页中断时，该页已经在内存，内核只需要将进程 B 的页表登记项指向次页即可。如下图所示：

三、mmap() 及其相关系统调用

mmap() 系统调用使得进程之间通过映射同一个普通文件实现共享内存。普通文件被映射到进程地址空间后，进程可以向访
问普通内存一样对文件进行访问，不必再调用 read()，write()等操作。

mmap() 系统调用形式如下：

1
void* mmap(void* addr, size_t len, int prot, int flags, int fd, off_t offset)

mmap 的作用是映射文件描述符 fd 指定文件的 [off, off+len] 区域至调用进程的 [addr, addr+len] 的内存区域, 如下图所示:

参数 fd 为即将映射到进程空间的文件描述字，一般由 open() 返回，同时，fd 可以指定为 -1，此时须指定 flags 参数中的 MAP_ANON，表明进行的是匿名映射（不涉及具体的文件名，避免了文件的创建及打开，很显然只能用于具有亲缘关系的进程间通信）。
len 是映射到调用进程地址空间的字节数，它从被映射文件开头 offset 个字节开始算起。
prot 参数指定共享内存的访问权限。可取如下几个值的或：PROT_READ（可读），PROT_WRITE（可写），PROT_EXEC（可执行），PROT_NONE（不可访问）。
flags 由以下几个常值指定：MAP_SHARED, MAP_PRIVATE, MAP_FIXED，其中，MAP_SHARED, MAP_PRIVATE 必选其一，而 MAP_FIXED 则不推荐使用。
offset 参数一般设为 0，表示从文件头开始映射。
参数 addr 指定文件应被映射到进程空间的起始地址，一般被指定一个空指针，此时选择起始地址的任务留给内核来完成。函数的返回值为最后文件映射到进程空间的地址，进程可直接操作起始地址为该值的有效地址。

四、mmap的两个例子

范例中使用的测试文件 data.txt：

1
2
3
4
aaaaaaaaa
bbbbbbbbb
ccccccccc
ddddddddd
  1. 通过共享映射的方式修改文件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <error.h>

#define BUF_SIZE 100

int main(int argc, char **argv)
{
    int fd, nread, i;
    struct stat sb;
    char *mapped, buf[BUF_SIZE];

    for (i = 0; i < BUF_SIZE; i++) {
        buf[i] = '#';
    }

    /* 打开文件 */
    if ((fd = open(argv[1], O_RDWR)) < 0) {
        perror("open");
    }

    /* 获取文件的属性 */
    if ((fstat(fd, &sb)) == -1) {
        perror("fstat");
    }

    /* 将文件映射至进程的地址空间 */
    if ((mapped = (char *)mmap(NULL, sb.st_size, PROT_READ | 
                    PROT_WRITE, MAP_SHARED, fd, 0)) == (void *)-1) {
        perror("mmap");
    }

    /* 映射完后, 关闭文件也可以操纵内存 */
    close(fd);

    printf("%s", mapped);

    /* 修改一个字符,同步到磁盘文件 */
    mapped[20] = '9';
    if ((msync((void *)mapped, sb.st_size, MS_SYNC)) == -1) {
        perror("msync");
    }

    /* 释放存储映射区 */
    if ((munmap((void *)mapped, sb.st_size)) == -1) {
        perror("munmap");
    }

    return 0;
}
  1. 私有映射无法修改文件
1
2
3
4
5
/* 将文件映射至进程的地址空间 */
if ((mapped = (char *)mmap(NULL, sb.st_size, PROT_READ | 
    PROT_WRITE, MAP_PRIVATE, fd, 0)) == (void *)-1) {
    perror("mmap");
}

五、使用共享映射实现两个进程之间的通信

两个程序映射同一个文件到自己的地址空间，进程 A 先运行, 每隔两秒读取映射区域，看是否发生变化。
进程 B 后运行，它修改映射区域，然后退出，此时进程 A 能够观察到存储映射区的变化。
进程 A 的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <error.h>

#define BUF_SIZE 100

int main(int argc, char **argv)
{
    int fd, nread, i;
    struct stat sb;
    char *mapped, buf[BUF_SIZE];

    for (i = 0; i < BUF_SIZE; i++) {
        buf[i] = '#';
    }

    /* 打开文件 */
    if ((fd = open(argv[1], O_RDWR)) < 0) {
        perror("open");
    }

    /* 获取文件的属性 */
    if ((fstat(fd, &sb)) == -1) {
        perror("fstat");
    }

    /* 将文件映射至进程的地址空间 */
    if ((mapped = (char *)mmap(NULL, sb.st_size, PROT_READ | 
                    PROT_WRITE, MAP_SHARED, fd, 0)) == (void *)-1) {
        perror("mmap");
    }

    /* 文件已在内存, 关闭文件也可以操纵内存 */
    close(fd);
    
    /* 每隔两秒查看存储映射区是否被修改 */
    while (1) {
        printf("%s\n", mapped);
        sleep(2);
    }

    return 0;
}

进程 B 的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <sys/mman.h>  
#include <sys/stat.h>  
#include <fcntl.h>  
#include <stdio.h>  
#include <stdlib.h>  
#include <unistd.h>  
#include <error.h>  
  
#define BUF_SIZE 100  
  
int main(int argc, char **argv)  
{  
    int fd, nread, i;  
    struct stat sb;  
    char *mapped, buf[BUF_SIZE];  
  
    for (i = 0; i < BUF_SIZE; i++) {  
        buf[i] = '#';  
    }  
  
    /* 打开文件 */  
    if ((fd = open(argv[1], O_RDWR)) < 0) {  
        perror("open");  
    }  
  
    /* 获取文件的属性 */  
    if ((fstat(fd, &sb)) == -1) {  
        perror("fstat");  
    }  
  
    /* 私有文件映射将无法修改文件 */  
    if ((mapped = (char *)mmap(NULL, sb.st_size, PROT_READ |   
                    PROT_WRITE, MAP_PRIVATE, fd, 0)) == (void *)-1) {  
        perror("mmap");  
    }  
  
    /* 映射完后, 关闭文件也可以操纵内存 */  
    close(fd);  
  
    /* 修改一个字符 */  
    mapped[20] = '9';  
   
    return 0;  
}

六、通过匿名映射实现父子进程通信

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define BUF_SIZE 100

int main(int argc, char** argv)
{
    char    *p_map;

    /* 匿名映射,创建一块内存供父子进程通信 */
    p_map = (char *)mmap(NULL, BUF_SIZE, PROT_READ | PROT_WRITE,
            MAP_SHARED | MAP_ANONYMOUS, -1, 0);

    if(fork() == 0) {
        sleep(1);
        printf("child got a message: %s\n", p_map);
        sprintf(p_map, "%s", "hi, dad, this is son");
        munmap(p_map, BUF_SIZE); //实际上，进程终止时，会自动解除映射。
        exit(0);
    }

    sprintf(p_map, "%s", "hi, this is father");
    sleep(2);
    printf("parent got a message: %s\n", p_map);

    return 0;
}

七、对 mmap() 返回地址的访问

linux 采用的是页式管理机制。对于用 mmap() 映射普通文件来说，进程会在自己的地址空间新增一块空间，空间大小由 mmap() 的 len 参数指定，注意，进程并不一定能够对全部新增空间都能进行有效访问。进程能够访问的有效地址大小取决于文件被映射部分的大小。简单的说，能够容纳文件被映射部分大小的最少页面个数决定了进程从 mmap() 返回的地址开始，能够有效访问的地址空间大小。超过这个空间大小，内核会根据超过的严重程度返回发送不同的信号给进程。可用如下图示说明：

总结一下就是，文件大小，mmap 的参数 len 都不能决定进程能访问的大小，而是容纳文件被映射部分的最小页面数决定进程能访问的大小。下面看一个实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdio.h>

int main(int argc, char** argv)
{
    int fd,i;
    int pagesize,offset;
    char *p_map;
    struct stat sb;

    /* 取得page size */
    pagesize = sysconf(_SC_PAGESIZE);
    printf("pagesize is %d\n",pagesize);

    /* 打开文件 */
    fd = open(argv[1], O_RDWR, 00777);
    fstat(fd, &sb);
    printf("file size is %zd\n", (size_t)sb.st_size);

    offset = 0;    
    p_map = (char *)mmap(NULL, pagesize * 2, PROT_READ|PROT_WRITE, 
            MAP_SHARED, fd, offset);
    close(fd);
    
    p_map[sb.st_size] = '9';  /* 导致总线错误 */
    p_map[pagesize] = '9';    /* 导致段错误 */

    munmap(p_map, pagesize * 2);

    return 0;
}

原文地址：http://kenby.iteye.com/blog/1164700

Posted Updated 7 minutes read (About 997 words)

浅显理解 Python 闭包

闭包这个概念在 JavaScript 中讨论和使用得比较多，不过在 Python 中却不是那么显而易见，之所以说“不是那么”，是因为即使用到了，也没用注意到而已，比如定义一个 Decorator 时，就已经用到闭包了。网上对闭包的各种解释，感觉非常晦涩，在这里谈谈我的浅显认识：要形成闭包，首先得有一个嵌套的函数，即函数中定义了另一个函数，闭包则是一个集合，它包括了外部函数的局部变量，这些局部变量在外部函数返回后也继续存在，并能被内部函数引用。

举个例子

这是个经常使用到的例子，定义一个函数 generate_power_func，它返回另一个函数，现在闭包形成的条件已经达到。

1
2
3
4
5
6
def generate_power_func(n):
    print "id(n): %X" % id(n)
    def nth_power(x):
        return x**n
    print "id(nth_power): %X" % id(nth_power)
    return nth_power

对于内部函数 nth_power，它能引用到外部函数的局部变量 n，而且即使 generate_power_func 已经返回。把这种现象就称为闭包。具体使用一下。

1
2
3
4
5
>>> raised_to_4 = generate_power_func(4)
id(n): 246F770
id(nth_power): 2C090C8
>>> repr(raised_to_4)
'<function nth_power at 0x2c090c8>'

从结果可以看出，当 generate_power_func(4) 执行后, 创建和返回了 nth_power 这个函数对象，内存地址是 0x2C090C8,并且发现 raised_to_4 和它的内存地址相同，即 raised_to_4 只是这个函数对象的一个引用。先在全局命名空间中删除 generate_power_func，再试试会出现什么结果。

1
2
3
>>> del generate_power_func
>>> raised_to_4(2)
16

啊哈，居然没出现错误， nth_power 是怎么知道 n 的值是 4，而且现在 generate_power_func 甚至都不在这个命名空间了。对，这就是闭包的作用，外部函数的局部变量可以被内部函数引用，即使外部函数已经返回了。

closure 属性和 cell 对象

现在知道闭包是怎么一回事了，那就到看看闭包到底是怎么回事的时候了。Python 中函数也是对象，所以函数也有很多属性，和闭包相关的就是 __closure__ 属性。__closure__ 属性定义的是一个包含 cell 对象的元组，其中元组中的每一个 cell 对象用来保存作用域中变量的值。

1
2
3
4
5
6
>>> raised_to_4.__closure__
(<cell at 0x2bf4ec0: int object at 0x246f770>,)
>>> type(raised_to_4.__closure__[0])
<type 'cell'>
>>> raised_to_4.__closure__[0].cell_contents
4

就如刚才所说，在 raised_to_4 的 __closure__ 属性中有外部函数变量 n 的引用，通过内存地址可以发现，引用的都是同一个 n。如果没用形成闭包，则 __closure__ 属性为 None。对于 Python 具体是如何实现闭包的，可以查看 Python闭包详解，它通过分析 Python 字节码来讲述闭包的实现。

最后总结

闭包特性有着非常多的作用，不过都是需要时才会不经意的用上，不要像使用设计模式一样去硬套这些法则。这篇文章按照自己的理解翻译至 Python Closures Explained，可能和原文有些不同之处，如有疑惑，请查看原文。附上一些参考资料。

  1. 闭包的概念、形式与应用: 可以从其中了解闭包的应用
  2. Python闭包详解：从字节码出发了解 Python 闭包的实现机制
  3. 理解Javascript的闭包: 从 Javascript 的闭包中了解一些闭包特性，可以和 Python 作下对比

原文地址：https://serholiu.com/python-closures

Posted Updated 33 minutes read (About 4882 words)

利用图片指纹检测高相似度图片

大概五年前吧，我那时还在为一家约会网站做开发工作。他们是早期创业公司，但他们也开始拥有了一些稳定用户量。不像其他约会网站，这家公司向来以洁身自好为主要市场形象。它不是一个供你鬼混的网站——是让你能找到忠实伴侣的地方。

由于投入了数以百万计的风险资本（在US大萧条之前），他们关于真爱并找寻灵魂伴侣的在线广告势如破竹。Forbes(福布斯，美国著名财经杂志)采访了他们。全国性电视节目也对他们进行了专访。早期的成功促成了事业起步时让人垂涎的指数级增长现象——他们的用户数量以每月加倍的速度增长。对他们而言，一切都似乎顺风顺水。

但他们有一个严重的问题——色情问题。

该约会网站的用户中会有一些人上传色情图片，然后设置为其个人头像。这种行为破坏了很多其他用户的体验——导致很多用户取消了会员。

可能对于现在的一些约会网站随处可见几张色情图片也许并不能称之为是问题。或者可以说是习以为常甚至有些期待，只是一个被接受然后被无视的在线约会的副产品。

然而，这样的行为既不应该被接受也应该被忽视。

别忘了，这次创业可是将自己定位在优秀的约会天堂，免于用户受到困扰其他约会网站的污秽和垃圾的烦扰。简而言之，他们拥有很实在的以风险资本作为背后支撑的名声，而这也正是他们需要保持的风格。

该约会网站为了能迅速阻止色情图片的爆发可以说是不顾一切了。他们雇佣了图片论坛版主团队，真是不做其他事只是每天盯着监管页面8个小时以上，然后移除任何被上传到社交网络的色情图片。

毫不夸张的说，他们投入了数万美元（更不用说数不清的人工小时）来解决这个问题，然而也仅仅只是缓解，控制情况不变严重而不是在源头上阻止。

色情图片的爆发在2009年的七月达到了临界水平。8个月来第一次用户量没能翻倍（甚至已经开始减少了）。更糟糕的是，投资者声称若该公司不能解决这个问题将会撤资。事实上，污秽的潮汐早已开始冲击这座象牙塔了，将它推翻流入大海也不过是时间问题。

正在这个约会网站巨头快要撑不住时，我提出了一个更鲁棒的长期解决方案：如果我们使用图片指纹来与色情图片的爆发斗争呢？

你看，每张图片都有一个指纹。正如人的指纹可以识别人，图片的指纹能识别图片。

这促使了一个三阶段算法的实现：

  1. 为不雅图片建立指纹，然后将图片指纹存储在一个数据库中。

  2. 当一个用户上传一份新的头像时，我们会将它与数据库中的图片指纹对比。如果上传图片的指纹与数据库任意一个不雅图片指纹相符，我们就阻止用户将该图片设置为个人头像。

  3. 当图片监管人标记新的色情图片时，这些图片也被赋予指纹并存入我们的数据库，建立一个能用于阻止非法上传且不断进化的数据库。

我们的方法，尽管不十分完美，但是也卓有成效。慢慢地，色情图片爆发的情况有所减慢。它永远不会消失——但这个算法让我们成功将非法上传的数量减少了**80%**以上。

这也挽回了投资者的心。他们继续为我们提供资金支持——直到萧条到来，我们都失业了。

回顾过去时，我不禁笑了。我的工作并没持续太久。这个公司也没有坚持太久。甚至还有几个投资者卷铺盖走人了。

但有一样确实存活了下来。提取图片指纹的算法。几年之后，我把这个算法的基本内容分享出来，期望你们可以将它应用到你们自己的项目中。

但最大的问题是，我们怎么才能建立图片指纹呢？

继续读下去一探究竟吧。

即将要做的事情

我们打算用图片指纹进行相似图片的检测。这种技术通常被称为“感知图像hash”或是简单的“图片hash”。

什么是图片指纹/图片哈希

图片hash是检测一张图片的内容然后根据检测的内容为图片建立一个唯一值的过程。

比如，看看本文最上面的那张图片。给定一张图片作为输入，应用一个hash函数，然后基于图片的视觉计算出一个图片hash。相似的图片也应当有相似的hash值。图片hash算法的应用使得相似图片的检测变得相当简单了。

特别地，我们将会使用“差别Hash”或简单的DHash算法计算图片指纹。简单来说，DHash算法着眼于两个相邻像素之间的差值。然后，基于这样的差值，就建立起一个hash值了。

为什么不使用md5,sha-1等算法？

不幸的是，我们不能在实现中使用加密hash算法。由于加密hash算法的本质使然，输入文件中非常微小的差别也能造成差异极大的hash值。而在图片指纹的案例中，我们实际上希望相似的输入可以有相似的hash输出值。

图片指纹可以用在哪里？

正如我上面举的例子，你可以使用图片指纹来维护一个保存不雅图片的数据库——当用户尝试上传类似图片时可以发出警告。

你可以建立一个图片的逆向搜索引擎，比如TinEye，它可以记录图片以及它们出现的相关网页。

你还可以使用图片指纹帮助管理你个人的照片收集。假设你有一个硬盘，上面有你照片库的一些局部备份，但需要一个方法删除局部备份，一张图片仅保留一份唯一的备份——图片指纹可以帮你做到。

简单来说，你几乎可以将图片指纹/哈希用于任何需要你检测图片的相似副本的场景中。

需要的库有哪些？

为了建立图片指纹方案，我们打算使用三个主要的Python包：

你可以使用下列命令一键安装所需要的必备库：

1
$ pip install pillow imagehash

第一步：为一个图片集建立指纹

第一步就是为我们的图片集建立指纹。

也许你会问，但我们不会，我们不会使用那些我为那家约会网站工作时的色情图片。相反，我创建了一个可供使用的人工数据集。

对计算机视觉的研究人员而言，数据集 CALTECH-101是一个传奇般的存在。它包含来自101个不同分类中的至少7500张图片，内容分别有人物，摩托车和飞机。

从这7500多张图片中，我随机的挑选了17张。

然后，从这17张随机挑选的图片中，以几个百分点的比例随机放大/缩小并创建N张新图片。这里我们的目标是找到这些近似副本的图片——有点大海捞针的感觉。

你也想创建一个类似的数据集用于工作吗？那就下载 CALTECH-101数据集，抽取大概17张图片即可，然后运行repo下的脚本文件gather.py。

回归正题，这些图片除了宽度和高度，其他各方面都是一样的。而且因为他们没有相同的形状，我们不能依赖简单的md5校验和。最重要的是，有相似内容的图片可能有完全不相同的md5哈希。然而，采取图片哈希，相似内容的图片也有相似的哈希指纹。

所以赶紧开始写代码为数据集建立指纹吧。创建一个新文件，命名为index.py，然后开始工作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# import the necessary packages
from PIL import Image
import imagehash
import argparse
import shelve
import glob

# construct the argument parse and parse the arguments
ap = argparse.ArgumentParser()
ap.add_argument("-d", "--dataset", required = True,
help = "path to input dataset of images")
ap.add_argument("-s", "--shelve", required = True,
help = "output shelve database")
args = vars(ap.parse_args())

要做的第一件事就是引入我们需要的包。我们将使用PIL或Pillow中的Image类载入硬盘上的图片。这个imagehash库可以被用于构建哈希算法。

Argparse库用于解析命令行参数，shelve库用作一个存储在硬盘上的简单键值对数据库（Python字典）。glob库能很容易的获取图片路径。

然后传递命令行参数。第一个，—dataset是输入图片库的路径。第二个，—shelve是shelve数据库的输出路径。

下一步，打开shelve数据库以写数据。这个db数据库存储图片哈希。更多的如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# loop over the image dataset
for imagePath in glob.glob(args["dataset"] + "/*.jpg"):
# load the image and compute the difference hash
    image = Image.open(imagePath)
    h = str(imagehash.dhash(image))

# extract the filename from the path and update the database
# using the hash as the key and the filename append to the
# list of values
    filename = imagePath[imagePath.rfind("/") + 1:]
    db[h] = db.get(h, []) + [filename]

# close the shelf database
db.close()

以上就是大部分工作的内容了。开始循环从硬盘读取图片，创建图片指纹并存入数据库。

现在，来看看整个范例中最重要的两行代码：

1
2
filename = imagePath[imagePath.rfind("/") + 1:]
db[h] = db.get(h, []) + [filename]

正如本文早些时候提到的，有相同指纹的图片被认为是一样的。

因此，如果我们的目标是找到近似图片，那就需要维护一个有相同指纹值的图片列表。

而这也正是这几行代码做的事情。

前一个代码段提取了图片的文件名。而后一个代码片段维护了一个有相同指纹值的图片列表。

为了从我们的数据库中提取图片指纹并建立哈希数据库，运行下列命令：

1
$ python index.py —dataset images —shelve db.shelve

这个脚本会运行几秒钟，完成后，就会出现一个名为db.shelve的文件，包含了图片指纹和文件名的键值对。

这个基本算法正是几年前我为这家约会创业公司工作时使用的算法。我们获得了一个不雅图片集，为其中的每张图片构建一个图片指纹并将其存入数据库。当来一张新图片时，我只需简单地计算它的哈希值，检测数据库查看是否上传图片已被标识为非法内容。

下一步中，我将展示实际如何执行查询，判定数据库中是否存在与所给图片具有相同哈希值的图片。

第二步：查询数据集

既然已经建立了一个图片指纹的数据库，那么现在就该搜索我们的数据集了。

打开一个新文件，命名为search.py，然后开始写代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# import the necessary packages
from PIL import Image
import imagehash
import argparse
import shelve

# construct the argument parse and parse the arguments
ap = argparse.ArgumentParser()
ap.add_argument("-d", "--dataset", required = True,
    help = "path to dataset of images")
ap.add_argument("-s", "--shelve", required = True,
    help = "output shelve database")
ap.add_argument("-q", "--query", required = True,
    help = "path to the query image")
args = vars(ap.parse_args())

我们需要再一次导入相关的包。然后转换命令行参数。需要三个选项，—dataset初始图片集的路径，—shelve，保存键值对的数据库的路径，—query，查询/上传图片的路径。我们的目标是对于每个查询图片，判定数据库中是否已经存在。

现在，写代码执行实际的查询：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# open the shelve database
db = shelve.open(args["shelve"])

# load the query image, compute the difference image hash, and
# and grab the images from the database that have the same hash
# value
query = Image.open(args["query"])
h = str(imagehash.dhash(query))
filenames = db[h]
print "Found %d images" % (len(filenames))

# loop over the images
for filename in filenames:
    image = Image.open(args["dataset"] + "/" + filename)
    image.show()

# close the shelve database
db.close()

首先打开数据库，然后载入硬盘上的图片，计算图片的指纹，找到具有相同指纹的所有图片。

如果有图片具有相同的哈希值，会遍历这些图片并展示在屏幕上。

这段代码使我们仅仅使用指纹值就能判定图片是否已在数据库中存在。

结果

正如本文早些时候提到的，我从CALTECH-101数据集的7500多张图片中随机选取17张，然后通过任意缩放一部分点产生N张新的图片。

这些图片在尺寸上仅仅是少数像素不同—但也是因为这一点我们不能依赖于文件的md5哈希（这一点已在“优化算法”部分进行了详尽的描述）。然而，我们可以使用图片哈希找到近似图片。

打开你的终端并执行下述命令：

1
$ python search.py —dataset images —shelve db.shelve —query images/84eba74d-38ae-4bf6-b8bd-79ffa1dad23a.jpg

如果一切顺利你就可以看到下述结果：

左边是输入图片。载入这张图片，计算它的图片指纹，在数据库中搜索指纹查看是否存在有相同指纹的图片。

当然——正如右边所示，我们的数据集中有其他两张指纹相同的图片。尽管从截图中还不能十分明显的看出，这些图片，虽然有完全相同的视觉内容，也不是完全相同！这三张图片的高度宽度各不相同。

尝试一下另外一个输入图片：

1
$ python search.py —dataset images —shelve db.shelve —query images/9d355a22-3d59-465e-ad14-138a4e3880bc.jpg

下面是结果：

左边仍然是我们的输入图片。正如右边展示的，我们的图片指纹算法能够找出具有相同指纹的三张完全相同的图片。

最后一个例子：

1
$ python search.py —dataset images —shelve db.shelve —query images/5134e0c2-34d3-40b6-9473-98de8be16c67.jpg

这一次左边的输入图片是一个摩托车。拿到这张摩托车图片，计算它的图片指纹，然后在指纹数据库中查找该指纹。正如我们在右边看到的，我们也能判断出数据库中有三张图片具有相同指纹。

优化算法

有很多可以优化本算法的方法——但最关键性的是要考虑到相似但不相同的哈希。

比如，本文中的图片仅仅是一小部分点重组了（依比例增大或减小）。如果一张图片以一个较大的因素调整大小，或者纵横比被改变了，对应的哈希就会不同了。

然而，这些图片应该仍然是相似的。

为了找到相似但不相同的图片，我们需要计算汉明距离（Hamming distance）.汉明距离被用于计算一个哈希中的不同位数。因此，哈希中只有一位不同的两张图片自然比有10位不同的图片更相似。

然而，我们遇到了第二个问题——算法的可扩展性。

考虑一下：我们有一张输入图片，又被要求在数据库中找到所有相似图片。然后我们必须计算输入图片和数据库中的每一张图片之间的汉明距离。

随着数据库规模的增长，和数据库比对的时间也随着延长。最终，我们的哈希数据库会达到一个线性比对已经不实际的规模。

解决办法，虽然已超出本文范围，就是利用 K-d trees 和 VP trees 将搜索问题的复杂度从线性减小到次线性。

总结

本文中我们学会了如何构建和使用图片哈希来完成相似图片的检测。这些图片哈希是使用图片的视觉内容构建的。

正如一个指纹可以识别一个人，图片哈希也能唯一的识别一张图片。

使用图片指纹的知识，我们建立了一个仅使用图片哈希就能找到和识别具有相似内容的图片的系统。

然后我们又演示了图片哈希是如何应用于快速找到有相似内容的图片。

从 repo 目录下下载代码。

周末学计算机视觉

如果你很喜欢本文而且还想了解更多与计算机视觉，图片处理以及建立图片搜索引擎相关的东西，那就去我的博客吧，地址是 PyImageSearch.com。

祝福！

译文地址：http://www.pyimagesearch.com/
原文地址：https://realpython.com/blog/python/fingerprinting-images-for-near-duplicate-detection/

Posted Updated 15 minutes read (About 2306 words)

云平台之 SaaS 随想

原文地址：http://88250.b3log.org/saas-essay

SaaS 平台

以应用为中心

“平台”本来就比较泛，再加上“SaaS”的话就更飘渺了。

我们先从一个简单的场景来看：

  1. 开发者开发应用后在市场上线
  2. 用户购买应用使用
  3. 开发者通过市场反馈调整运维，为后续版本计划提供依据
  4. 新版本上线，用户升级使用

这是以应用为中心的一个闭环（市场-开发-运维-市场），实现了应用的整个生命周期，我们可以把平台看成是这个场景的支撑，场景中的所有活动都是在平台上完成的，整个场景就是一个 SaaS 生态系统。

Read more
Follow

Tags

Android1
Arch Linux2
C1
DDNS1
Docker5
Fedora1
GC1
Git1
Golang7
Google1
HTC1
Intel1
K8S18
KVM1
Kubelet1
Kubernetes18
Linux4
MMap1
Makefile1
NAS2
NIO2
Openstack1
PaaS1
PostgreSQL1
Power Designer1
Prometheus1
Python15
Ruby2
SRE1
SSD1
SaaS1
Tornado1
Windows1
Youtube1
devicemapper1
dnsmasq1
e2e1
etcd1
hostapd1
terraform1
youtube-dl1
主板1
云计算14
交易1
人工智能1
刷机1
协程1
原创51
固态硬盘1
图像处理1
垃圾回收3
多线程1
存储1
安卓1
投资1
摄影1
操作系统1
期货1
机器学习1
树莓派5
游戏1
爬虫4
硬件2
笔记7
算法6
维修1
编程语言4
网络2
股票1
花生壳1
虚拟机1
蚁群算法1
读书笔记1
转载19
运维7
连连看1
金融1
闭包1
非阻塞2
黑客技术1

Links

Recents

Archives

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×