Реализация экспоненциального отката в Python

Question

У меня есть два списка "начало" и "конец". Они имеют одинаковую длину (4 миллиона каждый):

for i in xrange(0,len(start)):
      print start[i], end[i]

3000027 3000162
3000162 3000186
3000186 3000187
3000187 3005000
3005000 3005020
3005020 3005090
3007000 3007186
3007186 3009000
3009000 3009500
.......

Моя проблема в том, что я хочу перебрать два списка, начиная с одной и той же точки, но постепенно перебирая "конечный список", пока не найду значение, в котором разница между "start[i]" и "end[i+x" ]'больше 1000.

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

ПРИМЕЧАНИЕ: старый контент пропущен

В конечном итоге результат, который я ищу, - это (взяв иллюстративный рисунок выше):

print density
  [4, 2, 1 ...........]

Кто-нибудь может мне с этим помочь?

ОБНОВИТЬ

Хотя предыдущий ответ на этот вопрос действительно работает:

density=[]
i_s = 0
while i_s < len(start):
     i_e = i_s
     while i_e < len(end):
         if end[i_e] - start[i_s] > 1000:
             density.append(i_e - i_s + 1)
             i_s = i_e
             break
         i_e += 1
     i_s += 1


print sum(density)/float(len(density))
print max(density)
print min(density)

Я боюсь, что код очень медленный, так как я обновляю расширение i_e, добавляя к нему 1 с каждой итерацией внутреннего цикла while... Чтобы решить эту проблему, я хотел создать переменную counter, которая будет расширяться переменная 'i_e' динамически. Это будет сделано с помощью рекурсии, в результате чего переменная i_e будет экспоненциально увеличиваться до точки, где будет достигнута половина желаемого расстояния, а затем будет экспоненциально уменьшаться, пока не будет достигнуто желаемое расстояние.

Стратегия иллюстрации

Моя попытка это заключается в следующем:

Я создал рекурсивную функцию для обновления переменной 'counter'

counter=1 ##### initialise counter with value of 1
def exponentially_increase_decrease(start, end, counter):
    distance=end-start
    if distance<=500:  ###500 is half the desired distance
        counter=exponentially_increase_decrease(start, end, counter*2)
    else:
        counter=-exponentially_increase_decrease(start, end, counter/2)
    print counter
    return counter

Вызов функции в исходном коде:

density=[]
i_s = 0
while i_s < len(start):
     i_e = i_s
     while i_e < len(end):
         if end[i_e] - start[i_s] > 1000:
             density.append(i_e - i_s + 1)
             i_s = i_e
             break
         counter=counter=exponentially_increase_decrease(i_s, i_e, counter)
         i_e += counter
     i_s += 1

Я получаю следующую ошибку:

(Напечатано тысячи раз)

counter=exponentially_increase_decrease(start, end, counter*2)
RuntimeError: maximum recursion depth exceeded

Я не сталкиваюсь с такой проблемой и не уверен, правильно ли к ней подхожу... Кто-нибудь может помочь?

Answer 1

Это один из немногих случаев, когда я нахожу while петли, чтобы быть более простым, так как i_e а также i_s зависеть друг от друга. Вы могли бы использовать два range итераторы, и продвиньте первый на то, сколько вы потребляли от последнего, но это кажется слишком сложным.

>>> start
[3000027, 3000162, 3000186, 3000187, 3005000, 3005020, 3007000, 3007186, 3009000]
>>> end
[3000162, 3000186, 3000187, 3005000, 3005020, 3005090, 3007186, 3009000, 3009500]
>>> i_s = 0
>>> while i_s < len(start):
...     i_e = i_s
...     while i_e < len(end):
...         if end[i_e] - start[i_s] > 1000:
...             print(i_e - i_s + 1)
...             i_s = i_e
...             break
...         i_e += 1
...     i_s += 1
...
4
3
1

Answer 2

Не уверен, правильно ли я понял... Это то, что вы ищете?

MAX_DIFF = 1000
density = [0] * len(start)
for i in range(len(start)):
    for j in range(i, len(end)):
        density[i] += 1
        if end[i] - start[i] >= MAX_DIFF:
            break
print(density)