Какой алгоритм требует набора?

На моих первых курсах программирования мне сказали, что я должен использовать набор всякий раз, когда мне нужно что-то сделать, например удалить дубликаты чего-либо. Например: чтобы удалить все дубликаты из вектора, выполните итерацию по указанному вектору и добавьте каждый элемент в набор, после чего у вас останутся уникальные вхождения. Однако я мог бы также сделать это, добавив каждый элемент в другой вектор и проверив, существует ли этот элемент. Я предполагаю, что в зависимости от используемого языка может быть разница в производительности. Но есть ли причина использовать набор, отличный от этого?

В основном: какие типы алгоритмов требуют набора и не должны быть сделаны с любым другим типом контейнера?

Вы спрашиваете о наборах конкретно, но я думаю, что ваш вопрос о более широком понятии: абстракция. Вы абсолютно правы, что вы можете использовать Vector для этого (если вы используете Java, вместо этого используйте ArrayList.) Но зачем останавливаться на достигнутом? Для чего вам нужен Вектор? Вы можете сделать все это с массивами.

Когда вам нужно добавить элемент в массив, вы можете просто перебрать каждый элемент, а если его нет, вы добавляете его в конце. Но, на самом деле, вам нужно сначала проверить, есть ли место в массиве. Если нет, вам нужно создать новый массив большего размера и скопировать все существующие элементы из старого массива в новый массив, а затем вы можете добавить новый элемент. Конечно, вам также необходимо обновить каждую ссылку на старый массив, чтобы он указывал на новый. Есть все, что сделано? Большой! Теперь, что мы пытались сделать снова?

Или вместо этого вы можете использовать экземпляр Set и просто вызвать add(). Причина, по которой наборы существуют, состоит в том, что они являются абстракцией, которая полезна для множества общих проблем. Например, предположим, что вы хотите отслеживать элементы и реагировать, когда добавляется новый. Вы вызываете add()набор, и он возвращается trueили falseзависит от того, был ли набор изменен. Вы можете написать это вручную, используя примитивы, но почему?

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

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

Я предполагаю, что в зависимости от используемого языка может быть разница в производительности. Но есть ли причина использовать набор, отличный от этого?

Ах да, (но это не производительность.)

Используйте набор, когда вы можете его использовать, потому что неиспользование этого означает, что вы должны написать дополнительный код. Использование набора позволяет легко читать то, что вы делаете. Все это тестирование на логику уникальности скрыто где-то еще, где вам не нужно об этом думать. Это в месте, которое уже проверено, и вы можете верить, что это работает.

Напишите свой собственный код, чтобы сделать это, и вы должны беспокоиться об этом. BLEH. Кто хочет это сделать?

В основном: какие типы алгоритмов требуют набора и не должны быть сделаны с любым другим типом контейнера?

Не существует алгоритма, который «не должен выполняться с любым другим типом контейнера». Есть просто алгоритмы, которые могут использовать преимущества множеств. Приятно, когда вам не нужно писать дополнительный код.

Теперь нет ничего особенно особенного в этом отношении. Вы всегда должны использовать коллекцию, которая наилучшим образом соответствует вашим потребностям. В Java я нашел эту картинку, чтобы помочь принять это решение. Вы заметите, что у него есть три различных набора.

И, как справедливо отмечает @germi, если вы используете правильный набор для работы, ваш код станет проще для других.

Однако я мог бы также сделать это, добавив каждый элемент в другой вектор и проверив, существует ли этот элемент.

Если вы это сделаете, то реализуете семантику набора поверх структуры векторных данных. Вы пишете дополнительный код (который может содержать ошибки), и результат будет очень медленным, если у вас много записей.

Почему вы хотите сделать это, используя существующую, проверенную, эффективную реализацию набора?

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

Кроме того, множества имеют очень хорошо определенную алгебру. Если у вас есть набор автомобилей, принадлежащих Джорджу, и набор, принадлежащий Алисе, тогда союз, несомненно, является набором, принадлежащим как Джорджу, так и Алисе, даже если Джордж и Алиса владеют одним и тем же автомобилем. Таким образом, алгоритмы, которые должны использовать наборы, - это те, в которых логика участвующих объектов демонстрирует наборные характеристики. Это оказывается довольно распространенным явлением.

Как наборы реализуются и как гарантируется ограничение уникальности, это другой вопрос. Можно надеяться, что удастся найти подходящую реализацию для логики набора, которая устраняет дубликаты, учитывая, что наборы настолько фундаментальны для логики, но даже если вы делаете реализацию самостоятельно, гарантия уникальности присуща вставке элемента в набор и Вам не нужно «проверять, существует ли элемент».

Помимо характеристик производительности (которые очень важны, и их не так легко отбросить), множества очень важны как абстрактная коллекция.

Не могли бы вы эмулировать поведение Set (игнорируя производительность) с массивом? Да, конечно! Каждый раз, когда вы вставляете, вы можете проверить, есть ли элемент в массиве, а затем добавить элемент, только если он еще не был найден. Но это то, что вы сознательно должны осознавать и помнить каждый раз, когда вставляете в набор Array-Psuedo-Set. О, что это, вы вставили один раз напрямую, без предварительной проверки на наличие дубликатов? Хорошо, ваш массив нарушил свой инвариант (что все элементы уникальны и, что эквивалентно, дубликатов не существует).

Так что бы вы сделали, чтобы обойти это? Вы должны создать новый тип данных, назвать его (скажем, PsuedoSet), который оборачивает внутренний массив, и insertпублично предоставляет операцию, которая обеспечит уникальность элементов. Поскольку упакованный массив доступен только через этот общедоступный insertAPI, вы гарантируете, что дубликаты никогда не появятся. Теперь добавьте хеширование, чтобы улучшить производительность containsпроверок, и рано или поздно вы поймете, что реализовали полный цикл Set.

Я бы также ответил с заявлением и последующим вопросом:

На моих первых курсах по программированию мне сказали, что я должен использовать массив, когда мне нужно что-то вроде хранения нескольких упорядоченных элементов чего-либо. Например: хранить коллекцию имен сотрудников. Однако я также мог бы сделать это, выделив необработанную память и установив значение адреса памяти, заданного указателем начала + некоторое смещение.

Не могли бы вы использовать необработанный указатель и фиксированные смещения для имитации массива? Да, конечно! Каждый раз, когда вы вставляете, вы можете проверить, не смещается ли смещение от конца выделенной памяти, с которой вы работаете. Но это то, что вы сознательно должны осознавать и помнить каждый раз, когда вставляете в свой псевдо-массив. О, что это, вы вставили один раз напрямую, без предварительной проверки смещения? Хорошо, есть ошибка Сегментации с вашим именем на нем!

Так что бы вы сделали, чтобы обойти это? Вы должны создать новый тип данных, вызвать его (скажем, PsuedoArray), который обернет указатель и размер, и insertпублично предоставит доступ к операции, которая обеспечит, чтобы смещение не превышало размер. Поскольку упакованные данные доступны только через этот общедоступный insertAPI, вы гарантируете, что переполнения буфера не произойдет. Теперь добавьте некоторые другие вспомогательные функции (изменение размера массива, удаление элементов и т. Д.), И рано или поздно вы поймете, что реализовали полный цикл Array.

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

Алгоритмы на основе множеств широко используются в различных алгоритмах поиска путей и т. Д.

Для ознакомления с теорией множеств ознакомьтесь с этой ссылкой: http://people.umass.edu/partee/NZ_2006/Set%20Theory%20Basics.pdf

Если вам нужна семантика набора, используйте набор. Это позволит избежать ошибок из-за ложных дубликатов, потому что вы забыли удалить вектор / список на каком-то этапе, и это будет быстрее, чем вы можете сделать, постоянно обрезая свой вектор / список.

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

Чтобы вычислить пересечения множества, я перебираю первый массив и отмечаю элементы одним битом. Затем я перебираю второй массив и ищу отмеченные элементы. Вуаля, установите пересечение в линейном времени с гораздо меньшими затратами труда и памяти, чем в хеш-таблице, например, Союзы и различия одинаково легко применять с помощью этого метода. Помогает то, что моя кодовая база вращается вокруг элементов индексации, а не дублирует их (я дублирую индексы на элементы, а не данные самих элементов) и редко нуждается в сортировке, но годами я не использовал заданную структуру данных, так как результат.

У меня также есть некоторый зловредный код на C, который я использую, даже когда элементы не предлагают поля данных для таких целей. Он включает в себя использование памяти самих элементов путем установки наиболее значимого бита (который я никогда не использую) с целью маркировки пройденных элементов. Это довольно грубо, не делайте этого, если вы действительно не работаете на уровне, близком к сборке, но просто хотели бы упомянуть, как это может быть применимо, даже если элементы не предоставляют какое-то поле, специфичное для обхода, если вы можете гарантировать, что определенные биты никогда не будут использованы. Он может вычислить пересечение множества между 200 миллионами элементов (примерно 2,4 гигабайта данных) менее чем за секунду на моем dinky i7. Попробуйте выполнить пересечение множеств между двумя std::setэкземплярами, содержащими по сто миллионов элементов одновременно; даже близко не подходит.

Это в сторону ...

Однако я мог бы также сделать это, добавив каждый элемент в другой вектор и проверив, существует ли этот элемент.

Эта проверка, чтобы увидеть, существует ли элемент в новом векторе, обычно будет линейной временной операцией, которая сделает само пересечение множества квадратичной операцией (взрывная работа, чем больше входной размер). Я рекомендую вышеописанную технику, если вы просто хотите использовать простые старые векторы или массивы и делать это таким образом, чтобы чудесно масштабироваться.

В основном: какие типы алгоритмов требуют набора и не должны быть сделаны с любым другим типом контейнера?

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

Сходя с тангенса

Хорошо, я получил несколько хороших вопросов от JimmyJames относительно этого подхода пересечения множеств. Это немного отклоняется от темы, но, конечно, мне интересно, чтобы больше людей использовали этот базовый навязчивый подход для установки пересечения, чтобы они не строили целые вспомогательные структуры, такие как сбалансированные двоичные деревья и хеш-таблицы, только для целей операций над множествами. Как уже упоминалось, основное требование заключается в том, чтобы списки мелко копировали элементы так, чтобы они индексировали или указывали на общий элемент, который можно «пометить» как пройденный при прохождении первого несортированного списка или массива или чего-либо другого, чтобы затем получить на втором пройти через второй список.

Однако это может быть выполнено практически даже в многопоточном контексте, не затрагивая элементы при условии, что:

1. Два агрегата содержат индексы для элементов.
2. Диапазон индексов не слишком велик (скажем, [0, 2 ^ 26), не миллиарды и более) и достаточно плотно занят.

Это позволяет нам использовать параллельный массив (всего один бит на элемент) для целей операций над множествами. Диаграмма:

Синхронизация потоков необходима только при получении параллельного битового массива из пула и его освобождении обратно в пул (выполняется неявно при выходе из области видимости). Фактические два цикла для выполнения операции set не должны включать в себя синхронизацию потоков. Нам даже не нужно использовать параллельный битовый пул, если поток может просто распределять и освобождать биты локально, но битовый пул может быть удобен для обобщения шаблона в кодовых базах, которые соответствуют этому виду представления данных, где на центральные элементы часто ссылаются по индексу, так что каждый поток не должен беспокоиться об эффективном управлении памятью. Основными примерами для моей области являются системы сущностей-компонентов и представления с индексированными сетками. Оба часто нуждаются в установленных пересечениях и имеют тенденцию ссылаться на все, что хранится централизованно (компоненты и объекты в ECS и вершины, ребра,

Если индексы не заняты и редко разбросаны, то это все еще применимо при разумной разреженной реализации параллельного битового / логического массива, подобного тому, который хранит память только в 512-битных порциях (64 байта на развернутый узел, представляющий 512 смежных индексов). ) и пропускает выделение полностью свободных смежных блоков. Скорее всего, вы уже используете нечто подобное, если ваши центральные структуры данных редко заняты самими элементами.

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

Снова установить пересечения между сотнями миллионов элементов можно за секунду, используя этот подход на очень средней машине, и это в одном потоке.

Это также может быть сделано менее чем за половину времени, если клиенту не нужен список элементов для результирующего пересечения, например, если он хочет только применить некоторую логику к элементам, найденным в обоих списках, после чего он может просто передать указатель на функцию или функтор, или делегат, или что-либо еще, что необходимо вызвать для обработки диапазонов пересекающихся элементов. Что-то на этот счет:

// 'func' receives a range of indices to
// process.
set_intersection(func):
{
    parallel_bits = bit_pool.acquire()

    // Mark the indices found in the first list.
    for each index in list1:
        parallel_bits[index] = 1

    // Look for the first element in the second list 
    // that intersects.
    first = -1
    for each index in list2:
    {
         if parallel_bits[index] == 1:
         {
              first = index
              break
         }
    }

    // Look for elements that don't intersect in the second
    // list to call func for each range of elements that do
    // intersect.
    for each index in list2 starting from first:
    {
        if parallel_bits[index] != 1:
        {
             func(first, index)
             first = index
        }
    }
    If first != list2.num-1:
        func(first, list2.num)
}

... или что-то в этом роде. Самая дорогая часть псевдокода на первой диаграмме находится intersection.append(index)во втором цикле, и это относится даже к std::vectorзаранее зарезервированному размеру меньшего списка.

Что если я все скопирую?

Ну, прекрати это! Если вам нужно установить пересечения, это означает, что вы дублируете данные для пересечения. Скорее всего, даже ваши крошечные объекты не меньше 32-битного индекса. Очень возможно уменьшить диапазон адресации ваших элементов до 2 ^ 32 (2 ^ 32 элемента, а не 2 ^ 32 байта), если вам на самом деле не нужно создавать более ~ 4,3 миллиарда элементов, после чего требуется совершенно другое решение ( и это определенно не использует установленные контейнеры в памяти).

Ключевые матчи

Как насчет случаев, когда нам нужно выполнять операции над множествами, когда элементы не идентичны, но могут иметь совпадающие ключи? В этом случае та же идея, что и выше. Нам просто нужно сопоставить каждый уникальный ключ с индексом. Если ключ является строкой, например, то интернированные строки могут сделать именно это. В этих случаях для отображения строковых ключей на 32-битные индексы требуется хорошая структура данных, такая как trie или хеш-таблица, но нам не нужны такие структуры для выполнения операций над множествами результирующих 32-битных индексов.

Множество очень дешевых и простых алгоритмических решений и структур данных открываются, как эти, когда мы можем работать с индексами для элементов в очень разумном диапазоне, а не во всем диапазоне адресации машины, и поэтому зачастую это более чем стоит того, чтобы быть возможность получить уникальный индекс для каждого уникального ключа.

Я люблю индексы!

Я люблю индексы так же сильно, как пиццу и пиво. Когда мне было 20 с небольшим, я по-настоящему увлекся C ++ и начал проектировать все виды полностью совместимых со стандартами структур данных (включая приемы, необходимые для устранения неоднозначности ctor заполнения из ctor диапазона во время компиляции). Оглядываясь назад, это была большая трата времени.

Если вы вращаете свою базу данных вокруг централизованного хранения элементов в массивах и индексации их, а не хранения их фрагментированным образом и, возможно, по всему адресуемому диапазону машины, то вы можете в конечном итоге исследовать целый мир возможностей алгоритмизации и структуры данных, просто проектирование контейнеров и алгоритмов, которые вращаются вокруг старых intили старых int32_t. И я обнаружил, что конечный результат гораздо эффективнее и проще в обслуживании, когда я не постоянно переносил элементы из одной структуры данных в другую в другую.

В некоторых примерах используются случаи, когда можно просто предположить, что любое уникальное значение Tимеет уникальный индекс и экземпляры будут находиться в центральном массиве:

Многопоточные радикальные сортировки, которые хорошо работают с целыми числами без знака для индексов . На самом деле у меня есть многопоточная сортировка по основанию радиуса, которая занимает около 1/10 времени, чтобы отсортировать сто миллионов элементов как собственную параллельную сортировку Intel, а Intel уже в 4 раза быстрее, чем std::sortдля таких больших входов. Конечно, Intel гораздо более гибок, так как это сортировка на основе сравнения и может сортировать вещи лексикографически, поэтому он сравнивает яблоки с апельсинами. Но здесь мне часто нужны только апельсины, как я мог бы сделать радикальную сортировку только для того, чтобы получить удобные для кэша шаблоны доступа к памяти или быстро отфильтровать дубликаты.

Возможность создавать связанные структуры, такие как связанные списки, деревья, графики, отдельные цепочки хэш-таблиц и т. Д., Без выделения кучи на узел . Мы можем просто разместить узлы навалом, параллельно элементам и связать их вместе с индексами. Сами узлы просто становятся 32-битным индексом для следующего узла и сохраняются в большом массиве, например так:

Удобно для параллельной обработки. Часто связанные структуры не так удобны для параллельной обработки, поскольку по крайней мере неловко пытаться достичь параллелизма в обходе дерева или связанного списка, в отличие, скажем, от простого параллельного выполнения цикла for через массив. С представлением индекса / центрального массива мы всегда можем перейти к этому центральному массиву и обработать все в виде коротких параллельных циклов. У нас всегда есть этот центральный массив всех элементов, которые мы можем обработать таким способом, даже если мы хотим обработать только некоторые (в этот момент вы можете обработать элементы, проиндексированные в отсортированном по радикалам списке, для доступа к кешу через центральный массив).

Может связывать данные с каждым элементом на лету в постоянном времени . Как и в случае описанного выше параллельного массива битов, мы можем легко и очень дешево связать параллельные данные с элементами, скажем, для временной обработки. Это имеет варианты использования помимо временных данных. Например, система ячеек может захотеть позволить пользователям прикреплять столько меш UV-карт к мешу, сколько они хотят. В таком случае мы не можем просто жестко кодировать, сколько UV-карт будет в каждой отдельной вершине и грани, используя подход AoS. Нам нужно иметь возможность связывать такие данные на лету, и параллельные массивы здесь удобны и намного дешевле, чем любой сложный ассоциативный контейнер, даже хеш-таблицы.

Конечно, параллельные массивы не одобряются из-за их склонности к ошибкам синхронизации параллельных массивов друг с другом. Например, всякий раз, когда мы удаляем элемент с индексом 7 из массива «root», мы должны делать то же самое для «детей». Однако в большинстве языков достаточно просто обобщить эту концепцию в контейнер общего назначения, так что хитрая логика для синхронизации параллельных массивов друг с другом должна существовать только в одном месте по всей кодовой базе, и такой контейнер параллельного массива может используйте приведенную выше реализацию разреженного массива, чтобы не тратить много памяти на смежные свободные места в массиве, которые будут возвращаться при последующих вставках.

Дополнительная разработка: разреженное дерево битов

Ладно, я получил запрос на разработку еще чего-то, что, я думаю, было саркастичным, но я все равно это сделаю, потому что это так весело! Если люди хотят перенести эту идею на совершенно новые уровни, то можно выполнить пересечение множества, даже не выполняя линейную петлю через N + M элементов. Это моя окончательная структура данных, которую я использовал целую вечность и в основном модели set<int>:

Причина, по которой он может выполнять пересечения наборов, даже не проверяя каждый элемент в обоих списках, заключается в том, что один бит набора в корне иерархии может указывать на то, что, скажем, миллион смежных элементов занят в наборе. Просто проверив один бит, мы можем узнать, что N индексов в диапазоне [first,first+N)находятся в наборе, где N может быть очень большим числом.

Я фактически использую это как оптимизатор цикла при обходе занятых индексов, потому что, скажем, в наборе занято 8 миллионов индексов. Ну, обычно мы должны были бы получить доступ к 8 миллионам целых чисел в памяти в этом случае. С этим он потенциально может просто проверить несколько битов и найти диапазоны индексов занятых индексов для циклического прохождения. Кроме того, диапазоны индексов, с которыми он работает, расположены в отсортированном порядке, что обеспечивает очень удобный последовательный доступ к кешу, а не, скажем, итерацию по несортированному массиву индексов, используемых для доступа к исходным данным элемента. Конечно, этот метод работает хуже в крайне редких случаях, при этом в худшем случае все индексы равны четному числу (или каждому нечетному), и в этом случае нет смежных областей вообще. Но в моих случаях использования, по крайней мере,

Чтобы проверить, содержит ли набор, содержащий n элементов, другой элемент X, обычно требуется постоянное время. Чтобы проверить, содержит ли массив, содержащий n элементов, другой элемент X, обычно требуется O (n) времени. Это плохо, но если вы хотите удалить дубликаты из n элементов, внезапно это займет O (n) времени вместо O (n ^ 2); 100 000 предметов поставят ваш компьютер на колени.

И вы спрашиваете больше причин? "Помимо съемок, вам понравился вечер, миссис Линкольн?"