Теория множеств. Знаю, как многие пугаются математики, но конкретно теория множеств (наивная) очень проста и понятна. Более того, мы постоянно используем её элементы в обычной жизни. А уж в программировании она встречается на каждом шагу.
Основное понятие теории множеств, как ни удивительно - множество . Множеством обозначают совокупность объектов произвольной природы, рассматривающихся как единое целое. Простейший пример - цифры. Множество арабских цифр включает в себя 10 элементов и является конечным . Понятие конечности носит интуитивный характер и обозначает, что в множестве конечное число элементов.
Пример бесконечного множества - натуральные числа. В свою очередь множество натуральных чисел является подмножеством целых чисел, которые в свою очередь являются подмножеством рациональных чисел и так далее.
«Подмножество» означает, что все элементы одного множества также входят в другое множество, называемое надмножеством (по отношению к подмножеству).
Представление множеств кружками довольно удобно. Можно быстро оценить как друг с другом соотносятся разные множества.
Но математические объекты, такие как числа, не единственные возможные объекты множеств. Множеством можно назвать группу людей, стоящих на остановке в ожидании своего автобуса, или жильцов квартир одного дома, города или страны. Любой набор любых объектов, которые мы хотим рассматривать как одно целое.
Главное для нас в теории множеств - операции над ними. К ним относятся: дополнение, объединение, пересечение, разность, декартово произведение и некоторые другие.
Простой пример. Когда в Фейсбуке вы заходите на страницу другого человека, то Фейсбук показывает вам блок с общими друзьями. Если принять, что ваши друзья и друзья вашего друга - два множества, то общие друзья - множество, полученное как пересечение исходных множеств друзей.
Переходя к программированию, можно заметить, что массив очень похож на множество, и его действительно можно так рассматривать. Почему это так важно? Понимая принципы, на которых основаны некоторые операции, вы сможете реализовывать их наиболее быстрым и эффективным способом. Например, зная, что вам нужна операция пересечения множеств в php, вы можете попытаться найти функцию, которая делает поставленную задачу. Для этого достаточно ввести в гугл запрос: php set intersect (set - множество, intersect - пересечение). Первая (по крайней мере, у меня) ссылка в поисковой выдаче ведет на нужную функцию array_intersect . Тоже самое вас ждет и с другими операциями. Это частичный ответ на вопрос «нужна ли математика программистам?».
Кстати, не во всех языках есть встроенные функции для работы со множествами. В некоторых для этого нужно ставить дополнительные библиотеки, а в некоторых, например, в Ruby, операции со множествами реализованы с использованием арифметических операторов (объединение множеств: coll1 + coll2).
Отдельно стоит сказать, что реляционные базы данных построены на идеях реляционной алгебры, в которой теория множеств играет центральную роль. Базы данных - неотъемлемая часть веб-разработки, и позже мы с ними познакомимся.
Рассмотрим основные операции:
Пересечение
Пересечением множеств называется множество, в которое входят элементы, встречающиеся во всех данных множествах одновременно.
["vasya", "petya"]
Эта функция принимает любое количество массивов. То есть вы можете находить пересечение любого количества массивов за один вызов.
Объединение
Объединением множеств называется множество, в которое входят элементы всех данных множеств. Объединение множеств в php нельзя сделать одним вызовом, но его можно имитировать, соединив две функции:
["vasya", "kolya", "petya", "igor", "petya", "sergey", "vasya", "sasha"]; // unique удаляет дубли $sharedFriends = array_unique($friends); // => ["vasya", "kolya", "petya", "igor", "sergey", "sasha"]
Дополнение (разность)
Разностью двух множеств называется множество, в которое входят элементы первого множества, не входящие во второе. В программировании такая операция часто называется diff .
["kolya"]
Принадлежность множеству
Проверку принадлежности элемента множеству можно выполнить с помощью функции in_array:
Эти функции позволят вам различными способами оперировать с массивами. Массивы идеально подходят для хранения, изменения и работы с наборами переменных.
Поддерживаются одно- и многоразмерные массивы, как созданные пользователем, так и возвращенные в качестве результата какой-либо функцией. Существуют специальные функции для работы с базами данных, облегчающие работу с массивами данных, возвращаемых в результате выполнения запросов; также существуют функции, возвращающие массивы в качестве результата.
Чтобы получить больше сведений о том, каким образом создаются и используются массивы в PHP, обратитесь к главе Массивы данного руководства.
Установка
Для использования этих функций не требуется проведение установки, поскольку они являются частью ядра PHP.
Предопределенные константы
Перечисленные ниже константы всегда доступны как часть ядра PHP.
CASE_LOWER (integer)
CASE_LOWER используется с функцией array_change_key_case() для указания необходимости преобразования ключей массива в нижний регистр символов. По умолчанию функцией array_change_key_case() используется именно эта константа.
CASE_UPPER (integer)CASE_UPPER используется с функцией array_change_key_case() для указания необходимости преобразования ключей массива в верхний регистр символов.
array_change_key_case -- Возвращает массив, символьные ключи которого преобразованы в верхний или нижний регистр символов array_chunk -- Разбить массив на части array_combine -- Создать новый массив, используя один массив в качестве ключей, а другой в качестве соответствующих значений array_count_values -- Подсчитать количество всех значений массива array_diff_assoc -- Вычислить расхождение в массивах с дополнительной проверкой индекса array_diff_key -- Вычислить расхождение в массивах, сравнивая ключи array_diff_uassoc -- Вычислить расхождение в массивах с дополнительной проверкой индекса, осуществляемой при помощи функции, определённой пользователем array_diff_ukey -- Вычислить расхождение в массивах, используя функцию обратного вызова для сравнения ключей array_diff -- Вычислить расхождение в массивах array_fill -- Заполнить массив определенным значением array_filter -- Применяет фильтр к массиву, используя функцию обратного вызова array_flip -- Поменять местами значения массива array_intersect_assoc -- Вычислить схождение массивов с дополнительной проверкой индекса array_intersect_key -- Вычислить пересечение массивов, сравнивая ключи array_intersect_uassoc -- Вычислить пересечение массивов с дополнительной проверкой индекса, осуществляемой при помощи функции, определённой пользователем array_intersect_ukey -- Вычислить пересечение массивов, используя функцию обратного вызова для сравнения ключей array_intersect -- Вычислить схождение массивов array_key_exists -- Проверить, присутствует ли в массиве указанный ключ или индекс array_keys -- Выбрать все ключи массива array_map -- Применить функцию обратного вызова ко всем элементам указанных массивов array_merge_recursive -- Рекурсивно слить два или большее количество массивов array_merge -- Слить два или большее количество массивов array_multisort -- Сортировать несколько массивов или многомерные массивы array_pad -- Увеличить размер массива до заданной величины array_pop -- Извлечь последний элемент массива array_product -- Вычислить произведение значений массива array_push -- Добавить один или несколько элеметов в конец массива array_rand -- Выбрать одно или несколько случайных значений из массива array_reduce -- Итеративно уменьшить массив к единственному значению, используя функцию обратного вызова array_reverse -- Возвращает массив с элементами в обратном порядке array_search -- Осуществляет поиск данного значения в массиве и возвращает соответствующий ключ в случае удачи array_shift -- Извлечь первый элемент массива array_slice -- Выбрать срез массива array_splice -- Удалить последовательность элементов массива и заменить её другой последовательностью array_sum -- Вычислить сумму значений массива array_udiff_assoc -- Вычислить расхождение в массивах с дополнительной проверкой индексов, используя для сравнения значений функцию обратного вызова array_udiff_uassoc -- Вычислить расхождение в массивах с дополнительной проверкой индексов, используя для сравнения значений и индексов функцию обратного вызова array_udiff -- Вычислить расхождение массивов, используя для сравнения функцию обратного вызова array_uintersect_assoc -- Вычислить пересечение массивов с дополнительной проверкой индексов, используя для сравнения значений функцию обратного вызова array_uintersect_uassoc -- Вычислить пересечение массивов с дополнительной проверкой индекса, используя для сравнения индексов и значений функцию обратного вызова array_uintersect -- Вычислить пересечение массивов, используя для сравнения значений функцию обратного вызова array_unique -- Убрать повторяющиеся значения из массива array_unshift -- Добавить один или несколько элементов в начало массива array_values -- Выбрать все значения массива array_walk_recursive -- Рекурсивно применить пользовательскую функцию к каждому элементу массива array_walk -- Применить пользовательскую функцию к каждому члену массива array -- Создать массив arsort -- Отсортировать массив в обратном порядке, сохраняя ключи asort -- Отсортировать массив, сохраняя ключи compact -- Создать массив, содержащий названия переменных и их значения
ЗадачаЕсть два массива, и требуется найти их объединение (все элементы, но если элемент входит в оба массива, он учитывается один раз), пересечение (элементы, входящие в оба массива) или разность (элементы одного массива, не присутствующие в другом).
Решение
Для определения объединения:
$union = array_unique(array_merge($a, $b));
Для вычисления пересечения:
$intersection = array_intersection($a, $b);
Для нахождения простой разности:
$difference = array_diff($a, $b);
И для получения симметрической разности (исключающее ИЛИ):
Обсуждение
Многие из необходимых для таких вычислений компонентов встроены в PHP, нужно только объединить их в соответствующей последовательности.
При получении объединения из двух массивов создается один гигантский массив со всеми значениями исходных массивов. Но функция array_merge() разрешает дубликаты значений при объединении двух числовых массивов, поэтому нужно вызвать функцию array_unique(),
чтобы отфильтровать такие элементы.
Но при этом могут образоваться пропуски, поскольку функция array_unique() не уплотняет массив. Однако это не представляет затруднения, поскольку и оператор foreach, и функция each() без помех обрабатывают редко заполненные массивы.
Функция для вычисления пересечения имеет простое имя array_intersection() и не требует дополнительных усилий.
Функция array_diff() возвращает массив, содержащий все уникальные элементы массива $old, которые не входят в массив $new. Это называется простой разностью:
$difference = array_diff($old, $new);
Array
=> not
=> to
)
Результирующий массив $difference содержит "not" и "to", так как функция array_diff() чувствительна к регистру. В него не входит элемент "whatever", поскольку его нет в массиве $old.
Чтобы получить обратную разность, или, другими словами, найти уникальные элементы массива $new, отсутствующие в массиве $old, нужно поменять местами аргументы:
$old = array("To", "be", "or", "not", "to", "be");
$new = array("To", "be", "or", "whatever");
$reverse_diff = array_diff($new, $old);
Array
=> whatever
)
Массив $reverse_diff содержит только элемент "whatever".
Если нужно применить функцию или другой фильтр в функции array_diff(), встройте свой собственный алгоритм нахождения разности (вычитания):
// применим нечувствительный к регистру алгоритм вычитания; разность -i
$seen = array();
foreach ($new as $n) {
$seen++;
}
foreach ($old as $o) {
$o = strtolower($o);
if (!$seen[$o]) { $diff[$o] = $o; }
}
Первый оператор foreach создает ассоциативный массив для дальнейшего поиска.
Затем выполняется цикл по массиву $old и, если в процессе поиска элемент не найден, то он добавляется в массив $diff.
Этот процесс можно ускорить, объединив функции array_diff() и array_map():
$diff = array_diff(array_map("strtolower", $old),
array_map("strtolower", $new));
Симметрическая разность – это то, что принадлежит $a, но не принадлежит $b, плюс то, что есть в $b, но нет в $a:
$difference = array_merge(array_diff($a, $b), array_diff($b, $a));
Однажды установленный, алгоритм движется вперед. Функция array_diff() вызывается дважды и определяет две разности. Затем они объединяются в один массив. Нет необходимости вызывать функцию array_unique(), так как эти массивы были специально сконструированы как не имеющие общих элементов.
