算法 -- IT技术博客大学习 -- 共学习共进步！

• GINA 与 pGINA――实现自定义的 Windows 用户身份认证

　　最近接触到一个 Windows 平台下的开源项目――pGINA。鉴于网上没有较为完整的中文介绍，特在此推介一下。　　要知道 pGINA 做什么，首先需要了解 Windows 的用户管理框架。相关资料推荐阅读 Microsoft Windows Internals，这里不再赘述，只给出我列的一张 Linux 与 Windows 用户管理中的对应技术表格供熟悉 Linux 的开发人员参考。其实 Windows 也像 Linux 一样，开放了用户身份认证与用户管理系统的接口，允许第三方如同开发...

• OGRE里如何实现碰撞检测

在3D游戏中，碰撞检测算得上是最复杂也是最影响游戏效果的环节了，这里简单介绍一下如何在OGRE引擎里实现简单的碰撞检测。话不多说，先贴代码： bool EdenCollisionManager::Collide() { bool collide=f...

• 搜索引擎停用词

为节省存储空间和提高搜索效率，搜索引擎在索引页面或处理搜索请求时会自动忽略某些字或词，这些字或词即被称为Stop Words（停用词）。 Stop Words大致为如下三类：应用十分广泛，在Internet上随处可见的词，比如“Web”一词几乎在每个网站上均会出现，对这样的词搜索引擎无法保证能够给出真正相关的搜索结果，难以帮助缩小搜索范围，同时还会降低搜索的效率。语气助词、副词、介词、连接词等，通常自身并无明确的意义，只有将...

• 无知者无畏

吉利收购沃尔沃，18亿美金。李书福曾经的名言是“汽车就是四个轮子+两个沙发”，这句名言一度被业内人士当作笑谈，但是今天，李书福拿出18亿美金来，买下了最有技术含量的品牌，而且是带着知识产权一起买的，谁不服气？拿18亿美金出来。无论是造摩托的李书福，还是造电池的王传福，都在中国轿车家用普及的大行情里大展身手，业内人士有些愤愤不平，这两个土鳖也懂汽车？销量和业绩会说话。吉利和比亚迪真的不好吗？...

• 几个内存相关面试题（c/c++)

void GetMemory(char *p){p=(char*)malloc(100);}void Test(void){char *str = NULL;GetMemory(str);strcpy(str,”helloworld”);printf(str);}请问运行Test函数会有什么样的结果？答：程序崩溃。因为GetMemory并不能传递动态内存，Test函数中的str一直都是NULL。strcpy(str,”helloworld”);将使程序崩溃。char *GetMemory(void){char p[]=”helloworld”;return p;}void Test(void){char *str = N...

• 一种比较省内存的稀疏矩阵Python存储方案

推荐系统中经常需要处理类似user_id, item_id, rating这样的数据，其实就是数学里面的稀疏矩阵，scipy中提供了sparse模块来解决这个问题，但scipy.sparse有很多问题不太合用：1、不能很好的同时支持data[i, ...]、data[..., j]、data[i, j]快速切片；2、由于数据保存在内存中，不能很好的支持海量数据处理。要支持data[i, ...]、data[..., j]的快速切片，需要i或者j的数据集中存储；同时，为了保存海量的数据，也需要把数据的一部...

• 算法的意义

大学时候，学的最差的大概就是算法了。当时总是喜欢多想一步，问一下这个算法到底是为什么。结果老师也答不出。同一个学期，学的最高兴的，是操作系统。教课的是当时的系主任，国内的操作系统大牛。听他老人家讲课，总是能深入浅出的理解里面的设计理念。比如进程的调度，以CPU时钟资源的公平分配为原则；比如虚拟内存的大小，是方便和节约的折中；比如缓存的分配，是历史数据向未来的有效预测等等。那个时候就开始了解，其实算...

• CAP原理与最终一致性

在足球比赛里，一个球员在一场比赛中进三个球，称之为帽子戏法(Hat-trick)。在分布式数据系统中，也有一个帽子原理(CAP Theorem)，不过此帽子非彼帽...

• 基于关联规则的推荐系统

首先，要了解关联规则的几个概念，定义N为总事物数，N(A)、N(B)分别为项集A、项集B出现的次数，N(AB)为项集A、项集B同时出现的次数，A、B为不相交项集A∩B=O，规则A→B表示由A推到B：支持度（Support）：支持度是一种重要度量，支持度低的规则很可能是偶然现象，对推荐意义不大，另外支持度是数据剪枝的一个重要依据。置信度（Confidence）：置信度，字面上的解释就是这个规则到底有多可信，对于给定的规则A→B，置信度越高...

• 用Twitter的cursor方式进行Web数据分页

本文讨论Web应用中实现数据分页功能，不同的技术实现方式的性能方区别。上图功能的技术实现方法拿MySQL来举例就是 select * from msgs where thread_id = ? limit page * count, count 不过在看Twitter API的时候，我们却发现不少接口使用cursor的方法，而不用page, count这样直观的形式，如 followers ids 接口 URL: http://twitter.com/followers/ids.format Returns an array of numeric IDs for every user following the sp...

• 下载软件的专用地址生成方法

经常看到一些下载站做了一些专用软件下载地址，例如：迅雷下载地址，快车下载地址。那么这些地址怎么得来的呢？现在就链接的编码原理及转换详细说明一下，明白以后就可以用迅雷下载快车、旋风专用地址的软件啦。　　首先要明白Base64编码是怎么一回事，不懂的先去百度一下再回来。　　Base64编码是一种加密算法，Email的原始信息就是由Base64编码构成的。　　而这些专用链接都是通过Base64编码加工转换而成的。　　1、迅雷专用链...

• RSA 公钥格式转换之PHP实现

在.net中公钥的格式总是以modules 、exponent的格式存在的，但是openssl做加密、解密总是使用pem格式的，这里实现了前者到后者的格式转换。

• 实现多线程对队列的读写操作（封装类）

由于之前一个server用到后台线程的功能，所以写了一个线程+队列的通用模型。（代码见文章底的附件）应用场景：当处理的数据不影响回包，即可以在后台执行。使用方式：一个（或多个）...

• 限速类（C++版）

之前已经在博客里写过一篇关于限速的文章，这几天给别人用时发现，用C方式的结构式代码的确不方便别人使用，所以就用C++封装了一下，用起来也简单了很多。主要实现了： 1.对速度的限制...

• 简单的echo程序

Unix/Linux系统中最简单的shell命令之一echo，功能如其名，可以用它来讲解main函数，以取代经典但令人乏味的HellWorld。

• 野兽渡河问题

题目：有六只野兽A, a; B, b; C, c，其中A野兽为a的妈妈; B为b的妈妈；C为c的妈妈。大野兽和小b会划船，但小a和小c不会划船。一条船只能乘坐两只野兽。另外如果在船的任何一边或船上，只要任何一只小野兽离开了妈妈，又有其它的大野兽，那么它就会被吃掉。问有什么方案可保证六只野兽安全渡河。

• 独创比百度、Google分页还强的分页类

最近忙于游戏，总是觉得没什么好写的，时隔十天得上个重量级的日志了。上周就完成好了，为以后方便管理于维护，直接封装成方法以后用吧。给过两个版本的改进，觉得比百度、GG的分页更合理。共50页的例子，具体可以自行测试：第1页 1 2 3 4 5 >> 50第5页 1 > 50第7页 1 > 50第50页 1

• [一道面试题]含有*的字符串匹配问题

Question 字符串1：只含有英文字母字符串2：含有英文字母和*，其中符号*表示匹配任意字符0或者多次，即正则表达式里面的含义。现在给定这样的两个串，要求判断是否匹配？

• 计数和排序

以前看过一篇关于程序上的小技巧的文章，作者给出了正确的（或者至少可以称得上标准的）的解决方法，结尾他对这种技巧并不满意，认为是迫不得已才用的，等以后计算机发展了，可以使用“真实”的结果。我的想法和他截然相反，在我看来计算能力永远也追不上实际需求，我们会在越来越多的地方使用各种“有损优化”。这个词是我现想起来的，其实很多技巧都像 JPEG 标准一样，无伤大雅的丢弃了那些难以察觉的细节。

• 动态数组的 C 实现

上次谈到了一个常用的 ADT ，sequence 的 C 实现。通常，我们不会直接使用 sequence ，而是用它来实现满足最终需要的数据结构。比如消息队列，比如指令堆栈，等等。一个实现的优秀的 seq 的好处在于，即使你只用到其中一部分功能，也不会因为那些没用的部分损失太多的（时间和空间上的）性能。今天我想谈另一个更为实用的 ADT ，动态数组。这个在传世神作《C 语言接口与实现》中也提到过，我不是想说其写的不对，或是讲述的不周全...