Как я могу оптимизировать это понимание списка?

Question

Я хотел бы сгенерировать все возможные пары пар из списка с ограничением, что (a, b) == (b, a) и что ((a, b), (c, d)) = = ((c, d), (a, b)) для всех a, b, c, d. Кроме того, я могу предположить, что все элементы в списке, которые я предоставляю в качестве аргумента, различны.

Первое, что я сделал, это записал следующее понимание списка:

pairsOfPairs :: [a] -> [((a,a),(a,a))]
pairsOfPairs xs = [((w,x),(y,z)) | w <- xs, x <- xs, y <- xs, z <- xs,
                      w < x, y < z, w < y, w /= z, x /= y, x /= z]

Преимущество в том, что он идиоматичен, но очень медленный (профилирование показывает, что около 90% времени работы было потрачено на эту функцию и другую, аналогичную функцию).

Причина медлительности заключается в том, что для списка из n элементов он генерирует n ^ 4 пары кандидатов, но ограничения в конечном итоге сокращают его до n! / (8 * (n-4)!), Что означает, что мы делаем как минимум в 8 раз больше работы.

Есть ли способ переписать функцию pairsOfPairs, которая даст ей прирост скорости? Очевидно, это все равно будет O (n ^ 4), но я надеюсь снизить константу.

<Ч />

Редактировать: На самом деле, я почти всегда вызываю эту функцию со списком длиной 5, что означает, что в результате 5! / 8 = 15 элементов, но функция генерирует список из 5 ^ 4 = 625 элементов в качестве промежуточного шага. Если бы я мог устранить все эти промежуточные элементы, я бы получил ускорение примерно в 40 раз!

Answer 1

Простой способ сократить объем выполненной работы - отфильтровать как можно раньше.

pairsOfPairs :: Ord a => [a] -> [((a,a),(a,a))]
pairsOfPairs xs = [((w,x),(y,z)) | w <- xs, x <- xs, w < x, y <- xs, w < y, x /= y, 
                                   z <- xs, y < z, w /= z, x /= z]

Проверяя условия, как только они становятся доступными, мы избегаем O (n ^ 2)работать для каждой пары (w,x) с x <= w и т. д. Это не так уж и плохо.

Но можно получить больше, предварительно обработав список, если он отсортирован, мы можем избежать почти всей ненужной работы, выбрав такие пары, как

ordPairs :: [a] -> [(a,a)]
ordPairs (x:xs) = [(x,y) | y <- xs] ++ ordPairs xs
ordPairs [] = []