記憶體上限下的演算法

10 MB  = 10 * 2^20 bytes * 8  ~= 83.9 million bits    -> 83.9M distinct flags
       = 10 * 2^20 / 4        ~= 2.6 million ints     -> 2.6M counters
1 GB   = 2^30 bytes * 8        = 8.6 billion bits     -> a bit per 32-bit value, twice over

# python
# GENERAL PATTERN: bit vector (bitset) over values 0 .. size-1
# IDEA: byte i of the array holds the flags for values 8i .. 8i+7
# time = O(1) per op, space = size BITS (size/8 bytes)
class BitVector(object):
    def __init__(self, size):
        self.bits = bytearray((size + 7) // 8)   # 1 byte == 8 flags

    def get(self, pos):
        return (self.bits[pos >> 3] >> (pos & 7)) & 1

    def set(self, pos):
        self.bits[pos >> 3] |= 1 << (pos & 7)

// java
// GENERAL PATTERN: bit vector over values 0 .. size-1
// IDEA: word (pos >> 5) of an int[] holds the flags for 32 consecutive values
// time = O(1) per op, space = size BITS
class BitVector {
    private final int[] words;

    BitVector(int size) { words = new int[(size >> 5) + 1]; }   // /32, rounded up

    boolean get(int pos) { return (words[pos >> 5] & (1 << (pos & 31))) != 0; }

    void set(int pos)    { words[pos >> 5] |= 1 << (pos & 31); }
}

# python
# CtCI 10.8 - print duplicates in an array of values in [1, 32000], memory ~ 4 KB
# IDEA: the value IS the index — flip its bit; a bit already set means a repeat
# time = O(n), space = 32000 bits = 4 KB
def print_duplicates(nums):
    seen = BitVector(32000)
    for n in nums:
        if seen.get(n - 1):          # values start at 1, bits start at 0
            print(n)
        else:
            seen.set(n - 1)

# python
# CtCI 10.7 - find a missing non-negative int among ~4 billion, memory ~ 10 MB
# IDEA: pass 1 counts values per block of 2^20; a block holding < 2^20 values must miss one
#       pass 2 builds a bit vector for THAT BLOCK ONLY (2^20 bits = 128 KB)
# time = O(n) over 2 passes, space = 2048 counters (8 KB) + 128 KB
BLOCK = 1 << 20                              # 2^20 values per block

def find_missing(read_all, limit=1 << 31):   # read_all() -> a fresh iterator each call
    counts = [0] * -(-limit // BLOCK)        # 2048 counters; ceiling covers a part-block
    for v in read_all():                     # ---- pass 1
        counts[v // BLOCK] += 1

    def slots(i):                            # the last block may be shorter than BLOCK
        return min(BLOCK, limit - i * BLOCK)

    block = next((i for i, c in enumerate(counts) if c < slots(i)), -1)
    if block < 0:
        return -1                            # every block is full: nothing is missing

    lo, width = block * BLOCK, slots(block)
    seen = bytearray((width + 7) // 8)       # ---- pass 2, 128 KB for a full block
    for v in read_all():
        if lo <= v < lo + width:
            off = v - lo
            seen[off >> 3] |= 1 << (off & 7)

    for off in range(width):
        if not (seen[off >> 3] >> (off & 7)) & 1:
            return lo + off
    return -1                                # no gap: the input held every value

# python
# GENERAL PATTERN: shard a too-big file into buckets that each fit in RAM
# IDEA: h(key) % B decides the bucket -> identical keys can never split across buckets
# time = O(n) to shard + O(n) to process, space = O(largest bucket)
import hashlib

def bucket_of(key, n_buckets):
    # NOT the builtin hash(): Python salts str hashing per process, so a re-run
    # would send the same key to a different file
    digest = hashlib.md5(key.encode()).digest()
    return int.from_bytes(digest[:4], "big") % n_buckets

def count_words(lines, n_buckets, tmpdir):
    files = [open("%s/part-%d" % (tmpdir, i), "w") for i in range(n_buckets)]
    for line in lines:                                   # ---- pass 1: scatter
        for word in line.split():
            files[bucket_of(word, n_buckets)].write(word + "\n")
    for f in files:
        f.close()

    for i in range(n_buckets):                           # ---- pass 2: gather
        counts = {}                                      # one bucket fits in RAM
        with open("%s/part-%d" % (tmpdir, i)) as f:
            for word in f:
                word = word.rstrip("\n")
                counts[word] = counts.get(word, 0) + 1
        for word, c in counts.items():
            yield word, c

# python
# GENERAL PATTERN: external merge sort — sort more data than fits in memory
# IDEA: phase 1 turns the input into sorted runs; phase 2 k-way merges them, keeping
#       only k heads (one per run) in RAM
# time = O(n log n) compares; I/O = O(n) per pass, passes = 1 + log_k(#runs)
# NOTE: ONE merge pass, so it assumes len(runs) fits the fan-in the process can hold
#       open at once. More runs than that must be merged in rounds — see below.
import heapq
from contextlib import ExitStack

def external_sort(records, chunk_size, tmpdir):
    runs, chunk = [], []
    for rec in records:                                  # ---- phase 1: sorted runs
        chunk.append(rec)
        if len(chunk) == chunk_size:
            runs.append(_flush(chunk, tmpdir, len(runs)))
            chunk = []
    if chunk:
        runs.append(_flush(chunk, tmpdir, len(runs)))

    with ExitStack() as stack:                           # ---- phase 2: k-way merge
        files = [stack.enter_context(open(p)) for p in runs]   # closed on the way out,
        for line in heapq.merge(*files, key=int):              # even if the caller
            yield int(line)                                    # abandons the generator

def _flush(chunk, tmpdir, i):
    chunk.sort()
    path = "%s/run-%d" % (tmpdir, i)
    with open(path, "w") as f:
        f.writelines("%d\n" % x for x in chunk)
    return path