RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 629090
Accepted
Xander
Xander
Asked:2020-02-17 17:25:29 +0000 UTC2020-02-17 17:25:29 +0000 UTC 2020-02-17 17:25:29 +0000 UTC

层次结构的同步

  • 772

有一个分层数据结构,它会根据从外部源上传的内容定期更新。卸载可以是完整的,也可以针对一个特定节点。

每个节点在上传时都有一个布尔值“隐藏”属性。另外,节点有一些内容,可能是空的。此外,每个节点都有一个布尔“空”属性,需要在同步时重新计算。

如果节点匹配所有条件,则必须将空属性设置为 true:

  • 节点内容为空
  • 节点没有非空和非隐藏的孩子

在卸载的时候,保证子进程跟在他们的父进程之后,所以之前empty的定义是这样的:

该程序按顺序进行卸载,每个节点都添加到数据库或更新它(如果它已经存在)。查看上传内容是否为空内容。在其基础中选择该节点的既不为空也不隐藏的直接子节点。基于此将值设置为空。

之后,程序依次沿着该节点的父节点链上升,并为它们执行相同的过程。这是必要的,因为卸载的未处理部分将包含有关子项的信息,如果他们的列表或空值和隐藏值被更新,那么这可能会使父项的空值无效,并且需要重新计算。

我知道该算法看起来不是最优的,但我没有编写它。

现在任务来了:使节点可以作为另一个节点的别名(链接)。这是实现并行层次结构所必需的。

相应地,在空计算中,必须考虑到如果引用非空节点,则该节点必须是非空的。问题是别名可以出现在它所指的节点之前和之后的卸载中。

考虑到所描述的要求,实现这种结构的最佳方法是什么?

UPD:PosgreSQL 通过 sqlalchemy 用作数据库。因此,所有同步工作都由 Python 脚本执行。

节点表有字段:id、parent_id、link_id、hidden、empty,以及一些不以任何方式参与此任务的字段。

parent_id 和 link_id 是来自同一张表的 id。

还有一个包含内容的表格,每个节点从中获取一定数量的元素。

алгоритм
  • 1 1 个回答
  • 10 Views

1 个回答

  • Voted
  1. Best Answer
    Mike
    2020-02-18T02:47:34Z2020-02-18T02:47:34Z

    添加一个changed类型的字段int。我们建立一个部分索引:在列上create index tree_change on tree(changed) where changed is not null。从外部加载数据时,直接changed=1为所有内容或隐藏发生变化的记录设置字段应更改的方式。在这个阶段根本不考虑记录的层次结构。所有新条目也有.emptychanged=1

    加载外部数据后,我们执行以下查询:

    with recursive Q(id, parent_id, link_id, changed) as(
      select id, parent_id, link_id, changed from tree where changed=1
     union all
      select t.id, t.parent_id, t.link_id, Q.changed+1
        from Q, tree t where t.id=Q.parent_id or t.link_id=Q.id
    )
    UPDATE tree AS t
       SET changed = n.changed
      FROM (
        select id, max(changed) changed
          from Q where changed>1
         group by id
      ) n
     WHERE t.id = n.id;
    

    它为层次结构中的所有父记录(以及它link_id指示更改的记录)公开changed比子记录多 1。事实上,这是树中从修改后的节点到给定父节点的转换次数。如果同一节点与多个更改的子元素的距离不同,则取其中的最大值。

    因此,将为所有(分层)依赖于已更改节点的节点设置已更改。

    然后,在循环中,当更新至少更改了一条记录时,我们执行以下请求:

    update tree t
       set empty=(case when content is not null then 0
                  else (select coalesce(min(t1.empty::int),1)
                          from tree t1
                         where t1.parent_id=t.id or t1.id=t.link_id)
                 end)::boolean,
           changed=NULL
     where changed=$N
    

    哪里$N是循环迭代的序号从1到changed第一个请求后收到的最大值(直接取最大值是没有意义的,改变记录本身就表明这样的数字仍然存在)。

    循环中的每个查询都会根据节点本身(首先)及其所有直接子节点(如果节点本身没有内容)的状态为树节点计算空值。没有必要在层次结构中走得更深,因为只有在所有孩子都重新计算后才会更新父母(因为孩子显然有一个更小的changed)。

    我没有考虑字段值hidden,将其添加到第二个请求的状态计算逻辑中。

    • 1

相关问题

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    Python 3.6 - 安装 MySQL (Windows)

    • 1 个回答
  • Marko Smith

    C++ 编写程序“计算单个岛屿”。填充一个二维数组 12x12 0 和 1

    • 2 个回答
  • Marko Smith

    返回指针的函数

    • 1 个回答
  • Marko Smith

    我使用 django 管理面板添加图像,但它没有显示

    • 1 个回答
  • Marko Smith

    这些条目是什么意思,它们的完整等效项是什么样的

    • 2 个回答
  • Marko Smith

    浏览器仍然缓存文件数据

    • 1 个回答
  • Marko Smith

    在 Excel VBA 中激活工作表的问题

    • 3 个回答
  • Marko Smith

    为什么内置类型中包含复数而小数不包含?

    • 2 个回答
  • Marko Smith

    获得唯一途径

    • 3 个回答
  • Marko Smith

    告诉我一个像幻灯片一样创建滚动的库

    • 1 个回答
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Алексей Шиманский 如何以及通过什么方式来查找 Javascript 代码中的错误? 2020-08-03 00:21:37 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    user207618 Codegolf——组合选择算法的实现 2020-10-23 18:46:29 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5