[Python] How can I consolidate a NumPy ndarray of integer values more efficiently?

I apologize for including too much information.

I apologize for not including enough information.

What do I want the code to do?


arrayCurveLocations is an unsorted ndarray with pairs of integer numbers: curveLocations and distinctCrossings.

If a curveLocations number appears more than once in the ndarray, I want to consolidate the curveLocations rows by adding together the corresponding distinctCrossings numbers.

The newly created ndarray does not need to be sorted.

idk, I'm lost


I think numpy.unique is so close to being what I need. The following example from the docs reconstructs the original ndarray with the array of unique values and the array of "inverse indices". The indices subscript the array of unique elements, though.

numpy.unique(ar, return_index=False, return_inverse=False, return_counts=False, axis=None,
*, equal_nan=True, sorted=True)

# Reconstruct the input array from the unique values and inverse:

>>> a = np.array([1, 2, 6, 4, 2, 3, 2])
>>> u, indices = np.unique(a, return_inverse=True)
>>> u
array([1, 2, 3, 4, 6])
>>> indices
array([0, 1, 4, 3, 1, 2, 1])
>>> u[indices]
array([1, 2, 6, 4, 2, 3, 2])


If I had an array of indices that subscripted the original array, I think the following would work.

def aggregateCurveLocations(arrayCurveLocations: DataArray2columns) -> DataArray3columns:
u, indices4arrayCurveLocations = np.unique(arrayCurveLocations, return_fantasy_indices = True)
...
consolidatedDistinctCrossings = np.add.reduceat(arrayCurveLocations, indices4arrayCurveLocations)

I think I'm missing a fundamental concept


I'm trying to duplicate through consolidation, right? But the sort order is irrelevant. "If there are duplicates, then add them together" seems like a straightforward task, so I think I am overlooking something or misunderstanding something.

Appendices

Code


type DataArray2columns = numpy.ndarray[tuple[int, ...], numpy.dtype[numpy.uint64]]
type DataArray3columns = numpy.ndarray[tuple[int, ...], numpy.dtype[numpy.uint64]]

columnsArrayCurveGroups = columnsArrayTotal = 3
columnΩ: int = (columnsArrayTotal - columnsArrayTotal) - 1 # Something _feels_ right about this instead of `= -1`.
columnDistinctCrossings = columnΩ = columnΩ + 1
columnGroupAlpha = columnΩ = columnΩ + 1
columnGroupZulu = columnΩ = columnΩ + 1
if columnΩ != columnsArrayTotal - 1:
message = f"Please inspect the code above this `if` check. '{columnsArrayTotal = }', therefore '{columnΩ = }' must be '{columnsArrayTotal - 1 = }' due to 'zero-indexing.'"
raise ValueError(message)
del columnsArrayTotal, columnΩ

columnsArrayCurveLocations = columnsArrayTotal = 2
columnΩ: int = (columnsArrayTotal - columnsArrayTotal) - 1
columnDistinctCrossings = columnΩ = columnΩ + 1
columnCurveLocations = columnΩ = columnΩ + 1
if columnΩ != columnsArrayTotal - 1:
message = f"Please inspect the code above this `if` check. '{columnsArrayTotal = }', therefore '{columnΩ = }' must be '{columnsArrayTotal - 1 = }' due to 'zero-indexing.'"
raise ValueError(message)
del columnsArrayTotal, columnΩ

def aggregateCurveLocations(arrayCurveLocations: DataArray2columns) -> DataArray3columns:
arrayCurveGroups: DataArray3columns = numpy.tile(
A=numpy.unique(arrayCurveLocations[:, columnCurveLocations])
, reps=(columnsArrayCurveGroups, 1)
).T
arrayCurveGroups[:, columnDistinctCrossings] = 0
numpy.add.at(
arrayCurveGroups[:, columnDistinctCrossings]
, numpy.searchsorted(
a=arrayCurveGroups[:, columnCurveLocations]
, v=arrayCurveLocations[:, columnCurveLocations])
, arrayCurveLocations[:, columnDistinctCrossings]
)
# I'm computing groupZulu from curveLocations that are physically in `arrayCurveGroups`, so I'm using `columnCurveLocations`.
numpy.bitwise_and(arrayCurveGroups[:, columnCurveLocations], numpy.uint64(groupZuluLocator64), out=arrayCurveGroups[:, columnGroupZulu])
numpy.right_shift(arrayCurveGroups[:, columnGroupZulu], 1, out=arrayCurveGroups[:, columnGroupZulu])
# NOTE Do not alphabetize these operations. This column has curveLocations data that groupZulu needs.
arrayCurveGroups[:, columnGroupAlpha] &= groupAlphaLocator64
return arrayCurveGroups


Why do I believe this function is slow?


In VS Code, I used the Flamegraph extension, which uses py-spy, to measure the algorithm's performance on 10 different values. The total running time of each line is displayed in the left column. These values are representative of the many tests I've run. The full run time in this test was 204 seconds, the aggregateCurveLocations function was 107 seconds, and numpy.unique and numpy.searchsorted total to 101 seconds.

Continue reading...