В Go я использую int
для представления элементов набора, отсортированные []int
для представления подмножества и [][]int
для представления набора подмножеств. Не допускается наличие двух одинаковых []int
фрагментов (подмножеств). Таким образом, учитывая некоторые var setOfSubets [][]int
, я хотел бы обнаружить повторяющиеся фрагменты []int
в setOfSubets
. Каков эффективный идоматический способ обнаружения этих дубликатов?
Можно предположить, что элементы подмножества отсортированы.
В моей программе я возвращаю ошибку при обнаружении первого дубликата.
Например, пользователь может создать setOfSubsets
setOfSubsets := make([][]int, 0)
subSetA := []int{0, 1} // 0 and 1 are elements
subSetB := []int{0, 2} // 0 and 2 are elements
subSetADuplicate := []int{0, 1} // 0 and 1 are elements
setOfSubsets = append(setOfSubsets, subSetA)
setOfSubsets = append(setOfSubsets, subSetB)
setOfSubsets = append(setOfSubsets, subSetADuplicate)
// many more subsets added before the client calls
check(setOfSubets)
тогда мой код check(setOfSubsets [][]int) error
должен обнаружить, что {0, 1}
дублируется. В реальной программе могут быть тысячи элементов и, возможно, миллионы подмножеств. Чтобы внести ясность, мой вопрос в том, как лучше писать check(setOfSubsets [][]int)
Я думал об использовании карты с []int
в качестве ключа, но понял, что в Go это запрещено. Я также рассматривал возможность сортировки набора подмножеств, а затем проверки соседних подмножеств []int
срезов, но я не уверен, что это идиоматично или эффективно.
@Dave В этом случае это потребует этапа преобразования, и я не понимаю, как это может быть просто для подмножеств с тысячами элементов. Тем не менее, я думаю, что трюки с битами могут быть забавными, а иногда и полезными.
Если вы застряли на куске, вы не сможете хорошо выполнить много подходов. Лучшее, что я могу придумать, — это сортировка вставкой при добавлении наборов, поэтому проверка может быть O (n). Вам действительно нужно какое-то дерево здесь.
Я использую Rust для экстремальной теории графов, и хаки с битами жизненно важны для того, чтобы сделать что-либо в разумные сроки. Похоже, ваши наборы слишком велики для целых чисел, но в Go может быть библиотека битовых векторов, которая позволит это сделать. Или вы можете посмотреть здесь, где у кого-то была такая же проблема: forum.golangbridge.org/t/hashcode-for-a-array/6661
Для 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
Это красиво и просто, но имеет квадратичную сложность. Я думаю, что это будет очень медленно для миллионов подмножеств.
Для более быстрой работы, рассмотрите ли вы возможность использования одного целого числа для каждого набора/подмножества с битами, представляющими членство? Тогда проверка на наличие дублей осуществляется за O(1) путем сохранения хеш-набора видимых наборов/подмножеств.