Possibly Faster solution for #66

[kwhkim]

I thought maybe using .view() may be faster. And it seems.

w, h = 256,256

l = np.random.randint(0,4,(h,w,3), dtype=np.uint8)
l2 = np.zeros((h,w,4), dtype=np.uint8)
l2[...,:3]=l[...,:3]
l2[...,3] = l2[...,2]
l3 = l2.view(dtype=np.int32)
n= len(np.unique(l3))
print(n)

My %%timeit shows 2.68 ms ± 67.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) compared to Mark Setchell's version 4 ms ± 259 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) I think there might be some trade off between allocating new memory and using view.

The solution utilizes the fact that using .view() we can simply use np.unique(, axis=None). Since color is composed of 3bytes I just copied the last byte and did 4-bytes comparison with .view(dtype=np.int32)

[rougier]

Even if it is faster, I think it it less readable than the current solution. Also, the creation time of l2 + assignment might be negligible with such a small array, but for bigger arrays, it might be significant.

[kwhkim]

About the assignment problem, it is actually quite the opposite. As the array gets bigger, the time difference get bigger, too. Actually I thought just like you but it is not and it is quite a surprise for me too. I think my solution is "Surprise surprise" solution... even for you who might be a way more experienced than me in this sorts of task. And it is quite ubiquitous that there is tradeoff between readability and speed. The real problem I am wary of is that it needs 2.3 times more memory than the original solution. Anyway still it is quite instructive that the time cost for comparison is way bigger than the assignment. It's all up to you whether it should be included as another solution but I think it's worth it because the result is kinda surprise even for experience numpy users

[rougier]

Can you post here the code where you measure the two methods?

[kwhkim]

I just changed w, h to 1024,1024 and 2560,2560

%%timeit
#w, h = 256, 256
w, h = 1024, 1024 # Time elapsed 69.3
w, h = 2560, 2560 # 434
I = np.random.randint(0,4,(h,w,3), dtype=np.uint8)

# View each pixel as a single 24-bit integer, rather than three 8-bit bytes
I24 = np.dot(I.astype(np.uint32),[1,256,65536])

# Count unique colours
n = len(np.unique(I24))
#print(n)

# ====

%%timeit
#w, h = 256,256
w, h = 1024, 1024 # Time elapsed 46.7
w, h = 2560, 2560 # 291
l = np.random.randint(0,4,(h,w,3), dtype=np.uint8)
#l2 = np.zeros((h,w,4), dtype=np.uint8)
l2 = np.empty((h,w,4), dtype=np.uint8)
# w, h = 2560, 2560 -> 284, 280
l2[...,:3]=l[...,:3]
l2[...,3] = l2[...,2]
l3 = l2.view(dtype=np.int32)
n= len(np.unique(l3))
#print(n)

Oh one more thing. The allocation part could be made faster using np.empty() because it wont care about the initial value.

[rougier]

Do you have the version with %timeit expr ? I want to be sure to know what is measured exactly.

[kwhkim]

I dont get what you mean. %%timeit is for cell mode and %timeit is for in line mode They are essentially the same. https://ipython.readthedocs.io/en/stable/interactive/magics.html

[kwhkim]

https://colab.research.google.com/drive/1VAcfReYh5JDLPbfsfmyx5Yhjp2OgrxAx?usp=sharing

I realize that l2[...,3] = l2[...,2] is redudant if we do np.ones() or np.zeros()

So with np.zeros() and removing l2[...,3] = l2[..,2], I could get it even faster

[rougier]

Thanks. Last version is faster and more readable. Can you make a PR (reusing same notation I / I24)?