深入分析qsort库函数（三）（原创）

抚耳摸丝 — 2006-05-21 17:07:00

网上的文章当提到std::sort和qsort的区别时，通常把它们的性能差异归因于qsort的反引用开销，我们在这里通过实验来测试看看是不是这样，并且判断std::sort的算法是否有较之于qsort代码更优的性能，或者反过来。测试用的源代码如下： main.cpp 主函数所在的文件 #include #include #include #include #include #include "m_qsort.cpp"#include "funcs.h" using namespace std; #define N 1000000 int comp(const void* a,const void* b){ return *(int*)a-*(int*)b;} void main(){ int i,j,*a,*b; clock_t st,et,tt[3]={0}; a=(int*)malloc(sizeof(int)*N); b=(int*)malloc(sizeof(int)*N); getchar(); for (i=0;i<10;i++) { m_srand((long)time(NULL)); for (j=0;j

深入分析qsort库函数（二）（原创）

抚耳摸丝 — 2006-05-20 00:07:00

在这篇文章，我们把目光投向C++ STL中的函数std::sort。可能有些朋友要奇怪了：不是要讲qsort函数吗，怎么讲起std::sort来了？其实，std::sort是一个改进版的qsort，我们通过分析std::sort，可以了解到qsort函数的优点和不足之处，方便我们更好地理解qsort函数的性质，从而深刻理解快速排序的算法思想。我先介绍一下我分析的时候用的源代码。代码很简单，就是一个函数调用，排序随机生成的数组： #include "stdlib.h"#include "time.h"#include using namespace std; int A[50]; int _tmain(int argc, _TCHAR* argv[]){ int i; srand(time(NULL)); for (i=0;i<50;i++) A[i]=rand(); std::sort(A,A+50); return 0;} 在std:sort这一行下一个断点，然后跟踪进去就可以看到如下代码： template inline void sort(_RanIt _First, _RanIt _Last) { // order [_First, _Last), using operator< _Sort(_First, _Last, _Last - _First); } 实际上sort又调用了_Sort函数，我们再跟进： template inline void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal) { // order [_First, _Last), using operator< _Diff _Count; for (; _I

微软亚洲研究院的30项创新技术详解（转）

抚耳摸丝 — 2006-05-19 10:09:00

·电视迷们的福音：点播视/音频搜索在10年之内，互联网将成为一个浩大的视/音频档案库，其内容将覆盖主流媒体和终端用户内容，而个人电脑、电视和移动设备之间的界限将被抹平。搜索，将成为从这一巨大的信息库中找到所需内容的唯一途径。今天，大多数的视/音频搜索引擎依赖于人工创建的文字信息，比如包含视/音频网页的环绕文字，或者媒体注册源的描述性文字。而微软亚洲研究院的这一最新的视/音频搜索将改变用户从互联网上搜索视/音频的方式，它利用了语音识别和信息检索相关技术，使搜索视频语音内容中的文字成为可能；同时，用户可以通过遥控器直接在电视上使用搜索引擎，这也为观赏视频内容提供了极大的方便。 ·照片搜索 Photo2Search是微软亚洲研究院开发的一个全新的互联网服务。通过这种服务，移动用户可以使用照相手机实时的查询大规模图像数据库。该技术有着非常广阔的实际应用，包括海报，建筑，店面等。例如，用户只需简单的拍摄一张餐馆的照片，即可通过Photo2Search在数据库中根据其局部特征搜寻包含同样建筑的图片，经由我们为图像数据库建立的一个高效索引，用户能够快速获得该图片的搜索结果。通过图片的注释，用户可以获得和餐馆或其所在地点相关的更多信息，比如营业时间、附近的其它餐馆和用户评价等。 ·手机搜索目前，人们使用具有网页浏览功能的移动设备，即可直接访问搜索引擎获取所要寻找的信息，但在这些设备上，搜索结果并不像在桌面计算机上那样易于访问。而微软亚洲研究院的“手机搜索”技术，可以通过计算，自动分析出网页中各个部分的功能和其相关性，进而采用更加有效的信息表达方式把网页内容展示给用户。 ·基于结构传播的图像完成基于结构传播的图像完成是一种数字图像修复、擦除技术。其结构传播由3部分组成：首先，用户在图像上画一些曲线或线段来指定图像上缺失的显著结构信息；然后，基于贝叶斯信任传播算法，结构传播技术沿着用户画的曲线合成丢失的图像结构信息；最后，我们使用纹理合成技术合成所有剩余的图像纹理信息——基于结构传播的图像完成是当前世界上最好的数字图像修复技术之一。 ·视频对象分割和粘贴视频对象分割和粘贴技术可以将一个运动物体从一段视频序列中分割出来，并粘贴到其他任意图像或视频序列中。该技术由3部分组成：首先，我们将视频序列看作一个三维空时数据，使用基于图论的三维分割算

Google击败雅虎微软获搜索新算法（转）

抚耳摸丝 — 2006-05-19 09:53:00

Google最近收获了由以色列学生Ori Alon发明的一种高级文字搜索算法。　　　　据悉，雅虎和微软也曾与现在澳大利亚新南威尔斯大学攻读计算机科学博士的Alon谈判收购事宜，但Google最终得手。　　　　Google和Alon及其大学均拒绝发表评论，不过Google确认“Ori Alon在Google的加州山景城办公室工作”，新南威尔斯大学也证实雅虎和微软的确与其商业开发公司进行过谈判。　　　　Alon曾在半年前对媒体表示新南威尔斯大学已经为他的发明申请了专利。这项被称为“Orion”的技术只涉及文本搜索的最相关结果问题。除了目前仅限于英语版本的一个软件，Orion还能提供与原始关键词直接相关的一系列主题。　　Alon解释说：“举个例子，如果你搜索‘独立战争’(指以色列独立战争，即第一次中东战争)，就会得到‘Etzel’(犹太地下组织)、‘Palmach’(犹太武装力量)、‘Ben-Gurion’(独立战争时的以色列总理本·古里安)等一系列相关关键词。”　　　　这些文字只有在其链接与搜索关键词的关联度足够高的情况下才会出现在搜索结果页面上，而且会根据来源网站的质量进行评级。

深入分析qsort库函数（一）（原创）

抚耳摸丝 — 2006-05-18 16:33:00

正如大家所知道的，快速排序算法是现在作为数据排序中很常用的算法，它集成在ANSI C的函数库中。我们经常使用快速排序，就是调用qsort函数，那么qsort函数里面到底是怎么实现的呢？我们现在就来看一看。在这个系列的文章中，我们主要研究一下ANSI C的库函数qsort的源代码，并给出它的性能特性分析。其中使用的源代码是VS.net 2003中VC++自带的源代码，大家可以在 X:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\crt\src文件夹中找到这个名为qsort.c的文件。其他C/C++编程环境也有这个文件，只是在实现上面就可能有些差异而已。这篇文章先对qsort.c文件中的注释进行翻译，并在适当的时候进行一些分析工作。快速排序是一个递归的过程，每次处理一个数列的时候，就从数列中选出一个数，作为划分值，然后在这个数列中，比划分值小的数移动到划分值的左边，比划分值大的数移动到划分值的右边。经过一次这样的处理之后，这个数在最终的已排序的数列的位置就确定了。然后我们把比这个数小和比这个数大的数分别当成两个子数列调用下一次递归，最终获得一个排好序的数列。上面介绍的是基本快速排序的方法，每次把数组分成两分和中间的一个划分值，而对于有多个重复值的数组来说，基本排序的效率较低。集成在C语言库函数里面的的qsort函数，使用三路划分的方法解决这个问题。所谓三路划分，是指把数组划分成小于划分值，等于划分值和大于划分值的三个部分。下面我们开始分析源代码，在源代码中的解释以注释的形式出现： /****qsort.c - quicksort algorithm; qsort() library function for sorting arrays** Copyright (c) Microsoft Corporation. All rights reserved.**Purpose:* &

程序加速器

深入分析qsort库函数（三）（原创）

深入分析qsort库函数（二）（原创）

微软亚洲研究院的30项创新技术详解（转）

Google击败雅虎微软获搜索新算法（转）

深入分析qsort库函数（一）（原创）