Оптимизация декартовых запросов с аффинными затратами
Вопрос
У меня есть запрос на оптимизацию затрат, но я не знаю, как это сделать, если есть литература по этому вопросу.Это немного сложно объяснить, поэтому я заранее приношу извинения за объем вопроса.
Есть сервер, к которому я обращаюсь, который работает таким образом:
- запрос выполняется по записям (r1, ...rn) и полям (f1, ...fp).
- вы можете запросить только декартово произведение (r1, ..., rp) x (f1,...fp)
- Стоимость (время и деньги), связанная с таким запросом, зависит от размера запроса:
T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p
Без потери общности (просто путем нормализации) мы можем предположить, что b=1
таким образом, стоимость составляет:
T((r1, ...,rn)x(f1,...fp)) = a + n * p
- Мне нужно только запросить подмножество пар
(r1, f(r1)), ... (rk, f(rk))
, запрос, который поступает от пользователей.Моя программа действует как посредник между пользователем и сервером (который является внешним).У меня поступает много подобных запросов (десятки тысяч в день).
Графически мы можем представить это как разреженную матрицу n x p, для которой я хочу покрыть ненулевые значения прямоугольной подматрицей:
r1 r2 r3 ... rp ------ ___ f1 |x x| |x| f2 |x | --- ------ f3 .. ______ fn |x x| ------
Имея:
- количество подматриц поддерживается разумным из-за постоянной стоимости
- все 'x' должны находиться внутри подматрицы
- общая покрываемая площадь не должна быть слишком большой из-за линейной стоимости
Я назову g коэффициентом разреженности моей задачи (количество необходимых пар по сравнению с общим количеством возможных пар, g = k / (n * p)
.Я знаю этот коэффициент a
.
Есть несколько очевидных наблюдений:
- если a невелик, лучшим решением будет запросить каждую пару (запись, поле) независимо, а общая стоимость составит:
k * (a + 1) = g * n * p * (a + 1)
- если a велико, лучшим решением будет запросить все декартово произведение, и общая стоимость составит :
a + n * p
- второе решение лучше, как только
g > g_min = 1/ (a+1) * (1 + 1 / (n * p))
- конечно, порядки в декартовых произведениях неважны, поэтому я могу транспонировать строки и столбцы моей матрицы, чтобы сделать ее более легко охватываемой, например:
f1 f2 f3 r1 x x r2 x r3 x x
может быть переупорядочен как
f1 f3 f2 r1 x x r3 x x r2 x
И есть оптимальное решение, которое заключается в запросе (f1,f3) x (r1,r3) + (f2) x (r2)
- Пробовать все решения и искать более низкую стоимость - это не вариант, потому что комбинаторика взрывается:
for each permutation on rows: (n!) for each permutation on columns: (p!) for each possible covering of the n x p matrix: (time unknown, but large...) compute cost of the covering
поэтому я ищу приблизительное решение.У меня уже есть какой-то жадный алгоритм, который находит покрытие по заданной матрице (он начинается с унитарных ячеек, затем объединяет их, если доля пустой ячейки в слиянии ниже некоторого порога).
Чтобы запомнить некоторые цифры, мое n находится где-то между 1 и 1000, а мое p - где-то между 1 и 200.Шаблон покрытия действительно "блочный", потому что записи поступают в классы, для которых запрашиваемые поля похожи.К сожалению, я не могу получить доступ к классу записи...
Вопрос 1:Есть у кого-нибудь идея, умное упрощение или ссылка на статью, которая могла бы быть полезной?Поскольку у меня много запросов, алгоритм, который работает хорошо в среднем это то, что я ищу (но я не могу позволить, чтобы это работало очень плохо в каком-то крайнем случае, например, запрашивая всю матрицу, когда n и p большие, а запрос действительно довольно разреженный).
Вопрос 2:На самом деле, проблема еще сложнее:стоимость на самом деле больше похожа на форму: a + n * (p^b) + c * n' * p'
, где b - постоянная < 1 (как только у записи запрашивается поле, запрашивать другие поля не слишком дорого) и n' * p' = n * p * (1 - g)
это количество ячеек, которые я не хочу запрашивать (потому что они недопустимы, а запрос недопустимых данных требует дополнительных затрат).Я даже не могу мечтать о быстром решении этой проблемы, но все же...у кого-нибудь есть идея?
Решение
Выбор подматриц для покрытия запрошенных значений является формой установите проблему покрытия и, следовательно, NP завершен.Ваша проблема добавляет к этой и без того сложной проблеме то, что стоимость наборов различается.
То, что вы разрешаете переставлять строки и столбцы, не такая уж большая проблема, потому что вы можете просто рассматривать несвязанные подматрицы.Первая строка, столбцы с четвертого по седьмой и пятая строка, столбцы четыре два семь являются допустимым набором, потому что вы можете просто поменять местами вторую строку и пятую строку и получить подключенную подматрицу первая строка, четвертый столбец - вторая строка, седьмой столбец.Конечно, это добавит некоторые ограничения - не все наборы допустимы при всех перестановках, - но я не думаю, что это самая большая проблема.
В статье Википедии приводятся результаты неприменимости, согласно которым проблема не может быть решена за полиномиальное время лучше, чем с коэффициентом 0.5 * log2(n)
где n
это количество наборов.В вашем случае 2^(n * p)
является (довольно пессимистичной) верхней границей для количества наборов и дает то, что вы можете найти решение только с точностью до коэффициента 0.5 * n * p
за полиномиальное время (помимо N = NP и игнорирования меняющихся затрат).
Оптимистичная нижняя граница для количества наборов, игнорирующих перестановки строк и столбцов, равна 0.5 * n^2 * p^2
обеспечивая гораздо лучший коэффициент log2(n) + log2(p) - 0.5
.Следовательно, вы можете рассчитывать найти решение только в вашем наихудшем случае n = 1000
и p = 200
до коэффициента примерно 17
в оптимистическом случае и с коэффициентом около 100.000
в пессимистичном случае (по-прежнему игнорируя различные затраты).
Поэтому лучшее, что вы можете сделать, это использовать эвристический алгоритм (в статье Википедии упоминается почти оптимальный жадный алгоритм) и принять, что будет случай, когда алгоритм будет работать (очень) плохо.Или вы идете другим путем и используете алгоритм оптимизации и пытаетесь найти хорошее решение, затратив на это больше времени.В этом случае я бы предложил попробовать использовать A* поиск.
Другие советы
Я уверен, что где-то есть действительно хороший алгоритм для этого, но вот мои собственные интуитивные идеи:
Подход с подбрасыванием нескольких прямоугольников:
- Определите "примерно оптимальный" размер прямоугольника на основе a.
- Разместите эти прямоугольники (возможно, случайным образом) поверх требуемых точек, пока не будут покрыты все точки.
- Теперь возьмите каждый прямоугольник и сожмите его как можно больше, не "теряя" ни одной точки данных.
- Найдите прямоугольники близко друг к другу и решите, будет ли их объединение дешевле, чем хранение по отдельности.
Расти
- Начните с каждой точки в отдельном прямоугольнике размером 1х1.
- Найдите все прямоугольники в пределах n строк / столбцов (где n может быть основано на a);посмотрите, сможете ли вы объединить их в один прямоугольник без каких-либо затрат (или отрицательных затрат : D).
- Повторяю.
Сжиматься
- Начните с одного большого прямоугольника, который охватывает ВСЕ точки.
- Найдите прямоугольник, который имеет общую пару сторон с большим прямоугольником, но содержит очень мало точек.
- Вырежьте его из большого, чтобы получились два прямоугольника поменьше.
- Повторяю.
Четырехъядерный
- Разделите плоскость на 4 прямоугольника.Для каждого из них посмотрите, получите ли вы более высокую стоимость, выполнив дальнейшую рекурсию или просто включив весь прямоугольник.
- Теперь возьмите свои прямоугольники и посмотрите, сможете ли вы объединить любой из них с минимальными затратами.\
Также: имейте в виду что иногда будет лучше иметь два перекрывающиеся прямоугольники, чем один большой прямоугольник, который является их надмножеством.Например.тот случай, когда два прямоугольника просто перекрываются в одном углу.
Хорошо, мое понимание вопроса изменилось.Новые идеи:
Храните каждую строку в виде длинной битовой строки.И пары битовых строк вместе, пытаясь найти пары, которые максимизируют количество битов в 1.Разбейте эти пары на более крупные группы (отсортируйте и постарайтесь сопоставить действительно большие друг с другом).Затем создайте запрос, который попадет в самую большую группу, а затем забудьте обо всех этих битах.Повторяйте, пока все не будет готово.Может быть, иногда переключаться со строк на столбцы.
Найдите все строки / столбцы с нулем или несколькими точками в них."Удалите" их временно.Теперь вы смотрите на то, что было бы охвачено запросом, который их не учитывает.Теперь, возможно, примените один из других методов и впоследствии разберитесь с игнорируемыми строками / cols .Другой способ думать об этом - это:сначала разберитесь с более плотными точками, а затем переходите к более разреженным.
Поскольку ваши значения разрежены, может быть, многие пользователи запрашивают похожие значения?Возможно ли кэширование в вашем приложении?Запросы могут быть проиндексированы с помощью хэша, который является функцией позиции (x, y), чтобы вы могли легко идентифицировать кэшированные наборы, которые попадают в правильную область сетки.Например, хранение кэшированных наборов в виде дерева позволило бы вам очень быстро найти минимальные кэшированные подмножества, которые охватывают диапазон запросов.Затем вы можете выполнить линейный поиск по подмножеству, которое невелико.
Я бы рассмотрел n записей (строк) и p полей (столбцов), упомянутых в пользовательском запросе, заданном как n точек в p-мерном пространстве ({0,1} ^ p) с i-й координатой, равной 1, если у нее есть X, и определите иерархию кластеров, с самым грубым кластером в корне , включающим все X.Для каждого узла в иерархии кластеризации рассмотрите продукт, который охватывает все необходимые столбцы (это строки (любой подузел) x столбцы (любой подузел)).Затем решите снизу вверх, следует ли объединить дочерние покрытия (оплачивая все покрытие целиком) или сохранить их как отдельные запросы.(покрытия состоят не из смежных колонн, а именно из тех, которые необходимы;т. е.подумайте о битовом векторе)
Я согласен с Artelius в том, что дублирующие запросы на продукт могли бы быть дешевле;мой иерархический подход нуждался бы в улучшении, чтобы учесть это.
Я немного поработал над этим, и вот очевидный, O (n ^ 3) жадный алгоритм, нарушающий симметрию (записи и поля обрабатываются отдельно) в псевдокоде, подобном python.
Идея тривиальна:мы начинаем с попытки выполнения одного запроса для каждой записи и выполняем наиболее достойное слияние до тех пор, пока не останется ничего достойного для слияния.Этот алгоритм имеет очевидный недостаток в том, что он не допускает перекрывающихся запросов, но я ожидаю, что он будет достаточно хорошо работать в реальных условиях (с + n * (p^b) + c * n * p * (1 - g)
функция затрат) :
# given are # a function cost request -> positive real # a merge function that takes two pairs of sets (f1, r1) and (f2, r2) # and returns ((f1 U f2), (r1 U r2)) # initialize with a request per record requests = [({record},{field if (record, field) is needed}) for all needed records] costs = [cost(request) for request in requests] finished = False while not finished: # there might be something to gain maximum_gain = 0 finished = True this_step_merge = empty # loop onto all pairs of request for all (request1, request2) in (requests x request) such as request1 != request2: merged_request = merge(request1, request2) gain = cost(request1) + cost(request2) - cost(merged_request) if gain > maximum_gain: maximum_gain = gain this_step_merge = (request1, request2, merged_request) # if we found at least something to merge, we should continue if maximum_gain > 0: # so update the list of requests... request1, request2, merged_request = this_step_merge delete request1 from requests delete request2 from requests # ... and we are not done yet insert merged_request into requests finished = False output requests
Это O (n3 * p), потому что:
- после инициализации мы начинаем с
n
Запросы - в
while
цикл удаляет ровно один запрос из пула на каждой итерации. внутренний
for
цикл повторяется на (ni^2 - ni
) / 2 отдельные пары запросов, причем в худшем случае ni переходит от n к единице (когда мы объединяем все в один большой запрос).- Кто-нибудь может помочь мне указать на очень плохие случаи работы алгоритма.Звучит ли разумно использовать этот вариант ?
- Это O (n ^ 3), что слишком дорого для больших входных данных.Есть какие - нибудь идеи по его оптимизации ?
Заранее спасибо !