Jump to Navigation

数据结构与算法

对实现了RUDP的enet库定制化改造

对实现了RUDP的enet库定制化改造

### enet库介绍
enet是使用C语言实现的、简洁的、基于UDP的网络开发库。
最重要的特性是实现了UDP包的可选的可靠性、有序性。

除些以外,还实现了透明压缩功能,降低传输网络负载等。

但为了保持库本身的简单、可移植、方便嵌入特性,忽略掉了认证,服务发现,加密等功能。

enet库文档:http://enet.bespin.org/index.html

### 我的定制需求
我需要使用其reliable部分代码,即接收包要按照发送包的顺序,并且不能有丢包。
但是我的包并非来自UDP socket,所有无法直接使用现有的原装代码。

Qt5的ruby语言绑定实现系列: Clang AST 树遍历优化

目前要实现查找AST树中匹配方法或者函数symbol符号名字的Decl,通过遍历AST树方式实现。
但是,现在这个方式耗时很多,占用整个过程的50%时间,希望能在这个点上优化掉接近一半的时间。

以下就这个功能特点,分析整理可能的优化机制。

虽然所有是在整个AST树中,但实际不需要在整个树的根开始查找,而是从树的一个节点开始。
遍历过程,可能要加入新的新的结点。

实现上,可以看作一个森林数据结构,初始状态时,森林只有一个根节点。
执行过程中,遍历遇到另个函数声明,如果在这次调用中需要,则需要把这个节点加入到森林中,作为森林的一个新的根节点。

根据以上分析,实现执行会有回溯过程,并且回溯时的节点也变化了。
可以暂时把这种方式叫做回溯遍历方法。

考虑到这个过程,只需要关注inline的方法或者函数,可以不断进行深度遍历,
在整个遍历路径上遇符合条件的节点,回调执行相应的处理函数。
如果遍历方式没有问题的话,应该能够一次遍历完成所有的处理工作。
暂时把这种方式叫做单次扩展遍历方法。

分析完功能需求和可能的方式,接下来分析clang提供的遍历相关功能。

simhash(局部敏感哈希)示例演示

simhash(局部敏感哈希)示例演示
海明哈希算法

新窗口演示:http://qtcnet.duapp.com/demos/simhash.php

实际项目中的常见算法

【编者按】本文原始内容来源于stackexchange,遵循cc-wiki协议;

近日Emanuele Viola在Stackexchange上提了这样的一个问题,他希望有人能够列举一些目前软件、硬件中正在使用的算法的实际案例来证明算法的重要性,对于大家可能给到的回答,他还提出了几点要求:

JSON-RPC协议与网络传输

通常据说的JSON-RPC协议指的是数据格式协议,
对于数据包的传输,可以使用不同的网络连接协议实现,
最基本的只使用tcp传输,所有传递的数据包以 json格式为准。
对于无法识别成json格式的数据包,像其他的类似软件一样认为协议错误。

另外,其他的像http,websocket这些通用协议,都可以作为JSON-RPC的传输层使用。
RPC的概念是一个远程过程调用,想当于通过网络执行一段远程服务器上的代码。
那么这段代码可以理解成普通编程语言中的函数,
它有函数名字和函数参数,这样程序的其他位置可以通过名字与参数调用。
JSON-RPC协议也是如此,给远程服务器一段功能代码一个名字与输入参数,
然后通过网络发起这段功能代码的调用,执行并返回结果。

所以,JSON-RPC协议标准,每次调用都需要提供一个方法名,一组方法参数。

初步尝试opencv图像识别训练

在了解了一些关于opencv的功能与基本用法之后,开学尝试使用opencv做一些实际应用。
本次选定一个功能应用,识别验证码功能。
验证码用于网站的防伪,一般为大小写字母与数字,4-6个字符不等。

使用opencv识别,分解为以下步骤,
验证码图片的切割,把图片中的几个字符拆开成单独的字符图片。
使用拆开的字符图片执行opencv训练,
使用训练好的分类器文件,识别目标中的字符。

对于图片验证码的切割,又分为下面几个步骤,
图像去噪,去除图像的背景,混淆随机点/线
图像的加强或者平滑处理,让其中的字符更清楚
根据字符轮廓,切割出字符图片。

这一步中,对于稍微复杂的验证码,也非常难以做到,
例如在去噪的时候,会把字符线条也去掉了部分,对于比较细的字体,可能就被过滤掉了。
对于有比较粗的混淆线时,这种线一般与字符交叉重叠,
在计算字符的轮廓时,会出现两个字符粘连一在起的情况。
图片加强时,也会加强没有去掉的混淆点/线,影响识别字符轮廓
还有些字符距离可能由于倾斜或者字体大小不同而靠的非常近,

Paxos算法简述

Paxos算法是分布式中一个著名的一致性算法。它的假设前提是,在分布式系统中进程之间的通信会出现丢失、延迟、重复等现象,但不会出现传错的现象。Paxos算法就是为了保证在这样的系统中进程间基于消息传递就某个值达成一致。要理解paxos算法最好还是看作者本人(Leslie Lamport)的论文《The Part-Time Parliament》。在这里只是简单地介绍paxos最核心的思想,其实它还有很多的内容。

提议者和决议者是这里最重要的两个角色,paxos最核心的算法就是定义他们之间的通讯规则来保证某个变量在分布式系统中的一致性。

提议者是提出议案的人。每个议案都有一个议案号,议案号是区别不同议案的唯一标识,而且议案号是有大小次序的。这里的提议者不像我们真实世界里的提议者,这里的提议者提的议案内容不能随心所欲。提议者和决议者要遵循下面的规则:

1) 提议者先给议案决定一个议案号,注意整个系统中议案号都不能重复的。然后发消息给所有决议者,告诉他们我要提出第几号议案。

rsync 的核心算法

本文转载自酷壳coolshel  作者 陈皓   

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

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

BPS 2.2 发布,高性能 B 树实现

BPS 使用 twist 指针实现了B树,基于哈希表的集合,性能非常高。
BPS 2.2 增加了丢失数据结构清算程序,增加了两个用于获取第一个和最后一个元素的数据检索程序。

BPS应该是基于内存的。

借地发另几个类似的各有物色的btree算法实现:
基于磁盘的libgist: http://gist.cs.berkeley.edu/libgistv1/user_manual.html

基于密度的聚类算法-DBSCAN

一 什么是基于密度的聚类算法

由于层次聚类算法和划分式聚类算往往只能发现凸形的聚类簇。为了弥补这一缺陷,发现各种任意形状的聚类簇,开发出基于密度的聚类算法。这类算法认为,在整个样本空间点中,各目标类簇是由一群的稠密样本点组成的,而这些稠密样本点被低密度区域(噪声)分割,而算法的目的就是要过滤低密度区域,发现稠密样本点。

二 DBSCAN(Density-based Spatial Clustering of Applications with Noise)

是一种基于高密度联通区域的聚类算法,它将类簇定义为高密度相连点的最大集合。它本身对噪声不敏感,并且能发现任意形状的类簇。

DBSCAN中的的几个定义:

Ε领域:给定对象半径为Ε内的区域称为该对象的Ε领域

核心对象:如果给定对象Ε领域内的样本点数大于等于MinPts,则称该对象为核心对象。

直接密度可达:对于样本集合D,如果样本点q在p的Ε领域内,并且p为核心对象,那么对象q从对象p直接密度可达。

密度可达:对于样本集合D,给定一串样本点p1,p2….pn,p= p1,q= pn,假如对象pi从pi-1直接密度可达,那么对象q从对象p密度可达。

页面

订阅 RSS - 数据结构与算法


Main menu 2

by Dr. Radut