Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

MAINT: Speed up numpy.nonzero. #18368

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
wants to merge 15 commits into from
Closed

MAINT: Speed up numpy.nonzero. #18368

Changes from 1 commit
Commits
Show all changes
15 commits
Select commit Hold shift + click to select a range
c404910
Added optimizations and tests for numpy.nonzero
touqir14 Feb 8, 2021
a2b2a35
Changed np.bool to bool in the tests
touqir14 Feb 8, 2021
07dc717
Enabled optimization for undefined byteorder
touqir14 Feb 8, 2021
9b5c1c4
Fixed the byteordering swapping issue using PyArray_ISNBO
touqir14 Feb 8, 2021
5c79ab3
Added code to work with swapped axes views
touqir14 Feb 8, 2021
0015523
added optimizations for fortran style arrays!
touqir14 Feb 9, 2021
36801dc
F_contiguous and C_contiguous optimizations both work correctly!
touqir14 Feb 9, 2021
399d1b9
Added more tests covering F_contiguous arrays, slices and permuted di…
touqir14 Feb 9, 2021
8435e97
Ported the low level loops to the low level loops strided template file
touqir14 Feb 12, 2021
2dbe866
Merge remote-tracking branch 'upstream/master' into faster_nonzero
touqir14 Feb 12, 2021
aa422cb
Transformed the C and F style loops from macro to functions
touqir14 Feb 13, 2021
a302d4a
Added new benchmarking code for np.nonzero
touqir14 Feb 13, 2021
85ae692
Merge remote-tracking branch 'upstream/master' into faster_nonzero
touqir14 Feb 22, 2021
3480e1e
Merge remote-tracking branch 'upstream/master' into faster_nonzero
touqir14 Feb 25, 2021
3582137
Added some function declarations in lowlevel_strided_loops.h
touqir14 Feb 25, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Added more tests covering F_contiguous arrays, slices and permuted di… 
…mensions
  • Loading branch information
@touqir14
touqir14 committed Feb 9, 2021
commit 399d1b93a9e37c218945c7fc34eb6dfa5dca20a0
167 changes: 167 additions & 0 deletions 167 numpy/core/tests/test_numeric.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1285,6 +1285,14 @@ def test_nonzero_onedim(self):
idxs = np.nonzero(x)[0]
assert_equal(np.array_equal(np.where(x != 0)[0], idxs), True)

for _ in range(iters): # Check for slices
for dtype in types:
x = ((2**33)*np.random.randn(100)).astype(dtype)
x_view = x[:50]
x_view[[0,2,8,22,24]] = 0
idxs = np.nonzero(x_view)[0]
assert_equal(np.array_equal(np.where(x_view != 0)[0], idxs), True)


def test_nonzero_twodim(self):
x = np.array([[0, 1, 0], [2, 0, 3]])
Expand Down Expand Up @@ -1312,6 +1320,8 @@ def test_nonzero_twodim(self):
types = [bool, np.int8, np.int16, np.int32, np.int64, np.uint8, np.uint16, np.uint32, np.uint64, np.float32, np.float64]
idxs = np.arange(100)
iters = 10
dim_permutation = np.arange(2) # Shuffle dimensions

for _ in range(iters):
for dtype in types:
x = ((2**33)*np.random.randn(10, 10)).astype(dtype)
Expand All @@ -1327,10 +1337,90 @@ def test_nonzero_twodim(self):
assert_equal(nzs, 0)


for _ in range(iters): # This time randomly permute dimensions
for dtype in types:
x = ((2**33)*np.random.randn(10, 10)).astype(dtype)
np.random.shuffle(idxs)
num_zeros = np.random.randint(0, 101)
x.flat[idxs[:num_zeros]] = 0
np.random.shuffle(dim_permutation)
x = np.transpose(x, dim_permutation)
idxs_0, idxs_1 = np.nonzero(x)
assert_equal(np.count_nonzero(x), len(idxs_0))
nzs = 0
for i,j in zip(idxs_0, idxs_1):
if x[i,j] == 0:
nzs += 1
assert_equal(nzs, 0)
Comment on lines +1361 to +1364
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Its fine to implement nonzero in Python here, but please refactor it. You can use np.nditer if that helps. Or flatten and np.unravel_index (and np.ravel()) if the n dimensions are annoying to deal with.


# Repeat the above logic for fortran contiguous arrays
for _ in range(iters):
for dtype in types:
x = ((2**33)*np.random.randn(10, 10)).astype(dtype)
x = np.asfortranarray(x)
np.random.shuffle(idxs)
num_zeros = np.random.randint(0, 101)
x.flat[idxs[:num_zeros]] = 0
idxs_0, idxs_1 = np.nonzero(x)
assert_equal(np.count_nonzero(x), len(idxs_0))
nzs = 0
for i,j in zip(idxs_0, idxs_1):
if x[i,j] == 0:
nzs += 1
assert_equal(nzs, 0)


for _ in range(iters): # This time randomly permute dimensions
for dtype in types:
x = ((2**33)*np.random.randn(10, 10)).astype(dtype)
x = np.asfortranarray(x)
np.random.shuffle(idxs)
num_zeros = np.random.randint(0, 101)
x.flat[idxs[:num_zeros]] = 0
np.random.shuffle(dim_permutation)
x = np.transpose(x, dim_permutation)
idxs_0, idxs_1 = np.nonzero(x)
assert_equal(np.count_nonzero(x), len(idxs_0))
nzs = 0
for i,j in zip(idxs_0, idxs_1):
if x[i,j] == 0:
nzs += 1
assert_equal(nzs, 0)


for i in range(iters): # check for slices
x = ((2**33)*np.random.randn(10, 10)).astype(np.int32)
x.flat[[2,6,9,15,21]] = 0
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
x.flat[[2,6,9,15,21]] = 0
x.flat[[2, 6, 9, 15, 21]] = 0

x_view = x[:5,:5]

idxs_0, idxs_1 = np.nonzero(x_view)
assert_equal(np.count_nonzero(x_view), len(idxs_0))
nzs = 0
for i,j in zip(idxs_0, idxs_1):
if x_view[i,j] == 0:
nzs += 1
assert_equal(nzs, 0)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You can just use assert nzs == 0 if nzs is a Python scalar.


y = np.asfortranarray(x)
y_view = y[:5,:5]

idxs_0, idxs_1 = np.nonzero(y_view)
assert_equal(np.count_nonzero(y_view), len(idxs_0))
nzs = 0
for i,j in zip(idxs_0, idxs_1):
if y_view[i,j] == 0:
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
if y_view[i,j] == 0:
if y_view[i, j] == 0:

nzs += 1
assert_equal(nzs, 0)



Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Excessive white space. There should be one empty line between def's in classes. We are pretty strict on PEP.


def test_nonzero_threedim(self):
types = [bool, np.int8, np.int16, np.int32, np.int64, np.uint8, np.uint16, np.uint32, np.uint64, np.float32, np.float64]
idxs = np.arange(300)
iters = 10
dim_permutation = np.arange(3) # Shuffle dimensions

for _ in range(iters):
for dtype in types:
x = ((2**33)*np.random.randn(10, 10, 3)).astype(dtype)
Expand All @@ -1346,6 +1436,83 @@ def test_nonzero_threedim(self):
assert_equal(nzs, 0)


for _ in range(iters): # This time randomly permute dimensions
for dtype in types:
x = ((2**33)*np.random.randn(10, 10, 3)).astype(dtype)
np.random.shuffle(idxs)
num_zeros = np.random.randint(0, 301)
x.flat[idxs[:num_zeros]] = 0
np.random.shuffle(dim_permutation)
x = np.transpose(x, dim_permutation)
idxs_0, idxs_1, idxs_2 = np.nonzero(x)
assert_equal(np.count_nonzero(x), len(idxs_0))
nzs = 0
for i,j,k in zip(idxs_0, idxs_1, idxs_2):
if x[i,j,k] == 0:
nzs += 1
assert_equal(nzs, 0)

# Repeat the above for fortran contiguous arrays
for _ in range(iters):
for dtype in types:
x = ((2**33)*np.random.randn(10, 10, 3)).astype(dtype)
x = np.asfortranarray(x)
np.random.shuffle(idxs)
num_zeros = np.random.randint(0, 301)
x.flat[idxs[:num_zeros]] = 0
idxs_0, idxs_1, idxs_2 = np.nonzero(x)
assert_equal(np.count_nonzero(x), len(idxs_0))
nzs = 0
for i,j,k in zip(idxs_0, idxs_1, idxs_2):
if x[i,j,k] == 0:
nzs += 1
assert_equal(nzs, 0)


for _ in range(iters): # This time randomly permute dimensions
for dtype in types:
x = ((2**33)*np.random.randn(10, 10, 3)).astype(dtype)
x = np.asfortranarray(x)
np.random.shuffle(idxs)
num_zeros = np.random.randint(0, 301)
x.flat[idxs[:num_zeros]] = 0
np.random.shuffle(dim_permutation)
x = np.transpose(x, dim_permutation)
idxs_0, idxs_1, idxs_2 = np.nonzero(x)
assert_equal(np.count_nonzero(x), len(idxs_0))
nzs = 0
for i,j,k in zip(idxs_0, idxs_1, idxs_2):
if x[i,j,k] == 0:
nzs += 1
assert_equal(nzs, 0)


for i in range(iters): # Check for slices
x = ((2**33)*np.random.randn(10, 10)).astype(np.int32)
x.flat[[2,6,9,15,21]] = 0
x_view = x[:5,:5]

idxs_0, idxs_1 = np.nonzero(x_view)
assert_equal(np.count_nonzero(x_view), len(idxs_0))
nzs = 0
for i,j in zip(idxs_0, idxs_1):
if x_view[i,j] == 0:
nzs += 1
assert_equal(nzs, 0)

y = np.asfortranarray(x)
y_view = y[:5,:5]

idxs_0, idxs_1 = np.nonzero(y_view)
assert_equal(np.count_nonzero(y_view), len(idxs_0))
nzs = 0
for i,j in zip(idxs_0, idxs_1):
if y_view[i,j] == 0:
nzs += 1
assert_equal(nzs, 0)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

And one more comment that got losts. These tests seem very repitetive, can you try to use pytest.mark.parametrize or create a helper function like check_nonzero_result?




def test_sparse(self):
# test special sparse condition boolean code path
for i in range(20):
Expand Down
Morty Proxy This is a proxified and sanitized view of the page, visit original site.