How to become an author
Search
Write a publication
Pull to refresh

Comments 6

В части 1, получилось меньше 0.1сек вместо 3.5сек в части 1(снова)

WITH src AS 
(
SELECT 
	line[1] nodefrom,
	line[2] nodeto
FROM 
	regexp_matches(
$$
kh-tc
qp-kh
de-cg
ka-co
yn-aq
qp-ub
cg-tb
vc-aq
tb-ka
wh-tc
yn-cg
kh-ub
ta-co
de-co
tc-td
tb-wq
wh-td
ta-ka
td-qp
aq-cg
wq-ub
ub-vc
de-ta
wq-aq
wq-vc
wh-yn
ka-de
kh-ta
co-tc
wh-qp
tb-vc
td-yn
$$
,
'(\w+)\-(\w+)'
,'g'
) AS src(line)
),
transform_src AS (
SELECT 
	nodefrom,nodeto FROM src 
UNION ALL 
SELECT 
	nodeto,nodefrom FROM src
),
--каждый узел по списком связей
node_links AS 
(
SELECT  
	nodefrom,
	array_agg(nodeto) AS links
FROM 
	transform_src
GROUP BY 
	nodefrom
--исключить заведомо неподходящие
HAVING 
	nodefrom LIKE 't%' OR bool_or(nodeto ^@ 't') 
)
SELECT count(DISTINCT 
	(
	LEAST(nl1.nodefrom,nl2.nodefrom,u1),
	(array_remove(
		array_remove(ARRAY[nl1.nodefrom,nl2.nodefrom,u1],
					 LEAST(nl1.nodefrom,nl2.nodefrom,u1)),
		GREATEST(nl1.nodefrom,nl2.nodefrom,u1)))[1],
	GREATEST(nl1.nodefrom,nl2.nodefrom,u1)
	)
	)	
FROM 
	node_links AS nl1 
	CROSS JOIN node_links nl2,
	unnest(nl1.links) u1
WHERE 
	nl1.nodefrom > nl2.nodefrom
	AND nl2.nodefrom = ANY(nl1.links)
	AND u1 = ANY(nl2.links)
	AND (nl1.nodefrom ^@ 't' OR nl2.nodefrom ^@ 't' OR u1 ^@ 't');

Rating is hidden

"Нет предела совершенству". ))

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

Так-то можно уложиться в 60мс, если анализировать только t-наборы:

 explain (analyze, costs off)
WITH src AS (
  SELECT
    regexp_matches(
      $$
kh-tc
qp-kh
de-cg
ka-co
yn-aq
qp-ub
cg-tb
vc-aq
tb-ka
wh-tc
yn-cg
kh-ub
ta-co
de-co
tc-td
tb-wq
wh-td
ta-ka
td-qp
aq-cg
wq-ub
ub-vc
de-ta
wq-aq
wq-vc
wh-yn
ka-de
kh-ta
co-tc
wh-qp
tb-vc
td-yn
$$
    , '([a-z]{2})-([a-z]{2})'
    , 'g'
    ) pair
)
, tname AS ( -- собираем, с кем связаны 't?'
  SELECT
    pair[1] src
  , array_agg(pair[2]) dst
  FROM
    (
      SELECT
        *
      FROM
        src
      WHERE
        pair[1] ^@ 't'
    UNION ALL
      SELECT
        ARRAY[pair[2], pair[1]]
      FROM
        src
      WHERE
        pair[2] ^@ 't'
    ) T
  GROUP BY
    1
)
SELECT
  count(*)                                       -- все записи
  - count(*) FILTER(
    WHERE
      (pair[1] ^@ 't' AND NOT pair[2] ^@ 't') OR
      (NOT pair[1] ^@ 't' AND pair[2] ^@ 't')
  ) / 2                                          -- исключаем посчитанные дважды ta|{tb,x} и tb|{ta,x}
  - count(*) FILTER(
    WHERE
      (pair[1] ^@ 't' AND pair[2] ^@ 't')
  ) / 3 * 2                                      -- исключаем посчитанные трижды ta|{tb,tc}, tb|{ta,tc} и tc|{ta,tb}
FROM
  tname
, src
WHERE
  pair <@ dst; -- оба элемента исходной пары связаны с одним и тем же 't?'

Rating is hidden

В части 2 предложу такой вариант, у меня выполнился за 0.4 сек.

WITH src AS 
(
SELECT 
	line[1] nodefrom,
	line[2] nodeto
FROM 
	regexp_matches(
$$
kh-tc
qp-kh
de-cg
ka-co
yn-aq
qp-ub
cg-tb
vc-aq
tb-ka
wh-tc
yn-cg
kh-ub
ta-co
de-co
tc-td
tb-wq
wh-td
ta-ka
td-qp
aq-cg
wq-ub
ub-vc
de-ta
wq-aq
wq-vc
wh-yn
ka-de
kh-ta
co-tc
wh-qp
tb-vc
td-yn
$$
,
'(\w+)\-(\w+)'
,'g'
) AS src(line)
)
,transform_src AS (
SELECT 
	nodefrom,nodeto 
FROM 
	src 
UNION ALL 
SELECT 
	nodeto,nodefrom 
FROM 
	src
)
,full_links AS 
(
--полный набор узлов включая узел источник
SELECT  
	nodefrom,
	nodefrom || array_agg(nodeto) AS links
FROM 
	transform_src
GROUP BY 
	nodefrom
)
,crossing_lans AS 
(
--найти пересечения узлов в массивах и сформировать из них новый массив
SELECT 
	array_agg(l1 ORDER BY l1) AS nodes
FROM 
	full_links AS fl1 
	CROSS JOIN full_links AS fl2,
	unnest(fl1.links) AS l1,
	unnest(fl2.links) AS l2
WHERE 
	fl1.nodefrom > fl2.nodefrom
	AND l1 = l2
GROUP BY 
	fl1.nodefrom || fl2.nodefrom
)
--TABLE crossing_lans;
SELECT 
	array_to_string(nodes,',')
FROM 
	crossing_lans 
GROUP BY 
	nodes
HAVING 
	--Кол-во комбинаций узлов fl1.nodefrom и fl2.nodefrom = арифметметической прогрессии от длины массива
	count(*) = array_length(nodes,1) * (array_length(nodes,1) - 1) / 2
ORDER BY 
	count(*) DESC 
LIMIT 1;

Rating is hidden

Можно чуть ускорить вычисления пересечений массивов:

, crossing_lans AS (
  SELECT
    ARRAY(
      SELECT
        unnest(T1.links)
    INTERSECT ALL
      SELECT
        unnest(T2.links)
    ORDER BY
      1
    ) nodes
  FROM
    full_links T1
  JOIN
    full_links T2
      ON T2.nodefrom > T1.nodefrom
)

А вот подход с "арифметикой" и треугольными числами - это красиво, согласен, хотя и требует несколько более подробного объяснения, почему это так.

Rating is hidden

По crossing_lans, в этом случае порождается куча массив без пересечений и увеличивается время выполнения.

Rating is hidden

Забавный эффект... Но если избавиться от промежуточной группировки и пересечение массива искать внутри соединения:

WITH inp AS (
  SELECT
    pair[1] src
  , pair[2] dst
  FROM
    regexp_matches(
      $$
kh-tc
qp-kh
de-cg
ka-co
yn-aq
qp-ub
cg-tb
vc-aq
tb-ka
wh-tc
yn-cg
kh-ub
ta-co
de-co
tc-td
tb-wq
wh-td
ta-ka
td-qp
aq-cg
wq-ub
ub-vc
de-ta
wq-aq
wq-vc
wh-yn
ka-de
kh-ta
co-tc
wh-qp
tb-vc
td-yn
$$
    , '([a-z]{2})-([a-z]{2})'
    , 'g'
    ) pair
)
, directed AS (
  SELECT DISTINCT
    T.* -- (src, dst) | (dst, src) | (src, src) | (dst, dst)
  FROM
    inp
  , unnest(
      ARRAY[src, dst, src, dst]
    , ARRAY[dst, src, src, dst]
    ) T(src, dst)
)
SELECT
  array_to_string(grp, ',')
FROM
  (
    SELECT
      array_agg(d1.dst ORDER BY d1.dst) grp
    FROM
      directed d1
    JOIN
      directed d2
        ON d2.src = d1.dst AND -- вместо пересечения массивов
        d2.dst > d1.src
    GROUP BY
      d1.src, d2.dst
  ) T
, array_length(grp, 1) ln
GROUP BY
  grp
HAVING
  count(*) = array_length(grp, 1) * (array_length(grp, 1) - 1) / 2
ORDER BY
  count(*) DESC
LIMIT 1;

... то удается выйти на 183мс:

Rating is hidden
Sign up to leave a comment.

Your account

Sections

Information

Services

Support
© 2006–2025, Habr