Как я могу обнаружить повторяющиеся фрагменты целых чисел в Go?

Для map. Вы можете отсортировать и преобразовать каждый []int в строку. Я считаю, что это самое простое решение. Более сложный хэш можно было бы присвоить каждому значению в []int соответствующему простому числу (например, если у вас есть только положительные числа: 0->2, 1->3, 2->5 и т. д.) и умножить их. Продукт будет ключом, который напрямую скажет вам, равны ли два среза или нет. Но конечно. это может быстро выйти из-под контроля, если длина срезов int велика или если диапазон возможных значений int велик и, следовательно, требует больших простых чисел.

Если вас устраивает перебор нескольких отсортированных фрагментов, то slices.BinarySearch, вероятно, будет хорошим началом. Вам все равно придется перебирать все (возможно, миллионы) фрагментов и проверять, присутствует ли заданное число, но время для каждой проверки будет «всего» O(log n). Вы можете сначала сравнить длину срезов, чтобы ускорить этот процесс. Чтобы еще больше ускорить этот процесс, вы можете отсортировать [][]int по наибольшему значению в каждом []int и, следовательно, применить некоторый «мета» двоичный поиск, выделяя фрагменты []int, которые не могут содержать искомый фрагмент. Здесь вам нужен способ быстро узнать, какое на самом деле наибольшее число в []int, например, отсортировав их или заменив на struct IntSlice {Highest int, Values []int}.

Как почти (?) всегда, чем быстрее должен быть поиск, тем больше времени займет запись в структуру, поэтому вам следует быть осторожными, когда вы переусердствуете. Трудно сказать, какой подход лучше, поскольку это зависит от размера каждого среза, диапазона чисел в каждом срезе, количества операций чтения по сравнению с количеством записей/обновлений [][]int, распределения и т. д.

Один из простых подходов — сортировка subsets []][]int, в результате которой повторяющиеся подмножества будут располагаться рядом друг с другом (может быть несколько групп повторяющихся элементов). Затем дублирующиеся подмножества можно найти, проверив, равны ли соседние подмножества. Приведенный ниже пример кода возвращает nil, если дубликатов нет (все подмножества уникальны), или error об одном найденном дубликате (их может быть больше).

func checkSubsetsForDuplicates(subsets [][]int) error {
    subsetsCopy := make([][]int, len(subsets))
    // This copy could be omitted if it is ok to change the order of subsets
    copy(subsetsCopy, subsets)
    slices.SortFunc(subsetsCopy, slices.Compare)
    prevSubset := subsetsCopy[0]
    for _, subset := range subsetsCopy[1:] {
        if slices.Equal(prevSubset, subset) {
            return fmt.Errorf(
                "duplicate subsets are not allowed. The subset %v was found twice",
                subset)
        }
        prevSubset = subset
    }
    return nil
}

Я протестировал этот подход, используя

func BenchmarkCheckSubsetsForDuplicates(b *testing.B) {
    // Use combinations to get unique subsets.
    subsets := combin.Combinations(25, 10)    //    "gonum.org/v1/gonum/stat/combin"
    assert.Assert(b, len(subsets) == 3268760) // expected number of combinations

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        b.StopTimer()
        // Shuffle for an unbiased order of the subsets
        rand.Shuffle(len(subsets), func(i, j int) { subsets[i], subsets[j] = subsets[j], subsets[i] })
        b.StartTimer()
        err := checkSubsetsForDuplicates(subsets)
        assert.NilError(b, err)
    }

получение результатов

cpu: Intel(R) Processor 5Y10 CPU @ 0.80GHz
BenchmarkCheckSubsetsForDuplicates-4                  1        4126782886 ns/op
BenchmarkCheckSubsetsForDuplicates-4                  1        3947514637 ns/op
BenchmarkCheckSubsetsForDuplicates-4                  1        3824476894 ns/op
BenchmarkCheckSubsetsForDuplicates-4                  1        3805860089 ns/op
PASS

на моем 8-летнем ноутбуке. Для этих данных checkSubsetsForDuplicates занимает около 4 секунд. Результаты синхронизации будут зависеть от конкретных данных, но я удовлетворил «миллионы подмножеств», как указано в вопросе.

Вы можете написать свою функцию check() следующим образом:

func check(sos [][]int) error {
    for i, arr1 := range sos {
        for j, arr2 := range sos {

            // no point in comparing an array to itself
            // or repeating a comparison that was already made
            if i <= j {
                continue
            }
            if slices.Compare(arr1, arr2) == 0 {
                return fmt.Errorf("arrays %d and %d are the same: %v", i, j, arr1)
            }

        }

    }
    return nil
}

Игровая площадка: https://go.dev/play/p/lyxpgtXF4OX