大象起舞:用PostgreSQL解海盗分金问题_搜狐科技

大象起舞:用PostgreSQL解海盗分金问题_搜狐科技

原信头:大象起舞:运用PostgreSQL处理海盗船共享成绩

发起人

张泽鹏(redraiment):51信用卡信任业务资深的缔造者。

  • 资深的有挖掘习性的动物不填相识:风控已先后51次出土。、信审、标明证实和宁静与协同基金和信任相干的坑
  • 冷技术把持:51内 PostgreSQL、FreeBSD、Emacs、Lisp 宁静技术毒贩
  • 懒惰的巨蟹宫受难者:回绝连声,查找“元自动化”,自动化每个可以自动化的东西

安排绍介

在瞄准的午休时期写一封每周的信,指出云和恩莫的GAI常常绕着朋友圈转,说Elder Yang在Oracle中运用SQL来处理海盗船的成绩《势如破竹:应用SQL处理海盗船共享感兴趣的事最大值化成绩,看见后愉快。,确定赶集。 PostgreSQL 中处理该成绩。

成绩简述

有5美元钞票海盗分为100个金色的。,次由画确定。,瞄准分红一件商品,超越部份地(包含本人)认可度过。,另外,瞄准该测算表的海盗将被处决。。现时必要第人家海盗的冠处理一件商品。。

必需品辨析

原包装提到大约成绩可以用W来处理。,还成绩的辨析是暂时的的。,因而我要在我的思维指引航线中加少许。。

率先,可以从以下成绩中茫然的以下有益新闻:

  • 海盗人数:5
  • 金色的全部含义:100
  • 批量结出果实:命令曾经确定了。,海盗可以编号为1-5。
  • 交际必要的:制裁百分法 > 50%
  • 冠一件商品:成绩中海盗们需争得”保命”和”金色的”,前者比后者更要紧。,这样有三个结出果实,支出人家人家地扩张。

使准备好的成绩假说一切的海盗都是标志的。、十足情报,这平均数海盗们将使负担或压迫。:当且仅当,认可今天测算表的腰槽,高于回绝今天处理一件商品的腰槽,独一无二的认可。这样,博得今天处理一件商品,不管怎样如何有50%的海盗必要贿买。,让他们的支出超越后续一件商品。。

大约指引航线和总统竞选不常见的使有效。。比方,特朗普有指望当总统,每个共和党人都买到一枚金色的。;希拉丽相称总统,将只给每位民主党围攻发一枚金色的。腰槽很小。,但单方的围攻都赚得这少许。,结果缺点党当总统,这缺点小汇成。,因而他们都证实本人参加社交聚会的围攻。,创造仿佛稳定的最大报应。

布置拆开

一句话,为了贿买。,先默许竞争者的贿买战术,企图高地的的报应(吓唬性命的海盗)营救他们、救了他的命的海盗扩张了他的金色的全部含义。;失效贿买本钱,竞争者报答最低消费的小圈子的在前贿赂。

这平均数,5美元钞票海盗的冠战术倚靠四个一组之物海盗的战术。,四名海盗的战术倚靠三名海盗。,先后类推。大约指引航线,这是原包装提到的反向指引航线。:

  • 1海盗,他立即的懂得100枚金色的。,换句话说,分派测算表是:[100]
  • 2海盗,不管怎样瞄准什么一件商品,二者都都无能力的超越100居先的测算表支出。,因而次要的个提一件商品的海盗无能力的认可无论哪一个一件商品,换句话说,第人家海盗会在大约一场中不知不觉入睡。,分派测算表是:[零值], 100]
  • 3海盗,够用人家一场是海盗死了。,他可以用有助于贿买。,没金色的。,即冠分派测算表是:[100, 0, 0]
  • 4海盗,同样地,不管怎样瞄准什么一件商品,二者都都不能超越100的最大报应率。,因而有人家海盗命定要支持。,剩的两名海盗没从居先的测算表中沾光。,由于给他们每人一枚金色的。:[98, 0, 1, 1]
  • 5海盗,前四名海盗可以贿赂。,但比照最低消费本钱基音的,上朝反方向海盗获零进项在前贿赂,那么选择人家随机支出1的海盗做成某事人家。,给他2个金色的。,这样有两种处理一件商品。:[97, 0, 1, 2, 0] 或 [97, 0, 1, 0, 2]

训练

专门指引航线的人工推理,现时就开端运用它。 SQL 模仿大约指引航线。倒缺点说 SQL 这是处理这一成绩的冠选择。,据我看来度过大约成绩来获知和粘结。 SQL 的知。

标明构图

在大约成绩上,每个海盗都必要保存本人的全部含义和支出。。规范 SQL 言语中,除非企图数值越过、根本标明典型,如字母行,街区也作为复合标明典型来证实。,语法书是街区。…]`。海盗新闻可以贮存器在两个一段的整体街区中。,在内侧地第

保留海盗人数,次要的个一件商品保存海盗的汇成。,结果海盗遗失性命,数额将为空。。

譬如,街区〔2〕, 代表海盗号2没性命、街区〔4〕, 98,海盗4的高地的报应是98枚金色的。。

财产分配战术——是人多个海盗的新闻——也可以是,换句话说,二维整体街区。譬如,是你这么说的嘛!两个海盗的分派战术是:街区[〔1〕, 伤病军人, [2, 100]]`,第人家海盗屈服了。,次要的个海盗有100个金色的。。

贿买算法

比照后面的辨析,实时贿买的举步如次:

1。比照每个海盗的支出来分派分派战术。:

空是最上进的

B)钱的全部含义很小。

2。扩张海盗的上半年汇成

  • 半品脱全部含义:被拒绝或被抛弃的人或事物本人,过剩的海盗总额
    • N是偶数。:半品脱全部含义为`n / 2`
    • n是使诧异的。:半品脱全部含义为`(n + 1) / 2`
  • 贿买战术
    • 总数为 null 时,更代替0
    • 总数不 null 时,加1

三。调停后半时海盗支出为0。

本钱升序

PostgreSQL原始发生未企图流通时间街区的排序效能(intarray可插件做成某事sort职务可是用于非null的一位整数街区),二维整体街区构图的分派战术排序,率先必要将街区冲洗成行。,重用命令 度过排序。

不过PostgreSQL企图了将街区扩大成行的unNest'职务,但它真正的功能是平面化。,将使深奥构图变平。

譬如:`select UNEST(街区)〔1〕,2],[3,4]])` 将统计表4行。,而缺点认为会发生的双线记载。

这样,您必要本人创造街区的一维冲洗。。必要运用 `array_lower(anyarray, int) 和 `array_upper(anyarray, int) 街区下标的上下凡是由两个职务买到的。,那么用 `generate_series` 体格下标序列。

在意:SQL 做成某事街区下标是从 `1` 开端。假说战术街区的名称为 `strategy`,冲洗 排序的布置遗传密码如次:

select

strategy[i][1] as id,

strategy[i][2] as amount

from

generate_series(array_lower(strategy, 1),

array_upper(strategy, 1)) as t(i)

order by

amount nulls first

在内侧地 `nulls first` 在余地中布置。 `null` 排在最前。PostgreSQL 中,`null` 默许比非 `null` 值大,因而升序是够用的。,递减次序时排在最前。做 `nulls first` 或 `nulls last` 中间休息该默许行动。

邮票联想

为了断定关系代词海盗属于联想(前部份地),必要给是你这么说的嘛!排好序的列表标注新的下标, PostgreSQL 中企图了 `row_number()` 窗口职务,可以博得今天行的线数;接连地用职务 `array_length(anyarray, int) 可博得街区的一段,够用人家必要贿买的海盗的下标是 `(array_length(strategy, 1) + 1) / 2`。假说是你这么说的嘛!排好序的标明存入暂时表 `strategies`,则计算每人家海盗的贿买本钱布置遗传密码如次:

select

id,

amount,

case

— 断定设想是联想

when row_number() over () <= (array_length(strategy, 1) + 1) / 2

then 聚结(量) + 1, 0) — 活海盗金色的上升,亡故海盗还魂

else 0 — 够用部份地的海盗没金色的。

end as cost

from

strategies

分派一件商品

结果贿买的本钱(`sum(cost)`)高于总金色的全部含义(`100`),平均数无法买到超越半品脱的同意,抚养上一次的一件商品,即保存 `amount` 作为每个海盗的最大进项;另外,减去本钱剩的执意新增海盗的高地的进项(`100 – sum(cost)`),宁静海盗改用`cost`作为新朝反方向的最大进项。

在”标明构图”一节中曾经提过,战术的标明构图是二维整体街区,绪言为了排序,已将街区转成行记载,先必要运用 PostgreSQL 的窗口职务 `array_agg` 再将行记载转成街区,同时运用 `array_cat` 添加物人家海盗新闻。

假说是你这么说的嘛!邮票好联想的标明存入暂时表 `strategies`,则计算分派一件商品的布置遗传密码如次:

select

case

when sum(cost) <= 100 then -- 断定设想能存活

array_cat(array_agg(array[id, cost]),

街区[街区]一段(战术), 1) + 1,

100 – 和(本钱)]::int

else

array_cat(array_agg(array[id, 全部含义,

街区[街区]一段(战术), 1) + 1,

伤病军人]::int[])

end

from

strategies

迭代

像这样,已完全的分派一件商品单次调停的效能:倘若任性分派一件商品,能算出再扩张人家海盗时的最优分派战术。为了买到5个海盗的最优解,只需把大约效能迭代5次那就够了;但迭代指引航线中任何时候的输出都要作为再的输出。SQL完全地企图了 `with recursive`,同时容量迭代和管道两个效能!

`with` 部件用于明确只在人家查询中在的暂时表,带上 `recursive` 保留字后,实行的连声查询,譬如连声查询一切的子典型。我一向觉得大约名字太轻易给错误的劝告,它的专门实行指引航线实则肖像射程在前搜索(BFS),譬如:

with recursive foo(n) as (

values (1), (3), (5) — 队列初始影响

union all

select n + 3 from foo where n < 5

)

select * from foo;

大约连声查询布置遗传密码职务相当于上面的迭代 Python 布置遗传密码:

(队列), FO) = ([1, 3, 5], []) # 对应 values (1), (3), (5)

while queue:

n = (0)

(n)

if n < 5: # 对应 where n < 5

queue.append(n + 3) # 对应 select n + 3

print foo # 对应 select * from foo

是你这么说的嘛!两端布置遗传密码的实行结出果实都是:1、3、5、4、6、7,共6项标明。在内侧地前三项`1`、`3`、`5`是队列设定初值的标明,而`4`由`1`体格、6’是由3体格的、7’是由4体格的。

回归海盗分配金成绩,假说前一节做成某事分派战术职务被明确。,迭代布置遗传密码如次:

with recursive 向行贿(战术) as (

values (街区〔1〕, 100]]) — 初始影响,海盗夺走了每个

union all

select

贿买(战术) — 体格下人家分派战术

from

spoils

where

array_length(strategy, 1) < 5

)

换句话说,当战术一段没有5时,连声体格新战术。

完成布置遗传密码

像这样,必需品做成某事一切的效能点对应。 SQL 处理一件商品是可以处理的。:度过5次迭代,选出街区一段(海盗人数)为5的一件商品那就够了。以下是完成的 SQL 布置遗传密码,在 PostgreSQL 可立即的实行:

with recursive 向行贿(战术) as (

values (街区〔1〕, 100]]) — 初始影响,海盗夺走了每个

union all

select (

with strategies as ( — 用嵌套的 with 该部件将本钱计算到下人家影响。

select

*,

case

when row_number() over () <= (array_length(strategy, 1) + 1) / 2

then 聚结(量) + 1, 0)

else 0

end as cost

from (

select

strategy[i][1] as id,

strategy[i][2] as amount

from

generate_series(array_lower(strategy, 1),

array_upper(strategy, 1)) as t(i)

order by

amount nulls first

) as t

)

select

case

when sum(cost) <= 100 then -- 断定设想能存活

array_cat(array_agg(array[id, cost]),

街区[街区]一段(战术), 1) + 1,

100 – 和(本钱)]::int

else

array_cat(array_agg(array[id, 全部含义,

街区[街区]一段(战术), 1) + 1,

伤病军人]::int[])

end

from

strategies

)

from

spoils

where

array_length(strategy, 1) < 5

)

select

5 + 1 – strategy[i][1] as id,

strategy[i][2] as amount

from (

select

strategy,

generate_series(array_lower(strategy, 1),

array_upper(strategy, 1)) as i

from

spoils

where

array_length(strategy, 1) = 5

) as t

order by

id;

结出果实如次。,功能良好。,在我的本土试场中只必要 1ms:

新的应战

是你这么说的嘛!一件商品只买到人家最优解,从绪言辨析可知,5个海盗分金时有2个最优解,从此处杨长者又抨击了:”愿意只用一句 SQL 博得一切的的最优解?”有兴趣的小同伴可以进步应战一下,欢送微信交流!统计表搜狐,检查更多

责任编辑:

发表评论

电子邮件地址不会被公开。 必填项已用*标注