Установить операции (объединение, пересечение) в массиве Swift?

100

Существуют ли какие-либо стандартные вызовы библиотеки, которые я могу использовать для выполнения операций с двумя массивами или для самостоятельной реализации такой логики (в идеале как можно более функционально и эффективно)?

functional-programming swift set-operations devios1
источник
Набор можно реализовать поверх словаря, если вы хотите сделать это самостоятельно.
CodaFi 05
@CodaFi Вы имеете в виду использование ключей для обеспечения уникальности?
devios1 05
Не могли бы вы просто использовать `Dictionary <String, Void>?
Дэвид Берри

Ответы:

185

Да, у Свифта есть Setкласс.

let array1 = ["a", "b", "c"]
let array2 = ["a", "b", "d"]

let set1:Set<String> = Set(array1)
let set2:Set<String> = Set(array2)

Swift 3.0+ может выполнять операции с наборами как:

firstSet.union(secondSet)// Union of two sets
firstSet.intersection(secondSet)// Intersection of two sets
firstSet.symmetricDifference(secondSet)// exclusiveOr

Swift 2.0 может вычислять аргументы массива:

set1.union(array2)       // {"a", "b", "c", "d"} 
set1.intersect(array2)   // {"a", "b"}
set1.subtract(array2)    // {"c"}
set1.exclusiveOr(array2) // {"c", "d"}

Swift 1.2+ может рассчитывать по сетам:

set1.union(set2)        // {"a", "b", "c", "d"}
set1.intersect(set2)    // {"a", "b"}
set1.subtract(set2)     // {"c"}
set1.exclusiveOr(set2)  // {"c", "d"}

Если вы используете настраиваемые структуры, вам необходимо реализовать Hashable.

Спасибо Майклу Стерну в комментариях к обновлению Swift 2.0.

Спасибо Амджаду Хусейни в комментариях за информацию Hashable.

Джоэлпаркерхендерсон
источник
8
Обратите внимание, что, по крайней мере, в Swift 2.0 вы можете передавать массив в качестве аргумента этим функциям. Таким образом, set1.union(array2)и set1.exclusiveOr(array2)оба являются законными, в дополнение к формам, показанным выше.
Майкл Стерн
Что делать, если вы хотите пересечь 5 массивов? Или 6? Что делать, если количество массивов неизвестно?
Натан МакКаскл
2
@Nathan Зависит от установленной операции. Например, объединение множеств и пересечение множеств коммутативны и ассоциативны, поэтому вы можете обрабатывать множество множеств, используя итерацию или сцепление. Или вы можете создать собственные методы, использующие аргументы var, такие как Set union_all (...) и correct_all (...).
joelparkerhenderson
Что насчет того, если ваши массивы содержат повторяющиеся значения, например, чтобы определить, является ли $ 0 анаграммой $ 1, где входные символы могут иметь повторяющиеся буквы?
Дэйв Климан,
1
Если вы используете пользовательские структуры, вы должны соответствовать Hashable, что может раздражать, если у вас сложная структура
Амджад Хусейни
0

Нет никаких стандартных вызовов библиотеки, но вы можете посмотреть библиотеку ExSwift . Он включает в себя множество новых функций для массивов, включая разность, пересечение и объединение.

Коннор
источник
1
Предостережение: я без проблем использовал ExSwift для Swift 1.x, но для Swift 2.x он кажется совершенно неработоспособным, и на момент написания этой статьи не обновлялся в течение нескольких месяцев. Есть масса вилок, которым можно уделить больше внимания.
Робин Мачарг
0

Самый эффективный из известных мне методов - использовать годельные числа. Google для кодировки годеля.

Идея такая. Предположим, у вас есть N возможных чисел, и вам нужно составить их наборы. Например, N = 100 000 и вы хотите создать такие наборы, как {1,2,3}, {5, 88, 19000} и т. Д.

Идея состоит в том, чтобы сохранить список из N простых чисел в памяти, и для данного набора {a, b, c, ...} вы кодируете его как

 prime[a]*prime[b]*prime[c]*...

Итак, вы кодируете набор как BigNumber. Операции с BigNumbers, несмотря на то, что они медленнее, чем операции с целыми числами, все же очень быстрые.

Чтобы объединить 2 набора A, B, вы берете

  UNITE(A, B) = lcm(a, b)

наименьшее общее кратное для A и B, поскольку A и B - это множества и оба числа.

Чтобы сделать перекресток,

 INTERSECT(A, B) = gcd (a, b)

наибольший общий делитель.

и так далее.

Эта кодировка называется годелизацией, вы можете найти в Google больше, весь язык арифметики, написанный с использованием логики Фреге, может быть закодирован с помощью чисел таким образом.

Чтобы получить операцию is-member? это очень просто -

ISMEMBER(x, S) = remainder(s,x)==0

Для кардинала немного сложнее -

CARDINAL(S) = # of prime factors in s

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

Alinsoar
источник