Why is this custom bisect function on endless loop?

Question

I have a long script in which I was initially using bisect in. This was part of it (worked perfectly fine and as intended):

portfolios = [[1], [0.9], [0.8], [0.7], [0.6]] #Fills up list to avoid "index out of range" error later on in code
add_sharpe = [sharpe, name_a, weight_a, exchange_a, name_b, weight_b, exchange_b, name_c, weight_c, exchange_c]
for x in portfolios:
    if sharpe > x[0]:
        sharpes =  [i[0] for i in portfolios]
        if name_a not in x and name_b not in x and name_c not in x:
            print sharpe
            print sharpes
            print portfolios
            print add_sharpe
            position = reverse_bisect(sharpes, sharpe)
            print position
            portfolios.insert(position, add_sharpe)

However, now I needed a reverse bisect (descending order). Thankfully, I found a really good solution to this.

The code to create a reverse bisect is as follows:

def reverse_bisect(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    return lo

It works very well when I was testing it out with simple calculations. However, when I plug it into my script, it causes the script to freeze at that point when being run. I have no idea why this is happening, as I am using the same logic as before with bisect.bisect which worked perfectly fine.

This is what is now not working:

        if name_a not in x and name_b not in x and name_c not in x:
            position = reverse_bisect(sharpes, sharpe)
            portfolios.insert(position, add_sharpe)

For some reason, using the function appears to loop over portfolios.insert(position, add_sharpe) without end.

The output:

[1, 0.9, 0.8, 0.7, 0.6] #print portfolios
[[1], [0.9], [0.8], [0.7], [0.6]] #print sharpes
[1.6275936902107178, "CARR'S GROUP  (CARR.L)", 0.9, 'LSE  ', 'Church & Dwight Co. Inc. (CHD)', 0.05, 'NYSE  ', 'NCC Group plc. (NCC.L)', 0.05, 'LSE  '] #print portfolios
0 #print position
1.62759369021 #print sharpe
[1.6275936902107178, 1, 0.9, 0.8, 0.7, 0.6] #print portfolios
[[1.6275936902107178, "CARR'S GROUP  (CARR.L)", 0.9, 'LSE  ', 'Church & Dwight Co. Inc. (CHD)', 0.05, 'NYSE  ', 'NCC Group plc. (NCC.L)', 0.05, 'LSE  '], [1], [0.9], [0.8], [0.7], [0.6]]
[1.6275936902107178, "CARR'S GROUP  (CARR.L)", 0.9, 'LSE  ', 'Church & Dwight Co. Inc. (CHD)', 0.05, 'NYSE  ', 'NCC Group plc. (NCC.L)', 0.05, 'LSE  ']
1
1.62759369021
[1.6275936902107178, 1.6275936902107178, 1, 0.9, 0.8, 0.7, 0.6]
[[1.6275936902107178, "CARR'S GROUP  (CARR.L)", 0.9, 'LSE  ', 'Church & Dwight Co. Inc. (CHD)', 0.05, 'NYSE  ', 'NCC Group plc. (NCC.L)', 0.05, 'LSE  '], [1.6275936902107178, "CARR'S GROUP  (CARR.L)", 0.9, 'LSE  ', 'Church & Dwight Co. Inc. (CHD)', 0.05, 'NYSE  ', 'NCC Group plc. (NCC.L)', 0.05, 'LSE  '], [1], [0.9], [0.8], [0.7], [0.6]]
[1.6275936902107178, "CARR'S GROUP  (CARR.L)", 0.9, 'LSE  ', 'Church & Dwight Co. Inc. (CHD)', 0.05, 'NYSE  ', 'NCC Group plc. (NCC.L)', 0.05, 'LSE  ']
2
1.62759369021
[1.6275936902107178, 1.6275936902107178, 1.6275936902107178, 1, 0.9, 0.8, 0.7, 0.6]
[[1.6275936902107178, "CARR'S GROUP  (CARR.L)", 0.9, 'LSE  ', 'Church & Dwight Co. Inc. (CHD)', 0.05, 'NYSE  ', 'NCC Group plc. (NCC.L)', 0.05, 'LSE  '], [1.6275936902107178, "CARR'S GROUP  (CARR.L)", 0.9, 'LSE  ', 'Church & Dwight Co. Inc. (CHD)', 0.05, 'NYSE  ', 'NCC Group plc. (NCC.L)', 0.05, 'LSE  '], [1.6275936902107178, "CARR'S GROUP  (CARR.L)", 0.9, 'LSE  ', 'Church & Dwight Co. Inc. (CHD)', 0.05, 'NYSE  ', 'NCC Group plc. (NCC.L)', 0.05, 'LSE  '], [1], [0.9], [0.8], [0.7], [0.6]]
[1.6275936902107178, "CARR'S GROUP  (CARR.L)", 0.9, 'LSE  ', 'Church & Dwight Co. Inc. (CHD)', 0.05, 'NYSE  ', 'NCC Group plc. (NCC.L)', 0.05, 'LSE  ']
3

Please create an [MCVE](http://stackoverflow.com/help/mcve) demonstrating the problem. Since we have absolutely no idea what `sharpes`, `sharpe`, `portfolios`, or `add_sharpe` are, there's no way we can help you. — MattDMo, May 17 '15 at 04:44
Not an answer, but every time I need to write a bisection method, I end up copying this example implementation from C++: http://www.cplusplus.com/reference/algorithm/lower_bound/ — Juan Lopes, May 17 '15 at 04:54
@Juan Lopes thanks for the example. The code I have works well if you test it out. For example, if `l = [6,5,3,2,1]` and `reverse_bisect(l,4)` will work — Alex McLean, May 17 '15 at 04:57

dting · Accepted Answer · 2015-05-17T06:21:17.237

2

I think you are inserting into the list you are iterating. For example:

a = [1]

for x in a:
    a.insert(0, x)
    print a

This will put you in a loop where you keep inserting 1 to a.

edited May 17 '15 at 06:21

answered May 17 '15 at 06:12

dting

38,604
10
95
114

to be specific I am using `.insert()` but yes. Do you have any idea of how to simply add it once? – Alex McLean May 17 '15 at 06:15
I can't tell from your code where any of the variables are coming from and why you are iterating over portfolios. Is the code you posted nested inside another loop? – dting May 17 '15 at 06:24
I found the solution. I had to create a new list, and instead of inserting the value to the same list I was iterating over, I inserted it into the new list. Thanks for your help! – Alex McLean May 17 '15 at 06:28

Why is this custom bisect function on endless loop?

1 Answers1