получить индекс объединенного списка диапазонов - PullRequest
Новая
       55

получить индекс объединенного списка диапазонов

7 голосов
/ 06 мая 2020

У меня есть список диапазонов, все диапазоны в этом списке имеют одинаковые start и stop, но не одинаковые step.
например: 

[range(0, 10, 2), range(0, 10, 3)]

Of Конечно, список может содержать более двух диапазонов.
Список конкатенированных диапазонов представляет следующие числа: 

[0, 2, 3, 4, 6, 8, 9]

Я хочу получить x индекс списка конкатенированных диапазонов.
Например, индекс 5 в последнем примере будет 8.

Проблема в том, что диапазон может быть огромным (миллионы), и я не хочу превращать этот диапазон в список, чтобы получить индекс x. Мне нужно как-то рассчитать значение этого индекса x без «открытия» этого списка диапазонов

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

Есть идеи, как я могу этого добиться?

Ответы [ 3 ]

1 голос
/ 06 мая 2020

Вы можете создать новый range с теми же start и end и упаковать все step в новый список. Теперь для каждого числа из диапазона вы можете проверить, соответствует ли оно любому шагу . Вы можете превратить это в генератор: 

def steps_range(start, end, steps):
    for i in range(start, end):
        if any(i % x == 0 for x in steps):
            yield i

Теперь вы можете использовать oop на этом генераторе, пока не достигнете соответствующего индекса. Согласно вашему примеру: 

ranges = [range(0, 10, 2), range(0, 10, 3)]

start = ranges[0].start
end = ranges[0].stop
steps = [r.step for r in ranges]

target_index = 5

for i, num in enumerate(steps_range(start, end, steps)):
    print(num)
    if i == target_index:
        break

И это распечатает: 

0
2
3
4
6
8
0 голосов
/ 06 мая 2020 
def is_not_divisible_by_any(num, divs):
    return all(num % divisor for divisor in divs)

def get_idx_of_concated_list(the_list, idx):
    # Get the start, end and steps
    start, end = the_list[0].start, the_list[0].stop
    shifted_end = end - start
    steps = [r.step for r in the_list]

    # Get the number of numbers non-divisble by the steps until the given index (inclusive)
    num_not_divisibles = sum(is_not_divisible_by_any(num, steps) for num in range(idx+1))

    # The first candidate will be the given index + the above number of non-divisibles
    candidate = idx + num_not_divisibles

    # Forward by one till it is divisible by any of the steps
    while is_not_divisible_by_any(candidate, steps):
        candidate += 1

    # Check if the given index was valid
    if candidate > shifted_end:
        raise ValueError("The given index with those ranges exceed the stop value")

    # Since assumed start = 0, add the original start
    return candidate + start

# Example:
concat_list = [range(0, 1_000_000, 2), range(0, 1_000_000, 3), range(0, 1_000_000, 7)]
idx = 225_000
print(get_idx_of_concated_list(concat_list, idx))
# 289286

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

0, 1, 2, 3, 4, 5, ..., stop-1

Если бы для этой последовательности нам было предложено найти значение в x -м индексе, мы бы прямо сказали x в качестве ответа. Однако шаги диапазонов пропускают некоторые значения в этой последовательности. Например, если шаги 2 и 3, у нас будет 0, 2, 3, 4, 6, .. и так далее. Итак, если мы сможем найти количество тех пропущенных чисел, которые не делятся ни на один из заданных шагов (до данного индекса включительно), то мы просто добавим его и получим кандидата для решения.

Но кандидат по-прежнему может не делиться ни на один из этапов (например, рассмотрите свой пример в вопросе, где количество неделимых будет 2 (1 и 5), и мы добавляем 2 к заданному проиндексируйте 5 и получите 7; но это не делит 2 или 3 равномерно). Поэтому мы выполняем инкрементный поиск от candidate и далее, пока не найдем желаемое значение. И, наконец, поскольку мы приняли start как 0, мы добавляем исходное начальное значение обратно, чтобы получить результат.

Edit: я добавил проверку индекса, чтобы он не превышал конечное значение.

0 голосов
/ 06 мая 2020

Ключевым моментом является использование yield.

Сложность состоит в том, как справиться с ситуацией, когда заканчивается один yield. Последнее решение, которое я выберу, - использовать dict, использовать min, получить iterator, которому нужно переехать (next). И проверьте, доходит ли iterator до конца. Если это так, переместите его из dict. 

#!/usr/bin/env python3
import operator


class IterTool:
    def __init__(self, the_range):
        def foo(the_range):
            def bar():
                for i in the_range:
                    yield i
            return bar()

        self.the_range = foo(the_range)
        self.end = False

    def next_item(self):
        try:
            foo = next(self.the_range)
            return foo
        except StopIteration:
            self.end = True

    def is_end(self):
        return self.end


pool = {}
for i in [IterTool(range(0, 10000000000000, 2)), IterTool(range(0, 10000000000000, 3))]:
    pool[i] = i.next_item()
idx = 0
last_val = None
while all(map(lambda x: not x.is_end(), pool)):
    if len(pool) == 0:
        break
    key = min(pool.items(), key=operator.itemgetter(1))[0]
    val = pool[key]
    if val != last_val:
        if idx == 99999:
            print("%s=> %s" % (idx, val))
            break
        idx += 1
        last_val = val
    pool[key] = key.next_item()
    if key.is_end():
        del pool[key]

Результат: 

99999=> 149998

real    0m0.209s
user    0m0.200s
sys     0m0.004s
...