janqii

linux内核中链表的实现是相当的出色的，《linux内核设计与实现》（附录A）中说“linux内核使用了一种独一无二的方法遍历链表”、“为了这种巧妙设计，内核骇客们还是颇有点自豪的”。

-----------------------------------------------------------------------------------------------------------------------------------

1、链表结构体

struct list_head {
     struct list_head *next, *prev;
};
很显然，这是一个双向链表。不过，令人疑惑的是这个链表结构中竟然没有存储节点数据的字段，这是因为
它不是单独使用的，而是需要加入到表示具体数据结构的结构体中，与表示具体数据结构的结构体组合一起
使用，才能显示出它的用途和价值。
《……设计与实现》上说“一个list_head结构体本身没有什么意义，通常需要把它嵌入到自己的结构
体中”。

例如 struct my_struct{
             struct    list_head list;
             unsigned long      dog;
             void       *cat;
     }
这样表示具体数据结构的my_struct结构体就和list_head联系起来了。就可以把my_struct的对象通过
list成员链接起来，形成一个链表。
struct my_struct *p1,*p2,*p3......

p1->list->next=p2->list;
p2->list->pre=p1->list;
p2->list->next=p3->list;
p3->list->pre=p2->list;
p3->list->next=p1->list;
p1->list->pre=p3->list;

这样就通过list_head成员把my_struct的对象链接起来。
可以通过list_entry(p1->list,struct my_struct,list)来返回指向p1的my_struct指针，也就是
通过list_entry可以实现由list域访问其所属的结构体对象的功能。

2、链表操作函数
内核中很巧妙实现了链表的操作，大都非常简洁、精炼，通过宏或者内联函数实现，其中
list_entry的实现很有意思。

··初始化链表：
static inline void INIT_LIST_HEAD(struct list_head *list)
{
            list->next = list;
            list->prev = list;
}
可以看出初始化时链表前项节点和后向节点都指向了其本身。

··添加操作（此处仅列出一个）：

static inline void list_add(struct list_head *new, struct list_head *head)
{
        __list_add(new, head, head->next);
}

static inline void __list_add(struct list_head *new,
                              struct list_head *prev,
                              struct list_head *next)
{
        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
}

new是新添加项，添加到结点head所在的链表中，并且是加到head之后第一个结点。

··删除操作（仅列出一个）：

static inline void list_del(struct list_head *entry)
{
        __list_del(entry->prev, entry->next);
        entry->next = LIST_POISON1;
        entry->prev = LIST_POISON2;
}

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
        next->prev = prev;
        prev->next = next;
}

从链表中删除entry，并使其指向安全的位置LIST_POISON1和LIST_POISON2，关于这两个常量的解释和定义在
linux/poison.h（22行）
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)

··遍历链表：

遍历链表list_for_each是一个宏，展开了就是一个for循环

#define list_for_each(pos, head) \
        for (pos = (head)->next; prefetch(pos->next), pos != (head); \
                pos = pos->next)
其中prefech(pos->next)是处理器预取pos->next，通过处理器的预取功能，对for循环进行了优化。

··访问数据操作：

#define list_entry(ptr, type, member) \
        container_of(ptr, type, member)

#define container_of(ptr, type, member) ({                      \
        const typeof(((type *)0)->member) * __mptr = (ptr);     \
        (type *)((char *)__mptr - offsetof(type, member)); } )

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

container_of是一个有点复杂的宏,使用了C扩展关键字typeof，还有不好理解的求结构体成员
变量偏移.....
·((type *)0)是将0强制转化为type *，也就是指向type类型的指针

·((type *)0)->member是访问type结构中的member成员

·const typeof( ((type *)0)->member ) *__mptr 定义一个与((type *)0)->member同种类型的
指针变量（const变量）

·const typeof( ((type *)0)->member ) *__mptr=(ptr)对常量指针变量__mptr赋值
__mptr=ptr

·((size_t) &((TYPE *)0)->MEMBER得到member在type结构体中的偏移量，
offsetof(type,member)的展开效果

·(char *)__mptr - offsetof(type,member) 将__mptr强制转化为char类型指针，也就是__mptr
的地址，然后减去member在结构体中的偏移量，的到的自然就是结构体起始地址（偏移量求的很巧妙，
又很巧妙的获得结构体起始地址）。

·(type *)( (char *)__mptr - offsetof(type,member) )最后再强制转化为(type *)类型，
得到ptr所在的结构体对象（大功告成）。
到此成功的通过结构体对象的一个域的字段，获取了结构体对象本身，即访问list_head关联的结构对象
成功。
----------------------------------------------------------------------------------
取得结构体一个字段的偏移地址的方法 offsetof(type,member) 宏，设置的十分巧妙，
取得偏移后，具体对象的member地址-偏移地址，得到type对象的起始地址，设计相当的妙。

linux内核中求偏移量的宏定义如下
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

------------------------------宏测试小程序---------------------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

struct test_struct{
     char   ch;
     int    it;
     int    ul;
};

int main()
{
     size_t off=-1;
      struct test_struct *st,*rt;

     st = (struct test_struct *) malloc (sizeof(struct test_struct));

     st->ch='a';
     st->it=1;
     st->ul=1ul;

/*    off =(size_t)&(((struct test_struct *)0)->it);*/
      off=offsetof(struct test_struct,it);
//    rt=(struct test_struct *)((char *)(&st->it)-off);
      rt=(struct test_struct *)(((char *)&(st->it)-(char *)off));

      printf("%d %d %d",rt->it,off,sizeof(struct test_struct));


      return 0;
}
--------------------------------------------------------------------------------------------------------------
由于4字节补齐的原因，sizeof(struct test_struct)=12,而不是等于9

写了一个快排算法

然后进行了一些修改，随机的选择中轴元素，随机化处理了一下。

对两个算法进行比较，随机产生553k的数据进行排序，分别统计花费的时间。

一开始在windows下，直接 cl 进行编译链接，可执行文件112k，输出分别是 31ms和110ms。

后来偶然使用VC6编译，运行，可执行文件544k，大了432k，输出为94ms和171ms，分别慢了3倍和60+ms。

VS到底做了什么使得效率低了下来？？！！

另外还有一个发现，在数据比较多，随机化处理过的快排算法要比没有处理的快排效率要差很大。印象中好像是应该反过来，期望运行时间应该要优于后者，因为快排的最好的情况下才是O(n*lgn)，而随机化处理过之后期望运行时间是O(n*lgn)。

或者是因为多了随机化操作、数据交换操作和过程调用时间消耗而引起的？

---------------------------------------------------------code--------------------------------------------------------------------

#include<iostream>
#include<cassert>
#include<ctime>
#include<cstdlib>
using namespace std;

void quickSort(int arr[],int p,int r);
int Partition(int arr[],int p,int r);

void random_QuickSort(int arr[],int p,int r);
int random_Partition(int arr[],int p,int r);

inline void swap(int &a,int &b);
void writeFile(string file_name);
void readFile(string file_name,int arr[],int size);
void writeToFile(string file_name,int arr[],int size);

int main()
{
/*int i=-1;
int size=-1;
int *arr=NULL;

cin>>size;
arr=new int[size];

for(i=0;i<size;i++)
{
   cin>>arr[i];
}
quickSort(arr,0,size-1);
for(i=0;i<size;i++)
   cout<<arr[i]<<" ";

delete []arr;*/
const int size=100000;
int arr[size];
int arr2[size];

string in_file="dataIn.txt";
string out_file="dataOut.txt";
string out2_file="dataOut2.txt";

writeFile(in_file);
readFile(in_file,arr,size);
readFile(in_file,arr2,size);

clock_t start=clock();
quickSort(arr,0,size-1);
clock_t end=clock();
double diff=(double)(end-start);
cout<<diff<<endl;

clock_t start2=clock();
// insert_sort_rec(arr2,size-1);
random_QuickSort(arr2,0,size-1);
clock_t end2=clock();
double diff2=(double)(end2-start2);
cout<<diff2<<endl;

writeToFile(out_file,arr,size);
writeToFile(out2_file,arr2,size);
return 0;
}

void quickSort(int arr[],int p,int r)
{
if(p<r)
{
   int q=Partition(arr,p,r);

   quickSort(arr,p,q-1);
   quickSort(arr,q+1,r);
}
}

void random_QuickSort(int arr[],int p,int r)
{
if(p<r)
{
   int q=random_Partition(arr,p,r);
   random_QuickSort(arr,p,q-1);
   random_QuickSort(arr,q+1,r);
}
}

int Partition(int arr[],int p,int r)
{
int key=arr[r];
int i=p-1;
int j=p;

for(j=p;j<r;j++)
{
   if(arr[j]<=key)
   {
    i++;
    swap(arr[i],arr[j]);
   }
}

swap(arr[i+1],arr[r]);

return i+1;
}
int random_Partition(int arr[],int p,int r)
{
srand(time(NULL));
int rd=rand()%(r-p+1)+p;

swap(arr[rd],arr[r]);

return Partition(arr,p,r);
}

inline void swap(int &a,int &b)
{
int tmp=a;
a=b;
b=tmp;
}

void writeFile(string file_name)
{
int i=0;
FILE *fp;

fp=fopen(file_name.c_str(),"w");

if(!fp)
{
   cerr<<"failed to open file"<<endl;
   exit(-1);
}

srand(time(0));

while((i++)<100000)
{
   fprintf(fp,"%d ",rand()%100);
}

fclose(fp);
}

void readFile(string file_name,int arr[],int size)
{
FILE *fp=fopen(file_name.c_str(),"r");

assert(fp!=NULL);

for(int i=0;i<size;i++)
   fscanf(fp,"%d",&arr[i]);

fclose(fp);
}

void writeToFile(string file_name,int arr[],int size)
{
FILE *fp=fopen(file_name.c_str(),"w");
assert(fp!=NULL);

for(int i=0;i<size;i++)
   fprintf(fp,"%d ",arr[i]);

fclose(fp);

}

void insert_sort_rec(int array[],int size)
{
if(size>3)
   insert_sort_rec(array,size-1);

int i=size-1;
int key;

key=array[i];
i--;

while(i>=0 && array[i]>key)
{
   array[i+1]=array[i--];
}

array[i+1]=key;
}

计划之 4-18 to 4-25

----------------------------------------------------------------------------------------------------------------------------

linux kernel 结束第一遍

练习使用matlab

算法导论 至少读2章

expert 至少看完第五章

对所有认识的人微笑，打招呼

对所有不认识但是眼神碰撞的人微笑

散列表是普通数组的推广。

设计散列表主要是对哈希函数和处理冲突碰撞的选择和设计，好的哈希函数h可以使关键字比较均匀的散列在哈希表中，冲突较少。所谓“好”的哈希函数的主导思想，是使h尽可能地随机，减少碰撞，但是不可能完全避免碰撞，因为关键字域的势 |U|>m，m为散列表的槽数，总会有两个不同的关键字映射到同一个槽中，产生碰撞。

1、哈希函数

一个好的哈希函数应（近似地）满足简单一致散列的假设：每个关键字都等可能的散列到m个槽位的任何一个中去，并与其他的关键字已被散列到哪个槽位中无关。

不幸的是，一般情况下不太可能检查这一条件是否成立，因为人们很少能知道关键字所符合的概率分布，而各关键字可能并不是完全相互独立的。

算法导论中列举了四种哈希函数：直接定址法、除法散列法、乘法散列法和全域散列法。

其中除法散列法和乘法散列法利用了启发式的方法，第三个利用了随机化的技术。

a、除法散列法（模除法）

h(k)=k mod m

m的取值常常是与2的整数幂不太接近的质数（m是指散列表的槽数）。

b、乘法散列法

h(k)=|m*(k*A mod 1)| （取底）

用关键字k乘以常数A（0<A<1），并取出kA的小数部分。然后用m乘以这个值，对结果取底。

对 m 的选择没有特别的要求，一般选择为 2 的整数次幂

Knuth认为 A=（sqrt（5）-1）=0.6180339887......，取这个值比较理想

c、全域散列

h(k)=((a*k+b) mod p) mod m   （哈希函数族）

选择一个足够大的质数p，使得每一个可能的关键字k都落到0到p-1之间（包括0和p-1）。

Zp表示集合｛0，1，……，p-1｝，Zp*表示集合｛1，2，……，p-1｝。

容易知道p>m（p>=|U|>m）

a属于Zp*，B属于Zp

从函数族中随机的选取一个作为哈希函数

d、在严蔚敏的数据结构中还介绍了其他的构造哈希函数的方法（比如平方取中法，折叠法等）

2、处理碰撞的方法

a、哈希链接法

把冲突的关键字存储在冲突槽的链表中

在简单一致散列的假设下，一次不成功查找的期望时间为O（1+α），平均情况下一次成功的查找也需要同样的时间

b、开放寻址法

线性探测    h(k,i)=(h'(k)+i) mod m,i=0,1,……，m-1

二次探测   h(k,i)=(h'(k)+c1*i+c2*i*i) mod m     严蔚敏的数据结构中 c1=0，c2=-1

双重哈希（再哈希法） h(k,i)=(h1(k)+i*h2(k)) mod m

每一个关键字的探查序列

<h(k,0)，h（k,1）,……，h(k,m-1)>    

直到探寻到合适的位置为止

c、完全散列法

基本思想比较简单，采用两级的散列方案，每一级都采用全域散列。

有点类似哈希链接法，只不过，在冲突槽的链表上再采用一次全域哈希。

d、严蔚敏的数据结构中还介绍了 建立一个公共溢出区 的方法

------------------------------------一个小例子（哈希链接法 处理冲突）-------------------------------------------------

/*
* 算法导论 第十一章 散列表
*
* 哈希函数：模除散列法
* 冲突避免：哈希链接法
* */

/* 输出：14 1

               1   0

*/

#include<stdio.h>
#include<stdlib.h>

struct hash_node{
struct hash_node *next;
int data;
};

struct hash_table{
struct hash_node *base;
unsigned int count;
unsigned int size;
};

unsigned int hash1(int key, int m)
{
/*int rt=-1;*/
return key%m;
}

unsigned int hash2(int key, int m)
{
return 1+(key%(m-1));
}

unsigned int hash(int key, int m, int i)
{
return (hash1(key,m)+i*hash2(key,m))%m;
}

void chain_insert(struct hash_table *tbl, int key)
{
unsigned int pos=-1;
struct hash_node *new_node=NULL;

new_node=(struct hash_node *)malloc(sizeof(struct hash_node));
new_node->data=key;
new_node->next=NULL;

pos=hash(key,tbl->size,0);

if(tbl[pos].count==0)
{
   tbl[pos].base=new_node;
   tbl[pos].count += 1;
}
else
{
   new_node->next=tbl[pos].base;
   tbl[pos].base=new_node;
   tbl[pos].count += 1;
}
}

void chain_search(struct hash_table *tbl, int key, unsigned int *row,unsigned int *col)
{
int i=0;
int idx=-1;
struct hash_table tb;

idx=hash(key,tbl->size,0);

if(tbl[idx].count > 0)
{
   tb=tbl[idx];
   while(tb.base!=NULL && tb.base->data!=key)
   {
    tb.base=tb.base->next;
    i += 1;
   }
  
   *row=idx;
   *col=i;
  
   if(tb.base==NULL)
   {
    *row=-1;
    *col=-1;
   }
}
else
{
   *row=-1;
   *col=-1;
}
}

#define m 13

int main()
{
int i=0;
int row, col;
struct hash_table tbl[m];

for(i=0;i<m;i++)
{
   tbl[i].base=NULL;
   tbl[i].count=0;
   tbl[i].size=m;
}
chain_insert(tbl,1);
chain_insert(tbl,14);
chain_search(tbl,14,&row,&col);

printf("%d ",tbl[1].base->data);
printf("%d ",tbl[1].base->next->data);
printf("\n%d %d\n",row,col);

return 0;
}