Enterprise Just Builder

Solution for Enterprise Software Architecture

算法与数据结构

机器学习(1)数据挖掘 机器学习 和人工智能的区别

本文主要分为两部分,第一部分阐述数据挖掘(data mining)、机器学习(machine learning)和人工智能(AI)之间的区别。这三者的区别主要是目的不同,其手段(算法,模型)有很大的重叠,所以容易混淆。第二部分主要阐述以上的技能与数据科学(data science)的关系,以及数据科学(data science)和商业分析(business analytics)之间的关系。

数据挖掘 VS. 机器学习VS. 人工智能
数据挖掘 (data mining): 有目的地从现有大数据中提取数据的模式 pattern 和模型 model。
关键字:模式提取,大数据。

数据挖掘是从现有的信息(existing information)中提取数据的模式(pattern)和模型(model),即精选出最重要的信息,以用于未来机器学习和 AI 的数据使用。其核心目的是找到数据变量之间的关系。其发展出来的主要原因是大数据的发展,用传统的数据分析的方式已经无能处理那么多大量的看似不相关的数据的处理,因此需要数据挖掘技术去提取各种数据和变量之间的相互关系,从而精炼数据。

数据挖掘本质上像是机器学习和人工智能的基础,他的主要目的是从各种各样的数据来源中,提取出超集(superset)的信息,然后将这些信息合并让你发现你从来没有想到过的模式和内在关系。这就意味着,数据挖掘不是一种用来证明假说的方法,而是用来构建各种各样的假说的方法。数据挖掘不能告诉你这些问题的答案,他只能告诉你,A 和 B 可能存在相关关系,但是它无法告诉你 A 和 B 存在什么相关关系。

机器学习(machine learning): 自动地从过往的经验中学习新的知识。
关键字:关键字: 自动化,自我优化,预测,training data,推荐系统

>>> 阅读全文

 

, ,

用图着色来解决数独问题

在本文中,我将简单介绍图着色(graph coloring) 的概念,并演示如何用这一概念来解决 9×9 的数独(Sudoku Puzzle)。本文假设读者已对图(graph)的概念和表现形式相当熟悉。1

揭秘图着色
图是一组彼此之间互相链接的对象的数学表示。对象表示为顶点(节点),链接则称为边。

图着色则是为图的顶点指定”颜色”,让相邻的两个顶点不能共享相同的颜色。比如在上图中顶点 1 和 2 不能用相同的颜色因为有一条边连接着它们。然而顶点 2 和 3 可以用相同的颜色,因为它们彼此并未连接。下面可能的着色图之一。

很显然,图可以有多种可能的着色。我们的目标是力求使用最少的颜色。图1-3是另外两个可能的着色图。着色图(1)使用了3种颜色,而着色图(2)使用5种颜色,因此 着色图(1)比着色图(2)更好。

对于给定的图,着色是是为了使图可以正常着色的最少颜色数。使用至多 k 种颜色的着色被称为 K-着色(比如上面的例子中,着色图(1)为3-着色,而着色图(2)是5-着色)。

>>> 阅读全文

 

无锁双向链表

基于锁的同步机制总是受到象优先级反转(priority inversion )和死锁的困扰,即使这样,无锁同步还未引起重视。原因是要编写正确且高效的无锁代码实在困难1。本文演示了一个无锁双向链表的实现,实用且易于理解。第一个无锁双向链表是由 H°akan Sundell 实现的,本文中的方案利用了单字 (single-word) 的比较并转换(CAS — compare-and-swap)原子原语。在附录中提供了本方案与 H°akan Sundell 实现的链表的比较结果。 2

背景: 原子操作与 CAS
原子操作是指一系列必须整体完成的操作步骤,如果任何一步操作没有完成,那么所有完成的步骤都必须回滚,这样就可以保证要么所有操作步骤都未完成,要么所有操作步骤都被完成。在单核系统里,单个的机器指令可以看成是原子操作(如果有编译器优化、乱序执行等情况除外);在多核系统中,单个的机器指令就不是原子操作,因为多核系统里是多指令流并行运行的,一个核在执行一个指令时,其他核同时执行的指令有可能操作同一块内存区域,从而出现数据竞争现象。多核系统中的原子操作通常使用内存栅障(memory barrier)来实现,即一个 CPU 核在执行原子操作时,其他 CPU 核必须停止对内存操作或者不对指定的内存进行操作,这样才能避免数据竞争问题。3

因此在 X86 平台上,Intel 提供了在指令执行期间对总线加锁的手段。CPU 芯片上有一条引线 #HLOCKpin,如果汇编程序中的某条指令带了前缀 “LOCK”,CPU 执行到这条指令时就会 #HLOCKpin 的电位拉低直到该指令结束,从而将总线锁住,这样同一总线上其它 CPU 就暂时不能通过总线访问内存了,这样保证了指令在多处理器环境中的原子性。

所谓比较并交换 (CAS) 是在多线程中可用来获得同步的原子指令。CAS 操作包含三个操作数 —— 目标值(V)、原值(A)和新值(B)。CAS 指令会先将目标值 V 与原值 A 进行比较,如果二者相同,那么就可以新值 B 赋予目标值。

在 Windows 和 .NET 平台,由于历史原因,CAS 被写做 Interlocked API。原子操作在 Intel 架构 CPU 对应的汇编指令有 XCHG、CMPXCHG、INC 等,当然还得加上 LOCK 作为前缀。

>>> 阅读全文

 

, , ,

设计模式之 CQRS 模式简介

用户和信息系统交互的主要行为就是对数据库或数据仓库进行 CRUD 操作,设计者通常为此构建出一个可供创建、读取、更新和删除的数据模型。该模型的接口就是供存储和获取数据之用的。但这种标准的分层体系结构并未处理两个问题:协作(collaboration)与失效(staleness)。1

协作是指多个参与者使用/修改相同的数据集的情况 — 尽管他们未必真的是相互协作。而失效是指在协作环境中,数据已显示给用户之后,相同的数据可能已经被另一个参与者修改 — 即数据失效了。出于性能使用缓存则进一步加剧了数据失效的问题。解决这两大问题,正是命令查询责任分离模式 (CQRS — Command Query Responsibility Segregation )背后的驱动力。

在图1-1 中,我们可以看到用户基本上会发起两类操作:命令(Command) 和查询(Query),如显示当季销量最好的产品属于查询,而提交订单、修改密码等则属于命令,也就是说:

  • 命令操作:用于修改单个对象或者整个系统的状态(有时也称为 modifiers 或 mutators).
  • 查询操作:用于返回结果且不改变对象状态

从事务的角度上看,查询操作与命令操作对事务的要求不一样。由于查询操作不会改变系统状态,因而,不会产生最终的数据不一致。从请求响应的角度来看,查询操作常常需要同步请求,实时返回结果;命令操作则不然,因为我们并不期待命令操作必须返回结果,这就可以采用fire-and-forget方式,而这种方式正是运用异步操作的前提。

对于大多数软件系统而言,查询操作发起的频率通常要远远高于命令操作。由于查询操作不会造成数据的修改,因而它属于一种幂等操作,可以反复地发起,而不用担心会对系统造成影响。基于这种特性,我们还可以为其提供缓存,从而改善查询的性能。命令操作则与之相反,它会直接影响数据的改变。

>>> 阅读全文

 

,

字符串查找算法 (三) Morris-Pratt 查找算法 (KMP)

从前面两节的介绍,我们看到不管是 暴力字符查找 还是 Rabin-Karp 字符查找都不是太有效率。为了改进算法,我们首先需要详细了解其原理。我们已经知道暴力字符匹配很慢,之后我们 Rabin-Karp 算法中在引入了哈希函数来试图改进它。问题是 Rabin-Karp 和暴力字符查找的复杂度是一样的,都是 O(mn)。

很显然,我们需要一种不同的方法,但在了解不同的方法之前,让我们看看暴力字符串搜索的问题出在什么地方。在仔细了解其原理之后,我们可以回答这个问题。

在暴力匹配中,我们将文本的每一个字符和模式字串的第一个字符相比较。在匹配的情况下,我们转而比较模式的第二个字符和文本的下一个字符…。问题是,一旦这时发生不匹配的情况,就需要在文本中回溯多个位置。因此这种技术无法被优化。

如上图所示,一旦有个字符不匹配,我们必须回溯,从一个已经查找过的位置重新开始比较。在例子中,我们比较了文本和模式的第一,第二,第三个字符,在第四个字符出现了不匹配,然后……我们回溯回文本的第二字母开始重新比较。比如 在 “abcdefg” 中搜索 “abcdeg”,前五个字符 “abcdeg” 都是匹配的,第六个字符 f 和 g 不匹配,这时候,对于暴力搜索算法,i 将会+1,整个匹配重新开始一次,这就是回溯了。

仔细想一下,回溯其实完全可以避免的,因为如果知道是在第六个字符不匹配,那就说明前五个字符都是匹配的,对于这个例子来说,我们肯定知道源字符串前面五个字符是”abcde”。

>>> 阅读全文

 

字符串查找算法 (二) Rabin-Karp 算法

文章评价:
暴力字符串匹配(brute force string matching)是子串匹配算法中最基本的一种,它确实有自己的优点,比如它并不需要对文本(text)或模式串(pattern)进行预处理。然而它最大的问题就是运行速度太慢,所以在很多场合下暴力字符串匹配算法并不是那么有用。我们需要一些更快的方法来完成模式匹配的工作,然而在此之前,我们还是回过头来再看一遍暴力法匹配,以便更好地理解其他子串匹配算法。

如下图所示,在暴力字符串匹配里,我们将文本中的每一个字符和模式串的第一个字符进行比对。一旦我们找到了一个匹配,我们就将文本中写一个字符取出来和模式串的第二个字符进行比较。

该算法运行速度慢的主要原因有二:一方面,我们需要对文本中的每个字符都进行比对;另一方面,即使我们发现模式串首字符和文本中的某个字符相匹配,我们仍然需要对模式串中剩下的所有符号(字符)挨个进行比对,才知道它们是不是出现在接下来的文本中。那么,是否有别的方法可以用来判断文本是否包含模式串呢?

答案是肯定的,确实存在一种更快的方法。为了避免挨个字符对文本和模式串进行比较,我们可以尝试一次性判断两者是否相等。因此,我们需要一个好的哈希函数(hash function)。通过哈希函数,我们可以算出模式串的哈希值,然后将它和文本中的子串的哈希值进行比较。这里有一个问题,我们必须保证该哈希函数能够对一个较长的字符串返回较短的哈希值。然而,我们又不能指望较长的模式串能得到较短的哈希值。但除此之外,这个新方法在速度上应该能比暴力法有显著提升。

这种更快的方法就是Rabin-Karp算法。

>>> 阅读全文

 

字符串查找算法 (一)暴力查找算法(BF)

对数据库开发和文本处理软件而言,字符串匹配(String matching)可谓至关重要。幸运的是,在所有的现代程序设计语言和代码库中,字符串处理函数比比皆是,它们对我们的日常工作大有裨益。字符串算法主要可分为几大类。字符串查找就是其中之一,我们要做的就是回答此模式串是否在文本中出现过。

概述

进行字符串查找时,最基本的方法就是“暴力(brute force)”法,通常来说,所有名字里含有“暴力(brute force)”二字的算法都很慢。

暴力算法核心思想是:T 是长度为 N 文本串,P 是长度为 M 模式串。 首先将 S[1] 和 P[1] 比较,若相等,则再比较 S[2] 和 P[2],如果一直到P[M]为止等相等,则匹配成功;若 S[1] 和 P[1] 不等,则 P 向右移动一个字符的位置,再依次进行比较。这意味着需要检查文本中的每个字符与模式串(通常比文本短)的匹配情况。。算法是效率最低的算法。

该算法最坏情况下要进行M*(N-M+1)次比较,时间复杂度为O(M*N)。

>>> 阅读全文

 

二叉树

原文 原作者: Nick Parlante
本文的主旨是介绍二叉树(binary-tree)的基本概念,并通过 C/C++ 和 Java 的实现来解决一系列的实际问题。二叉树有很优雅的递归指针结构,所以也是个学习递归指针算法的好机会。

二叉树简介
二叉树由节点组成,其中每个节点包含一个“左”指针,一个“右”指针和一个数据元素。”根”指针指向树的最顶层节点。左、右的指针以递归方式指向两边较小的”子树”。空指针则表示二叉树不带任何元素 —-— 空的树。正规的递归的定义如下:一个既不是空的(用空指针表示)也不是由单一节点组成的二叉树,其左右节点(recursive definition ahead) 各指向一个二叉树。

“二叉搜索树”(BST) 或”有序二叉树”是一种节点按顺序排列的二进制树:对于每一个节点,其左子树中的所有元素都是小于等于该节点 (< =),和其右子树的所有元素均大于该节点 (>)。满足上面条件的树是二叉搜索树–例如 “根”节点是 5,和其左子树节点 (1、 3、 4) 是小于等于 5,和其右子树节点(6 9) 均大于 5。递归的,每个子树都必须遵循二进制搜索树约束: 在 (1、 3、 4) 子树,3 是根节点,而且 1 < = 3 和 4 > 3。请注意:描述问题要特别注意措词 — “二叉搜索树”和”二叉树”是不同的。

树的底端的节点的子树为空,因此被称为“叶”节点(1,4,6)而其他的节点则成为“内部”节点(3,5,9)。

Binary Search Tree Niche

>>> 阅读全文

 

哈希算法

文章评分:

哈希(Hash)算法就是单向散列算法,它把某个较大的集合P映射到另一个较小的集合Q中,假如这个算法叫 H,那么就有 Q = H(P)。对于 P 中任何一个值 p 都有唯一确定的 q 与之对应,但是一个 q 可以对应多个 p。作为一个有用的 Hash 算法,H 还应该满足:H(p) 速度比较快;给出一个 q,很难算出一个 p 满足 q = H(p);给出一个 p1,很难算出一个不等于 p1 的 p2 使得 H(p1)=H(p2)。

数学原理听起来很抽象,这里我们举个有趣的例子。农场里有很多的小猪,每个的体重都不一样,假设体重分布比较平均,都在100到120公斤之间(我们考虑到公斤级别),我们按照体重区间来分,建了10个小猪圈。 1号圈圈养90-92公斤的小猪,2号圈圈养92-94公斤的小猪,以此类推…。然后把每个小猪,按照体重赶进各自的猪圈里,记录档案。

好了,如果我们要精确找到某个小猪怎么办呢?我们需要每个猪圈,每个小猪的比对吗? 当然不需要了。 我们先看看要找的这个小猪的体重,然后就找到了对应的猪圈了。 在这个猪圈里的小猪的数量就相对很少了。 我们在这个猪圈里就可以相对快的找到我们要找到的那个小猪了。

对应回 hash 算法:就是按照 hashcode 分配不同的猪圈,将 hashcode 相同的猪放到一个猪圈里。 查找的时候,先找到 hashcode 对应的猪圈,然后在逐个比较里面的小猪。

>>> 阅读全文