如何高效合并含稀疏值的NumPy整数ndarray？

抱歉，我之前提供的信息过多。
抱歉，我之前提供的信息不足。

arrayCurveLocations是一个未排序的ndarray，包含成对整数：curveLocations和distinctCrossings。

若某个curveLocations值在ndarray中多次出现，我需要合并对应行，将其distinctCrossings值相加。

生成的新ndarray无需排序。

“稀疏”值与numpy.bincount #

我认为curveLocations的值属于“稀疏”值：它们几乎不连续，且最大值与最小值差距极大。根据numpy.bincount文档，其输出长度等于np.amax(x)+1。算法每次迭代递减n时都会调用该函数，而最大值由n决定：curveLocationsMAXIMUM: int = 1 << (2 * n + 4)。例如当n为25时，分箱数约为2^54，且大部分分箱为空。

我觉得numpy.unique几乎能满足我的需求。以下是文档中的示例，通过唯一值数组和“逆索引”数组重构原ndarray，但这些索引是针对唯一元素数组的。

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

# 从唯一值和逆索引重构输入数组：

>>> 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])

如果我有一个能下标原数组的索引数组，我认为以下代码可行：

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

我要做的是通过合并去重，对吧？但排序顺序无关紧要。“有重复项就相加”看似简单，所以我觉得自己可能忽略或误解了某些内容。

定义符号的部分代码 #

完整代码运行起来有点麻烦：

from mapFolding.algorithms.oeisIDbyFormula import A000682
for n in range(3,40):
    print(A000682(n))

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

为何我认为该函数运行缓慢？ #

在VS Code中，我使用Flamegraph扩展（基于py-spy）对算法在10个不同值下的性能进行了测试。每行的总运行时间显示在左列，这些值能代表我多次测试的结果。本次测试总运行时间为204秒，aggregateCurveLocations函数耗时107秒，其中numpy.unique和numpy.searchsorted累计耗时101秒。

内容的提问来源于stack exchange，提问作者hunterhogan