Как провести операцию пересечения множеств (массивы) в golang?

Question

[lelvisl]

Добрый день!

Есть два массива разной длинный с переменными (ну например string)

Возможна ли в golang стандартными средствами операция, которая выдаст пересечение двух этих массивов - переменные, которые находятся в обоих массивах?

Answer 1

[lega]

Можно сделать map[string]int, и сделать по одному проходу для каждого массива где в каждой итерации будете увеличивать значение в map на 1 (где ключ = слово из массива).
В итоге в map будут лежать ключи со значением 2 - это пересечения, а где 1 - наоборот "уникальные".

Comments

[lelvisl]

С ходу сложно в глову легло, ща нарисую на листике и попробую.

[lega]

Вот сделал пример: https://play.golang.org/p/Xh009uAy-M
4 режима:
1 - те что есть только в левом массиве
2 - те что только в правом
3 - пересечение, то что вам нужно
4 - это те что в пересечение не попали

формируется за 1 проход, будет работать быстрее чем ваш квадратный перебор.

[lelvisl]

lega: Спасибо большое!

Answer 2

[Кирилл]

нет, но её несложно и самому написать

Comments

[lelvisl]

Я написал, но оно работает медленно. Потому и спросил - может go умеет это делать быстро.

[Кирилл]

может, скорее всего нужно переписать то что уже написанно) go написан на go, поэтому "go умеет это делать быстро" не совсем корректно

сколько данных и пример вашей реализации давайте ;)

[lelvisl]

package main

import (
"fmt"
)

func main() {
foo := []string{}
bar := []string{}
baz := []string{} //пересечение массивов
foo = append(foo, "a")
foo = append(foo, "b")
foo = append(foo, "c")
foo = append(foo, "d")
bar = append(bar, "r")
bar = append(bar, "a")
bar = append(bar, "d")

for i := 0; i < len(foo); i++ {
for j := 0; j < len(bar); j++ {
if foo[i] == bar[j] {
baz = append(baz, foo[i])
}
}
}
fmt.Println(baz)
}

Просто эту операцию проводить нужно 500 тысяч раз)
P.S. пока думаю как это запаралелить

[Илья]

lelvisl: Если один массив используется много, то сделать с сортировкой. А если элементы внутри массива, в котором искать, не повторяются, то ещё и удалять из него.

[lelvisl]

первый массив - от 3 до 10 элементов. второй тоже не больше 10.

Ни в первом ни во втором нет повторений, все строковые.

Суть в том, что сейчас у меня 500 тысяч первых массивов. Ща думаю как распаралелить, и как писать вывод в единое место.

[Никита]

lelvisl: Вам нужно 500к раз создать новые слайсы? или 1 раз их создать, но их размерность 500к и у вас цикл 500к раз прокручивает?

[lelvisl]

Никита: Есть 500к массивов, в которых теги. Каждый из них надо сверить с массивом, в котором нудные мне теги, и я на этой операции получаю список массивов, которые имеют нужные мне теги.

[Никита]

lelvisl: Вам желательно перестроить базу этих массивов с тегами где будет участвовать ещё один массив, в котором описаны зависимости. ИМХО, такое количество конечно лучше хранить в БД и из неё доставать данные одной выборкой. Даже SQLite на мобильнике выполнит такую операцию довольно быстро, ну уж точно быстрее простого перебора.
Если нет возможности менять исходные данные ничего быстрее вашего кода вы не найдёте, т.к. это физически невозможно. Такие объёмы данных надо предварительно подготавливать для дальнейшей работы.

[Кирилл]

lelvisl: ну у вас же не задача на нахождение пересечения 2-х массивов, собственно цель то этого всего в чем, зачем вам искать пересечение в 500к слайсов ?

[lelvisl]

Кирилл: суть в том, что у меня уже активная иархитектура, которую я не пересторю.
DB1 - запись х с параметрами
DB2 - запись х с другими параметрами

Сначала я селект делаю в DB1, вынимаю список x по параметру а

потом по этому списку выгружаю записи из DB2, сверяю теги, с нужными мне и выгружаю окончательный список

[Кирилл]

lelvisl: не очень то эффективно из БД вытаскивать 500к записей, вы тут явно не в Го упираетесь

[Никита]

lelvisl: Изменять нельзя, но добавить никогда не проблема) создайте DB3, прочтите выше мой комментарий. И как заметил Кирилл go здесь не при чем, вы изначально не в ту сторону уперлись

[lelvisl]

Никита: Не варинат пересторить базы, на них уже работает апликейшн. Мое дело - неофициально вытаскивать данные и самостоятельно строить статистику
(вендор заломил огромные бабки за статистику.)

А тут без внешней надстройки над базой никак, я просто выбрал го, так как им в данный момент активно пользуюсь.

[Никита]

lelvisl: Вы меня чуть чуть не поняли, стройте свою базу с ссылками или полностью копирующую необходимые данные, но уже в удобном для вас виде. Если контент часто меняется, то можно запустить по таймингу граббер. Но как ни крути преподготовка вам обязательно нужна иначе физически невозможно ускорение.

[lelvisl]

Никита: говорю же, базы все могу только "читать", ничего менять не имею возможности)

[Никита]

lelvisl: Я писал выше: "Вам желательно перестроить базу этих массивов с тегами где будет участвовать ещё один массив, в котором описаны зависимости.", кстати что товарищ lega вам уже готовое реализовал.