Без потери общности примем меньшее множество за A, а большее соответственно за B, поскольку размер множества можно определить за O(1).
Поиск одного элемента в B занимает O(log|B|), всего поисков будет |A|, итого общая оценка O(|A|log|B|).
Отсюда вопрос, а чего собственно вы хотите? :)
В принципе вы можете использовать структуру Disjoint Set Union, она позволяет за амортизированное O(1) проверять в какое множество входит элемент, но таких проверок всё равно понадобится O(|A|).
Ещё можно использовать какие-нибудь методы предпросчёта, например такой: пусть у нас всего N множеств, заведем матрицу NxN, в ячейке (i, j) находится множество, совпадающее с пересечением множеств i и j, оценка на время вставки и удаления O(N), на выписывание пересечения O(|N_i ∩ N_j|). На память O(N^2 * max(|N_i|))
Philipp, если в крупных компаниях, то это потому что ноуты с макосью бесплатно выдают, а нахаляву мак — отличная машинка :)
Тут наверное важно вот на что обратить внимание: мак выбирают в основном из-за того, что это хороший готовый инструмент, а новые инструменты чаще всего делают люди, которым интересно в кишках копаться.
New_one, так это же только первая глава, дальше он объясняет как на основе релюшек сделать минимальную логику, потом обобщает это на транзисторы и вот у вас есть примитивный сумматор, который дальше используется как строительный блок для CPU. Короче зря бросили, книжка отличная :)
Programmir, но корреляцию между качеством образования и успешностью никто не отменял.
Исключительные ситуации возможны, это правда, просто не нужно думать, что ваша ситуация обязательно исключительная — с вероятностью 95% вы не попадаете в топ 5%.
Ninazu,
Такого рода задачами занимается теория информации (это чтобы было куда копать).
Вы, для своей задачи, можете применять например выравнивание над битовыми представлениями данных, или то же расстояние Левенштейна.
Если две последовательности отличаются не слишком сильно, то они ложатся в один бакет, поиск происходит путём сравнения новой последовательности со всеми имеющимися, такая кластеризация для бедных.
Если ваши данные всё-таки не совсем случайные, то можно придумать более хорошее решение.
Александр Туркин, вы видимо путаете что-то. faiss - это библиотека для построения индексов на векторах произвольных размерностей, как строятся вектора не имеет ровным счётом никакого значения (это к слову о facenet), расстояния между ними нужно как-то измерять, это тоже параметр индекса.
https://github.com/facebookresearch/faiss/blob/323...
Здесь реализованы L2 и InnerProduct, если вам нужна какая-то своя метрика, то вы вполне можете её дописать, это не возбраняется, поскольку лицензия BSD. Но зачем она вам?
