General discussions: binary search in array problem 170

colin_mcnicholl 2019-05-09 08:42:33

I have coded this problem in python 3 and first attempt the response was:

'Your answer is correct, but you spent about 463 seconds instead of 60.'

My second attempt I got the response:

'Your answer is correct, but you spent about 188 seconds instead of 60.'

Running 3 repeats 10 times each with timeit I get about 22 seconds for each of the repeats with range about 0.3 secs.

I have profiled my code and made all the changes I can manage.

Could you suggest what further changes I should investigate please ?

Rodion (admin) 2019-05-09 20:32:13

Colin, Hi!

Hm-m-m, just a suggestion first - make sure there is no confusion between the running time and the time which is checked (between page is (re)loaded and the answer submitted).

I had a look at your code, it seems to be close, but I'm sorry to say at least the saved version is not completely correct so I can't make it perfectly working without significant modification to check myself.

I have a few suggestions, if you don't mind:

make it simple, remove anything unnecessary, it looks you at some moment is lost in your attempts :)
in python 3 we have integer division, without floor: guess = (max + min) // 2

probably the most important:

codes = (country_codes[binarysearch(range_starts, IP)]
    if check_IP_between(IP, range_starts[binarysearch(range_starts, IP)]
                            range_ends[binarysearch(range_starts, IP)])

Here you call binarysearch for each item 3 times, if I get it right. At least two of them are identical at all.

It's a bit overkill. Thus you get your program 3 times slower (given that Python is one of the slowest of the popular languages, 20 times slower than C, roughly - this may be enough to frustrate your attempts).

What we want is just:

find the value in range_start which is less or equal to the target (so that next range_start is greater).
and it is the only time we want to call binary search for given target
then we just check if it meets range_end; if yes - return country code, if no - return NA; ranges can't overlap of course (no IP can belong to two ranges)

You probably can easier implement this in for-loop (though probably list-comprehension form also can be written).

colin_mcnicholl 2019-05-11 08:40:23

Thanks for the suggestions. I have implemented these. On point 3 I had (as usual started with a for loop) which in this case is much more readable than the comprehension.

Yes I am now sure my problem is with the running time and the time which is checked (between page is (re)loaded and the answer submitted).

I find it impossible to:

(re)load the problem page; select all test data copy all test data paste all test data to a page in my text editor and save as a file. run my program select, copy, paste my program to the problem page select, copy, paste my answer to the problem page (this bit seems to take a several seconds) before submit button becomes available

in less than 90 seconds.

Are there some "tricks" I am overlooking ?

Quandray 2019-05-11 16:56:47

Hi Colin, how long does your code take to run?

colin_mcnicholl 2019-05-13 08:34:27

Less than 2 seconds.

Results for 3 repeats of running 10 times each:

getcountrycodes time: [15.666020911999999, 16.053110846000003, 19.654100063]

Quandray 2019-05-13 15:05:44

All I can suggest is, copy your program code, before you reload the problem page. Then, paste your program code before copying the test data.

colin_mcnicholl 2019-05-14 08:34:50

With practice I managed to improve my page loading, cutting and pasting to get submission in under 60 seconds.

Problem solved.

Thanks for suggestion - it did help.