matplotlib基础

Introduction

matplotlib是一个很好用的可以画2D图的Python模块。它提供了很方便进行可视化数据的方案。下面是对matplotlib的使用进行了一个简单的记录。

Simple plot

import numpy as np

X = np.linspace(-np.pi, np.pi, 256,endpoint=True)
C,S = np.cos(X), np.sin(X)

这里的X是一个数组,里面有256个数,范围是\([-\pi,\pi]\)。接下来的CS是分别是cos值和sin值。

基础绘图

import numpy as np
import matplotlib.pyplot as plt

X = np.linspace(-np.pi, np.pi, 256, endpoint=True)
C,S = np.cos(X), np.sin(X)

plt.plot(X,C)
plt.plot(X,S)

plt.show()

对图进行一些设置

# Imports
import numpy as np
import matplotlib.pyplot as plt

# Create a new figure of size 8x6 points, using 100 dots per inch
plt.figure(figsize=(8,6), dpi=80)

# Create a new subplot from a grid of 1x1
plt.subplot(111)

X = np.linspace(-np.pi, np.pi, 256,endpoint=True)
C,S = np.cos(X), np.sin(X)

# Plot cosine using blue color with a continuous line of width 1 (pixels)
plt.plot(X, C, color="blue", linewidth=1.0, linestyle="-")

# Plot sine using green color with a continuous line of width 1 (pixels)
plt.plot(X, S, color="green", linewidth=1.0, linestyle="-")

# Set x limits
plt.xlim(-4.0,4.0)

# Set x ticks
plt.xticks(np.linspace(-4,4,9,endpoint=True))

# Set y limits
plt.ylim(-1.0,1.0)

# Set y ticks
plt.yticks(np.linspace(-1,1,5,endpoint=True))

# Save figure using 72 dots per inch
# savefig("../figures/exercice_2.png",dpi=72)

# Show result on screen
plt.show()

改变颜色和线的粗细

plt.figure(figsize=(10,6), dpi=80)
plt.plot(X, C, color="blue", linewidth=2.5, linestyle="-")
plt.plot(X, S, color="red",  linewidth=2.5, linestyle="-")

设置X轴和Y轴的范围

plt.xlim(X.min()*1.1, X.max()*1.1)
plt.ylim(C.min()*1.1, C.max()*1.1)

设置坐标轴的刻度

plt.xticks( [-np.pi, -np.pi/2, 0, np.pi/2, np.pi])
plt.yticks([-1, 0, +1])

设置坐标轴刻度上的字

plt.xticks([-np.pi, -np.pi/2, 0, np.pi/2, np.pi],[r'$-\pi$', r'$-\pi/2$', r'$0$', r'$+\pi/2$', r'$+\pi$'])

plt.yticks([-1, 0, +1],[r'$-1$', r'$0$', r'$+1$'])

移动坐标轴

ax = plt.gca()
ax.spines['right'].set_color('none')
ax.spines['top'].set_color('none')
ax.xaxis.set_ticks_position('bottom')
ax.spines['bottom'].set_position(('data',0))
ax.yaxis.set_ticks_position('left')
ax.spines['left'].set_position(('data',0))

为图添加说明

plt.plot(X, C, color="blue", linewidth=2.5, linestyle="-", label="cosine")
plt.plot(X, S, color="red",  linewidth=2.5, linestyle="-", label="sine")

plt.legend(loc='upper left', frameon=False)

添加注释

t = 2*np.pi/3
plt.plot([t,t],[0,np.cos(t)], color ='blue', linewidth=1.5, linestyle="--")
plt.scatter([t,],[np.cos(t),], 50, color ='blue')

plt.annotate(r'$\sin(\frac{2\pi}{3})=\frac{\sqrt{3}}{2}$',
             xy=(t, np.sin(t)), xycoords='data',
             xytext=(+10, +30), textcoords='offset points', fontsize=16,
             arrowprops=dict(arrowstyle="->", connectionstyle="arc3,rad=.2"))

plt.plot([t,t],[0,np.sin(t)], color ='red', linewidth=1.5, linestyle="--")
plt.scatter([t,],[np.sin(t),], 50, color ='red')

plt.annotate(r'$\cos(\frac{2\pi}{3})=-\frac{1}{2}$',
             xy=(t, np.cos(t)), xycoords='data',
             xytext=(-90, -50), textcoords='offset points', fontsize=16,
             arrowprops=dict(arrowstyle="->", connectionstyle="arc3,rad=.2"))

See also

Numpy 100 Numpy exercises Ten simple rules for better figures

C++ zip实现

最近心血来潮想在C++里实现一些像在python里一样好用的小组件,主要是希望充分发挥C++11for循环的威力。在完成了enumerate之后,在zip的完成上用了比较久的时间。

在这里记录下来自己对zip的简单实现。

主要就用了模板递归,结合了一些C++11的新特性完成的。

#pragma once

namespace twistoy {
	template<typename first, typename... last>
	class zip_iterator {
	public:
		using value_type = std::tuple<typename first::reference, typename last::reference...>;
		using rebind = zip_iterator<first, last...>;
		using sub_iterator = zip_iterator<last...>;
	private:
		first it_;
		sub_iterator sub_it_;
	public:

		zip_iterator(first it, sub_iterator sub_it) : it_(it), sub_it_(sub_it) {}

		rebind& operator++() {
			++it_;
			++sub_it_;
			return *this;
		}

		value_type operator *() {
			return std::tuple_cat(std::tuple<typename first::reference>(*it_), *sub_it_);
		}

		bool operator != (const rebind& others) const {
			return (it_ != others.it_) && (sub_it_ != others.sub_it_);
		}

	};

	template<typename first>
	class zip_iterator<first> {
	public:
		using value_type = std::tuple<typename first::reference>;
		using rebind = zip_iterator<first>;
	private:
		first it_;
	public:
		zip_iterator(first it) : it_(it) {}
		value_type operator *() {
			return value_type(*it_);
		}
		rebind& operator++() {
			++it_;
			return *this;
		}
		bool operator != (const rebind& others) const {
			return it_ != others.it_;
		}
	};

	template<typename first, typename... last>
	class zip_impl : zip_impl<last...> {
	public:
		using iterator = zip_iterator<typename first::iterator, typename last::iterator...>;
	private:
		first& value_;
	public:
		zip_impl(first& value, last&... args) : value_(value), zip_impl<last...>(args...) {}
		iterator begin() {
			return iterator(value_.begin(), zip_impl<last...>::begin());
		}
		iterator end() {
			return iterator(value_.end(), zip_impl<last...>::end());
		}
	};

	template<typename first>
	class zip_impl<first> {
	public:
		using iterator = zip_iterator<typename first::iterator>;
	private:
		first& value_;
	public:
		zip_impl(first& value) : value_(value) {}
		iterator begin() {
			return iterator(value_.begin());
		}
		iterator end() {
			return iterator(value_.end());
		}
	};

	template<typename... args_t>
	zip_impl<typename std::decay<args_t>::type...> zip(args_t&... args) {
		zip_impl<typename std::decay<args_t>::type...> tmp(args...);
		return tmp;
	}
}

C++ Template

函数模板

使用模板

模板被编译了两次,分别发生在:

  1. 实例化之前,先检查模板代码本身,查看语法是否正确。
  2. 在实例化旗舰,检查模板代码,查看是否所有的调用都有效。

模板的推导

在模板推导的过程中,不会进行自动的类型转换,每个类型都必须正确的匹配。

template<typename T>
inline T const& max (T const& a, T const& b);

max(4, 7); // OK: 两个实参的烈性都是int
max(4, 4.2); // ERROR: 第二个实参的类型是double,这里没有把第一个int自动升级成了double

有三种方法来处理:

  1. 对实参进行强制类型转换,使它们可以相互匹配。max(static_cast<double>(4), 4.2);
  2. 显示制定T的类型。max<double>(4, 4.2);
  3. 制定两个参数可以有不同的类型。

模板参数

在函数模板内部,不能制定缺省的模板实参。

重载函数模板

函数的所有重载版本的声明都应该位于该函数被调用的位置之前。

类模板

类模板的特化

如果要特化一个类模板,还要特化该类模板的所有成员函数。虽然也可以只特化某个成员函数,但这个做法并没有特化整个类,也就没有特化整个类模板。

局部特化

template<typename T>
class MyClass<T, T>;

template<typename T>
class MyClass<T, int>;

template<typename T1, typename T2>
class MyClass<T1*, T2*>;

有多个局部特化同等程度的匹配某个声明的时候,那么该声明具有二义性:

MyClass<int, int> m;
// MyClass<T, T>, MyClass<T, int>
MyClass<int*, int*> m;
// MyClass<T, T>, MyClass<T1*, T2*>

为了解决第二种二义性,可以提供一个指向相同类型指针的特化:

template<typename T>
class MyClass<T*, T*>;

缺省模板实参

像指定一个函数的缺省实参一样。

非类型模板参数

对于函数模板和类模板,模板参数并不局限于类型,普通纸也可以作为模板参数。

非类型模板参数的限制

非类型模板参数可以是常整数(包括枚举值),或者指向外部链接对象的指针。

浮点数和类对象 是不允许作为非类型模板参数的。

技巧性基础知识

关键字 typename

当某个依赖于模板参数的名称是一个类型时,就应该使用 typename

.template 构造

template <int N>
void printBitset (std::bitset<N> const& bs) {
    std::cout << bs.template to_string<char, char_traits<char>, allocator<char> >();
}

template 去修饰后面的 to_string 的显式实例化模板版本的 < ,不是数学上的小于号,而是模板实参列表的起始符号。

使用 this->

对于具有基类的类模板,自身使用名称 x 并不一定等于 this->x。即使该 x 是从基类继承获得的。

对于那些在基类中声明,并且依赖于模板参数的符号(函数或者变量等),你应该在他们前面使用this->或者Base<T>::。如果希望完全避免不确定性,你可以限定所有的成员的访问。

成员模板

template<typename T>
class Stack {
    ...
    template <typename T2>
    Stack<T>& operator = (Stack<T2> const&);
}

对于类模板而言,只有被调用的函数才会被实例化。

模板的模板参数

template<typename T, template <typename ELEM> class CONT = std::deque>
class Stack;
  • 在上面那段代码中第一行的 class 是不能和 typename 互换的,因为这里是为了定义一个类,而不是表示一个类型。
  • 没有用到上面的 ELEM 参数,所以可以省略不写。
  • 函数模板不支持模板的模板参数。
  • 模板的模板实参必须精确的匹配。匹配时并不会考虑“模板的模板实参”的缺省模板实参。

模板的实参匹配

template<typename T,
            template <typename ELEM,
                        typename ALLOC = std::allocator<ELEM> > class CONT = std::deque>
class Stack;

零初始化

希望对所有的对象都用缺省构造函数初始化。

template <typename T>
void foo() {
    T x = T();
}

对于类模板,需要把所有数据成员的缺省构造函数在这个类的缺省构造函数中调用。

字符串作为函数模板的实参

由于长度的区别,有些字符串属于不同的数据类型。applepeach,具有相同的类型 char const[6],然而 tomato 的类型是 char const[7]。如果使用的是引用类型的话,在实例化模板的时候,就会出现类型不同的问题。

template <typename T>
inline T const& max (T const& a, T const& b) {
    return a < b ? b : a;
}

::max("apple", "peach"); // ok
::max("apple", "tomato");

但是在这里使用非引用类型的参数,就是可以的。因为如果使用非引用类型的参数,在这里会进行一个数组到指针类型的转换(这个转型过程通常被叫做decay)。

字符数组和字符串指针不匹配的问题,根据不同的情况,可以:

  • 使用非引用参数,取代引用参数。(可能会导致无用的拷贝。)
  • 进行重载。编写接受引用和非引用参数的两个版本。(可能导致二义性)
  • 对具体类型进行重载。
  • 重载数组类型。比如:
template <typename T, int N, int M>
T const * max (T const (&a)[N], T const (&b)[M]) {
    return a < b ? b : a;
}
  • 强制要求应用使用显式的类型转换。

2015 长春站亚洲区 && 退役总结

在路上

我居然到去长春比赛之前才知道,哈尔滨居然离长春这么近。【好吧,不要在意我的地理,我一直以为去长春至少要做个飞机什么的呢,23333。没想到残酷的事实告诉我,长春比牡丹江还近66666666。】 去的时候的路上在刷微博的时候,居然发现自己和SDL在一辆车上,找她扯淡扯到了快下车,所以在去的时候的车上也没感到什么痛苦,就一下子到了。 回来的时候我在努力的编故事【hhh,我要给小鲜肉们安利舰娘hhhhh】,偶尔和小伙伴们扯一会,可能是比完赛大家心情都还不错的原因, 气氛也是非常的好,虽然火车时间比去的时候长了一个小时,可是也够开心了啊。

宾馆里

老实说,宾馆的条件还是可以的。没什么可吐槽的,唯一算上和宾馆有关的吐槽就应该是不认识路还强行要带路的LCH同学。热身赛回来的时候,他说自己是认得路的,我们也天真的相信了他,结果…

比赛中

热身赛

热身赛一共四道题目,A题很逗比的是一个测试人品的题,官方的说法是要测试一下服务器压力。23333。还真的有人品很好的2次就过了,也是厉害。热身赛做了一小会就跑去玩数独和扫雷了。时至今日,我终于学会了扫雷的玩法,【新技能get!】

正赛

比赛前就听说了这次比赛的题目数量应该是比较多的,和长老预料的不一样的是这次的题目难度并没有因为题量而降低多少。 比赛开始之后像我们这种队伍就开始紧跟榜单,接连发现了两道水题,F题(1Y/25)和L题(1Y/20)。这两个题呗我们迅速的A掉了。都是1Y。然而当我们看到了J题的时候,本来标解是Trie的,可是我们第一时间想到的是一个$n^3$的暴力枚举的办法,我显然以为是会TLE的。结果在赛场上GF想到了一个略微优化了一点的方法,抱着如果TLE就再仔细想想的念头尝试了一次,结果WA掉了。这次的WA给了我们很大的信心,调掉了一个小bug就A掉了。2Y/76 于此同时的是LFQ在写G题。可是一开始他读错了题意,写完一份DFS之后发现并不能通过样例,重构之后1Y/134。 这时候我们已经出了四题了,还算是排在了一个还可以的位置上。在LFQ写G题的时候,我和GF在考虑H题的解法。最开始想了一个按照升序来优化枚举的$n^3$的算法。接连WA了很多发,中间也有够侥幸心理觉得既然J题的都可以水过,那么H题的数据也不会太强吧,然后强行TLE了一次。后来发现了这是一个完全背包的模型,飞快重写了完全背包,一次就通过了,最后6Y/252。 在GF写升序优化版本的H题的时候,我和LFQ读了E题,并迅速的发现了这应该是个简单的递推一次,然后分情况求解的过程。在GF的H题WA了在纸面上Debug的时候,写好了E题,过了样例就WA了一发。最开始是以为有精度问题的,判断了精度之后又WA了。最后发现自己在一个很蠢很蠢的地方,我们明明想到也写在纸上了的一个条件并没有写进去,加上特判条件,3Y/260。

最后我们的成绩也就以6题收尾的。拿了人生中的第一个ACM金牌吧,说不开心都是假的,不过成绩都是过去的事情了,让自己变得更强才更重要呢。

结束语

以金牌收尾的ACM生涯,我自己看来是已经圆满了的。回忆自己搞算法竞赛的过程,从高中时候搞算法竞赛逃课被老师告诉家长,周围的人都劝我不要在学下去了,耽误了茫茫多的文化课,结果NOIP还是以一个很差的成绩收尾了;到了大学开始搞ACM,从大一的时候参加省赛和东北赛都是二等奖滚粗,到大二和亮哥、学姐一起拿到了亚洲区银牌,省赛开始和放牛组队拿到了奇怪的省赛冠军和东北赛一等奖,到了今天我也已经大三了,也算是得偿所愿吧,终于拿到了一个金牌。想想时间过的还真是快的可以,一晃就在茫茫多的训练中过去了。想一想自己以后会不会轻松一点呢,应该就会有周末了吧,假期也可以出去和小伙伴溜达溜达体验祖国的大好风光了? 要说到学ACM我都收获了什么,首先是收获了一群很棒的小伙伴,其次就是在参加比赛的过程中锻炼和证明了自己的能力吧,我觉得。 好像觉得也没什么可写下去的了,就这样吧。我终于有一天退役了,以前看着别人的退役贴都感觉好厉害,今天自己也躺在床上写下了这个不算退役贴的退役贴吧。就这样吧,再见ACM!

2015 省赛、东北赛总结

Part1. 省赛

先来吐槽下工大,热身赛之前大家都在外面站着连个休息的地方都没有,整个人都被冻傻了…正赛那天早上还好(其实我感觉主要是天比较给力,比较暖和,也可能是我机智的穿上了棉袄的原因…2333。)
然后就是题目的部分了,所有题目主要就是题面比较难读吧,绝对是的。我们一致认为着出题人的英语绝对有问题,然后脑洞有点大…(绝对脑洞巨大…)

  • A题,直到现在我依旧没能看懂题目在说什么,如何通过题面得到样例的…
  • B题,大概貌似是一个贪心吧,我们队按照这个思路写了挺长时间的,,然后WA了,,感觉小问题小坑很多…
  • C题,我们队也开了,主要是前面三个小时就已经A了五个题了,后面就一起开了B题和C题,结果都坑掉了。 题目大概是说一个连连看,当前状态有多少种合法的选择消去的方案。暴力的用优先队列+BFS尝试了一下,结果T掉了。
  • D题,其实是一个很简单的贪心啦,题意上面也没有什么难度和坑。很容易1A,我记得。
  • E题,这道题我读题意读了挺长时间的,然后样例上还有点小问题。(英语太烂23333)读懂题意以后也会很简单的。
  • F题,我们队用的方法是数位DP,当然由于数据范围的关系暴力好像也是可以过的。
  • G题,这道题真正的坑点在脑洞上…我至今都是这么认为的。虽然这道题是我们夺冠的关键,,,但是依旧改变不了这是一个脑洞题的事实。只要记得,并不是一个联通块周围有白子和黑子是一人0.5,而是按照白子和黑子的个数按权分配的!就可以了。
  • H题,斗地主,给你三家牌,问第一家能不能春天…并没有仔细的思考下去…
  • I题,给三张牌算得分,很简单的模拟。
  • J题,裸的二分图匹配。WA了一次居然是因为数组忘记清空了…23333。

如实的说,能夺冠这件事完全就是恰好我们的脑洞开到了出题人的脑洞上去,和我们队本来的实力没有那么大的关系。

Part2. 东北赛

到了东北赛感觉好了很多啊,进门也不要排队了,也不要在外面傻傻的冻着了。顿觉幸福…

  • A题,水题不多说。1A。
  • B题,二维树状数组模板。1A。
  • C题,题意是说求一个三角形结构中选k个的最大权。读到这道题的时候,我们还在卡着其他的两个题,所以就没有多想下去,而且那么时间想下去也不知道能不能想出来…
  • D题,类似树形DP的东西,没什么坑点。1A。
  • E题,说道E题就要说,我很愧对我的高数和大物老师,嗯…还有我高中的数学老师。思路卡了一次,错了一次,然后才发现应该如何的简单处理,最后还卡了一下精度处理上。傻的不行…
  • F题,没读,现在写总结的时候,,也不想读。
  • G题,对x做质因子分解求出所有的质因子,然后对于每一个查询m,只要做一个优先队列+BFS就可以了。因为只会找第5个大的。所以结果会很少的。WA了几次都WA在了重复数字的处理上。处理掉了就没问题了。
  • H题,很简单的一个BFS,坑在了起点就在一个除了1之外的触发器上。嗯…由于忘记了这里,WA了一个半小时。
  • I题,水题。最开始数据错了,应该是,最后rejudge了,不过也听说有好多小伙伴被坑了。
  • J题,同F。
  • K题,我们最后时刻在写的五子棋的问题。我们的想法就是对于有人胜利的情况,来判断局面是否合法,方法就是尝试删掉每一个棋子,看会不会让整个棋局上没有人胜利了,如果有这样的棋子,那么就代表是合法的,否则就不合法。

总结起来我们一共过了7个题,在7个题里好像也不算速度很快的,要不排名还能再上升一些的。感觉这次比较还是比较能反映出我们队的水平吧。
在比赛里也学到了好多东西,嗯…亮哥说比完赛要去实习了,祝亮哥实习愉快喽~

c++11 完美转发+变长参数

完美转发(argument forwarding):

给定一个函数F(a1, a2, ..., an),要写一个函数G,接受和F相同的参数并传递给F。
这里有三点要求:
1. 能用F的地方,G也一定能用。
2. 不能用F的敌方,G也一定不能用。
3. 转发的开销应该是线性增长的。

这里在C++11出现之前,人们做了很多尝试。就出现了很多的替代方案,直到C++11出现之后,才有了一个完美的解决方案。

非常量左值引用转发

template<typename T>
void g(T1& t) {
    return f(t);
}

void f(int t) {}

这里不能传入非常量右值g(1))。

常量左值引用

template<typename T>
void g(const T1& t) {
    return f(t);
}

void f(int& t) {}

常量左值引用在这里也挂掉了,这里函数g是没法把常量左值引用传递给非常量左值引用的。

非常量左值引用+常量左值引用

这种方案就是给每个参数写常量左值和非常量左值两个版本的,这个方案的重载函数个数是指数型增长的,在参数多的时候会挂掉的。而且,在传入非常量参数的时候,可能会引发二义性。

常量左值引用+const_cast

template<class T>
void g(const T& t) {
    return f(const_cast<T&>(t));
}

这里看起来好像解决了方案2里的问题。可是这种转发变量被修改了,不是我们想要的结果。

非常量左值引用+修改的参数推导规则

template<typename T>
void f(T& t){
    std::cout << 1 << std::endl;
}

void f(const long &){
    std::cout << 2 << std::endl;
}

int main(){
    f(5);// prints 2 under the current rules, 1 after the change
    int const n(5);
    f(n);// 1 in both cases
}

这里会对原有代码有破坏。

右值引用

template<typename T>
void g(T&& t) {
    return f(t);
}

这里不能g不能接受一个左值,因为不能把一个左值传递给一个右值引用。

右值引用+修改的参数推导规则转发

引用叠加原则:

TR的类型定义声明v的类型v的实际类型
T&TRA&
T&TR&A&
T&TR&&A&
T&&TRA&&
T&&TR&A&
T&&TR&&A&&

这里如果只去修改对右值引用推导规则,这样就避免对原有的代码的破坏。

template<typename T>
void g(T&& t) {
    return f(std::forward<T>(t));
}

这里已经可以处理好转发部分了。可是我还是不满意,我希望可以更完美一点,就是无论什么参数,多少参数都可以。这里要结合C++11的变长参数模板来完成。

template<typename... Args>
void g(Args... arg) {
    return f(std::forward(arg)...);
}

这里包括了变长参数包的展开,这里还可以用sizeof...(Args)来获取变长参数的个数。


参考:

1.c++ - How would one call std::forward on all arguments in a variadic function? - Stack Overflow
2. c++11 - Perfect forwarding - what's it all about? - Stack Overflow
3. c++ - Variadic template templates and perfect forwarding - Stack Overflow
4. The Forwarding Problem: Arguments
5. C++11维基百科

cJSON代码阅读(parse)部分

static const char *skip(const char *in) {while (in && *in && (unsigned char)*in<=32) in++; return in;}

跳过空白字符。空白字符即ASCII小于等于32的字符。(我还特意查了ascii的表…)。这里我可能会用isspace(掩面逃…)

static const char *parse_value(cJSON *item,const char *value)
{
    if (!value)                     return 0;
    if (!strncmp(value,"null",4))   { item->type=cJSON_NULL;  return value+4; }
    if (!strncmp(value,"false",5))  { item->type=cJSON_False; return value+5; }
    if (!strncmp(value,"true",4))   { item->type=cJSON_True; item->valueint=1;  return value+4; }
    if (*value=='\"')               { return parse_string(item,value); }
    if (*value=='-' || (*value>='0' && *value<='9'))    { return parse_number(item,value); }
    if (*value=='[')                { return parse_array(item,value); }
    if (*value=='{')                { return parse_object(item,value); }

    ep=value;return 0;
}

这里是parser的核心。判断该读入的元素类型。null,true,false这三个简单类型可以直接处理。其他的分别交给parsenumber,parsearray和parse_object处理。ep是这里用于错误处理的指针,当出错的时候,ep指针里保存的就是当前出现错误的位置。

首先是parse_string部分:

static const unsigned char firstByteMark[7] = { 0x00, 0x00, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC };
static const char *parse_string(cJSON *item,const char *str)
{
    const char *ptr=str+1;char *ptr2;char *out;int len=0;unsigned uc,uc2;
    if (*str!='\"') {ep=str;return 0;}

    while (*ptr!='\"' && *ptr && ++len) if (*ptr++ == '\\') ptr++;

    out=(char*)cJSON_malloc(len+1);
    if (!out) return 0;

    ptr=str+1;ptr2=out;
    while (*ptr!='\"' && *ptr)
    {
        if (*ptr!='\\') *ptr2++=*ptr++;
        else
        {
            ptr++;
            switch (*ptr)
            {
                case 'b': *ptr2++='\b'; break;
                case 'f': *ptr2++='\f'; break;
                case 'n': *ptr2++='\n'; break;
                case 'r': *ptr2++='\r'; break;
                case 't': *ptr2++='\t'; break;
                case 'u':
                    uc=parse_hex4(ptr+1);ptr+=4;

                    if ((uc>=0xDC00 && uc<=0xDFFF) || uc==0)    break;

                    if (uc>=0xD800 && uc<=0xDBFF)
                    {
                        if (ptr[1]!='\\' || ptr[2]!='u')    break;
                        uc2=parse_hex4(ptr+3);ptr+=6;
                        if (uc2<0xDC00 || uc2>0xDFFF)       break;
                        uc=0x10000 + (((uc&0x3FF)<<10) | (uc2&0x3FF));
                    }

                    len=4;if (uc<0x80) len=1;else if (uc<0x800) len=2;else if (uc<0x10000) len=3; ptr2+=len;

                    switch (len) {
                        case 4: *--ptr2 =((uc | 0x80) & 0xBF); uc >>= 6;
                        case 3: *--ptr2 =((uc | 0x80) & 0xBF); uc >>= 6;
                        case 2: *--ptr2 =((uc | 0x80) & 0xBF); uc >>= 6;
                        case 1: *--ptr2 =(uc | firstByteMark[len]);
                    }
                    ptr2+=len;
                    break;
                default:  *ptr2++=*ptr; break;
            }
            ptr++;
        }
    }
    *ptr2=0;
    if (*ptr=='\"') ptr++;
    item->valuestring=out;
    item->type=cJSON_String;
    return ptr;
}

首先是遍历了一次整个string,统计出一共的字符个数,存在了len里,中间遇到转义的部分跳过了后面的字符。个数统计好之后,申请内存。这里的cJSON_malloc就是原本的malloc。在这个函数的定义出可以找到:

static void *(*cJSON_malloc)(size_t sz) = malloc;

重新从头遍历整个string,不转义的部分是不用处理的。需要特殊处理的就是转义的部分,其实这部分也只有utf-16到utf-8的编码转换问题。(这里的magic number实在是太多了,我还没不知道utf-16和utf-8的编码方式。实在是看不懂了。)

static const char *parse_number(cJSON *item,const char *num)
{
    double n=0,sign=1,scale=0;int subscale=0,signsubscale=1;

    if (*num=='-') sign=-1,num++;
    if (*num=='0') num++;
    if (*num>='1' && *num<='9') do  n=(n*10.0)+(*num++ -'0');   while (*num>='0' && *num<='9');
    if (*num=='.' && num[1]>='0' && num[1]<='9') {num++;        do  n=(n*10.0)+(*num++ -'0'),scale--; while (*num>='0' && *num<='9');}
    if (*num=='e' || *num=='E')
    {   num++;if (*num=='+') num++; else if (*num=='-') signsubscale=-1,num++;
        while (*num>='0' && *num<='9') subscale=(subscale*10)+(*num++ - '0');
    }

    n=sign*n*pow(10.0,(scale+subscale*signsubscale));

    item->valuedouble=n;
    item->valueint=(int)n;
    item->type=cJSON_Number;
    return num;
}

这里数字的处理就简单很多了。 sign表示有没有负号,如果有的话sign是-1,否则sign为1。
去掉前导0之后,读入每位存在n里。 发现有".",并且下一位是数字的话,就说明这是一个小数,开始读入小数点之后的部分。这里用scale来表示当前的数的小数点应该向左移动几位。(这样是不是也同样保证了精度呢?) 读入E,科学计数法表示。处理方式和前面一样。 最后计算出n就可以了。这里把浮点数和整数放在一起处理了。只要在最后valueint只取n的整数部分就可以了。(我自己尝试实现的时候,把整数和小数分开读的,在存类型的时候也尝试把他们分开了。)这种方式需要在输出的时候做一个特殊处理,判断一下valuedouble和valueint之间的差,如果小于给定的eps那就认为这个数字是一个整数,否则认为是小数。

static const char *parse_array(cJSON *item,const char *value)
{
    cJSON *child;
    if (*value!='[')    {ep=value;return 0;}

    item->type=cJSON_Array;
    value=skip(value+1);
    if (*value==']') return value+1;

    item->child=child=cJSON_New_Item();
    if (!item->child) return 0;
    value=skip(parse_value(child,skip(value)));
    if (!value) return 0;

    while (*value==',')
    {
        cJSON *new_item;
        if (!(new_item=cJSON_New_Item())) return 0;
        child->next=new_item;new_item->prev=child;child=new_item;
        value=skip(parse_value(child,skip(value+1)));
        if (!value) return 0;
    }

    if (*value==']') return value+1;
    ep=value;return 0;
}

接下来是关于数组的处理。和其他时候一样,先判断起始字符合法性。然后重复: 1. 新建cJSON对象
2. 读掉空白字符
3. 读入这个对象
4. 读掉空白字符
5. 判断这个字符是否是“,“。如果是,转到1,如果不是判断结尾字符合法性,退出。
数组里面的元素,是用了一个双向链表实现的。具体的定义在cJSON这个结构体的定义处给出了。

static const char *parse_object(cJSON *item,const char *value)
{
    cJSON *child;
    if (*value!='{')    {ep=value;return 0;}

    item->type=cJSON_Object;
    value=skip(value+1);
    if (*value=='}') return value+1;

    item->child=child=cJSON_New_Item();
    if (!item->child) return 0;
    value=skip(parse_string(child,skip(value)));
    if (!value) return 0;
    child->string=child->valuestring;child->valuestring=0;
    if (*value!=':') {ep=value;return 0;}
    value=skip(parse_value(child,skip(value+1)));
    if (!value) return 0;

    while (*value==',')
    {
        cJSON *new_item;
        if (!(new_item=cJSON_New_Item()))   return 0;
        child->next=new_item;new_item->prev=child;child=new_item;
        value=skip(parse_string(child,skip(value+1)));
        if (!value) return 0;
        child->string=child->valuestring;child->valuestring=0;
        if (*value!=':') {ep=value;return 0;}
        value=skip(parse_value(child,skip(value+1)));
        if (!value) return 0;
    }

    if (*value=='}') return value+1;
    ep=value;return 0;
}

最后有关于parse的就是关于object对象的parse了。常规的判断其实字符,读掉空白字符。这里先判断了一次结束字符来看是不是空的。 因为一旦有了元素之后,在判断下一个元素是否存在的时候,判断的条件就变成了“,”。这部分在数组中有一样的处理。 这里整体的过程其实和数组的区别只在读入单个元素的方法上: 先读入一个string,读冒号“:”,读value。然后每个child的属性里的string部分保存了这个value的名字。(这里这个保存方式,是不是在get的时候的效率会出现问题呢。感觉这里如果多处理一点,对string串做一个hash可能效果会好一点。)

这样parse细节的部分就都看完了。cJSONParse函数是对cJSONParseWithOpts的一个封装。cJSON_ParseWithOpts函数处理了读入一个value之外的就是判断了是否需要null作为结束,和返回值存到哪里的问题。代码也很简单:

cJSON *cJSON_ParseWithOpts(const char *value,const char **return_parse_end,int require_null_terminated)
{
    const char *end=0;
    cJSON *c=cJSON_New_Item();
    ep=0;
    if (!c) return 0;

    end=parse_value(c,skip(value));
    if (!end)   {cJSON_Delete(c);return 0;}

    if (require_null_terminated) {end=skip(end);if (*end) {cJSON_Delete(c);ep=end;return 0;}}
    if (return_parse_end) *return_parse_end=end;
    return c;
}

编译时期计算数组

#include <iostream>
#include <array>
using namespace std;

constexpr int N = 1000000; constexpr int f(int x) { return x*2; }

typedef array<int, N> A;

template<int... i> constexpr A fs() { return A{{ f(i)... }}; }

template<int...> struct S;

template<int... i> struct S<0,i...> { static constexpr A gs() { return fs<0,i...>(); } };

template<int i, int... j> struct S<i,j...> { static constexpr A gs() { return S<i-1,i,j...>::gs(); } };

constexpr auto X = S<N-1>::gs();

int main() { cout << X[3] << endl; }

在编译时期计算一个数组里面的元素,这种方法在\(N\)较大的时候会出现constexpr递归深度较大的问题。这种线性的求法似乎不能很好的处理当\(N\)较大的情况。所以这时候可以通过二分所求的\(N\)来解决这个问题。这样最大的递归深度就从\(N\)变成了\(logN\)了。 排名第一的回答中代码是这样写的:

template<class T> using Invoke = typename T::type;

template<unsigned...> struct seq{ using type = seq; };

template<class S1, class S2> struct concat;

template<unsigned... I1, unsigned... I2>
struct concat<seq<I1...>, seq<I2...>>
  : seq<I1..., (sizeof...(I1)+I2)...>{};

template<class S1, class S2>
using Concat = Invoke<concat<S1, S2>>;

template<unsigned N> struct gen_seq;
template<unsigned N> using GenSeq = Invoke<gen_seq<N>>;

template<unsigned N>
struct gen_seq : Concat<GenSeq<N/2>, GenSeq<N - N/2>>{};

template<> struct gen_seq<0> : seq<>{};
template<> struct gen_seq<1> : seq<0>{};

// example

template<unsigned... Is>
void f(seq<Is...>);

int main(){
  f(gen_seq<6>());
}

原文: http://stackoverflow.com/questions/13072359/c11-compile-time-array-with-logarithmic-evaluation-depth

Link Cut Tree

动态树(Dynamic Tree Problems)是一类要动态维护森林连通性问题的总称。一般要维护森林中某个点到根结点的某些数据,应该支持一棵树切割成两棵树,或者两棵树合并成一棵树的操作。而解决这一类问题的基础数据结构就是LCT。

整体维护的过程有点类似于树链剖分的维护过程,不过树链剖分里维护的重链由于是静态的,可以用线段树去维护。对于动态的,我们可以用splay来维护。

Structure

我们用操作access(x)来表示访问节点x。那么定义:

  • Preferred Child:对于一个节点P,如果最后被访问的节点x在以其子节点Q为根的子树中,那么就称Q为P的Preferred Child
  • Preferred Edge:每个点到自己的Preferred Child之间的边,叫做Preferred Edge
  • Preferred Path:由Preferred Edge组成的一条不可延伸的路径,叫做Preferred Path

这样我们发现,每个点仅会属于一个preferred path。这样,一棵树就可以由几个preferred path来表示。对于每个preferred path,我们都维护一个splay,维护和的key值,就是每个点在preferred path中的深度。我们把这个splay称作:Auxiliary Tree(辅助树?这名字好难听……)。每个辅助树的根节点都保存着和上一个辅助树的哪一个点是相连的,这个指向被称作:path-parent pointer。

Operations

access

当我们访问了节点v之后,它将没有preferred child,并且应该是一条preferred path的最后一个节点(at the end of the path)。在我们的辅助树中节点都是按照深度排序的,也就是说,这时候所有在点v右侧的点都是应该被断开的。这个操作在splay上是很容易的。我们只要对v做一次splay操作,把它转到根节点上,然后断开它的右子树,然后右子树的根的path-parent pointer指向v就可以了。
然后我们继续向上遍历直到这条path的根,调整需要调整的部分。我们只要跟着path-parent pointer走就可以了,因为v节点现在是根了。这一定是有序的。如果我们发现当前点不是根的话,我们会顺着path-parent pointer走到另一条path上的一个点w上。接下来,我们对w进行一次splay,然后断掉它的右子树,维护这个右子树的path-parent pointer。然后把v放在w右子树的位置上。(这里相当于把两个splay合并起来了。可以合并的原因是因为所有在v所在的辅助树里的点的深度都应该比w大。因为一直的有序可以保证这一点。)对v再做一次splay。重复这个过程,直到我们走到了根上。

PS:这里都用child[x][0]来表示x的左子树,child[x][1]来表示x的右子树。

int access(int x) {
    int y = 0;
    do {
        splay(x);
        root[child[x][1]] = true;
        root[child[x][1] = y] = false;
        pushUp(x);
        x = father[y = x];
    } while(x);
    return y;
}

FindRoot

FindRoot操作用来寻找点v在所在树的根节点。这个操作很简单,我们只要对v做一次access操作,这样v和它的根就应该在一个splay中了。那么此时的根就应该是这个splay最左边的节点。

Cut

断掉v和其父亲节点之间的边。首先access节点v。然后讲v旋转到所在辅助树的根节点上。断掉左子树。维护好path-parent pointer就可以了。

void cut(int v) {
    access(v);
    splay(v);
    father[child[v][0]] = 0;
    root[child[v][0]] = true;
    child[v][0] = 0;
}

PS:如果要断掉两个点之间的边呢?会比这个麻烦一点。

void cut(int u, int v) {
    access(u);
    splay(u);
    reserse(u);
    access(v);
    splay(v);
    father[child[v][0]] = father[v];
    father[v] = 0;
    root[child[v][0]] = true;
    child[v][0] = 0;
}

Link

如果v是一个树的根,而w是另一个树里的点的话。只要让w成为v的父亲。我们可以同时对wv都做一次access操作。让w成为v的左子树。

void link(int u, int v) {
    access(u);
    splay(u);
    reverse(child[u][0]);
    access(v);
    splay(v);
    child[v][1] = u;
    father[u] = v;
    root[u] = false;
}

这是一个例题。(我才不会说我是看到这道题才来学的LCT呢…)
传送门:NOI2014 魔法森林

Python Tips

switch...case的写法

可以用if...elif...else的办法,或者使用跳转表:

{
    0: "zero",
    1: "one",
    2: "two"
}.get(x, "error")

有关于常量

显然命名风格这种办法并不能根本上阻止常量被改变。那么就可以定义一个类,修改这个类的__setattr__方法,当检查到key已经存在的时候直接抛出一个异常就可以了。

使用with自动关闭资源

with语句可以在代码块执行完毕后还原进入该代码块时的现场。包含有with语句的代码块的执行过程:
1. 计算表达式的值,返回一个上下文管理器对象。
2. 加载上下文管理器对象的__exit__()方法以备后用。
3. 调用上下文管理器对象的__enter__()方法。
4. 如果with语句中设置了目标对象,则将__enter__()方法的返回值赋值给目标对象。
5. 执行with中的代码块。
6. 如果步骤5中的代码正常结束,调用上下文管理器对象的__exit__()方法,其返回值直接忽略。
7. 如果步骤5中的代码执行过程中发生异常,调用上下文管理器对象的__exit__()方法,并将异常类型、值以及trackback信息作为参数传递给__exit__()方法。如果__exit__()返回值为false,则异常会被重新抛出;如果其返回值为true,异常被挂起,程序继续执行。

避免finally中可能发生的陷阱

小心由于finally中的return和break,导致被临时保存的应该向上层抛出的异常的屏蔽。
finally会在其他部分的return之前被执行,也就是说其他部分中return的值会被保存起来,先去执行finally中的代码。如果finally中有return的话,会导致很奇怪严重的错误。

判断对象是否为空

Python中以下数据会当作空来处理:

  • 常量None。
  • 常量False。
  • 任何形式的数值类型零,如:0、0L,0.0,0j。
  • 空的序列,如:""、()、[]。
  • 空的字典,如:{}。
  • 当用户定义的类中定义了nonzero()方法和len()方法,并且该方法返回整数0或者布尔值False的时候。

Python会首先调用__nonzero__()方法来判断返回值为True或False。如果没定义这个方法,则会调用__len__()方法判断返回值是否为0。如果都没有,那么该类的实例在用布尔测试的时候都为真。

连接字符串应优先使用join而不是+

这里join比+的效率要高上很多。这里是由于join会先遍历整个list中的所有字符串,把他们的长度加起来,只进行一次内存申请,这里所有的字符串只会被拷贝一次;而运算符+则是每进行一个运算都要申请一次内存,并且进行一次内存拷贝,这样n个字符串连接就要进行n-1次内存申请。

sort()和sorted()

sorted(iterable[, cmp[, key[, reserse]]])
a.sort([cmp[, key[, reserse]]])
  • sort会直接修改原有列表,sorted会返回一个排序后的对象。
  • 传入key比传入cmp的效率高,大约快50%。

使用traceback获取栈信息

traceback.print_exc()

使用模块实现单例模式

在python中,模块是可以保证只初始化一次,线程安全,模块内变量绑定在模块中。完美的符合了单例模式的要求。

利用mixin特性让程序更灵活

利用了Python的mixin特性。在运行时可以改变一个实例的基类。

#demo
import mixins
def staff():
    people = People()
    bases = [getattr(minxins, i) for i in config.checked()]
    people.__bases__ += tuple(bases)
    return people
				<div style="clear:both;">
				</div>