LINUX.ORG.RU

разбить диапазон

 ,


0

1

может кто нибудь сталкивался с таким.
пытаюсь реализовать алгоритм на python позволяющий делать следующее
есть диапазон номеров
от 1 000 000 до 2 192 999
нужно его разбить на под диапазоны
1)-1 000 000 по 1 999 999 префикс для диапазона 1
2)-2 000 000 по 2 099 999 префикс для диапазона 20
3)-2 100 000 по 2 189 999 префикс для диапазона 210, 211.. 218
4)-2 190 000 по 2 192 999 префикс 2190, 2191, 2192,


или 2 193 000 по 3 000 000
1)- 2 193 000 по 2 199 999 префикс 2193 ..2199
2)- 2 200 000 по 2 999 999 префикс 22, 23 .. 29
3) один номер 3 000 000 префикс 3000000
алгоритм находящий префикс из разбитого диапазона уже реализовал. а вот как находить диапазоны не понятно. подскажите в какую сторону думать ?

конечный автомат (ну или рег. выражения)

invy ★★★★★ ()

Может вам поможет вот этот код? Он создает генератор диапазонов

class crange(object):
    def __init__(self, k):
        self.k = k
    def __call__(self, x):
        if self.k <= 0:
            return None
        if self.k > x:
            self.k -= x
            return xrange(self.k, self.k+x)
        x = self.k
        self.k = 0
        return xrange(0, x)
Пользоваться примерно так:
сr = crange(1000000) # Задаем правую границу диапазона
cr(2000)  # просим диапазон [0, 2000]
cr(3000)  # просим диапазон [2001, 3000]

k0valenk0_igor ★★★ ()

Если я правильно понял задачу, то подойдёт что-то такое, например:

ranges = ({'from': 1000000, 'to': 1999999, 'prefix': 1},
          {'from': 2000000, 'to': 2099999, 'prefix': 20},
          {'from': 2100000, 'to': 2189999, 'prefix': lambda x: int(x / 10000)})

def get_prefix(value):
    for d in ranges:
        if value >= d['from'] and value <= d['to']:
            if hasattr(d['prefix'], '__call__'):
                return d['prefix'](value)
            else:
                return d['prefix']

print(get_prefix(1234567)) # 1
print(get_prefix(2000001)) # 20
print(get_prefix(2182999)) # 218

И так далее. Но наверняка будут и решения покрасивее.

risenshnobel ★★★ ()
Ответ на: комментарий от risenshnobel

поиск префикса по разбитому диапазону уже реализован. трудности в том что бы найти эти разбитые диапазоны.
Т.Е найти поддиапазон 1 000 000 по 1 999 999 из большого диапазона 1 000 000 до 2 192 999.

думаю как то так надо двигаться . добить до целого миллиона
потом добить до целых ста тысяч и тд.
но если диапазон 2 193 000 по 3 000 000 то наоборот добить до целой тыщи, добить до целых 10 тысяч и тд.

хотя возможно можно как то по другому это сделать. собственно мой вопрос в этом - найти диапазоны .

NimoLime ()
Ответ на: комментарий от NimoLime

поиск префикса по разбитому диапазону уже реализован. трудности в том что бы найти эти разбитые диапазоны.
Т.Е найти поддиапазон 1 000 000 по 1 999 999 из большого диапазона 1 000 000 до 2 192 999.

Меня смущает слово «найти». Откуда берутся эти числа для обозначения границ диапазонов «1 999 999, 2 099 999, 2 189 999, 2 192 999, 2 199 999, 2 999 999». Они формируются по какому-то правилу или просто изначально заданы и всегда неизменны? И что далее должно произойти с найденным поддиапазоном?

justAmoment ★★★★★ ()
Ответ на: комментарий от justAmoment

Откуда берутся эти числа для обозначения границ диапазонов «1 999 999, 2 099 999, 2 189 999, 2 192 999, 2 199 999, 2 999 999»

они берутся исходя из такой логики
1 000 000 по 1 999 999 префикс для диапазона 1
то есть любая строка из этого диапазона начинающаяся на 1 ( будет входить в диапазон этих номеров)

2 000 000 по 2 099 999 префикс для диапазона 20
то есть любая строка начинающаяся на 20 . тут мы не можем использовать префикс просто 2 поскольку изначальный диапазон
от 1 000 000 до 2 192 999 в который не входят все цифры начинающиеся на 2.

и тд.

вообще это получается задача обратная задаче поиска направления по префиксу.

например в SQL бд прописаны префиксы 1, 20 , 210 итд. мы к нему делаем запрос select like . и sql отдает нам наиболее подходящий префикс по этому номеру. префиксы могут быть разной длинны. но sql находит его по наибольшему совпадению от начала номера.

NimoLime ()
Ответ на: комментарий от NimoLime

А зачем вообще понадобилось разбивать диапазоны на поддиапазоны? У тебя есть код который заданному номеру сопоставляет префикс, разве этого не достаточно?

true_admin ★★★★★ ()
Ответ на: комментарий от NimoLime

например в SQL бд прописаны префиксы 1, 20 , 210 итд. мы к нему делаем запрос select like . и sql отдает нам наиболее подходящий префикс по этому номеру. префиксы могут быть разной длинны. но sql находит его по наибольшему совпадению от начала номера.

Ok. Вот эта часть реализована в SQL, и уже работает, и менять её не надо. Я правильно понимаю? Теперь представим всё, что у тебя происходит, в виде блок-схемы.

данные на входе --> Чёрный ящик --> данные на выходе.
Вот это всё:

они берутся исходя из такой логики 1 000 000 по 1 999 999 префикс для диапазона 1 то есть любая строка из этого диапазона начинающаяся на 1 ( будет входить в диапазон этих номеров)

2 000 000 по 2 099 999 префикс для диапазона 20 то есть любая строка начинающаяся на 20 . тут мы не можем использовать префикс просто 2 поскольку изначальный диапазон от 1 000 000 до 2 192 999 в который не входят все цифры начинающиеся на 2.

дипазоны, поддиапазоны, их приоритеты, границы, префиксы. Всё это убираем в чёрный ящик и больше не трогаем.

Теперь вопрос. Что из себя представляют данные на входе: это числа или строки; сколько их: единицы, сотни, миллионы, миллиарды?

Потом что-то происходит с этими данными в чёрном ящике.

Второй вопрос. Что появляется на выходе чёрного ящика: числа или строки; сколько их?

justAmoment ★★★★★ ()
Ответ на: комментарий от true_admin

А зачем вообще понадобилось разбивать диапазоны на поддиапазоны?


что бы найти наиболее короткий список префиксов. Префиксы изначально не известны. это человеческий мозг - может увидеть префиксы увидеть количество миллионов в префиксе, тысяч, сотен.
( алгоритм который находит префикс из так сказать правильного диапазона(диапазона в котором целое число либо сотен либо тысяч либо миллионов) есть ) . но вот как их найти эти целые диапазоны, что бы по ним уже найти префиксы...

У тебя есть код который заданному номеру сопоставляет префикс, разве этого не достаточно?



этот код работает когда в список префиксов уже сформирован. задача найти эти префиксы.

то что я указал в условиях что префикс для 1)-1 000 000 по 1 999 999 равен 1 - это я всего лишь указал разложив в уме диапазон. задача найти этот префикс.

NimoLime ()
Ответ на: комментарий от NimoLime

Честно говоря, я до сих пор ничего не понимаю.

Префиксы даны или их надо сформировать? Если сформировать то по какому принципу?

Почему есть префикс 20, 21 итп, но нет 10, 11?

Короче, всё это очень странно.

true_admin ★★★★★ ()
Ответ на: комментарий от justAmoment

Ok. Вот эта часть реализована в SQL, и уже работает, и менять её не надо. Я правильно понимаю? Теперь представим всё, что у тебя происходит, в виде блок-схемы.



Задача сформировать эти префиксы - допустим для бд sql что бы по ним определять куда направлять этот номер. задача обратная - для бд найти эти префиксы, и так что бы их число было как можно меньше.
вы поняли немножко не верно. для того что бы схема с черным ящиком заработала и нужно найти эти префиксы.

можно еще вот так провести аналогию.
найти адрес сети по известному диапазону ip адресов и маске ( но только для десятичных чисел)
эту задачу решает маршрутизатор когда к нему прилетает пакет из маски вычисляет адрес и рулит в разные gateway
но для десятичных логика ИЛИ не подойдет. это очень грубая аналогия.

NimoLime ()
Ответ на: комментарий от true_admin

Префиксы даны или их надо сформировать? Если сформировать то по какому принципу?


изначально префиксов нет. их нужно сформировать.
по принципу: от 1 000 000 до 2 192 999
x- любое число
1)в этот диапазон входит любой номер начинающийся на 1 XXX XXX
2)так же в этот диапазон пролезет любое число начинающееся на
2 0ХХ ХХХ
3)так же в этот диапазон пролезет войдет любое число начинающееся на 2 10х ххх или 211х ххх, .. 218x xxx
4) 2190xxx 2191xxx 2192xxх

собственно надо найти эти числа return [1, 20, 210, 211,218 и тд]

Почему есть префикс 20, 21 итп, но нет 10, 11?


префикс 10 может быть, но он не нужен поскольку - он и так уже удовлетворяет условию начинающийся на 1 . 11 - тоже начинается на 1 .

NimoLime ()
Ответ на: комментарий от NimoLime

префикс 10 может быть, но он не нужен поскольку - он и так уже удовлетворяет условию начинающийся на 1

Тогда по логике префикс 20, 210 итп не нужны, они уже включены в префикс 2.

В общем, я не понимаю логики. Если не секрет, какая глобальная задача решается?

true_admin ★★★★★ ()
Ответ на: комментарий от NimoLime

ex.py:

res = []
j = 2192999
while(j > 0):
    res.append(j)
    j = (j / 10) - 1 if (j % 10 == 0) else (j - 1)
print sorted(res)

aedeph@aedeph:~/sandbox/python$ python ex.py
[1, 20, 210, 211, 212, 213, 214, 215, 216, 217, 218, 2190, 2191, 21920, 21921, 21922, 21923, 21924, 21925, 21926, 21927, 21928, 219290, 219291, 219292, 219293, 219294, 219295, 219296, 219297, 219298, 2192990, 2192991, 2192992, 2192993, 2192994, 2192995, 2192996, 2192997, 2192998, 2192999]

Но вообще, тебе это не нужно. Тебе нужно немедленно в букварь для грамотности и в учебник по дискретной математике для нормального формулирование мыслей.

aedeph_ ★★ ()
Ответ на: комментарий от aedeph_

s/ание/ания/

ps:

в функциональном стиле:

def fun(x):
    if (x > 0):
        return fun((x / 10) - 1 if (x % 10 == 0) else (x - 1)) + [x]
    else:
        return []
print fun(2192999)

в функциональном стиле не для девочек:

print (lambda f: (lambda x: x(x))(lambda y: f(lambda z: y(y)(z))))(lambda f: lambda x: (f(x / 10 - 1 if (x % 10 == 0) else x-1) if x > 1 else []) + [x])(2192999) 

aedeph_ ★★ ()
Ответ на: комментарий от aedeph_

j/10

Вы, батенька, так пишете, как будто оператор деления «/» работает одинаково во всех версиях пайтона. Вы, кстати, на какой запускали?

Virtuos86 ★★★★★ ()
Ответ на: комментарий от aedeph_

спасибо за предложенное решение.

думаю над тем как бы сделать так что бы сократить результат.
ведь по идее для 1000000 до 2192999
результат должен быть
[1, 20, 210, 211, 212, 213, 214, 215, 216, 217, 218, 2190, 2191, 2192]
нет необходимости расписывать префикс 2192 - потому что все номера начинающиеся с этого префикса 2192 входят в диапазон.
И как быть если диапазон задан с нижней границей 2193000 по 3001299 ?
согласен что условия изложил сумбурно, я больше связист чем программист. Не сочтите за труд просветите, как будет звучать условие в терминах дискретной математики ?

NimoLime ()
Ответ на: комментарий от true_admin

Тогда по логике префикс 20, 210 итп не нужны, они уже включены в префикс 2.


префиксы 20, 210 нужны ибо диапазон 1000000 до 2192999
то есть может быть число 2666111 которое не входит в этот диапазон. а использовав префикс 20 мы явно указываем, что в него подпадают все числа начинающиеся на 20ххххх.

Глобальная задача найти префиксы из заданного диапазона номеров, что бы их количество (префиксов) было как можно меньше. в маршрутизации очень часто приходится решать такие задачи. в голове то они решаются уже не задумываясь а вот программно...

NimoLime ()
Ответ на: комментарий от NimoLime

как бы сделать так что бы сократить результат

res = []
j = 2192999
while(j > 0):
    if (j % 10 == 9)
         j = j / 10
    else
         res.append(j)
         j = (j / 10) - 1 if (j % 10 == 0) else (j - 1)
print list(reversed(res))

И как быть если диапазон задан с нижней границей 2193000 по 3001299 ?

Бить на две области относительно 3000000, с нижней частью разбираться домножив на -1.

Не сочтите за труд просветите

Сочту.

aedeph_ ★★ ()
Ответ на: комментарий от NimoLime

Понял, надо найти набор префиксов для заданного диапазона. Товарищ сверху, вроде, написал код. Речь идёт об IP-адресах? Попробуй так же посмотреть в гугле что-то типа «IP split address range into subnets».

true_admin ★★★★★ ()
from operator import floordiv, mul

def case(case_list):
    pred, calc = case_list[0]
    return calc() if pred() else case(case_list[1:])

def min_order(num):
    return 1 if num%10 else 10*min_order(num//10)

def intervals(low, high):
    def take(num, order, direction):
        is_last      = lambda : num + order == high + 1
        is_excess    = lambda : num + order > high
        is_overflow  = lambda : not num%(order*10)

        nxt          = lambda : [num//order]
        
        do_not_shift = lambda a, offset : a
        anyway       = lambda : True

        diver        = lambda step, order_shift, direction : lambda : take(num + step, order_shift(order, 10), direction)

        last_case      = is_last, nxt
        excess_case    = is_excess, diver(0, floordiv, 'backward')
        overflow_case  = is_overflow, diver(0, mul, 'forward')
        anyway_case    = lambda direction : (anyway,  lambda : nxt() + diver(order, do_not_shift, direction)())

        return {
            'forward'  : lambda : case((last_case, excess_case, overflow_case, anyway_case('forward'))),
            'backward' : lambda : case((last_case, excess_case, anyway_case('backward')))
        }[direction]()

    return take(low, min_order(low), 'forward')

print(intervals(1000000, 2192999))
print(intervals(2193000, 3000000))
anonymous ()
Ответ на: комментарий от anonymous

Спасибо Огроменское. уже пол дня вникаю, ( не могу столько переменных в голове держать) где бы куда бы пойти учится, что бы такие задачки щелкать на раз...
Еще интересно сколько времени заняла реализация...

NimoLime ()
Ответ на: комментарий от NimoLime

Еще интересно сколько времени заняла реализация...

на алгоритм - минут 30, лежа в ванне

на реализацию - минут 60

на обфускациюабстракции - часа 3

anonymous ()
Ответ на: комментарий от anonymous

н да впечатляет. я свой мозг так хорошо не знаю что бы идти думать в ванну. полагаю любой труд должен быть оплачен. куда заносить? или, либо в любом случае я в долгу.

NimoLime ()
Ответ на: комментарий от NimoLime

ну ок, вот вариант без абстракций, лол

def min_order(num):
    return 1 if num%10 else 10*min_order(num//10)

def prefixes(low, high):
    
    def forward(num, order):
        nxt = num + order
        if nxt == high + 1:
            return [num//order]
            
        if nxt > high + 1:
            return backward(num, order//10)
                        
        if not num%(order*10):
            return forward(num, order*10)
            
        return [num//order] + forward(nxt, order)

    def backward(num, order):
        nxt = num + order
        if nxt == high + 1:
             return [num//order]
             
        if nxt > high + 1:
            return backward(num, order//10)
                        
        return [num//order] + backward(nxt, order)
        
    return forward(low, min_order(low))
Его, наверное, проще будет распарсить.

Валидностью я особо не заморачивался, так что вполне возможно оно на каких-то входных данных свалится.

Оплачивать не надо)

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.