技术

链表实现多项式及相关操作

多项式数据结构：

1
2
3
4
5
6
typedef struct polyNode *polyNodePtr;
struct polyNode {
    int coef; // 整型系数部分
    int expon; // 指数部分
    poluNodePtr next;
};

多项式加法操作：

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
polyNodePtr polyAdd(polyNodePtr a, polyNodePtr b)
{
    polyNodePtr c, tail, zeroNode;
    tail = malloc(sizeof(tail));
    c = tail;

    while (a && b)
    {
        if (a->expon == b->expon)
        {
            sum = a->coef + b->coef;
            if (sum)
                attach(sum, a->expon, &tail);

            a = a->next;
            b = b->next;
        }
        else if (a->expon > b->expon)
        {
            attach(a->coef, a->expon, &tail);
            
            a = a->next;
        }
        else
        {
            attach(b->coef, b->expon, &tail);

            b = b->next;
        }
    }

    for (; a; a = a->next) attach(a->coef, a->expon, &tail);
    for (; b; b = b->next) attach(b->coef, b->expon, &tail);

    tail->next = NULL;

    zeroNode = c;
    c = c->next;
    free(zeroNode);

    return c;
}

多项式销毁：

1
2
3
4
5
6
7
8
9
10
void erase(polyNodePtr *p)
{
    polyNodePtr node;
    while (*p)
    {
        node = *p;
        *p = (*p)->next;
        free(node);
    }
}

代码：poly_list.c

技术

Max Sum Subset Problem

最大子列和问题
最简单、时间复杂度为O(n^3)的实现方法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def get_max_sum_subset_n3(x):
    max_sum = 0
    index = []
    # 子列起始元素下标
    for i in range(len(x)):
        # 子列终止元素下标
        for j in range(i, len(x)):
            sum = 0 # 初始子列和
            # 计算子列和，from i to j
            for k in range(i, j+1):
                sum = sum + x[k]
            # 如果当前子列和大于最大子列和
            if sum > max_sum:
                # 子列和赋给最大子列和
                max_sum = sum
                # 子列下标
                index = range(i, j+1)
    # 返回最大子列和以及子列
    return [max_sum, [x[h] for h in index]]

时间复杂度为O(n^2)的实现方法

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
def get_max_sum_subset_n2(x):
    max_sum = 0 # 最大子列和
    start_index = -1 # 实时起始下标
    the_start_index = -1 # 最大子列起始下标
    the_stop_index = -1 # 最大子列终止下标

    for i in range(len(x)):
        sum = 0 # 初始子列和为0
        for j in range(i, len(x)):
            # 如果实时和为0，则当前元素为子列起始位置
            if sum == 0:
                start_index = j
            # 实时子列和加上当前元素
            sum = sum + x[j]
            # 如果当前子列和大于最大子列和
            if sum > max_sum:
                # 把当前子列和赋给最大子列和
                max_sum = sum
                # 记录最大子列和起始下标
                the_start_index = start_index
                # 记录终止下标
                the_stop_index = j
            
            # 如果当前子列和为负数，重置当前子列和为0
            if sum < 0
                sum = 0

    return [max_sum, [x[k] for k in range(the_start_index, the_stop_index+1)]

速度最快、时间复杂度为O(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
35
def get_max_sum_subset_n(x):
    # 空间换时间，用多个变量记录各个状态下的信息
    sum = 0 # 实时和值
    max_sum = 0 # 实时最大值
    start_index = -1 # 实时起始下标
    the_max_sum_ever = 0 # 循环到目前为止，子列最大和
    the_start_index = -1 # 循环到目前为止，子列起始下标
    the_stop_index = -1 # 循环到目前为止，子列终止下标
    
    for i in range(len(x)):
        # 第i个元素之前的最大子列和加上第i个元素
        sum = max_sum + x[i]
        # 判断当前和是否大于0
        if sum > 0:
            # 实时和大于0，当前子列还未中断
            if max_sum == 0:
                # 如果实时最大和等于0，则说明当前下标为子列起始下标
                start_index = i
            # 子列未中断，则将实时和赋给实时最大和
            max_sum = sum
        else:
            # 如果当前和小于0，则可认为当前第i个元素终止了最大子列
            # 实时最大和归0
            max_sum = 0
        # 实时值与历史值对比
        if max_sum > the_max_sum_ever:
            # 如果实时最大和大于历史最大和
            # 则将实时最大和赋给历史最大和
            the_max_sum_ever = max_sum
            # 当前下标作为终止下标
            the_stop_index = i
            # 当前起始下标作为历史起始下标
            the_start_index = start_index
    # 返回历史最大和以及子列
    return [the_max_sum_ever, [x[j] for j in range(the_start_index, the_stop_index+1)]]
技术

How to read statement in C

How to read statement in C?

Reference: 解读C的声明

发现一个解读C语言声明的好方法， 记录下来以备后患.

使用英语解读C语言声明

先上一组解读例子： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int hoge;
// eng: hoge is variable of int
// chn: hoge 是 int（类型） 的 变量
int hoge[10];
// eng: hoge is array[10] of int
// chn: hoge 是 int（类型）  的 数组【10个元素】
int hoge[10][3];
// eng: hoge is array[10] of array[3] of int
// chn: hoge 是 int（类型）  的 数组【10】  的 数组【3】
int *hoge[10];
// eng: hoge is array[10] of pointer to int
// chn: hoge 是 指向int（类型）指针 的 数组【10】
int (*hoge)[3];
// eng: hoge is pointer to array[3] of int
// chn: hoge 是 指向 int（类型）的数组  的 指针
int func(int a);
// eng: func is function(int a) returning int
// chn: func 是 返回int（类型） 的 函数（int a）
int (*func)(int a);
// eng: func is pointer to function(int a) returning int
// chn: func 是 指向 返回int（类型）的函数（int a） 的 指针

这种格式化的翻译不是真正的英语， 前期靠这种方式理解C语言声明确实很low， 不要着急， 熟练之后再鄙视吧。

翻译规则

基本元素的翻译：

  • aaa（变量名hoge、函数名func） => aaa is | aaa 是
  • aaa => variable of … |
  • bbb[10] => array of …
  • ccc() => function returning …
  • ddd => pointer to …
    翻译顺序：
    以 `int (    func)(int a)` 为例
  1. 首先翻译表示符： func is
  2. 优先翻译标示符所在括弧中的内容： func is pointer to
  3. 翻译用来表示表示符类型的符号（例如用来表示数组的[]， 用来表示函数的()）： func is pointer to function returning
  4. 最后， 追加类型指定符（最左边用来指定类型）： func is pointer to function returning int
    最后的翻译结果就是：

    func is pointer to function returning int
    这句话也不好理解， 再稍加润色一下就是：
    func is a poniter that point to the function that returning int
    翻译成中文就是：
    func 是 指向 返回int的函数 的指针

练习：
char *name[10]

name is array[10] of pointer to char
name 是 指向char 的 数组
double *d
d is pointer to double
d 是 指向 double类型 的 指针
。。。

技术

What is metaclass

What is metaclass?

Reference: answer on stackoverflow

python中的class也是对象

大多数的语言中，class是一段描述如何创建对象的代码，python也是这样，不过python中的class不仅仅是这样，它本身也是一个对象。
作为一个对象，你就能对它进行如下操作:

  • 将class对象赋给一个变量
  • 复制它
  • 给它添加属性
  • 可以将它作为一个参数传递给一个函数

动态的创建class

你可以随意的创建一个class，就想任何其他对象一样的。你可以在函数中创建一个对象并将它返回，这并不是很‘动态’，因为这样只不过class的定义写进函数中而已，
当你使用class关键字时，python就会自动创建一个class对象。python提供了一个手动创建class对象的方法——type() 

1
type(object)    # 返回对象的type

以上是我们熟悉的用法，但是type()还有一个功能——创建class对象。

1
2
3
4
5
6
7
8
type(classNamem classParentTuple, classAttributeDictionary)    # 返回一个新的type（class对象）

>>> Foo = type('Foo', (), {'bar':1})
>>> f = Foo()
>>> type(f)
>>> __main__.Foo
>>> f.bar
>>> 1

给class对象绑定方法

1
2
3
4
5
6
>>> def echoBar(self):
>>>     print(self.bar)
>>> Foo = type('Foo', (), {'bar':1, 'echoBar':echoBar})
>>> f = Foo()
>>> f.echoBar()
>>> 1

什么是metaclass呢？

任何对象都是由class或metaclass所创建的，class对象就是由metaclass创建的

type类似于str（用来创建string实例的class），int（创建整数对象的class），它就是python用来创建所有class对象的metaclass
type是内置的metaclass，你也可以创建自己的metaclass

metaclass属性

通过设置class的__metaclass__属性来指定创建class对象所使用的metaclass，metaclass的值可以是任何可调用的对象，包括函数，
python会去查找metaclass所指定的对象，如果找不到，python将会使用type来创建class对象。查找的顺序是1.在class内部查找；2.在模块内查找；
3.在父类中查找

小心！__metaclass__属性不会被继承！metaclass所指定的对象必须要能创建一个class对象！

定制metaclass

使用metaclass的目的是在创建class对象的时候做一些操作，就想在创建类实例的时候，自动调用init来做一些操作。
举一个‘愚蠢’的例子来说明，在创建class对象的时候自动将所有自定义的attribute改成大写字母（显然没什么卵用），现在我们来通过设置metaclass来实现该目的。
通过函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def upper_case(futrue_class_name, futrue_class_parent, future_class_attribute):
    uppercase_attr = {}
    for name, val in futrue_class_attribute.items():
        if not name.startswith('__'):
            uppercase_attr[name.upper()] = val
        else:
            uppercase_attr[name] = val
            return type(futrue_class_name, futrue_class_parent, uppercase_attr)
### python2.x
__metaclass__ = upper_case
class Foo():
    bar = 1
print(hassattr(Foo, 'bar'))    # return False
print(hassattr(Foo, 'BAR'))    # return True

### python3.x    (documetation)[https://docs.python.org/3/library/2to3.html?highlight=metaclass#2to3fixer-metaclass]
class Foo(metaclass=upper_case):
    bar = 1
print(hassattr(Foo, 'bar'))    # return False
print(hassattr(Foo, 'BAR'))    # return True

通过class

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
class UpperAttrMetaclass(type):
    uppercase_attr = {}
    def __new__(uperattr_metaclass, futrue_class_name, futrue_class_parent, future_class_attribute):
    # def __new__(cls, clsname, bases, dct):    # this is production code
        for name, val in future_class_attribute.items():
            if not name.startswith('__'):
                uppercase_attr[name.upper()] = val
            else:
                uppercase_attr[name] = val
                return type(futrue_class_name, futrue_class_parent, uppercase_attr)
        return type(future_class_name, future_class_parents, uppercase_attr)
        # or
        return type.__new__(future_class_name, future_class_parents, uppercase_attr)    # this is much OOP
        # or even cleaner
        return super(UpperAttrMetaclass, cls).__new__(cls, clsname, bases, uppercase_attr)
### python2.x
__metaclass__ = UpperAttrMetaclass
class Foo():
    bar = 1
print(hassattr(Foo, 'bar'))    # return False
print(hassattr(Foo, 'BAR'))    # return True

### python3.x    (documetation)[https://docs.python.org/3/library/2to3.html?highlight=metaclass#2to3fixer-metaclass]
class Foo(metaclass=UpperAttrMetaclass):
    bar = 1
print(hassattr(Foo, 'bar'))    # return False
print(hassattr(Foo, 'BAR'))    # return True

__new__和__init__差不多，后者是在创建实例时自动被调用，前者则是在创建class对象是被调用，__new__中第一个参数是class对象本身，
就像class方法第一个参数self是实例本身一样，定义如此，不必在意
好了，这就是所有有关metaclass的概念了

为什么使用metaclass class而不是function？

metaclass属性可以是任何可调用的对象，那为什么要使用class，而不是function呢？class明显要复杂的多，自己找虐吗？

  • 使用class使目的更明显
  • 可以使用OOP思想，使metaclass可以继承于其它metaclass，覆盖父类中的方法，甚至metaclass中还可以使用metaclass！
  • 可以使你的代码结构更清晰，简单的代码用不着metaclass，而复杂的代码中使用class来作为metaclass可以将一组方法group起来，使代码更加易读
  • 可以hook on __new__``__init__``__call__，你可以将所有的操作都放在__new__方法中（因为它是最先调用的方法），但是分开操作更有意义一些
  • metaclass之所以叫metaclass这是有原因的！use class and shut up!

为什么使用metaclass？

为什么使用这种不起眼而且易出错的特性？

你根本不用关心metaclass，因为99%的人都用不上，如果你想知道你为什么用这个特性，那么你就是那99%中的一员…
如果你实在想知道，可以举一个使用metaclass的例子来说明一下:
在web框架django中，我们这样定义model:

1
2
3
class Person(models.Model):
    name = models.CharField(maxlength=30)
    age = models.IntegerField()

然后我这样使用model：

1
2
guy = Person(name="Jerry Young", age=23)
print(guy.age)    # return 23 instead of models object

定义时age是一个models.IntegerField对象，而打印出来却是一个int，这就是因为创建Person class对象时使用了metaclass做了一些操作。

写在最后

1.你应该清楚class是对象，也可以用来创建对象；class本身就是metaclass的实例对象；python所有的东西都是对象，他们都是class或metaclass的实例，除了type；type是它自己的metaclass
2.你应该清楚metaclass是很复杂的，你可能不会想在简单的代码逻辑中使用它，你可以使用两种类似功能的技术：

  • monkey patching
  • class decorators
    99%的情况下你想修改class可以使用上述两种替代方案，但是99%的情况下你不需要修改class。
技术

Raspberry pi 直连Ubuntu系统笔记本

想通过ssh连上你的raspberry pi就应该使你的电脑和raspi处在同一个网段下(你的raspi有独立IP当我没说), 那么首先想到的就是把它们都连接到同一个路由器上, 如果手边没有路由器的话, 其实你也可以直接用一根网线直接连接你的电脑和raspi!

Step 1: 准备一根网线

不就是一根网线么? 有什么好讲的? 是这样的, 笔者之前上网搜索的时候, 看过一篇帖子:Raspberry与笔记本直连, 里面有个人说

camark
发表于 2013-1-10 15:51:24 |只看该作者
肯定不行。双机直连需要特殊的网线，而且要设置在一个网段。。

笔者当时就有点失望, 不过也硬着头皮随便找了一根网线, 最后也成功了, 最后也没有深究那个人说的是否是对的, 因此, 在此强调, 照着本文操作, 可能面临的风险

Step 2: 设置你笔记本的网络

其实也就是新建一个网络连接, 以Ubuntu 15.04为例子, 打开网络连接(屏幕右上角双箭头或wifi标志处), 点击编辑连接, 点击新建连接后如下图所示:

add a new connection

选择Ethenet(以太网), 点击创建, 在弹出来的框框中点击IPv4 Settings选项卡, Method栏选择Automatic (DHCP), 图如下:

config your new connection

至此, 网络设置就OK了

Step 3: 插进去!!

把网线的一头插笔记本, 一头插raspi, 点击上步新建的网络连接, 等待连接建立成功, 不出意外, 连接成功了! 出意外的肯定是网络连接没设置好或者网线是坏的(这tm不是废话么…)

Step 4: Find out your Raspi’s IP address

连接建立后你可以查看一下笔记本的连接信息, 找出你的笔记本IP地址, 注意! 是查看你连接raspi的网络连接的IP地址, 而不是如果你连了wifi的IP地址!

假设你的笔记本IP地址是 10.42.0.1 , 使用nmap查找同网段所有主机IP地址, 在终端下键入nmap 10.42.0.1/24, 等待片刻你会发现有两台主机, 一台你的笔记本, 一台就是raspi, 还可以看到有哪些端口打开着. 至于nmap, 你需要自行安装, 一般终端键入sudo apt-get install nmap即可, 好了, 拿到你的raspi的IP, 就OK了, 接着键入ssh pi@raspi的IP地址, 默认密码raspberry