将值范围内的元素分类为簇的算法？

Question

本质上，我想列出诸如...

a 345
b 762
c 983
d 425
e 45
...

并给定最大距离，为包含该范围内其他元素的每个元素创建聚类。例如，如果我将上面的最大距离指定为 300，则聚类将是...

a 345
d 425
e 45

b 762
c 983

c 983
b 762

d 425
a 345

e 45
a 345

约束明智，我正在读取文件中的条目，这在我正在做的工作中很常见。因此，我通常将算法的重点放在读取条目时进行工作，而不是读取文件中的所有内容，将其存储在一些方便的结构中，然后对其进行处理。无论如何，存储文件中的条目然后根据这些值执行排序，然后只遍历排序列表并进行适当的输出是我试图避免的事情。

我已经进行了一些外行的头脑 Storm ，但在我花大量时间进行彻底分析之前，我觉得我已经在某个地方看到过这个或者有一个与此非常相似的算法。除非您愿意，否则我不会要求某人提出一种算法，我只是想知道是否有任何现有的算法可以解决这个问题或与它非常相似的问题。

谢谢。

Answer 1

另一种可能的洪水填充算法使用一些改进的二进制搜索来减少所需比较的数量:

Pseudo-code:
def clustersWithinRange(values, distance): //Should run in O(n log n)
    sortedValues = values.sorted()
    valueCount = values.len()
    clusters = Array()

    cachedLower = 0
    cachedUpper = values.len
    cachedValue = null

    for i in range(0, valueCount):
        value = sortedValues.get(i)
        if (cachedValue == value): //duplicate value, no need to calculate twice
            clusters.add(clusters.get(i).copy()) //simply clone last cluster or nop if no duplicate clusters wanted
        else:
            lower = sortedValues.binaryBoundSearch(values, value, distance, cachedLower, i, LowerBoundMatchFlag)
            upper = sortedValues.binaryBoundSearch(values, value, distance, cachedUpper, valueCount, UpperBoundMatchFlag)
            clusters.add(sortedValues[lower:upper+1])//add sublist within (and including) lower...upper to clusters
            cachedLower = lower
            cachedUpper = upper
    return clusters

    def withinDistance(valueA, valueB, distance):
        return abs(valueA - valueB) <= distance

    def binaryBoundSearch(values, value, distance, low, high, searchFlag):
        // Possible values of searchFlag:
        // "LowerBoundMatchFlag" to get the leftmost found match.
        // "UpperBoundMatchFlag" to get the rightmost found match.
        if (high < low):
            return -1 // not found
        mid = low + ((high - low) / 2)
        matchPosition = -1
        aValue = values[mid]
        if (withinDistance(aValue, value, distance)):
            matchPosition = mid
            displacement = (searchFlag == LowerBoundMatchFlag) ? -1 : 1
            if (mid > low && mid < high && withinDistance(values.get(mid + displacement), value, distance)):
                newLow = (searchFlag == LowerBoundMatchFlag) ? low : mid + displacement
                newHigh = (searchFlag == LowerBoundMatchFlag) ? mid + displacement : high
                matchPosition = binaryBoundSearch(values, value, newLow, newHigh, searchFlag)
        else:
            flag = compare(aValue, value)
            if (flag < 0): // current position too far left
                matchPosition = binaryBoundSearch(values, value, mid + 1, high, searchFlag)
            else if (flag > 0): // current position too far right
                matchPosition = binaryBoundSearch(values, value, low, mid - 1, searchFlag)

        return matchPosition