100 lines
3.0 KiB
Python
100 lines
3.0 KiB
Python
#!/usr/bin/env python3
|
|
|
|
|
|
class Stats:
|
|
def __init__(self, data):
|
|
"""
|
|
Here we create a _table_ (dictionary), with the
|
|
frequency for the numbers contained in data,
|
|
which should take a linear amount of time in the
|
|
input length, then we execute a loop of constant
|
|
amount of iteration, which adds 1002 steps.
|
|
But it's constant.
|
|
So overall the __init__ method, should take
|
|
a linear amount of time, in the data length.
|
|
"""
|
|
_data = {}
|
|
# loop is linear in the data.
|
|
for v in data:
|
|
# Dictionary access should be constant time.
|
|
_data[v] = _data.get(v, 0) + 1
|
|
|
|
_list, prev = [], 0
|
|
# Adding a constant 1001 steps.
|
|
for i in range(0, 1002):
|
|
# Constant time step
|
|
new = _data.get(i, 0) + prev
|
|
# constant time step
|
|
_list.append(new)
|
|
prev = new
|
|
self._list = _list
|
|
|
|
def less(self, value):
|
|
"""
|
|
This method executes in constant time, because
|
|
it's a list access by element.
|
|
"""
|
|
return self._list[value - 1]
|
|
|
|
def between(self, m, M):
|
|
"""
|
|
This method executes in constant time, because
|
|
it's consuming two times a constant method,
|
|
plus an arithmetic operation.
|
|
"""
|
|
return self.less(M + 1) - self.less(m)
|
|
|
|
def greater(self, value):
|
|
"""
|
|
This method executes in constant time, because
|
|
it's consuming two times a constant method,
|
|
plus an arithmetic operation.
|
|
"""
|
|
return self.less(1001) - self.less(value + 1)
|
|
|
|
|
|
class DataCapture:
|
|
def __init__(self, *args, **kwargs):
|
|
self._values = []
|
|
|
|
def add(self, *values):
|
|
"""
|
|
This method is actually cheating, but the explanation is
|
|
the extend method on a list, will the same amount
|
|
of time as the count of objects you are adding.
|
|
If you intend to consume this method to add
|
|
a single element then it's a constant time, but is
|
|
you are adding a _list_ of methods (by using the positional
|
|
arguments), it will take a linear time in the arguments.
|
|
"""
|
|
self._values.extend(values)
|
|
|
|
def build_stats(self):
|
|
"""
|
|
Here we delegate everything to the Stats
|
|
init, the init for the Stats object,
|
|
will receive a _sorted list_,
|
|
which I think it's a good assumption to start
|
|
with.
|
|
"""
|
|
# The sorted where turns this in to O(n*log(n))
|
|
return Stats(self._values)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
# Example code execution
|
|
capture = DataCapture()
|
|
capture.add(3)
|
|
capture.add(9)
|
|
capture.add(3)
|
|
capture.add(4)
|
|
capture.add(6)
|
|
stats = capture.build_stats()
|
|
|
|
val = stats.less(4)
|
|
print("Less 4: (2) \t", val, val == 2)
|
|
val = stats.between(3, 6)
|
|
print("Between 3, 6: (4)\t", val, val == 4)
|
|
val = stats.greater(4)
|
|
print("Greater 4: (2) \t", val, val == 2)
|