Greetings Overflowers,
- Наш алгоритм должен получить запрос в структуре DAG и вывести список совпадений, удовлетворяющих графику.
- Каждое ребро в графе указывает науникальный список объектов для фильтрации.
- Каждый объект имеет два значения, скажем, HEAD и TAIL.
- Связанные узлы по направленным ребрам в графе напоминают HEAD и TAILs этих объектов.
- Например, для DAG-запроса из трех подключенных узлов требуется два объекта (по одному из списка каждого ребра), где заголовок одного равен хвосту другого.
- И т. Д. С более сложными запросами DAG.
- Следовательно, роль алгоритма состоит в том, чтобы возвращать все возможные перестановки объектов, которые удовлетворяют критериям совместного использования HEAD / TAIL (при равенстве).
- Одиночный удар - это просто возможный список перестановок таких объектов.
Наше текущее решение работает следующим образом:
- Сортировка по HEAD / TAIL, затем списки заказов по возрастанию по длине (сначала самое короткое).
- Перебор объектов из кратчайшего списка.
- Двоичный поиск объектов в следующем списке, которые делят значение HEAD / TAIL с объектом из последнего найденного списка, непосредственно подключенного к нему.
- Если в списке нет такого объекта, вернитесь к предыдущему списку и попробуйте с сортировкой его следующего объекта.
- Если этот следующий объект соответствует критериям края / списка, мы снова продвигаемся вперед, в противном случае мывернуться назад и т. д.
- Если мы дойдем до самого длинного списка, у нас будет попадание, состоящее из всех объектов из каждого списка, которые соответствуют общим критериям DAG.
- Вернуться к предыдущему спискуи попробуйте снова, пока мы не достигнем дна первого кратчайшего списка.
Как видите, мы просто можем равномерно разделить первый список между потоками.Однако это может привести к несбалансированной нагрузке на разные потоки.Таким образом, порядок поиска списков может повлиять на производительность.Мы выбираем переход с кратчайшего на самый длинный, чтобы промах был обнаружен на ранней стадии, прежде чем мы достигнем более длинных списков, в которых мы пытаемся линейно, а не двоично.Если мы выберем самый длинный и самый короткий, мы сможем достичь идеального баланса, хотя всегда будем вынуждены полностью перебирать самый длинный список, влияющий на производительность.
Что вы думаете об этом балансе?Это стандартная алгоритмическая проблема, имя которой я могу найти в Google?Есть ли другие способы одновременного обхода групп доступности баз данных, которые могут повысить производительность?
Большое спасибо!