key生成器的两种持久化方案

需求：
        key生成器功能是生成一个唯一的key，不能重复。序列化是将已经生成的key序列化到磁盘，以防机器宕机，key丢失导致生成重复的key；我们的需求key是顺序增长的。


方案一：
        先生成key后持久化；用户模块调用key生成器时，生成器先将key返回给用户，并将返回给用户的最大key存储在内存中，到一定量后（比如，已经返回给用户64个key）将key序列化到文件。文件中还存在一个标识位，正常打开、关闭文件时设置相应的标识位。key生成器启动读取序列化文件时，判断文件是否被正常关闭，是则正常读取文件中最大的key，否则读取文件中的key加上64（略过，保证key不重复），再继续去生成key。

方案二：
        先持久化后生成key ；用户模块调用key生成器时，先将key序列化到文件，再将key返回给用户。直接序列化一个区间到文件，如程序启动时，key从1开始，不直接序列化1，而将64序列化到文件，这样之后从2-63的调用就不需再去序列化文件了，减少了文件的写操作。此方案不需在文件中存储任何标识位，机器宕机之后，序列化文件中的key肯定是最大的，后续的key不会重复。


        以上两种方案，都是从别人的代码和交流中获得的，我比较喜欢第二种方案，简单，省去了不必要的错误恢复。有时候换一种思路或者说逆向思路可以让你的设计更为简单、容易理解。

堆栈实现先进先出队列

实现思路：
        使用两个大小相同的堆栈（命名为s1,s2），来实现堆栈。队列包含一下几个操作：创建、注销、满判断、空判断、入队、出队。

创建：
       创建管理结构体，结构体包含队列容量、使用量、包含两个栈指针的数组。使用另外的库函数来创建堆栈。两个栈的大小和队列的容量相同。

注销：
       顺序注销两个栈，以及管理结构体。

满判断：
空判断：
       根据管理结构体中存储的容量和使用量来判断。

入队：
        首先使用前面的函数判断队列是否满，满则出错。将数据压入栈s1，并增加使用量计数。

出队：
        首先判断队列是否为空，空则出错。判断s2栈是否为空，空则将s1栈内容出栈，入栈到s2，s1的最后一个元素直接返回给函数调用者，不入栈；s2栈非空，则直接从s2中返回一个元素给函数调用者。返回元素要较少使用量计数。


代码实现见github(https://github.com/zhangst/exercise/tree/master/interview/fifo)，这种实现还有一个问题，空间浪费。创建一个容量为16的队列，需要两个容量为16的堆栈才能实现，总空间占用为32了。

折半查找的实现

折半查找又成为二分查找，常用来对有序的线性表做元素查找。适用于一经建立，很少改变并且经常查找的场景。

实现如下：

/**
* Function binary_search (number, array, array_len)
*
*  Returns
*    -1,if not found.index of array,if found.
*
*  Parameters
*    @number:     the nubmer waiting for search
*    @array:      search array pointer
*    @array_len:  esarch array len
*
*  Description
*    premise that array is orderly.
*
**/
static int binary_search(int number, int *array, int array_len)
{
    int mid, start = 0, end = array_len - 1;

    while (start <= end) {
        mid = (start + end) / 2;
        if (array[mid] < number)
            start = mid + 1;
        else if (array[mid] > number)
            end = mid - 1;
        else
            return mid;
    }

    return -1;
}

使用二分思想，求平方根的函数：

/**
* Function mysqrt (y, precision)
*
*  Returns
*    
*
*  Parameters
*    @y:          
*    @precision:  
* 
*  Description
*    求y的平方根,x*x == y
*
**/
static double mysqrt(double y, double precision)
{
    double x, start = 0.0, end = y;
    
    assert(y > 0.0);
    while (1) {
        x = (start + end) / 2;
        if (x*x < y)
            start = x;
        else
            end = x;

        if (fabs(x*x - y) < precision)
            break;
    }

    return x;
}

素数的求解

大一刚开始学习程序设计的时候，自己就遇到过素数求解的问题，今天又遇到在这里总结一下。
素数又称质数，为大于1的自然数中，除了1和整数自身外，没法被其他自然数整除的数。
因为素数没有特定的规律，最简单的方法就是使用穷举法了，我们判断一个数字是否为素数，就一个个的判断他是否能被其他的数整除，如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#include <stdio.h>   /* 判断一个正整数是否素数 */ static int prime_number(const int n) { int i;   if (n == 2) return 0;   for (i = 2; i < n; i++) { if (n % i == 0) { return -1; } }   return 0; }   int main(void) { int i;   for (i =2; i < 100; i++) { if (prime_number(i) == 0) { printf("%3d ", i); } }   return 0; }

这里我们稍微深入思考一下，我就就很容易想到如下的信息：
1 偶数是不可能是素数的
2 判断奇数是否为素数是不需要那偶数去除它的
3 素数循环不必循环到n，到根号n就可（理论上为什么不清楚）
按以上的方法修改下程序，效率会提高很多，程序如下。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include <stdio.h>   /* 判断一个正整数是否素数 */ static int prime_number(const int n) { int i;   if (n == 2) return 0;   for (i = 3; i*i < n; i += 2) { if (n % i == 0) { return -1; } }   return 0; }   int main(void) { int i;   printf("%3d ", 2); for (i = 3; i < 100; i += 2) { if (prime_number(i) == 0) { printf("%3d ", i); } }   return 0; }

两个练习题

冒泡排序和二分查找的练习。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

#include <stdio.h> #include <assert.h> #include <stdlib.h> /* srand rand */ #include <time.h> #include <unistd.h>   static int binary(int arr[], const int size, const int n) { int high, low, mid;   assert(arr != NULL); assert(size > 0);   high = size - 1; low = 0;   while (low <= high) { mid = (high + low) / 2;   if (arr[mid] == n) { return mid; } else if (arr[mid] > n) { high = mid - 1; } else if (arr[mid] < n) { low = mid + 1; } }   return -1; }   static void maopao(int arr[], const int n) { int i, j, temp;   assert(arr != NULL); assert(n > 0);   for (i = 0; i < n; i++) { for (j = n - 1; j > i; j--) { if (arr[j] < arr[j-1]) { temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } } }   static void print(const int arr[], const int n) { int i;   for (i = 0; i < n; i++) { printf("%d,", arr[i]); }   printf("\n"); }   int main(void) { int arr[20]; int i; int b_ret, len;   srand(time(NULL)); for (i = 0; i < 20; i++) { arr[i] = rand() % 100; }   len = sizeof(arr)/sizeof(int);     print(arr, len); maopao(arr, len); print(arr, len);   b_ret = binary(arr, len, 47);   if (b_ret != -1) { printf("47 is in %d\n", b_ret); } else { printf("don not exist!\n"); }   return 0; }