编程珠玑

位图排序

• 输入：一个包含n个正整数的文件，其中每个正整数都小于n，在这里n = 10^7，其中n个整数都是不可重复的。
• 输出：以升序排列的整数列表
• 约束：最多1MB内存，无限内存，时间最多几分钟，10s就可认为不需要优化了。

思考：一个整数占用4字节，10^7的整数占用的内存是4*10^7.一次性读取到内存中显然是不可能的。所以我们可以使用10^7/2^20 = 39趟归并排序，也就需要40次的IO操作，IO无疑是瓶颈。

我们可以使用10位长的字符串表示一个所有元素小于10的非负整数集合（集合3大特性），如：{1,2,3,5,8}可表示为：

0111010010 # 如果对应的位是1表示处于该集合

以上的方法非常巧妙，本来需要4个字节表示的数，仅仅通过一个位就实现了，空间瞬间剩下的几十倍，有不有？

这样就可以使用10^7个位表示10^7个整数，占用空间为10^7/2^20 = 9.53M。python实现如下：

#!/usr/bin python
#coding:utf-8
# 生成10^7个乱序整数

import random

RANGE = 10000000
arr = [i for i in range(RANGE)]
random.shuffle(arr)

f = open('../test/input/bitSort.input','w')

for i in arr:
	f.write(str(i) + '\n')
f.close()

print 'generator input file success!'

#!/use/bin python
#coding:utf-8
# 位排序

import time

start = time.time()

#1.init set to empty
RANGE = 10000000
arr = [0 for i in range(RANGE)]

#2.insert each present elements into the set
for line in open('../test/input/bitSort.input'):
	num = int(line)
	arr[num] = 1

#3.write sorted ouput
f = open('../test/output/bitSort.output','w')
for i in range(RANGE):
	if arr[i] == 1:
		f.write(str(i) + '\n')	
f.close()

end = time.time()

print 'arrar is sorted and generator output file success! and take time:' + str(end - start) 

位图数据结构：描述了一个有限定义域内的稠密集合，其中每个元素最多出现1次并且没有和其他任何数据与该元素关联。

随机算法

可以跳出局部最优解找到整体最优解
更快的运行速度
机器学习领域中许多算法都要用到随机的思想：随机森林，蒙特卡洛树

数据规模的概念

在1秒内解决问题

N^2 处理10^4
N 处理10^8
NlogN 处理10^7

许多主流语言使用抛出异常的方式处理错误的，但是可能传统的返回值可能更好。抛出异常的主要好处是可以将业务代码和错误处理代码分开，但是无形中改变了控制流。

office软件如此臃肿的原因是它的文件格式本身就是一个文件系统，二进制表示。相比标准的html文档少了lexing（词法分析）和parser（解析）的过程，速度提高了几个数量级。

a=i*5在C++中可能不是表示乘法的意思，因为可能运算符重载。等号和乘号都可能重载。

软件的原则：一个对象具有setter就一定需要提供getter。

标记清除垃圾回收算法基于有向图的多点可达性，能到达的对象被标记，从而回收不带标记的对象。对有向无环图进行dfs可以实现拓扑排序。而检测一个有向图中是否有环也可以用dfs。

java泛型擦除：早期的java没有泛型，所有的泛型将在运行时擦除。也就是说运行时List和List没有区别。C++中通过模板替换的方法实现泛型，java的泛型为了兼容老的系统，在运行时会将泛型擦除。也就是说在运行的时候：List,List,List没有区别。List不是List