找出链表中间元素

2014/04/23 算法算法

单链表最大的特点就是“不走回头路”，不能实现随机存取。如果我们想要找一个数组a的中间元素，直接a[len/2]就可以了，但是链表不行，因为只有a[len/2 - 1] 知道a[len/2]，其它节点不知道。因此，如果按照数组的做法依样画葫芦，要找到链表的中点，我们需要做两步（1）知道链表有多长（2）从头结点开始顺序遍历到链表长度的一半的位置。这就需要1.5n（n为链表的长度）的时间复杂度了。

有没有更好的办法呢？答案是有的。想法很简单：两个人赛跑，如果A的速度是B的两倍的话，当A到终点的时候，B应该刚到中点。这只需要遍历一遍链表就行了，还不用计算链表的长度。

阅读全文

大小端判断

2014/03/31 技术 Linux CPlusPlus

大端模式，是指数据的高位，保存在内存的低地址中，而数据的低位，保存在内存的高地址中，这样的存储模式有点儿类似于把数据当作字符串顺序处理：地址由小向大增加，而数据从高位往低位放；

小端模式，是指数据的高位保存在内存的高地址中，而数据的低位保存在内存的低地址中，这种存储模式将地址的高低和数据位权有效地结合起来，高地址部分权值高，低地址部分权值低，和我们的逻辑方法一致。

CPU大小端判断函数，C/C++代码

#include <iostream>
using namespace std;
int judgeLittleEndian()
{
  union{
    int i;
    char c;
  }u;
  u.i = 1;
  return u.c;
}

int main(int argc, char *argv[])
{
  if(judgeLittleEndian())
    cout<<"\tLittle Endian!"<<endl;
  else
    cout<<"\tBig Endian!"<<endl;

  return 0;
}

阅读全文

引用计数

2014/03/30 技术 CPlusPlus

最近在看《提高c++性能的编程技术》一书，第十二章提到引用计数，要开始学习新知识了~

学习之前先抄录书中一段精彩的言论

于自然界，熵的原理亦可用于软件工程之中–所有实体都会随着时间的消逝而消失。一个软件项目最初可能源起于某个设计清晰、实现简单的小型原型系统。只包含基本功能的原型系统，要使它们满足上市需求，往往都要经历急速扩展的过程。这通常是为了满足客户对于新功能（有时是难解的）的突发性需求以及对原有瑕疵的改进需要。新功能的开发加上旧错误的修补会对原先清晰明了的设计造成重大破坏。随着时间的推移，设计和实现的清晰性也会随着代码维护及频繁的发布周期而不复存在，软件不可避免的变得紊乱不堪，区分软件好坏的唯一标准就是衰退率。

引用计数是对共享的动态内存的一种管理方法，STL库的string就是用到了引用计数的方法

1. 概念

引用计数用来记录当前有多少指针指向同一块动态分配的内存。当有指针指向这块内存时，计数器加1；当指向此内存的指针销毁时，计数器减1。当引用计数为0时，表示此块内存没有被任何指针指向，此块被共享的动态内存才能被释放。

2. STL库的string利用引用计数共享内存

#include <stdio.h>
#include <string>

using namespace std;

int main()
{
	string str1("aaa");
	printf("the address of str1 is: %x\n",str1.c_str());
	string str2("bbb");
	printf("the address of str2 is: %x\n",str2.c_str());
	string str3("aaa");
	printf("the address of str3 is: %x\n",str3.c_str());
	string str4 = str1;
	printf("the address of str4 is: %x\n",str4.c_str());
	str1 = str2;
	printf("the address of str1 is: %x\n",str1.c_str());
	str2[2] = 'a';
	printf("the address of str2 is: %x\n",str2.c_str());
}

结果如下：

the address of str1 is: 1816028

the address of str2 is: 1816058

the address of str3 is: 1816088 //str3和str1并不共享一块内存

the address of str4 is: 1816028 //str4和str1共享一块内存，所以初始化（string（const char*））和赋值（operator=（const string&））是不一样的

the address of str1 is: 1816058 //str1和str2共享一块内存

the address of str2 is: 18160b8 //写str2，因为引用计数的关系，要分配新的内存给str2

STL string共享内存的原则(copy on write)：

利用初始化或赋值生成多个内容相同的string，当没有对这些string进行写操作时，它们会共享同一块内存。当有写操作出现时，才会有新的内存重新分配。

3. 利用引用计数实现简易String

问题：我们对String类的内存进行计数，但引用计数这个变量是类的什么类型的成员变量？

解答：

1) 普通私有成员变量，每个类都有一个独立的计数器变量，在新的类对象拷贝构造和赋值的时候需要进入原来的类对象中去获取这个计数器，再进行修改，在同一个类对象之间缺乏通用性。

2) static变量，类的所有对象公用一个计数器变量。字符串”aaaa”和”bbbb”使用不同的内存，它们应该分别有对应自己内存的计数器变量。

结论，对每一块内存分配一个变量，可以在动态分配字符串内存是多分配一个字节，将计数器的值放在第一个字节中；也可以在动态分配内存前先动态分配一个int型的内存来存放这个计数器。

在《More Effective C++》的Item 29中有关于引用计数的实现，可供参考

阅读全文

2014年阅读书单

2014/01/29 读书书单

阅读全文

Berkeley DB

2014/01/24 技术数据库

Berkeley DB的简介

Berkeley DB（BDB）是一个高性能的嵌入式数据库编程库（引擎），它可以用来保存任意类型的键／值对 (Key/Value Pair)，而且可以为一个键保存多个数据。Berkeley DB可以支持数千的并发线程同时操作数据库，支持最大256TB的数据。

BDB提供诸如C语言，C++，Java，Perl，Python，Tcl等多种编程语言的API，并且广泛支持大多数类Unix操作系统和Windows操作系统以及实时操作系统（如 VxWorks）。

1991年，Berkeley DB的第一个版发行（Linux系统也在这一年诞生），其最初的开发目的是以新的HASH访问算法来代替旧的hsearch函数和大量的dbm实现，该版本还包含了B+树数据访问算法。

1992年，BSD UNIX第4.4发行版中包含了Berkeley DB1.85版。基本上认为这是Berkeley DB的第一个正式版。

1996年，Sleepycat软件公司成立，提供对Berkeley DB的商业支持。

2006年，Sleepycat被Oracle收购，当时最新版本是4.7.25。

2009年，SUN被Oracle收购，不知道MySQL会不会再次启用Berkeley DB。

Berkeley DB的特点

Berkeley DB可以轻松支持上千个线程同时访问数据库，支持多进程、事务等特性。Berkeley DB运行在大多数的操作系统中，例如大多数的UNIX系统，和windows系统，以及实时操作系统。 Berkeley DB 还拥有对一些老的UNIX数据库，例如dbm, ndbm und hsearch的兼容接口，对于在java系统中的使用，Berkeley DB提供了一个压缩成jar单个文件的java版本。这个版本可以运行在java虚拟机上使用，并且拥有和C语言版本相同的所有操作和功能。 Berkeley DB XML，是一个接口，通过它可以实现对XML数据存贮的支持。对XML数据的访问，会使用相应的查询语句如Xquery, Xpath。 Berkeley DB只支持单一的数据结构，它的所有数据包括两个部分：key 和　data. Berkeley DB原则上是为嵌入式数据库设计的。

阅读全文