/
utils.py
94 lines (76 loc) · 3.01 KB
/
utils.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
# Copyright 2014: Mirantis Inc.
# All Rights Reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License"); you may
# not use this file except in compliance with the License. You may obtain
# a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
# License for the specific language governing permissions and limitations
# under the License.
import math
class GraphZipper(object):
def __init__(self, base_size, zipped_size=1000):
"""Init graph zipper.
:param base_size: Amount of points in raw graph
:param zip_size: Amount of points that should be in zipped graph
"""
self.base_size = base_size
self.zipped_size = zipped_size
if self.base_size >= self.zipped_size:
self.compression_ratio = self.base_size / float(self.zipped_size)
else:
self.compression_ratio = 1
self.point_order = 0
self.cached_ratios_sum = 0
self.ratio_value_points = []
self.zipped_graph = []
def _get_zipped_point(self):
if self.point_order - self.compression_ratio <= 1:
order = 1
elif self.point_order == self.base_size:
order = self.base_size
else:
order = self.point_order - int(self.compression_ratio / 2.0)
value = (
sum(p[0] * p[1] for p in self.ratio_value_points)
/ self.compression_ratio
)
return [order, value]
def add_point(self, value):
self.point_order += 1
if self.point_order > self.base_size:
raise RuntimeError("GraphZipper is already full. "
"You can't add more points.")
if not isinstance(value, (int, float)):
value = 0
if self.compression_ratio <= 1: # We don't need to compress
self.zipped_graph.append([self.point_order, value])
elif self.cached_ratios_sum + 1 < self.compression_ratio:
self.cached_ratios_sum += 1
self.ratio_value_points.append([1, value])
else:
rest = self.compression_ratio - self.cached_ratios_sum
self.ratio_value_points.append([rest, value])
self.zipped_graph.append(self._get_zipped_point())
self.ratio_value_points = [[1 - rest, value]]
self.cached_ratios_sum = self.ratio_value_points[0][0]
def get_zipped_graph(self):
return self.zipped_graph
def percentile(points, percent, ignore_sorting=False):
if not points:
return None
if not ignore_sorting:
points.sort()
k = (len(points) - 1) * percent
f = math.floor(k)
c = math.ceil(k)
if f == c:
return points[int(k)]
d0 = points[int(f)] * (c - k)
d1 = points[int(c)] * (k - f)
return d0 + d1