Posts: 4,560
Threads: 1,464
Joined: Sep 2016
looking up numbers in a very sparse unordered collection is easy with a dictionary. but what about a sparse collection of ranges? this would be a set of numbers that are either present or absent where a range is a span of values than might number in excess of existing memory but the number of ranges boundaries do not. an example of this can be indexing a collection by floating point ranges. let's say you add the range 4.5 to 5.25 to such a collection. now is 4.500000000001 in the range? clearly you will not be putting trillions of individual numbers in the object. what if the range is a range of ints from 4500000000000000 to 6000000000000000?
so what i am looking for is an object class that can allow the insertion of ranges into each instance where the supported type for range indexing is anything that support < or > comparison. it needs to support overlapping replacement insertions, as well as deletions. each insert will also have a value to get back out if th requested index is inside that ramge.
Tradition is peer pressure from dead people
What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Posts: 544
Threads: 15
Joined: Oct 2016
Nov-29-2017, 01:45 PM
(This post was last modified: Nov-29-2017, 02:18 PM by Windspar.)
example
# width is how many floating point
# step must be an integer not a float
def float_range(width, start, end=None, step=1):
float_width = 10 ** width
if end is None:
end = start * float_width
start = 0.1 * float_width
else:
start = start * float_width
end = end * float_width
# return range(start, end, step)
while start < end:
yield start / float_width
start += step
if __name__ == '__main__':
for i in float_range(2, 4.5, 5.0):
print(i)
if i == 4.7: break
example class form
class FloatRange:
# width is how many floating point
# step must be in integer
def __init__(self, width, start, end=None, step=1):
self.width = 10 ** width
if end is None:
self.start = int(0.1 * self.width)
self.end = int(start * self.width)
else:
self.start = int(start * self.width)
self.end = int(end * self.width)
self.book = self.start, self.end, step
self.step = step
def __iter__(self):
while self.start < self.end:
yield self.start / self.width
self.start += self.step
def __lt__(self, value):
return value * self.width < self.book[0]
def __gt__(self, value):
return value * self.width > self.book[1]
# special check to see if variabel inside range
def __eq__(self, value):
return self.book[1] > int(value * self.width) >= self.book[0]
if __name__ == '__main__':
rangef = FloatRange(2, 4.5, 4.7)
print(rangef == 4.61)
for i in rangef:
print(i)
99 percent of computer problems exists between chair and keyboard.
Posts: 8,090
Threads: 154
Joined: Sep 2016
Nov-29-2017, 02:47 PM
(This post was last modified: Nov-29-2017, 03:59 PM by buran.)
@Windspar:
you should implement special method __contains__ to check membership, not __eq__
https://docs.python.org/3/reference/data...iner-types
Posts: 544
Threads: 15
Joined: Oct 2016
@ buran Thanks
small improvement
def __contains__(self, value):
return int(value * self.width) in range(*self.book)
99 percent of computer problems exists between chair and keyboard.
Posts: 544
Threads: 15
Joined: Oct 2016
Working with floats are annoying. So I change to Fraction.
from fractions import Fraction
def fract10(value, width):
return Fraction(value, 10 ** width)
class FloatRange:
def __init__(self, width, start, start_width, end=None, end_width=None, step=1):
self.width = Fraction(10 ** width, 1)
if end is None:
self.start_width(10 ** self.width, 1)
self.end_width = Fraction(10 ** start_width, 1)
self.end = Fraction(start, 10 ** start_width)
self.start = Fraction(1, self.width)
else:
self.start_width = Fraction(10 ** start_width, 1)
self.end_width = Fraction(10 ** end_width, 1)
self.start = Fraction(start, 10 ** start_width)
self.end = Fraction(end, 10 ** end_width)
self.step = Fraction(step, 10 ** width)
self.start_range = self.start, self.end, self.step
def __iter__(self):
while self.start < self.end:
yield float(self.start / self.width * self.start_width)
self.start += self.step
def __lt__(self, value, width):
return Fraction(value, 10 ** width) <= self.start_range[0]
def __gt__(self, value, width):
return Fraction(value, 10 ** width) > self.start_range[1]
def __contains__(self, value_tup):
value, width = value_tup
v = int(Fraction(value, 10 ** width) * self.width)
s = int(self.start_range[0] * self.start_width)
e = int(self.start_range[1] * self.end_width)
step = int(self.step * self.width)
return v in range(s, e, step) # or
#return e > v >= s
if __name__ == "__main__":
frange = FloatRange(3, 450, 2, 470 , 2)
print((452, 2) in frange)
print((452, 3) in frange)
#for i in frange:
# print(i)
99 percent of computer problems exists between chair and keyboard.
Posts: 4,560
Threads: 1,464
Joined: Sep 2016
in English, the plural form of range is ranges. i'm looking for a class that supports more than one range. an instance of such a class should start empty and have a default value (can be specified or be None if not specified). i then add range 2,3.5 to have a value of 'foo'. i then add range 4.5,6 to have a value of 'bar'. i then lookup 4.75 and get 'bar'. i then delete range 3,5. i repeat lookup 4.75 and now i get the default value. so delete is just a case of adding a range of the default value. this is a "flat" range container.
a "stack" range container would return a list of values based on the inserts being stacked over and the lookup seeing the stack. so in the above i would get [None, 'bar', None]. a special smash function would mash down everything in the range specified so that if range 3,5 is smashed (a true delete) then looking up 4.75 returns [None].
there would also be network address variants of those that can be optimized and support high speed route tables.
maybe these have already been done?
Tradition is peer pressure from dead people
What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Posts: 8,090
Threads: 154
Joined: Sep 2016
Then start coding whatever you want.
Posts: 544
Threads: 15
Joined: Oct 2016
Nov-30-2017, 05:56 PM
(This post was last modified: Nov-30-2017, 05:59 PM by Windspar.)
@ Skaperen Thank to you. I learn how to work with floats as Fraction. Learn how to convert them.
Example my float range
from fractions import Fraction
class FloatRange:
# width = how many float points
def __init__(self, width, start, end, step=1):
self.width_size = width
self.width = Fraction(10 ** width, 1)
if end is None:
self.end = self.num_to_fraction(start)
self.start = Fraction(1, 10 ** width)
else:
self.start = self.num_to_fraction(start)
self.end = self.num_to_fraction(end)
self.step = Fraction(step, 10 ** width)
self.float_range = self.start, self.end, self.step
def num_to_fraction(self, pynum):
if type(pynum) is float:
f = str(pynum)
i = f.find('.') + 1
return Fraction(int(f.replace('.', '')), 10 ** (len(f) - i))
return Fraction(pynum, 1)
def convert(self, value):
str_value = str(value)
index = str_value.find('.') + 1
width = len(str_value) - index
if width < self.width_size:
return int(str_value.replace('.','')) * (10 ** (self.width_size - width))
elif index == 0:
return int(str_value.replace('.','')) * (10 ** self.width_size)
return int(str_value.replace('.',''))
def __iter__(self):
while self.start < self.end:
yield float(self.start)
self.start += self.step
def __lt__(self, value):
return self.num_to_fraction(value) > self.float_range[1]
def __gt__(self, value):
return self.num_to_fraction(value) < self.float_range[0]
def __contains__(self, value):
v = self.convert(value)
s = int(self.float_range[0] * self.width)
e = int(self.float_range[1] * self.width)
st = int(self.float_range[2] * self.width)
return v in range(s, e, st) # or
#return s <= v < e
if __name__ == "__main__":
for i in range(1,4):
frange = FloatRange(i, 4.5, 4.7)
print("\n ** FloatRange contains float point", i, "**")
print(452 in frange)
print(45.2 in frange)
print(4.52 in frange)
print(4.521 in frange)
print("\n ** Less than and Greater than test **")
frange = FloatRange(2, 4.5, 4.7)
print(4.4 < frange)
print(4.6 < frange)
print(4.6 > frange)
print(4.8 > frange)
print("\n ** Output test **")
for i in frange:
print(i)Are you looking for something like this ?
from fractions import Fraction
class Ranges:
def __init__(self):
self.range_list =
def add(self, start, end):
for index, item in enumerate(self.range_list):
if item is None:
self.range_list[index] = (start, end)
return
self.range_list.append((start, end))
def num_to_fraction(self, pynum):
if type(pynum) is float:
f = str(pynum)
i = f.find('.') + 1
return Fraction(int(f.replace('.', '')), 10 ** (len(f) - i))
return Fraction(pynum, 1)
def fetch(self, value):
for index, group in enumerate(self.range_list):
if group is None:
continue
elif group[0] <= value < group[1]:
return index, group
return None, None
def run(self, index, width):
if self.range_list[index] is None:
return
step = Fraction(1, 10 ** width)
width = Fraction(10 ** width, 1)
start, end = map(self.num_to_fraction, self.range_list[index])
while start < end:
yield float(start)
start += step
def run_combine(self, index, width, combine):
for i in self.run(index, width):
yield combine + str(i)
def run_ip4(self, index, width, index2, width2):
for i in self.run(index, width):
for j in self.run(index2, width2):
yield str(i) + '.' + str(j)
def smash(self, index):
self.range_list[index] = None
def __str__(self):
line = "Ranges ["
for r in self.range_list:
if r is None:
line += "None, "
else:
line += "({0}, {1}), ".format(*r)
return line[:-2] + ']'
if __name__ == '__main__':
my_range = Ranges()
my_range.add(17.21, 17.27)
my_range.add(2, 3.5)
my_range.add(4.5, 6)
for i in my_range.run_combine(1, 1, "192.168."):
print(i)
print()
for i in my_range.run_ip4(0, 2, 2, 1):
print(i)
99 percent of computer problems exists between chair and keyboard.
Posts: 4,560
Threads: 1,464
Joined: Sep 2016
Dec-01-2017, 04:10 AM
(This post was last modified: Dec-01-2017, 04:17 AM by Skaperen.)
(Nov-30-2017, 04:52 AM)buran Wrote: Then start coding whatever you want.
this is one of those things i perceive as being too big/complex for me to do. so i will use what other people have made or i will have nothing to use.
@ Windspar
how does that handle overlapping ranges? can it handle ranges between strings like ('bar','foo')?
i would also want to compare two ranges objects to know if they represent the same set of ranges (with the same value for each range) regardless of how different overlappings produce these ranges.
and much like a dictionary can produce an iterable, i want to have that. while dict.items() would return an iterable of (key,value), ranges.items() would return an iterable of (from,to,value). either of these can be sorted.
and adding 2 ranges that are exactly adjacent with the same value should (as seen in .items()) become a combined range.
oh, instead of (from,to,value) it could be (range,value). there would be a range class that should be a simple class and then the ranges class that manges many.
then i will get more demanding and want 2D and 3D ranges. or maybe more elaborate shapes. imagine a class where i can merge a cube of 'purple' and a sphere of 'red' and a thing of green defined by a shape class object.
Tradition is peer pressure from dead people
What do you call someone who speaks three languages? Trilingual. Two languages? Bilingual. One language? American.
Posts: 544
Threads: 15
Joined: Oct 2016
Here a start.
float_range.py . Some small changes
from fractions import Fraction
class FloatRange:
# width = how many float points
def __init__(self, width, start, end, step=1):
self.base = width, start, end, step
self.width = Fraction(10 ** width, 1)
if end is None:
self.end = self.num_to_fraction(start)
self.start = Fraction(1, 10 ** width)
else:
self.start = self.num_to_fraction(start)
self.end = self.num_to_fraction(end)
self.step = Fraction(step, 10 ** width)
self.float_range = self.start, self.end, self.step
def num_to_fraction(self, pynum):
if type(pynum) is float:
f = str(pynum)
i = f.find('.') + 1
return Fraction(int(f.replace('.', '')), 10 ** (len(f) - i))
return Fraction(pynum, 1)
def convert(self, value):
str_value = str(value)
index = str_value.find('.') + 1
width = len(str_value) - index
if width < self.base[0]:
return int(str_value.replace('.','')) * (10 ** (self.base[0] - width))
elif index == 0:
return int(str_value.replace('.','')) * (10 ** self.base[0])
return int(str_value.replace('.',''))
def __iter__(self):
self.start = self.float_range[0]
while self.start < self.end:
yield float(self.start)
self.start += self.step
def __lt__(self, value):
return self.num_to_fraction(value) > self.float_range[1]
def __gt__(self, value):
return self.num_to_fraction(value) < self.float_range[0]
def with_in(self, value):
s, e, st = self.float_range
if type(value) is FloatRange:
s2, e2, st2 = value.float_range
if self.with_in(s2) or self.with_in(e2) or value.with_in(s) or value.with_in(e):
return True
return False
else:
v = self.num_to_fraction(value)
return s <= v < e
def __contains__(self, value):
v = self.convert(value)
s = int(self.float_range[0] * self.width)
e = int(self.float_range[1] * self.width)
st = int(self.float_range[2] * self.width)
return v in range(s, e, st)
def __repr__(self):
line = "FloatRange: {0}Width: {1}, Start: {2}, End: {3}, Step: {4}{5}"
return line.format('{', *self.base, '}')
if __name__ == "__main__":
for i in range(1,4):
frange = FloatRange(i, 4.5, 4.7)
print("\n ** FloatRange contains float point", i, "**")
print(452 in frange)
print(45.2 in frange)
print(4.52 in frange)
print(4.521 in frange)
print("\n ** Less than and Greater than test **")
frange = FloatRange(2, 4.5, 4.7)
print(4.4 < frange)
print(4.6 < frange)
print(4.6 > frange)
print(4.8 > frange)
print("\n ** Within test **")
a = FloatRange(1, 4.6, 5.0)
b = FloatRange(3, 4.6, 5.0)
c = FloatRange(2, 4.0, 5.0)
d = FloatRange(2, 4.9, 5.0)
print(a.with_in(frange))
print(b.with_in(frange))
print(c.with_in(frange))
print(d.with_in(frange))
print("\n ** Output test **")
for i in frange:
print(i)ranges.py
from float_range import FloatRange
class Ranges:
def __init__(self):
self.ranges = {}
def items(self):
return self.ranges.items()
def keys(self):
return self.ranges.keys()
def values(self):
return self.ranges.values()
def __getitem__(self, key):
return self.ranges[key]
def __delitem__(self, key):
del self.ranges[key]
def add(self, key_name, width, start, end=None, step=1):
if end is None:
self.ranges[key_name] = FloatRange(width, start)
else:
self.ranges[key_name] = FloatRange(width, start, end, step)
def fetch(self, value, value_end=None):
return_keys = []
if value_end is None:
for key, f_range in self.items():
if value in f_range:
return_keys.append(key)
else:
v_range = FloatRange(0, value, value_end)
for key, f_range in self.items():
if f_range.with_in(v_range):
return_keys.append(key)
return return_keys
def smash(self, start, end=None):
del_keys = []
if end is None:
for key, f_range in self.items():
if start in f_range: # or with_in
del_keys.append(key)
else:
v_range = FloatRange(0, start, end)
for key, f_range in self.items():
if v_range.with_in(f_range):
del_keys.append(key)
for key in del_keys:
del self.ranges[key]
def merge(self, key1, key2):
return FloatRange(
max(self.ranges[key1].base[0], self.ranges[key2].base[0]),
min(self.ranges[key1].base[1], self.ranges[key2].base[1]),
max(self.ranges[key1].base[2], self.ranges[key2].base[2]),
min(self.ranges[key1].base[3], self.ranges[key2].base[3]) )
if __name__ == '__main__':
m_range = Ranges()
m_range.add('foo', 1, 2, 3.5)
m_range.add('bar', 1, 4.5, 6)
m_range.add('foo2', 1, 7.5, 10)
for i in m_range['foo']:
print(i)
print(m_range.keys())
print("\n ** Merge Test **")
print(m_range.merge('foo', 'bar'))
print("\n ** Smash Test **")
m_range.smash(3, 5)
print(m_range.keys())
print("\n ** Fetch Test **")
m_range.add('foo', 1, 2, 3.5)
m_range.add('bar', 1, 4.5, 6)
print(m_range.fetch(3, 5))
99 percent of computer problems exists between chair and keyboard.
|
