一个数组中的元素被分为low, medium, high三类,实现一个排序算法,将该数组按照不同的类别进行排序。规则为low < medium < high.

Example:

Input:

The input array is ['g', 'n', 'e', 'c', 't', 'z', 'o', 'f'], and the elment sorted into 3 categories as below:

low: a-h
med: i-p
high: q-z

Output:

['c', 'e', 'g', 'f', 'n', 'o', 'z', 't']

function provided listed below, and its algorithm complexityis O(n).

bool islow(char c);
bool ismed(char c);
bool ishigh(char c);

Resolution:

You can sort any array with famous sorting algorithm, like bubblesort, insertsort, quicksort and etc. However, any sorting algorithm,  based on comparation of element, can’t do better than O(nlogn) without extra memory.

The element in the array has partitioned into 3 categories, which means this array only have three different element. Therefore, You do not need to care about the ranking of element in same categories.  So, Sorting the array could use 2 partition algorithm in quicksort. First, select an element in medium category as pivot, after partition, the left side of element in low category, and the right side is mixer of medium & high. Then, select a high one, partition the latter part of array. You will get the result.  and the complexity of algorithm is O(n).

Code:

阅读全文…

Microsoft在2007年的文章中描述了他们用于维护大规模互联网服务的工具利器AutoPilot,采用简单的模型和设计思想,AutoPilot负责自动化的运维数据中心中提供服务的大规模机器。想起每次上线时的等待,尤其在部分模块启动时间很长的时候,必须到全部都部署完成并check完成后才能完事的痛苦过程,就感叹国外的先进生产力。原文pdf见这里

Design Principles

  1. 被autopilot管理的large-scale web service必须自身有一定的容错性,任何一个节点或者部分节点的失效都应该不影响系统对外的正常服务。autopilot是一个lazy action的监控&修复Service。
  2. Simplicity is as important as fault-tolerance when building a large-scale reliable, maintainable system。最近一年对这句话感触很深,一个本身就很庞大的系统,在很多地方必须尽可能的简单,任何过于精巧的实现解决的问题,一旦出了问题,很可能都会带来更严重的问题,并且很难处理。Autopilot在设计上的机制上非常简单,从错误分类、到执行的操作以及节点的状态定义都简单通用,不进行特化。同时允许用户端程序自己进行部分扩展。

单个Autopilot实例负责管理的一堆机器被成为一个cluster,数据中心中的购置的机器配置都是符合一系列标准套餐中的某种。

阅读全文…

周末阅读了下陈硕老师的分布式系统的工程化开发方法,原地址连接请猛击这里(blog, 视频),也将blog上的一页页演讲稿整理成了pdf借花献佛一下,点击这里下载。

在阅读完陈硕老师的演讲稿以及相关视频后,回顾了下自己工作一年来碰到的一些问题,梳理下一些设计中需要考虑的点。与陈硕老师的题目不同,这里主要针对大型互联网后台程序,存在模块间的交互,但部署同一个服务模块的不同机器之间的状态是一致的,因此不讨论分布式系统中常见一致性、通信、选举等问题。

  • Design for failure —— 大型互联网的后端服务是7*24 online service的,因此当出现异常时(单个或者多个节点异常,必须在尽可能保证服务的前提下,尽快恢复)
  • 能重启、快速重启 —— 一个服务启动的速度对该模块的日常更新,以及异常情况下的快速恢复有着决定性的作用,在开发时应该尽可能的缩短启动的时间,在完成必须启动和加载的相关配置后,优先提供服务。此外陈硕老师提到的优雅重启,也是需要考虑的问题,尽可能的减少停止服务重启时刻对现在正在service的请求造成的影响。
  • 避免阻塞 —— 对于多个模块通过tcp交互的场景,如果某个模块的工作线程被阻塞,则会导致上游不断的超时,甚至请求堆积到被阻塞的模块,因此需要尽可能的减少阻塞。可以通过设置合理的超时时间,调高工作线程数等方式。
  • 监控 —— 对于7*24 online的service尤为重要,最好能全方位的提供一个方便的探测当前模块服务状态的接口,unix文件系统都会预留proc这样的接口,可以观察正在运行的进程状态。这里的探测不仅仅包括常用的硬件如CPU、内存、网卡、句柄等探测,甚至包含与上下游交互的健康状态,以及其他业务相关的信息。
  • 操纵性 —— 除了监控,对于自己写的online service,在上线服务后,应该具备一定的可操控能力,例如运行时改变一些行为状态,避免异常时只能选择回滚。对于一些关键的功能点,应该有一些可运行时reload的开关控制,在特殊情况时进行操作。
  • 分步升级 —— 多个模块不可能同时升级,如果涉及接口的变动,采用C buffer传递字节信息会造成接口不兼容的依赖,考虑idl/protocol buffer。

————————分割线——————————扯点其他的————————————

在陈硕老师的PPT中提到了在epoll的水平触发(LT)方式下,accept返回EMFILE时的异常问题解决,自己实验了下,并没有持续返回可读,通过tcpdump查看,发现accept失败后,系统发送了FIN包主动断开的连接,怀疑与linux内核版本有关。可以查看下面tcpdump的数据。

阅读全文…

,

在实际中碰到这样一类问题,有一个结构体,中间包括各种不同的类型,但有一种函数,需要对不同类型字段的值都进行统计、排序等操作,函数中90%的代码都相同,唯一的不同是获取目标结构体的不同字段的值,为了避免针对不同类型的字段,声明不同类型的变量,通过封装get_field_val(struct)为模板函数解决此问题。如下代码

#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct info_t{
 int a;
 string b;
 int c;
};

class account{
public:
 template<class T>
 void account_field(int type)
 {
 vector<T> vec;
 for(int i = 0; i < 8; i++)
 {
 T val;
 val = get_val<T>(infos[i], type);
 vec.push_back(val);
 }
 //统计, 排序xxxx一堆工作
 //...
 return;
 }

 template<class T>
 T get_val(info_t info, int type)
 {
 if(type == 1)
 return info.a;
 else
 return info.c;
 }

private:
 info_t infos[8];
};

template<> string account::get_val<string>(info_t info, int type)
{
 return info.b;
}

int main(void)
{
    account a;
    a.account_field<int>(1);
    a.account_field<string>(2);
    return 0;
}

如上,使用模板get_val函数和type获取指定字段的值,并且针对string进行模板的特化。对于类成员模板函数的特化,必须放在类定义的外部,否则会报Explicit specialization in non-namespace scope的错误,具体的原因可以参见如下说明。如果没有该特化,也可以直接重载一个函数,但这样就不能在调用函数时显示特化了,特别是对于调用a.account_field<T>(type)的函数。

An explicit specialization shall be declared in the namespace of which the template is a member, or, for member templates, in the namespace of which the enclosing class or enclosing class template is a member.

An explicit specialization of a member function, member class or static data member of a class template shall be declared in the namespace of which the class template is a member.

,

当我们需要对某段读写文件并进行处理的程序进行性能测试时,文件会被系统cache住从而影响I/O的效率,必须清理cache中的对应文件的才能正确的进行性能测试。通常清理内存可以采用下面的这条命令,但这条命令只有root才能使用,另外一方面这个会清理所有的cache,也许会影响其他程序的性能。

echo 3>/proc/sys/vm/drop_caches

linux下有一个posix_fadvise函数可以用来对cache中的文件进行清理,有关posix_fadvise的详细说明查看man手册。

int posix_fadvise(int fd, off_t offset, off_t len, int advice);

”Programs  can  use  posix_fadvise  to  announce an intention to access file data in a specific pattern in the future, thus allowing the kernel to perform appropriate optimisations”

fd是文件的描述符,用于清理对应文件cache的advice值选取POSIX_FADV_DONTNEED,利用此函数编写下面程序进行文件的清理。

int clear_file_cache(const char *filename)
{
	struct stat st;
	if(stat(filename , &st) < 0) {
		fprintf(stderr , "stat localfile failed, path:%s\n",filename);
		return -1;
	}

	int fd = open(filename, O_RDONLY);
	if( fd < 0 ) {
		fprintf(stderr , "open localfile failed, path:%s\n",filename);
		return -1;
	}

	//clear cache by posix_fadvise

	if( posix_fadvise(fd,0,st.st_size,POSIX_FADV_DONTNEED) != 0) {
		printf("Cache FADV_DONTNEED failed, %s\n",strerror(errno));
	}
	else {
		printf("Cache FADV_DONTNEED done\n");
	}

	return 0;
}

此外,linux-ftools这个工具也可以帮助清理并查看文件的内存状态,主页上也有详细的使用说明。编译后我们利用fincore这个工具来查看文件在内存中的状态,有关fincore的实现可以在linux下man mincore,mincore是根据缓存buffer指针来其指向的缓冲区判断在cache中的状态,fincore就是在mincore的基础上直接操作文件,就是通过对文件mmap获得指针,再调用mincore来判断。

首先我们通过cp命令拷贝了一个相对有点容量的文件,然后利用fincore查看文件在内存中的cache情况,可以看到大概cache了99.55%。

image

接着执行上面那段代码的运行程序,之后再执行命令查看该文件的缓存状态

image

可以看到,该文件在内存中已经没有被cache了。实际的清理效果也可以通过一些占用I/O的读文件程序来测试,一般程序第二遍运行时候由于文件已经被cache,实际程序运行的速度会比较快,通过上面的posix_fadivse清理之后,又会恢复和第一遍差不多的时间。

, ,

以下的一段代码是不是很眼熟

     char *a = new char[1024];
     if(a == NULL) {
           //申请失败,处理
     }
     else {
          //正常处理....
     }

的确经常会在程序里这样用,特别是上学时候很多的教科书里想当然的申请失败,返回了NULL。由于使用C++的同学一般不太使用Exception机制,而会忽略异常。其实C++的库中对operator new的声明如下形式。

void* operator new (std::size_t size) throw (std::bad_alloc);
void* operator new (std::size_t size, const std::nothrow_t& nothrow_constant) throw();
void* operator new (std::size_t size, void* ptr) throw();

第一种是我们最常使用的,这种方式在申请失败时会抛出std::bad_alloc的异常,而非返回NULL,如下代码。

#include <iostream>
#include <unistd.h>
using namespace std;

int main(void)
{
    while(1) {
        char *a = new char[1024*1024*1024];
        if( a != NULL) {
            cout<<"new 1GB buffer size"<<endl;
        }
        else {
            cout<<"new failed!\n"<<endl;
            return -1;
        }
    }
    return 0;
}

其运行结果如下图,可以看出,程序抛出了std::bad_alloc的异常

第二种则添加了nothrow参数,使得new不抛出异常。
对上面的第8行做如下修改:

        char *a = new(nothrow) char[1024*1024*1024];

从运行结果就可以看出来,程序不抛出异常,而直接返回NULL指针了。

最后一种是placement new,即是在ptr指向的空间上new对象,本身并不申请空间,因此也不会异常。

默认情况下的new是会抛出std::bad_alloc异常的,可以使用set_new_handler来处理默认情况下的异常,代码如下:

#include <iostream>
#include <unistd.h>
using namespace std;

void no_memory () {
  cout << "Failed to allocate memory!"<<endl;
  //这里可以写点清理代码
  throw bad_alloc();  //默认处理函数,继续往上层抛出
  exit (1);
}

int main(void)
{
    set_new_handler(no_momery);
    while(1) {
        char *a = new char[1024*1024*1024];
        if( a != NULL) {
            cout<<"new 1GB buffer size"<<endl;
        }
        else {
            cout<<"new failed!\n"<<endl;
            return -1;
        }
    }
    return 0;
}

则程序执行到new抛出了异常时,会利用set_new_handler的函数进行处理,也可以不throw转而直接exit/return等,执行效果如下:

这段代码告诫自己平常学习应该多钻研,多问,不能想当然,特别是学校课堂上的东西都太过于理想。如果不清楚的应该多看官方一点的东西,有关operator new的东西可以查看这里,描述的很清楚。

蔡勒(Zeller)公式,

传送门

int getDayofWeek(int day, int month, int year)
{
     int week;
     if(month < 3)
     {
        year -= 1;
        month += 12;
     }
     int c = int(year/100);
     int y = year - 100*c;
     week = int(c/4) - 2*c + y + int(y/4) + (26*(month + 1)/10) + day - 1;    // caculate the day of week
     week = (week%7 + 7) % 7;
     return week;   //0 for Sunday, 1 for Monday... 6 for Saturday
}

面试基础常见问题之一,基本流程如下,1,2点是容易忽视的点

1)处理空白字符;

2)处理符号字符;

3)处理数值字符;

4)返回结果。

int atoi(const char* str)
{
    int result = 0;
    int sign = 0;
    assert(str != NULL);
    // proc whitespace characters
    while (*str==' ' || *str=='\t' || *str=='\n')
        ++str;
    // proc sign character
    if (*str=='-')
    {
        sign = 1;
        ++str;
    }
    else if (*str=='+')
    {
        ++str;
    }
    // proc numbers
    while (*str>='0' && *str<='9')
    {
        result = result*10 + *str - '0';
        ++str;
    }
    // return result
    if (sign)
        result *= -1;
    return result;
}

还真的有公司笔试考了这个填空,每次看到这个都记得不太准,kmp算法的难点就是求next数组,
遂回来仔细研究了下求next串的方法,kmp算法中主串不用回溯的的原因就是因为可以利用已知匹配来确认子串的滑动距离。

设s=” s1 s2 … sn ”, t=” t1 t2 … tm ”,在匹配过程中,当si≠ tj(1≤i≤n-m+1,1≤j≤m)时,存在(前面的j-1个字符已匹配):
si-j+1 … si-1 = t1 t2 … tj-1
若模式中存在可互相重叠的最长的真子串,满足:
t1 t2 … tk-1 =tj-k+1 tj-k+2 … tj-1

根据上式,求next串的过程,可以理解为模式串自身匹配自身,则有t1 t2 … tk-1 =tj-k+1 tj-k+2 … tj-1,而t(k) == t(j) , 则next[j+1] = next[j] + 1,否则就next[j+1] = next[k`] + 1 ,这个k`要一直0或者t(j) = t(next[k]) …

书上的代码都是字符串从下标1开始,next也从下标1开始。。。这些贴出从下标0开始的


void get_next(const char *s, int *next)
{
     int i=0,j=-1;
     next[0] = -1;
     while(s[i])
     {
          if( j == -1 || s[i] == s[j])
          {
              i++;
              j++;
              next[i] = j;
          }
          else
              j = next[j];
     }
 }

 int kmpfind(const char *t, const char *s,int *next)
 {
     int i = 0,j=0;
     int lena = strlen(t);
     int lenb = strlen(s);
     while(i < lena && j < lenb)
     {
                if(j == -1 || t[i] == s[j])
                {
                     i++;
                     j++;
                     if(s[j] == '\0')
                        return i - j;
                 }
                else
                    j = next[j];
     }
     return -1;
 }
, ,

回西安的第一天又被发短信催着去面试,介于无聊,所以准备去被鄙视下,两个月的实习会让面试那些东西又忘光了。。在其他人都是链表节点的删除、字符串循环左移一位的题目下。。。我幸运的被问了一句“写个大数乘法吧”,So,只好模拟手算过程,然后想边计算边搞进位,结果写的漏洞百出的被鄙视了,话说成天php的,写变量的时候都老容易写出来$。

任何一个数都可以表示成为  x = a(n) * 10^n + a(n-1)*10(n-1) + … + a(0)的形式,

则 x*y = (a(n) * b(n))*10^(2n) + (a(n)*b(n-1) + a(n-1)*b(n))*10^(2n-1) + … + a(0)*b(0)

程序中可以直接按上述公式乘,乘完的结果再做进位的调整

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

void reverse(char *str)
{
     int len = strlen(str);
     int i=0;
     for(i=0;i<len/2;i++)
     {
          char tmp = str[i];
          str[i] = str[len-i-1];
          str[len-i-1] = tmp;
     }
}

void mul(int *ret,char *a,char *b)
{
     int lena = strlen(a);
     int lenb = strlen(b);
     int i,j;
     for(i=0;i<lena;i++)
     {
         for(j=0;j<lenb;j++)
         {
             ret[i+j] = ret[i+j] + (a[i] - '0') * (b[j] - '0');
         }
     }
     for(i=1;i<lena + lenb + 2;i++)
     {
          ret[i] += ret[i-1]/10;
          ret[i-1] = ret[i-1]%10;
     }
}

int main(void)
{
    char a[256],b[256];
    scanf("%s%s",a,b);
    reverse(a);
    reverse(b);
    int lena = strlen(a);
    int lenb = strlen(b);
    int *ret = (int *)malloc(sizeof(int)*(lena + lenb + 2));
    int i=0;
    for(i=0 ; i<lena + lenb + 2;i++)
       ret[i] = 0;
    mul(ret,a,b);
    i = lena + lenb + 1;
    while(ret[i] == 0)
    {
       i--;
       if(i == -1)
         break;
    }
    if(i == -1)
         printf("0\n");
    else
    {
        while(i>=0)
        {
           printf("%d",ret[i]);
           i--;
        }
        printf("\n");
    }
    system("pause");
    return 0;
}