import random


def sample(records, k):
    """
    Choose a length-``k`` subset of ``records`` using reservoir sampling.  if k < len(records),
    all are returned.
    """
    result = []
    for i, record in enumerate(records):
        if len(result) < k:
            result.append(record)
        else:
            r = random.randint(0, i)
            if r < k:
                result[r] = record
    return result