Speeding Up and Optimizing Python Loop

Question

I have been banging my head against the wall for the last couple days, trying to optimize my code to improve speed. This chunk of code right here however is still quite slow, and I am not quite sure how to improve its speed specifically.

The problem, when using speed tests, seems to be primarily the nested for loop. The loop that calculates distance seems to be relatively quick.

As an explanation of the code, I am reading in images using openCV, going through that image, and finding the nearest pixel to a given location. I want to ignore certain colors within my conditional in the nested for loop, as well as ignore previously visited pixels elsewhere in my code.

    found = False
    randArray = []
    for i in range(0,imgCol):
        for j in range(0,imgRow):
            if(pixelInLine[j*imgCol + i] == 0  and numpy.any(img2[j, i] != 0) and isWhite(j,i) == False):
                found = True
                temp = points(j,i)
                pointArray.append(temp)

                #The pixelsInLine is to ignore previously visited pixels
                #The rest of the above conditional is to ignore colors I don't want


    myDist = 0
    currDist = sys.maxsize
    distArray = []
    for sx in pointArray:
        myDist = math.sqrt( ((currR-sx.rr)**2)+((currC-sx.cc)**2))
        if myDist == currDist:
            distArray.append(sx)
        if myDist < currDist:
            distArray = []
            distArray.append(sx) 
            currDist = myDist

    if found == True:
        rrr = distArray[0].rr
        ccc = distArray[0].cc

you might wanna break the loop after hitting if condition, found = True ? — Skycc
– Skycc, Commented Sep 11, 2019 at 4:00
I have done that in the past, and yes it is considerably faster. Its a good idea, and I appreciate it, but it just finds the first available pixel in the loop. Which isn't really the functionality I want. I'd like to find the nearest pixel, a close one, or at least an algorithm that is more organic than just going left to right top to bottom finding the first open spot. — Snoozy
– Snoozy, Commented Sep 11, 2019 at 4:07
Should possibly be migrated to the CodeReview site, but I can't flag for that site. — MegaEmailman
– MegaEmailman, Commented Sep 11, 2019 at 4:10

mackorone · Accepted Answer · 2019-09-13 07:45:46Z

1

It's difficult to tell exactly what's going on, but my understanding is that you're trying to find the set of pixels that satisfy some property and have the smallest Euclidean distance from some other pixel. If that's the case, rather than testing every single pixel in the array, why not start with the closest pixels? If/when you find ones that satisfy the desired properties, you can stop searching, because you know that there aren't any that are closer.

edited Sep 13, 2019 at 7:45

answered Sep 11, 2019 at 4:19

mackorone

1,0766 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Snoozy Over a year ago

Interesting, I hadnt thought of anything like this before, I appreciate it. Im not 100% sure about how implementation would look, primarily because I am getting my image array from openCV and sorting that by distance doesnt come to me right away. Ill do some research and see if I can get it working.

mackorone Over a year ago

> sorting that by distance - This is just a matter of defining a function that returns the Euclidean distance from your fixed point, let's call it a: def func(b): return math.sqrt((a.x - b.x) ** 2 + (a.y - b.y) ** 2). Then you can use the function like this: sorted_pixels = sorted(array_of_pixels, key=func). Note that you can drop the math.sqrt if you want, since it doesn't affect sort order.

One Lyner Over a year ago

You have n^2 pixels so sorting them is O(n^2 log n) which is slower than O(n^2)

mackorone Over a year ago

@OneLyner whoops, you're completely right. Will update my answer to remove the sorting part. (There are other ways of checking the closest pixels first.)

One Lyner · Accepted Answer · 2019-09-13 08:14:57Z

If you are doing this for many pixels, the part with the conditionals doesn't depend on the pixel you are looking at at the moment. An improvement would the be to do this O(n^2) pixel selection only once, and late on only update it when you update pixelInLine e.g.

As @mackorone noticed, you can also try to enumerate the pixels from the closest to the farthest. But then it depends if you are expecting pointArray to be big or small. If it's small enough, going through all of it can be quicker than a fancy enumeration.

Collectives™ on Stack Overflow

Speeding Up and Optimizing Python Loop

2 Answers 2

4 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Linked

Related