Алгоритм, который сортирует элементы в диапазоне значений в кластеры?

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

Ограничения мудры, я читаю записи в файле, который является общим с работой, которую яделает.Таким образом, я обычно сосредотачиваю свои алгоритмы на выполнении работы, поскольку она читает записи, а не на чтении всего в файле, хранении его в некоторой удобной структуре и последующей работе над ним.В любом случае, я стараюсь избегать сохранения записей из файла, а затем выполнять сортировку по этим значениям, а затем просто проходить через отсортированный список и делать соответствующий вывод.

Я сделал несколько дилетантовМозговой штурм, но прежде чем я проведу много времени, делая тщательный анализ, я чувствую, что я где-то видел это или что есть алгоритм, очень похожий на это.Я не прошу кого-то придумать алгоритм, если вы не чувствуете такой склонности, просто интересуюсь, существуют ли какие-либо существующие, которые решают эту проблему или очень похожую на нее.

Спасибо.

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