Comments 9
Допустим, что почта бывает корпоративная (одна для нескольких пользователей). Опустим причины, по которым кто-то использует такой адрес для регистрации в сервисе (чем вы там занимаетесь). Но как быть с номером телефона? Существует сценарий, когда два совершенно разных человека указали один и тот же номер? Я может чего-то не понимаю, но выглядит как "мы себе сами сделали сложно, а потом героически побеждали эту сложность".
Не во всех продуктах на входе пользователь указывает номер телефона. И это главная проблема, которую мы решаем, вы верно заметили. Если бы был номер телефона во всех снепшотах, было бы гораздо проще.
Бывает иногда, что муж и жена указывают одинаковый номер телефона. Скорее всего для нас они будут одним человеком после объединений.
Но самый частый пример - это опечатки, как ни странно... Операторы при вводе данных под диктовку ошибаются, и если объединять только по номеру телефона, получаются "Франкенштейны". Заметить такие ложные слияния по практике очень сложно, поэтому мы и используем несколько полей в правилах
В корне своего замечания вы абсолютно правы. Будь бизнес-требования "более математичными", реализация была бы существенно проще. Однако, как оказывается, реальность состоит из ньюансов.
Большое спасибо за статью! Не так часто встретишь применение нестандартных алгоритмов в production-задачах.
Единственная большая претензия - сильное сомнение в корректности асимптотики и как следствие - слегка кликбейтный заголовок :)
> Либо можно подойти к этому вопросу с точки зрения оценки влияния, привнесённого каждым добавленным в систему снепшотом. Это тоже жизнеспособная позиция, и она точнее. Вызванные слияния зависимы от первого слияния, поэтому оценка превратится в произведение.
Если мы слегка переформулируем алгоритм, станет очевидно, что никакого произведения нет.
Пусть у нас изначально есть текущий набор снепшотов и мастеров. Теперь мы хотим добавить новый снепшот в набор. Мы создаем для него отдельный мастер и далее M раз ищем другого мастера, связанного с текущим каким-то правилом, объединяем эти два мастера и переходим к следующей итерации. Поэтому в асимптотике везде нужно опустить M из степени в обычный множитель.
В качестве дополнительного возможного улучшения (которое потенциально может немного уменьшить константу) я бы ещё рассмотрел вариант с индексами не для правил, а для отдельных атрибутов, то есть отдельный индекс для телефона, отдельный для почты и тд. С учётом того, что случаи с одинаковыми значениями атрибутов достаточно редки на практике, это может дать улучшение с точки зрения уменьшения количества обновлений индексов при увеличении количества чтений из индекса.
В оценке я, действительно, сомневаюсь. Меня подтолкнула к выбору такого пути рассуждений длительность выполнения алгоритма на практике. Вернее, её зависимость от входных данных. Она совершенно точно меньше квадратичной, и больше линейной :)
Если мы слегка переформулируем алгоритм, станет очевидно, что никакого произведения нет.
Пусть у нас изначально есть текущий набор снепшотов и мастеров. Теперь мы хотим добавить новый снепшот в набор. Мы создаем для него отдельный мастер и далее M раз ищем другого мастера, связанного с текущим каким-то правилом, объединяем эти два мастера и переходим к следующей итерации. Поэтому в асимптотике везде нужно опустить M из степени в обычный множитель.
И с вашим подходом я совершенно согласен. Я думал о нём как альтернативе. Но не смог додуматься вот до чего.
В нём нужно оценить число таких слияний. M выглядит зависимой от n, так как каждое объединение порождает генерацию новых значений в индексах. Новые значения в индексах влияют на потенциальные следующие слияния. Так получается, что одно слияние порождает другие. M оставить константой было бы грубым приближением.
Оценить M трудно. Мне хотелось сначала в статье написать, что это число экспоненциально зависит от n, так как количество новых записей в индексах на каждом слиянии имеет экспоненциальную зависимость. Но в какой-то момент я понял, что эта зависимость не от n, а от числа параметров в правиле.
На этом моя цепочка мыслей обрывается, не могу сообразить связь между M и n в таком подходе. Но и интуиция её присутствия меня не покидает. Поэтому оценка в статье из другого подхода, где связать слияния удалось.
Это ответ на первую часть вашего сообщения :)
Немного моих мыслей по поводу оценки M.
Во-первых как-бы это ни было очевидно, M <= n - 1, так как после n-1 слияния останется один мастер :) Это как минимум ограждает нас от мыслей о каких-то экспоненциальных вариантах.
Во-вторых можно оценить с другого взгляда. Пусть мы проделали все слияния. В получившемся мастере у нас получилось x значений для ФИО, y значений для телефона и так далее. Теперь для каждого существующего правила посчитаем сколько комбинаций (Z) параметров у нас есть (в случае правила фио+телефон получается Z=x*y).
Утверждение - выбранное правило мы использовали для слияния максимум Z раз. Так как до слияния для каждой комбинации существовал максимум один мастер, включающий эту комбинацию (если бы это было не так, то слияния нужно было бы производить раньше).
Для окончательной оценки нужно сложить Z_i для всех правил.
Как это перенести на реальную задачу. В самом частом случае у нас для каждого атрибута будет одно значение в мастере. В таком случае M <= количество правил. Для случаев когда у нас по K разных значений атрибута получается M <= (количество правил) * K^2 (для случая с двумя атрибутами на правило).
Да, вы абсолютно правы. Моя ошибка. Очевидным это становится в имплементации:
https://github.com/Evgeny-Mamaev/dedu/blob/b253fbe048b41c1bd1bbdad4062f19815e0902e1/deduplicator.py#L534
n * log^m(n) превращается в n * log(n).
Хорошее замечание по поводу разделения индексов. Я много думал об этом улучшении, но довести до логического завершения не смог. Остановило вот что.
Чтобы обеспечить возможность в индекс добавить одинаковые значения, пришлось "приклеивать" в конце полей порядковый номер. Иначе ссылаться на эти значения невозможно, потому что они одинаковые.
У последнего значения в правиле всегда в такой реализации есть суффикс, например, -1, -2... Если разделить индексы составные на индексы по полям, то такой суффикс должен быть у последнего в правиле поля в отдельном индексе и не быть в других полях.
Однако, поля в разных правилах могут быть в разных местах. Не обязательно ФИО при концевой позиции в одном правиле будет в конце в другом. Тогда в случае присутствия поля в разных местах в нескольких правилах, в индекс попадут значения как с суффиксом, так и без.
Такое смешение ведёт к разрушению парадигмы: в каких-то случаях нужны значения только без суффиксов, а в других - только с суффиксами.
Если у вас есть идеи, как это обойти, я буду очень рад предложениям. Потому что это существенно уменьшило бы константу, как вы точно заметили.
Думаю всё зависит от того, о какой структуре данных для индекса мы говорим.
Для себя я представлял это так.
1) В структуре мастера храним все списки (или множества) значений для всех атрибутов (все телефоны, все фио и тд). Вдобавок конечно скорее всего храним ещё список айдишников снепшотов.
2) Для каждого атрибута (телефон, фио) заводим отдельный индекс. Структура индекса - словарь: key - значение атрибута, value - множество идентификаторов мастеров, у которых есть такое значение заданного атрибута.
Теперь есть 2 главных операции.
1) Поиск кандидатов для слияния с текущим мастером по заданному правилу.
Из правила вытаскиваем атрибуты, для каждого атрибута из структуры текущего мастера вытаскиваем значения этого аттрибута. Для каждого значения первого атрибута из соответствующего индекса достаем множество айдишников мастеров. Объединяем через ИЛИ эти множества. Далее переходим ко второму атрибуту. В конце нужно пересечь итоговые множества через И.
Если в конечном множестве больше одного идентификатора (текущий мастер там точно будет), значит мы нашли как минимум одного кандидата на слияние. Далее можем их последовательно слить.
2) Слияние двух мастеров.
Сначала опционально можно решить кого в кого будем сливать (выгоднее сливать меньшего мастера в большего, но на практике возможно разница не будет большой).
Далее из мастера-источника переносим в мастер-сток значения атрибутов, параллельно обновляя данные в индексах (удаляя из них айдишник мастера-источника и добавляя айдишник мастера-стока). Дополнительно переносим список айдишников снепшотов.
Согласен с идеей. Остановило меня от такой реализации необходимость различать одинаковые значения в индексах для последующего удаления. Ведь после разлияния (особый кейс, обусловленный бизнес-требованиями) ссылки из индексов нужно удалить.
Ссылка в индексе, как вы написали, - пара ключ (строка) и значение, на ключ нельзя сделать ссылку для удаления извне, можно только двоичным поиском найти. Если будут две одинаковые строки, ссылающиеся на разные мастера, их можно проверить перебором. А если больше, то это уже может константу увеличить для операции разделения.
Здесь, конечно, вопрос к тому, как часто раздения происходят. Возможно, этим "усложнением" удаления ссылки можно пренебречь.
А вообще, меня ваш комментарий навёл на мысль, что переход к раздельным индексам позволит избежать удаления ссылок во время слияния. Ведь теперь можно при слиянии в паре ключ-значение менять только значение, указывать вместо старого на нового мастера. А в текущей реализации нужно ссылку из составного индекса удалять и новые ссылки создавать и вставлять, так как комбинации полей меняются в новом мастере.
Спасибо большое за ваши идеи!
В борьбе со сложностью, или Как обуздать лог-линейный алгоритм (со ссылкой на код)