Округление вверх по итерируемому объекту
Есть итерируемый объект, в котором элементы отсортированны и уникальны. Для простоты такой кортеж:
c = (1,3,7,12,17)
И некое натуральное число n.
Нужно, как в операции округления вверх, получить элемент кортежа, который либо равен этому числу, либо является ближайшим следующим числом. (Если n больше последнего элемента, то следует возвращать последний элемент)
Моё решение таково:
def closest_next(itrbl, n):
itrtr = iter(itrbl)
nn = next(itrtr)
while n > nn:
try:
nn = next(itrtr)
except StopIteration:
return nn
return nn
Для:
for _ in range(1,19):
print(_ , closest_next(c,_))
Должно выдавать:
1 1
2 3
3 3
4 7
5 7
6 7
7 7
8 12
9 12
10 12
11 12
12 12
13 17
14 17
15 17
16 17
17 17
18 17
Думаю мой вариант можно в раза 4 сократить, и сделать его O(logN).
Ответы (2 шт):
Ну, можно сделать немного попроще вроде:
def closest_next(itrbl, n):
for nn in itrbl:
if n <= nn:
break
return nn
А если вы хотите именно скорость, а не простоту, то никаких итерейблов, тогда нужна готовая индексируемая отсортированная коллекция (список, кортеж) и искать в ней двоичным поиском нужный элемент, тогда будет O(logN). А с итерейблом вам придётся перебирать элементы последовательно, пока не найдётся нужный и это будет порядка O(N) какой алгоритм ни возьми.
Можно воспользоваться модулем bisect, который как раз и выполняет двоичный поиск в отсортированных данных.
>>> import bisect
>>> c = (1,3,7,12,17)
>>> c[min(len(c)-1, bisect.bisect_left(c, 0))]
1
>>> c[min(len(c)-1, bisect.bisect_left(c, 1))]
1
>>> c[min(len(c)-1, bisect.bisect_left(c, 5))]
7
>>> c[min(len(c)-1, bisect.bisect_left(c, 13))]
17
>>> c[min(len(c)-1, bisect.bisect_left(c, 20))]
17