持续到2月，坚持至少一周2更, on algorithms…

Use case of a bitvec:
v = bitvec(capacity)
v.set(45322)
v.set(1000234)
…
if v.has(453222): print(‘ok it’s there’)

Data structure:
bytearray

Key concepts on storage:
- 1M bytes == 8M bits, meaning bitvec on 1MB memory will be able to handle 8M numbers, with the max number to be 8M – 1 (assuming we need to store 0 in the bitvec)
- 10M numbers requests 10/8M bytes – Assuming ‘M’ is always 2^20, not necessarily 1,000,000.

Key implementation problems:
In the case of v.set(num),
- What is the corresponding position (naming it as pos) for num in the underlying bytearray?
pos = num / 8 (or num >> 3)
- What is the corresponding mask index (naming it as r, remainder) in bytearray[pos]?
r = num % 8 (or num & 0×7)

The implementation of bit vector:

class prog_1_2_bitvec:
    """
    >>> v = prog_1_2_bitvec(6)
    >>> v.set(2)
    >>> v.set(5)
    >>> print('%x' % v.bytes[0]) # should be 100100
    24
    >>> v.has(2)
    True
    >>> v.has(5)
    True
    >>> v.unset(2)
    >>> v.has(2)
    False
    >>> v.unset(5)
    >>> v.has(5)
    False
    >>> v.set(3)
    >>> v.has(3)
    True
    """

    def __init__(self, max):
        if max <= 0: raise Exception('invalid max - length <= 0')
        self.bytes = bytearray(int(max / 8 + 1))
        self.max = max

    def set(self, num):
        self._valid(num)
        pos, mask = self._divide(num)
        self.bytes[pos] |= mask

    def has(self, num):
        self._valid(num)
        pos, mask = self._divide(num)
        return self.bytes[pos] & mask == mask

    def unset(self, num):
        self._valid(num)
        pos, mask = self._divide(num)
        self.bytes[pos] &= ~mask

    def count(self):
        # lie: TODO: best way to count the number of 1
        # will cover it later
        pass

    def _divide(self, num):
        d = num >> 3
        r = num & 0x7
        return (d, 1 << r)

    def _valid(self, num):
        if num < 0: raise Exception('invalid num - negative number')
        if num >= self.max: raise Exception('invalid num - num > %d' % self.max)

The implementation of multi-pass bitvec sort:

def prog_1_3_bitsort_multipass(l, max, k):
    """
    TODO: margin conditions...

    >>> max = 1 << 8
    >>> l = prog_1_4_gen_list(max, max >> 1)
    >>> print(l[0:20])  # doctest:+ELLIPSIS
    [...]
    >>> l = prog_1_3_bitsort_multipass(l, max, 2)
    >>> print(l[0:20])  # doctest:+ELLIPSIS
    [...]
    >>> test_verify_sorted(l)
    True
    """
    def sort_singlepass(l, max, i, k):
        # assumptions:
        # 1. let slice = max / k, the func is to handle numbers from range i * slice ~ (i + 1) * slice
        # 2. The mapping relationship is n => n - i * slice
        # exception cases (needs assertion):
        # 1. max / k has remainder
        slice = int(max / k)
        upper = (i + 1) * slice
        lower = i * slice
        v = prog_1_2_bitvec(slice)
        for n in l:
            if n < lower or n >= upper: continue
            mapped_n = n - lower
            v.set(mapped_n)
        sortedlist = [n + i * slice for n in range(slice) if v.has(n)]
        return sortedlist

    sortedlist = []
    for i in range(0, k):
        sortedlist += sort_singlepass(l, max, i, k)
    return sortedlist

Hints:
- Overall: define use case – UT, method signature, etc
- Write logic: write mainstraem logic with notes (in comments) or assertions for exception / corner cases.
- Organize mind: cases!!

Tests (TODO):
- Areas: UT – like UT for sort_singlepass, basic E2E (positive), negative like to pass numbers less than 0 or exceeding data volume, code coverage (previous test cases may have covered most), performance