ITeye博客

沙砾

zxxapple · 共 24 篇文章

Linux下用gcc生成静态库和动态库 (转载)

一、基本概念 1.1 什么是库 在 windows 平台和 linux 平台下都大量存在着库。 本质上来说库是 一种可执行代码的二进制形式,可以被操作系统载入内存执行。 由于 windows 和 linux 的平台不同(主要是编译器、汇编器和连接器 的不同),因此二者库的二进制是不兼容的。 本文仅限于介绍 linux 下的库。 1.2 库的种类 linux 下的库有两种:静态库和共享库(动态库)。 二者的不同点在于代码被载入的时刻不同。 静态库的代码在编译过程中已经被载入可执行程序,因此体积较大。 共享库的代码是在可执行程序运行时才载入内存的,在编译过程中仅简单的引用,因此代码体积较小。 1…

2012-10-19 16:57 · 随笔 · 评论(0)

(转载) 快速排序、希尔排序、插入排序、选择排序、归并排序、堆排序总结

一、快速排序的基本思想 设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为: ①分解: 在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。 注意: 划分的关键是要求出基准记录所在的…

2012-10-17 11:14 · 算法 · 评论(0)

不借助其它变量交换两变量值的三种算法

在学习程序语言和进行程序设计的时候,交换两个变量的值是经常要使用的。通常我们的做法是:定义一个新的变量,借助它完成交换。代码如下: int a,b,t; a=10; b=15; t=a; a=b; b=t; 这种算法易于理解,特别适合帮助初学者了解计算机程序的特点,是赋值语句的经典应用。在实际软件开发当中,此算法简单明了,不会产生歧义,便于程序员之间的交流,一般情况下碰到交换变量值的问题,都应采用此算法(以下称为标准算法)。 标准算法最大的缺点(其实根本不算缺点)就是需要借助一个临时变量。那么不借助临时变量可以实现交换吗?答案是肯定的!这里我们可以用至少三种算法来实现,他们是: 1)算术运算…

2012-10-16 10:27 · 算法 · 评论(0)

编程珠玑开篇--磁盘文件排序问题

转载。。。。 编程珠玑开篇--磁盘文件排序问题 输入: 所输入的文件,至多包含n个正整数,每个正整数都小于n,题目中n = 10^7,如果输入时某个正整数重复出现俩次,就会产生致命的错误,这些整数,与其他任何数据都不相关. 输出: 以增序形式输出经过排序的整数列表 约束 至多只有1MB(包括程序本身)可用的主存,但是可以用的磁盘空间是充足的,运行时间至多几分钟,10秒针是最适宜的运行时间. 作者第一个方案使用基于磁盘的合并排序.将每个号码用32位整数表示,可以在1MB的空间里存储250000个号码,使用一个带有40个通道的程 序,在第一个通道中将0到249999之间的整数读入内存,并对它们进…

2012-10-16 10:07 · 算法 · 评论(0)

各种排序算法的稳定性和时间复杂度小结

各种排序算法的稳定性和时间复杂度小结 冒泡法: 这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡: 复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。 直接插入排序: O(n*n) 选择排序: O(n*n) 快速排序:平均时间复杂度log2(n)*n,所有内部排序方法中最高好的,大多数情况下总是最好的。 归并排序: log2(n)*n 堆排序: log2(n)*n 希尔排序:算法的复杂度为n的1.2次幂 这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法: 首先我们考虑最理想的情况 1.数组的大小是2的幂,这样分下去始终可以被2整除。…

2012-10-16 09:22 · 算法 · 评论(0)

套接字select异步模型

Select 模型原理 利用 select 函数,判断套接字上是否存在数据,或者能否向一个套接字写入数据。目的是防止应用程序在套接字处于锁定模式时,调用 recv (或 send )从没有数据的套接字上接收数据,被迫进入阻塞状态。 select 参数和返回值意义如下: int select ( IN int nfds, //0, 无意义 IN OUT fd_set* readfds, // 检查可读性 IN OUT fd_set* writefds, // 检查可写性 IN OUT f d_set* exceptfds, // 例外数据 IN const struct timeval* ti…

2012-06-07 18:19 · 套接字 · 评论(0)

GetData软件使用--获取曲线图中的数据

使用场合:1、想引用别人论文中的某个数据(曲线)图,但论文中没有这个图的数据,直接把图抓过来显得太逊了, 希望提取出这个图中的数据信息生成矢量图;2、希望从这个图中提取出数据用于自己的研究; 软件来源:此软件由俄国人开发(好多这种功能强大的小软件都是俄国人开发的,pfpf) getdata-graph-digitizer.com上可以下载到试用版,21天的试用期,好像无功能限制,目前最新版本:2.24, 有中文和英文界面可供选择,其他有俄文、乌克兰文、日文、朝鲜文,居然还有印度尼西亚文(开发者有印尼朋友?) ; 使用方法: 1 启动GetData Graph Digitizer,打开要处理的…

2012-03-21 21:54 · 随笔 · 评论(0)

HDFS的缺点以及相应的改进策略

HDFS是一个不错的分布式文件系统,它有很多的优点,但也存在有一些缺点。目前而言,它在以下几个方面就效率不佳: 低延时访问 HDFS不太适合于那些要求低延时(数十毫秒)访问的应用程序,因为HDFS是设计用于大吞吐量数据的,这是以一定延时为代价的。HDFS是单Master的,所有的对文件的请求都要经过它,当请求多时,肯定会有延时。当前,对于那些有低延时要求的应用程序,HBase 是一个更好的选择。现在HBase的版本 是0.20,相对于以前的版本,在性能上有了很大的提升,它的口号就是goes real time。 使用缓存或多master设计可以降低client的数据请求压力,以减少延时。还有…

2012-03-09 20:24 · hadoop · 算法 · 评论(0)

求一个数列的最长非递增(递减)子序列

问题描述: 给出一个数列,找出其中最长的单调递减(或递增)子序列。比如数列 4,2,6,3,1,5 最长递增子数列为2,3,5 相似的问题:1求最大和的子序列 2最大公共子串 3最大公共子序列 注意:串与序列的关系,,串是连续的,而序列则不可以。。。 解决办法 :在网上得到两种解法 解法一: 首先将这个序列进行排序,然后再求出已排序的和未排序的这两个数列最长公共子序列 解法二:就是用动态规划法来解决问题: 我们假设原数列定义为数组a[],然后定义一个数组b[i],表示以a[i]结尾的最长公共子序列的长度,只要求出所有的b[i]数组也就可以确定最长的公共子序列, 那么我们根据已经求出的b[0]…

2012-03-09 16:22 · 算法 · 评论(0)

数列的排列与组合问题

关于数列的全排列已经另外一篇文章中提到过了, 下面来介绍下数列的组合问题: 例如;序列12345 如果输入m=3,原序列的长度n=5 得到的组合数组是:123 124 125 134 135 145 234 235 245 345 如上得到所有的位数为2的组合方式,从上面的数我们也可以用序号表示: a[0],a[1],a[2],a[3],a[4],a[5] 得到的组合数a[0],a[1],a[2]可用下标012表示 那么组合数就可以用原来数列的的下标表示即可: 从一开始,得到的组合数列,所有组合数的下标是 递增 的,最后一个组合序列的最后一位的下标即为n-1; 我们定义一个数组p[x]=y …

2012-03-03 19:25 · 算法 · 评论(0)

n-皇后以及全排列的问题--递归以及非递归的解法

首先说下全排序的问题 这个问题可以说是最经典的问题, 实现这个问题的最经典的方法莫过于递归实现了: 代码确实很简洁:(从网上转载---很多的) void perm(char *buf,int start,int end) { if(start==end){//当只要求对数组中一个字母进行全排列时,只要就按该数组输出即可 for(int i=0;i<=end;i++){ printf("%c",buf[i]); } printf("\n"); } else{//多个字母全排列 for(int i=start;i<=end;i++){ char temp=buf[start];//交换数组第一个…

2012-03-01 09:19 · 算法 · 评论(0)

关于链表追赶--链表中环的问题

关于环的问题, 介绍几个个经典的题目: 1.求链表倒数第k个结点 最经典,最常见的解法就是,设置两个指针p1,p2,一开始分别指向头结点,首先p2先移动k个节点,之后开始p1,p2每次移动1个节点,直到p2达到最后一个节点位置,那么p1指向的就是倒数第k个节点。 不过这种解法主要是针对单链表,且链表中不存在环的,如果是双向链表,或者是存在环的链表呢? 在判断是否在最后一个节点上就会出现问题了,ps.循环链表中判断最后一个节点就需要查看其pre指针指向的节点是否是刚才遍历过的节点。对于存在环的节点判断最后一个节点就有点麻烦了: 判断一个链表是否存在环 环的定义如上: 定义两个指针,开始的时候分…

2012-02-28 15:19 · 算法 · 评论(0)

非递减字符串问题

如题: 在非递减字符串中,从左到右的字符依次按ASC码非递减排列,例如 abcd,aaaa,aabb等等,现在假设字符串由a-j等10个字符串组成,请你确定特定长度的非递减字符串的数目。 算法思想:当我显现看到这个题,有些迷惑,为什么是十个字符串呢,,后才自然想到对应十个阿拉伯数字0-9. 问题就可以从这个地方解决。把某个长度的串看成是一个整数,想办法取出这个整数的每一个具体的位,然后进行 比较不就可以判断是否复合条件,比如给定的长度为4,我就从0000遍历到9999,找出复合条件的整数然后计数,不就可以了吗。这个方法效率肯定会比较低,而且如果刚给的字母的个数超过10,就不能用这个办法了。。…

2012-02-16 13:29 · 算法 · 评论(2)

MapReduce框架中PageRank算法的简单实现

主要实现思想在另一篇博客中已经提到: 具体实现每次迭代包括两个Job 第一个分散各个节点的PR值 第二个用于将dangling节点的PR值分散到其它节点 主要包括5个类 PageRankNode:图中的节点类-代表一个页面 PageRankJob:实现分散各个节点的PR值的类 DistributionPRMass:实现dangling节点的PR值分散到其它节点的Job类 RangePartitioner:partition类 将连续的节点分配到同一个reduce中 PageRankDirver:整个工作的驱动类(主函数) package com.zxx.PageRank; import ja…

2012-02-15 14:27 · MapReduce框架 · 评论(6)

PageRank算法 之我看

PageRank是google搜索中用于计算页面的重要程度,即PR值。下面就是其计算公式: 我们可以把这也页面的连接关系看成图的结构,页面就是图中的一个节点,边代表页面之间的链接关系, 其中P(n)代表的就是第n个节点的PR值,L(n)代表n节点的所有入度节点的集合,C(m)代表m节点的出度, G代表的是所有的节点数目,a代表的是随机的跳转到任何一个页面的概率,1-a代表进入到当前页面中的连接的概率 伪代码:摘自Jimmy lin (没有考虑 dangling节点 以及 随机概率) 问题: 最常见的问题是dangling节点(该节点的出度为零,即该网页内没有任何其他的网页的链接)的问题,如果…

2012-02-15 13:22 · 算法 · 评论(1)