Быстрое сравнение списков

Я понял, что надо сравнить 2 не списка а множества, т.к. порядок элементов в контейнере не важен, при этом отношение порядка на элементах не определено? Равенство определено, раз сравнивать хотите. Можно сделать хэш-таблицу и заполнить ее по одному и другому списку с хешами по элементам и инкрементом по значению. Это будет О(n+m). А потом пробежаться по ней, и если везде двойки - то списки равны (как множества). Пробежка тоже за О(max(m,n)).

А что понимается под сравнением списков, что является результатом? Совпадение наборов элементов?

Операции больше/меньше можно ввести всегда. Для POD-типов тупо побайтно (лексикографически) например.

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

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

Ну дык если операция отношения определена, то набиваем из одного списка множество (std::set например), потом идем по другому списку и множество чистим. И не надо хэшей.

Если операция отношения не определена (хотя я не понимаю почему ее нельзя ввести - ее ВСЕГДА можно ввести), то тогда хуже... ну тогда множество надо строить на основе хэша, разуруливая коллизии, Вы правы. ну например хэш-таблица (классическая), где значениями являются сами элементы.

Надо выбрать хороший хеш для перестраховки.

В общем случае «это фантастика»(c)

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

В общем да. Порядок не то, чтобы совсем не важен, но его трудно ввести для целей сравнения. Ну например, представь, что надо сравнить два разных библиотечных каталога разных библиотек. В которых у одних и тех же книжек и журналов могут по разному записаны авторы, где-то полное ФИО, где-то сокращения, то же и с названиями, есть ещё понятие схожести для изданий разных лет и т.п.

Можно сделать хэш-таблицу и заполнить ее по одному и другому списку с хешами по элементам и инкрементом по значению. Это будет О(n+m). А потом пробежаться по ней, и если везде двойки - то списки равны (как множества). Пробежка тоже за О(max(m,n)).

Проблема в том, что само сравнение не совсем чёткое. Я забыл об этом важном моменте сказать. Хотя можно попробовать подумать, чтобы хэши близких элементов были близки. Обычно хэш-функцию стараются сделать наоборот, но тут. хм. В общем, идея, не знаю правда, что получится.

Вот если сравнение нечеткое, то это уже интересней гораздо.

Можно ли ввести метрику какую то (чиселку, показывающую насколько два элемента отличаются в каких то попугаях), и сказать что если местрика меньше epsilon то элементы равны?

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

Ответил в предыдущем сообщении. В том-то и некоторая проблема, что совпадения нечёткие.

Операции больше/меньше можно ввести всегда.

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

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

Можно ли ввести метрику какую то (чиселку, показывающую насколько два элемента отличаются в каких то попугаях), и сказать что если местрика меньше epsilon то элементы равны?

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

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

А скольки мерное пространство (сколько компонент в каждом элементе)?

Это все работает только для точного сравнения.

Есть ли хитрые способы это сделать быстрее чем O(n^2) для не отсортированных списков,

ты не поверишь но - есть и быстрее квадратичного способа сравнение двух неупорядоченных списков - например.

ШАГ №1 nlogn упорядочиваешь списки , дальше сам.

и не важно если нет на элементах отношения полного порядка - достаточно частичного - используешь топологическую - затем на «поколениях» делаешь сличение множеств.

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

Ну если можно так загрубить, то да, Вы правы;-)

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

4 или 5, где-то так.

если известно что вы хотите делать с результатом сравнения то конечно есть. Hint: вернуть функцию это вообще O(1) :-)

а если ещё известно как эти списки получаются, то для множеств можно найти более эффективное представление чем «неотсортированный список»

кстати, ответ о том что «два неотсортированных списка не равны» вы и так в среднем получаете за время O(ln n).

Ну тогда ассоциативный массив без вариантов.

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

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

а если ещё известно как эти списки получаются, то для множеств можно найти более эффективное представление чем «неотсортированный список»

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

кстати, ответ о том что «два неотсортированных списка не равны» вы и так в среднем получаете за время O(ln n).

Нужно не отношения равенства, а пересечение множеств найти.

Нужно не отношения равенства, а пересечение множеств найти.

отдавай итератор.

отдавай итератор.

Да при чём тут конкретные детали реализации? Прежде чем его отдавать надо понять как его формировать. Впрочем, обсуждение в теме навело на кое-какие мысли. Хотя бы частичные отношения, наверное, можно придумать.

Да при чём тут конкретные детали реализации?

при том что тут раздел Dev. :-)

Прежде чем его отдавать надо понять как его формировать

в чём проблема? имея множества A,B представленные списками, получить итераторы для множеств A+B, A*B, A/B - это на уровне учебника..

в чём проблема? имея множества A,B представленные списками, получить итераторы для множеств A+B, A*B, A/B - это на уровне учебника..

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

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

Проблема в скорости.

где-то 50% «проблем в скорости» озвучиваемых на ЛОР, на самом деле «грех преждевременной оптимизации»

а потом любая предварительная обработка (сортировка,ранжирование и проч) делают твой алгоритм строго линейным и прожорливым по памяти: взять множества А B, получить и сохранить другие представления А' B', посчитать C=пересечение А' B', обрабатывать элементы C. Против параллельного (или ленивого) исполнения: взять первый элемент из итератора, во время его обработки получить следующий.

совать в unordered_set, работает за O(n)

сортируешь списки и сравниваешь поэлементно сложность o(nlogn)

Сначала порезать оба каталога на однозначные куски (по году издания), сравнивать только парные куски О(зависит от «сколько кусков»). И удалять идеально совпавшие элементы из списков о(n^2/2).

Это множества, упорядочить их нельзя, (между элементами нет сравнения). Есть только проверка на нечеткое равенство.

Например (эти должны быть равны):

Кулинария. Введение в профессию. Фазанов Г.
Кулинария. Введение. Сазанов
Введение в кууууулинарию. Оазанов Г.

С нечетким равенством тоже жопа - могут слегка отличаться и слова и их порядок. Есть ли расстояние Хеминга-Левинштейна для нечеткого сравнения - хз.

Во примерно такие записи и надо объединять! Разве что жестоких опечаток не очень много (хотя есть). Ну и год может быть банально не проставлен.

Пока что пришёл к выводу, что искусственный интеллект для полноценного правильно сравнения мне не создать ;-) Следовательно, чем-то придётся жертвовать. Думаю для нечёткого сравнения строк в каждом из полей просто выбрать какой-нибудь критерий похожести.

Опечаток типа «кууууулинарию» не припомню, но что-то вроде «нгкулинарию» попадается. (Интересно как их допустили, но приходится считаться)

Метод Хеминга требует одинаковой длины, но метод Левенштейна слегка ресурсожор сам по себе. Но попробую, что получится.

Ну и год может быть банально не проставлен.

Кусок без года - можно сравнивать со всеми годами.

«нгкулинарию»

м.б. скан

Еще (для сравнения названий): Словам можно приписать вес: терминам,фамилиям - больше, предлогам,союзам(и др. часто встречающимся) - меньше. Падежные окончания - порезать.

Словам можно приписать вес: терминам,фамилиям - больше, предлогам,союзам(и др. часто встречающимся) - меньше.

Разумно, собственно так и собирался.

Падежные окончания - порезать.

Ещё и морфологию прикручивать (а как определять падежные окончания) слишком жирновато может выйти в плане борьбы за скорость.

Ещё и морфологию прикручивать (а как определять падежные окончания) слишком жирновато может выйти в плане борьбы за скорость.

надо прикрутить так, чтобы на скорость не влияло: сначала представляешь данные в нормализованном виде (например, отсекаешь окончания) - это всего O(n+m). а потом уже сравниваешь, с сортировкой или без