user7792658 - 29 days ago 5

Python Question

I have two lists 'start' and 'end'. They are of the same length (4 million each):

`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

.......

My problem is that I want to iterate the two lists, starting at the same point, but but progressively iterate along the 'end list' until I find a value where the difference between 'start[i]' and 'end[i+x]' is greater than 1000.

I have made my best attempt at doing this where I use an endless loop to iterate the 'end list' until the difference with start exceeds 1000 and then start from that point and perform the same operation from there...

Ultimately the output that I am looking for is (taking the illustrative figure above as an example):

`print density`

[4, 2, 1 ...........]

Can anyone help me with this?

While the previous answer to this question does indeed work:

`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 am afraid that the code is extremely slow as I am updating the extension of 'i_e' by adding 1 to it with each iteration of the inner while loop...

To solve this I wanted to create a 'counter' variable that will extend the 'i_e' variable dynamically. This will be done with recursion whereby the i_e variable will be increased exponentially up until the point where half the desired distance is reached and then will be exponentially decreased until the desired distance is reached.

Strategy illustration

My attempt at this is as follows:

I created a recursive a function to update a variable 'counter'

`density=[]`

i_s = 0

counter=1 ##### initialise counter with value of 1

def exponentially_increase_decrease(start, end, counter):

distance=end-start

if distance<=500:

counter=exponentially_increase_decrease(start, end, counter*2)

else:

counter=-exponentially_increase_decrease(start, end, counter/2) ## make it negative so that it subtracts from the 'counter'

return counter

Calling the function within the original code:

`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=exponentially_increase_decrease(i_s, i_e, counter)

i_e += counter

i_s += 1

I get the following error:

(Printed thousands of times)

`counter=exponentially_increase_decrease(start, end, counter*2)`

RuntimeError: maximum recursion depth exceeded

I am not experienced with this kind of problem and am not sure if I am approaching it correctly... can anyone help?

Answer Source

This is one of the few cases where I find `while`

loops to be more straight-forward, since `i_e`

and `i_s`

depend on each other. You could use two `range`

iterators, and advance the former by how much you've consumed from the latter, but that seems overly complicated.

```
>>> 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
```