主页 / dba / 问题 / 291751
Accepted
Gajus
Asked: 2021-05-18 18:14:37 +0800 CST

如何找到两种货币之间的最短路径？

  • 772

我有桌子currency_pair(c1, c2)；值为(usd,bnb), (cake,bnb), (cake,eth).

我需要找到允许我比较的最短usd路径eth。

这里的结果将是那些相同的值。然后我可以使用第一对建立 usd-bnb 关系，然后我可以使用它来计算 usd-cake 关系，然后我可以使用它来计算 usd-eth。

由于顺序不是确定的，我做的第一步是创建一个物化视图currency_pair_map(c1, c2)，它是 的并集select c1, c2 union select c2, c1。这似乎简化了逻辑。

如果我正确地考虑了这一点，我需要做的是使用WITH RECURSIVE吗？我还应该有某种“depth_limit”参数，以确保在无法建立一对时查询失败。

大声思考这个问题，我们应该始终从以下内容开始：

SELECT *
FROM currency_pair
WHERE
  c1 = 'usd' AND
  c2 = 'eth'

如果有结果，我们应该到此为止。

如果没有，那么我们需要找到所有usd-*对并继续搜索，直到找到以 结尾的一对eth。

使用这个逻辑，到目前为止我有：


WITH RECURSIVE pair_route AS (
  SELECT
    1 depth,
    cp1.id,
    cp1.c1,
    cp1.c2
  FROM currency_pair cp1
  WHERE
    cp1.c1 = 'usd'
  UNION
  SELECT
    pr1.depth + 1,
    cp2.id,
    cp2.c1,
    cp2.c2
  FROM pair_route pr1
  INNER JOIN currency_pair cp2 ON cp2.c1 = pr1.c2
  WHERE
    pr1.depth < 4
)
SELECT *
FROM pair_route;

我认为这是正确的。现在我只需要跟踪路径 (ID) 并确定最短路径。

postgresql recursive

2 个回答

  1. Best Answer

    您可以使用此递归查询：

    WITH RECURSIVE c AS (
      SELECT c1, c2 FROM currency_pair
   UNION
      SELECT c2, c1 FROM currency_pair
), curr_path AS (
      SELECT ARRAY[c1, c2] AS path
      FROM c
      WHERE c2 = 'usd'
   UNION ALL
      SELECT c.c1 || p.path
      FROM c
         JOIN curr_path AS p
            ON c.c2 = (p.path)[1]
      WHERE c.c1 <> ALL (p.path)
)
SELECT path
FROM curr_path
WHERE path[1] = 'eth'
ORDER BY cardinality(path)
LIMIT 1;

    首先，我计算对称闭包。

    然后，我从我们拥有的货币对开始构造“转换路径”数组，然后将新货币添加到可以转换为第一个数组元素且尚未出现在数组中的数组中。

    一旦我得到所有以 . 结尾的转换链'usd'，我就会选择以 . 开头的最短链'eth'。

    • 9

  2. 虽然 Laurenz 的回答很棒，但它并不是最有效的。

    我发现在生产中执行此操作的最佳方法是：

    1. 从尝试找到直接对开始
    2. 然后尝试通过查找第一条腿、最后一条腿和所有连接来找到对
    3. 然后回退到 Laurenz 解决方案

    #2 中提到的查询看起来像这样：

    WITH
  pair_symmetric_closure AS (
    SELECT
      cp1.c1,
      cp1.c2
    FROM currency_pair cp1
    UNION
    SELECT
      cp1.c2,
      cp1.c1
    FROM currency_pair cp1
  )
SELECT *
FROM pair_symmetric_closure psc1
INNER JOIN pair_symmetric_closure pcp2 ON pcp2.c1 = psc1.c2
INNER JOIN pair_symmetric_closure pcp3 ON pcp3.c1 = pcp2.c2
WHERE
  psc1.c1 = 'usd' AND
  pcp3.c2 = 'eth';
    • 1

相关问题