Classe des elements dans des intervalles. (binning)

peigne.py

class IPeigne:
    """
    IPeigne(dents).

    Classe des elements dans des intervalles. (binning)
    """

    def count(self, elems):
        """Bin elems into buckets."""


class CachedPeigne(IPeigne):

    def __init__(self, dents):
        self.dents = dents
        self.cache = {}
        self.buckets = {d:0 for d in dents}

    def count(self, elems):
        s = sorted(elems)
        for e in s:
            if e not in self.cache:
                # print(f'> not-in-cache {e}')
                for d in self.dents:
                    print('.')
                    if e <= d:
                        print(f'>> caching {e} -> {d}')
                        self.cache[e] = d
                        self.buckets[d] += 1
                        break
            else:
                i = self.cache[e]
                print(f'> cached {e} <- {i}')
                self.buckets[i] += 1
            # print(self.buckets, ',', self.cache)
            print(self.buckets)
        return self.buckets


class Peigne(IPeigne):

    def __init__(self, dents):
        self.dents = dents
        self.buckets = {d:0 for d in dents}

    def count(self, elems):
        s = elems
        for e in s:
            for d in self.dents:
                print('.')
                if e <= d:
                    print(f'>> {e} -> {d}')
                    self.buckets[d] += 1
                    break
            print(self.buckets)
        return self.buckets

import timeit


def test(number=100, nelems=5000, nbins=20):
    bins = [i*10 for i in range(nbins)]
    print(f'{bins=}')
    for span in range(10,0,-1):
        elems = [bins[-1]] * int(nelems/span)
        print(f'{len(elems)=}')
        a = timeit.timeit(lambda: Peigne(bins).count(elems), number=number)
        b = timeit.timeit(lambda: CachedPeigne(bins).count(elems), number=number)
        print('peigne',a,'cached',b,'ratio',a/b)