Bitmap算法
我們可能在算法書中都看過觉壶，對于海量數(shù)據(jù)的處理是有一些獨特的算法的叉讥，通常來說如下六種：
序號 算法
1 分而治之/hash映射 + hash統(tǒng)計 + 堆/快速/歸并排序
2 雙層桶劃分
3 Bloom filter/Bitmap
4 Trie樹/數(shù)據(jù)庫/倒排索引
5 外排序
6 分布式處理之Hadoop/Mapreduce
這里我介紹的是Bitmap，BitMap就是用一個bit位來標記某個元素對應的Value泣懊， 而Key即是該元素吁津，該方法在快速查找、去重晌块、排序、壓縮數(shù)據(jù)上都有應用
假設我們要對0-7內的5個元素(4,7,2,5,3)排序帅霜，因為要表示8個數(shù)匆背，我們就只需要8個bit（1Bytes）。
元素 無 無 2 3 4 5 無 7
占位 × × √ √ √ √ × √
地址 0 1 2 3 4 5 6 7
這樣就排序完成了义屏，該方法難在數(shù)對二進制位的映射靠汁，因為類型到底多長是和平臺和環(huán)境有關的蜂大，我們假定int是32bit，之后假設我們現(xiàn)在有320個數(shù)據(jù)需要排序，則int a[1+10]勃教，a[0]可以表示從0-31的共32個數(shù)字捎迫，a[1]可以表示從32-61的共32個數(shù)字，我們可以想象這是一個二位數(shù)組澳叉，但是其實并不是
我們可以很容易得出隙咸，對于一個十進制數(shù)n沐悦，對應在數(shù)組a[n/32][n%32]中
# encoding: utf-8
from collections import namedtuple
from copy import copy
Colour = namedtuple('Colour','r,g,b')
Colour.copy = lambda self: copy(self)
black = Colour(0,0,0)
white = Colour(255,255,255) # Colour ranges are not enforced.
class Bitmap():
? ? def __init__(self, width = 40, height = 40, background=white):
? ? ? ? assert width > 0 and height > 0 and type(background) == Colour
? ? ? ? self.width = width
? ? ? ? self.height = height
? ? ? ? self.background = background
? ? ? ? self.map = [[background.copy() for w in range(width)] for h in range(height)]
? ? def fillrect(self, x, y, width, height, colour=black):
? ? ? ? assert x >= 0 and y >= 0 and width > 0 and height > 0 and type(colour) == Colour
? ? ? ? for h in range(height):
? ? ? ? ? ? for w in range(width):
? ? ? ? ? ? ? ? self.map[y+h][x+w] = colour.copy()
? ? def chardisplay(self):
? ? ? ? txt = [''.join(' ' if bit==self.background else '@'
? ? ? ? ? ? ? ? ? ? ? for bit in row)
? ? ? ? ? ? ? for row in self.map]
? ? ? ? # Boxing
? ? ? ? txt = ['|'+row+'|' for row in txt]
? ? ? ? txt.insert(0, '+' + '-' * self.width + '+')
? ? ? ? txt.append('+' + '-' * self.width + '+')
? ? ? ? print('\n'.join(reversed(txt)))
? ? def set(self, x, y, colour=black):
? ? ? ? assert type(colour) == Colour
? ? ? ? self.map[y][x]=colour
? ? def get(self, x, y):
? ? ? ? return self.map[y][x]
bitmap = Bitmap(20,10)
bitmap.fillrect(4, 5, 6, 3)
assert bitmap.get(5, 5) == black
assert bitmap.get(0, 1) == white
bitmap.set(0, 1, black)
assert bitmap.get(0, 1) == black
bitmap.chardisplay()
