bandsample function drops last sample with "non-binary" stepsize

[kuchenrolle]

What you were trying to do

Create a bandsample from a population of a target size.

What actually happened

If the step (sum_of_frequencies / sample_size) is not representable in binary without rounding error, the last item is not added to the sample, because the comparison of accumulator and step fails. Potentially this might also happen at other points, but that may not be an issue, not sure.

I can get around that if I replace the "accumulator >= step" comparisons with "round(accumulator, 3) >= round(step, 3)", but that seems fishy, presumably there is a better way.

How to reproduce

from pyndl.preprocess import bandsample
population = {'a': 4, 'b': 4, 'c': 2, 'd': 2, 'e': 1, 'f': 1}

bandsample(population, 3, cutoff=1)  # step: 4.666666666666667, one item missing
# Counter({'c': 2, 'a': 4})
bandsample(population, 4, cutoff=1)  # step: 3.5, all items included
# Counter({'d': 2, 'b': 4, 'a': 4, 'c': 2})

System details

Pyndl Information

General Information

Python version: 3.7.2
Pyndl version: 0.6.1

Operating System

OS: Linux x86_64
Kernel: 4.15.0-20-generic
CPU: 12
Mem: 2382MiB/10608MiB
Swap: 0MiB/2047MiB

Dependencies

pandas: 0.24.1
xarray: 0.11.3
pip: 19.0.1
numpy: 1.15.4
cython: 0.29.5
netCDF4: 1.4.2

[Trybnetic]

Thanks for reporting this bug! This should definitely not happen! We are on it and hope to resolve it soon!

[kuchenrolle]

I'm using this function now:

import random
from cmath import isclose

def bandsample(population,
               sample_size=50_000, cutoff=5, seed=2311, verbose=False):
    """
    Creates a sample of size sample_size out of the population using
    band sampling.
    Modified from pyndl package.
    """

    # make a copy of the population
    # filter all words with freq < cutoff
    population = [(word, freq) for word, freq in population.items()
                  if freq >= cutoff]

    # shuffle words with same frequency
    random.Random(seed).shuffle(population)
    population.sort(key=lambda x: x[1])  # lowest -> highest freq

    step = sum(freq for word, freq in population) / sample_size
    if verbose:
        sys.stdout.write(f"step {step:.3}\n")

    sample_indices = set()
    accumulator = 0.0

    for idx, (word, freq) in enumerate(population):
        accumulator += freq
        if verbose:
            sys.stdout.write(f"{word}\t{freq}\t{accumulator:.3}\n")

        if accumulator >= step or isclose(accumulator, step):
            sample_indices.add(idx)
            accumulator -= step
            if verbose:
                sys.stdout.write(f"add\t{word}\t{accumulator:.3}\n")

            while accumulator >= step or isclose(accumulator, step):
                idx = idx - 1
                if idx not in sample_indices:
                    sample_indices.add(idx)
                    accumulator -= step
                    if verbose:
                        word, freq = population[idx]
                        sys.stdout.write(f"  add\t{word}\t{accumulator:.3}\n")

    sample = Counter(dict(population[i] for i in sample_indices))
    return sample

[derNarr]

1. Can you create a pull request with this version?
2. Why are you using sys.stdout.write instead of print?
3. Have you tested if the seeding works reliably?

Thanks!

[derNarr]

Two things we could add along fixing this:

1. Giving reasonable ValueError if sample_size is larger than population size (the old code simply runs and gives the whole population; the new code raises an IdexError.
2. Adds functionality to pre-select samples from the population (requested by @striatum )

[kuchenrolle]

1. Maybe I'll get around to do this (and incorporate the additions) next week. How exactly is the pre-selection supposed to work?
2. I'm just used to using stdout and stderr (where that ValueError would go), but I guess otherwise the difference to print has largely evaporated in python 3.
3. The random.Random instance is generated and seeded anew with every call to the function and nothing else will consume it (unlike the regular random methods, that all share state), so I'm not sure how this would not be reliable if the version is held constant. But if you know how to test that, that would be good.