T********i
发帖数: 2416 | 1 你这个思路卖多段相关性紧耦合的票性能还是比不上单机。因为distributed
transaction的开销比内存遍历有向图的开销高几个数量级。 |
|
b*******s
发帖数: 5216 | 2 我按照我的理解画了个图，给魏老师的方案配上外围系统，如果理解错了，不关魏老师
的事
下面加点解释。
图里面示意了一次订票的流程。用户先log in，然后查询始发／终到站信息，以及车次
，这个没什么复杂的，都是静态的，图里面没有表示，随便web server去哪里要
然后用户选了一列车，开始查座位信息，这时web server去向图里面的cache服务器要
数据，这里面的数据表示可以有很多方法，先假定一种，假定这列车有16节车厢，占
2bytes，每车厢256个座，32个bytes，每个座途中可能停靠站32个，算4 bytes，0为未
占，1为占据，基本一列车的占座信息就是这38个bytes. 这个状态和实际座位占用不是
严格对应的，用有向图要更便捷一些，暂时先用这个来示意
用户选中一个座位，递交请求，web server发送对某个位置的请求，就是对那个38个
bytes的一个掩码，想要占据的bits设1，其余0
然后就到了魏老师的系统，在里面处理，如果能占据，就对cache和standby进行update
，等standby的ack，等到了就告诉web server，位置占到了；占不到... 阅读全帖 |
|
z****e
发帖数: 54598 | 3 如果我拿到这个需求
首先第一步，肯定不会马上提出什么解决方案，开始各种计算
那是书呆子的行为，当年我刚毕业时候，公司安排去拓展
有一个项目就是，给一组一堆任务，然后每一个任务都有不同权重
有些人拿到任务，不经过讨论，马上就着手阅读题目，然后开始按照题目要求做
这么做的问题就在于，有些任务权重低，但是任务本身消耗很大
所以有些人努力了半天，其实最后给组里面做出的是负贡献
鄙人其实也是其中之一，这个也没什么好否认的
但是从那以后，我做任何事情之前，都会 我慢
先别急，看清楚形势，分析后，决定优先顺序之后，再做不迟
上来就吭哧吭哧一顿做的，用当时教练的话说，都是书呆子
做事情要有的放矢，人的精力是有限的
好，那首先有了需求，然后先尽可能多地收集各种资料
其他资料也许你不会想到，但是铁道部现在有什么系统
尤其是现在有什么it系统，你总会想到吧？你不会天真地认为
这个需求就是从无到有写一个无依赖无关联的系统吧？
铁道部好歹也算是发展了几十年了，内部会没有一个正在运作的it系统？
其他不敢说，但是拍脑袋想，也能想到，里面肯定会有database
会有app server，还会有一些web serv... 阅读全帖 |
|
N********n
发帖数: 8363 | 4
我不反对，但赵测一张大嘴"有向图是扯"就否了, HOHO |
|
|
k****i
发帖数: 101 | 6 大道至简，老魏谈春运设计思路时开宗明义：车票和沿线各站数据高依赖，所以紧耦合
系统最适合，全局状态有向图可以化解。
好虫基于CAP原理的现成通用方案，解决了throughput的问题，系统可以scale out并且
highly available。
但用RDBMS及sharding来解决数据高依赖，如同oop2所讲，多个transactions难以组合
，还是要定制。
好虫也提到了淘宝用户同时购买多件商品，也是数据高依赖。但fzzh24指出，淘宝双十
一会出现一货多卖的。
所以，春运这个具体问题，首先要争论解决的，是高并发下数据的高依赖性。其他方面
，套用fzzh24的话，是补丁，可以逐步完善。
祝各位节日快乐。 |
|
N*******t
发帖数: 66 | 7 就是计算每个节点的流域面积吗？如果是，这实际上是个很简单的问题，接近O(n)复杂
性吧。简单地说就是，把那些节点连成有向图，然后先历遍所有叶子节点（最上游节点
），计算它们的流域面积（就是节点面积），然后历遍那些已计算流域面积的节点的下
游节点，对那些它们所有上游节点都已计算流域面积的节点计算流域面积（就是把上有
节点的流域面积加起来再加上它自己的节点面积）。然后按这个方法依次历遍下游节点
，计算流域面积。希望没理解错楼主的问题。
node |
|
p***o
发帖数: 1252 | 8 Check closure problem on wiki. Most likely you don't need CP and
a network flow solver is good enough.
系。 |
|
h*******u
发帖数: 15326 | 9 你这个没定义清楚。比如a和b无关，ab是不是等价ba？在K里面你想怎么处理？
系。 |
|
b***e
发帖数: 1419 | 10 Seems it's just a queue construct starting from the super set of roots. For
your example, start with:
{{}|{a,b}, {a}|{b}, {b}|{a}, {a,b}|{}}
Note we use S1|S2 to denote a state where the nodes in S1 must appear and
nodes in S2 must not appear in any future extension.
Pop {}|{a,b}. You can not reach more with empty starting set, so this is it.
Pop {a}|{b}, which means a is in and b is out. This state only reaches {a,c
}|{b}, so we push that in.
Pop {b}|{a}. This state doesn't reach anywhere, ... 阅读全帖 |
|
l*****a
发帖数: 135 | 11 ab == ba,代表了一个“ab两个任务都完成了”这么一个状态 |
|
l*****a
发帖数: 135 | 12 thanks for replying!
For
it.
,c |
|
q*c
发帖数: 9453 | 13 topological sorting.
系。 |
|
b*****9
发帖数: 89 | 14 基本算法database已经说了，用算符优先级算法，相当于把中缀转后会缀表达式。如果
计算器的操作符很多需要扫一下计算器的语法生成一个有向图计算所有操作符栈内和栈
外的优先级，不多的话手算下就可以。具体请参考龙书前几章。 |
|
X****r
发帖数: 3557 | 15 随便想了一下，不一定对。
你引入两个元素和，分别大于和小于其他所有元素，然后把原来的有向图里可
以被传递律推导出来的边删掉，最后枚举一下和之间的路径，每一条就代表你
想要的一个子集。 |
|
l******6
发帖数: 340 | 16 1. 把 == 关系都元素合并到一个node。否则不能确定无环， 把相等元素归并到一个集
合也满足要求
2 以 < 和 <= 的关系建立有向图（想不到 a <= b <= c <= a 成环的例子 ， 如果能
成环只能取等， 会归到1里面吧）
3. topological sort
4. 按topological 的顺序做dfs， 访问的点归为一个子集并从图中删除或者标为不可
再访问。 |
|
N********n
发帖数: 8363 | 17
这么做BC和CD就拴在一起了，要是拆到俩节点上BD票就变低效率的DistTran
了。铁路网是个双联通有向图，这一个ORDER，那一个ORDER, 车票最后就是
全拴在一起强耦合。
淘宝也解决不了这个问题，他们那些商品之间没有多少耦合并发容易，你去
购物时不会下什么只有“这双鞋”和“那本书”都存在时才出手的单子。 |
|
g*****g
发帖数: 34805 | 18 确切说是个全联通有向图。不需要啥tree traversal，广度优先遍历就是。 |
|
o****e
发帖数: 417 | 19 哦，首先澄清一下条件：第一，每秒百万张票(不同起点终点），否则你搞一个1百万张
同样的票就没有必要讨论了。第二，每人限购5张票，那么transaction数目是每秒20万
到1百万之间，实时出票。第三，单机，最多128个CPU；第四，全国任何站点都包括。
第五，12306支持每新出一条线路和车次，就自动更新，无需更新代码。
如果这些条件没错的话瞻仰一下老魏。那么请教老魏你说一下你的设计spec：
1。中国境内火车站大约有5752个，几千个车次，几百条线路，形成一个有向双向可行
驶的网。每秒百万张票意味着图论算法要在1us内完成在这个复杂有向图里的路由问题
。怎么解决？有没有spec可供参考，解决方案里的硬件有没有可能买得到。
2。单机每秒20万到1百万transaction，瓶颈应该在数据库的写动作(和网络传输)。老
魏你的spec要求怎样，解决方案里的硬件有没有可能买得到？
如果老魏能合理地解决以上两个问题，估计就能做得出。要求写代码做出系统来才算正
确的话，那不是讨论问题的方式。 |
|
l*******m
发帖数: 1096 | 20 主要是针对大型项目，incremental build和dependency control. 一般的项目，
cmake就够了。
要说亮点，狗家最牛的当然是index, query. bazel 有一套query的东东。最典型的就
是分析build dependencies. 总之，bazel把build system抽象成一个非循环的有向图。 |
|
w***g
发帖数: 5958 | 21 Aa0 Aa1 Aa2 Aa3 ... Aa9
Ab0 Ab1 Ab2 Ab3 ... Ab9
Ac0 Ac1 Ac2 Ac3 ... Ac9
...
Az0 Az1 Az2 Az3 ... Az9
Ba0 Ba1 Ba2 Ba3 ... Ba9
...
就这么下去一直到
Zz0 Zz1 Zz2 Zz3 ... Zz9
这样产生出来的串长度一共26*26*10= 6760
我觉得能满足要求。
一般问题是一个在四字母字串作为节点的有向图上找long path的问题。
基本套路是深度优先搜索。但是这个问题的longest path版本是著名的
NP难问题。深度优先搜索如果没法立即出结果，那等多久才能出结果
就不好说了。或者说5000可能立刻就出结果了，但是改成50000可能永远
也出不了结果。 |
|
f*******t
发帖数: 7549 | 22 来自主题: Programming版 - 可微分编程 DL与FP的结合，会不会成为未来的编程方式呢？
Yann LeCun：深度学习已死，可微分编程万岁！
原创 2018-01-06 文强 新智元
【新智元导读】LeCun又发表惊人言论，继昨天参与深度学习论战、喷机器人Sophia后
，今天他在Facebook主页发文，称“深度学习已死，可微分编程万岁！”深度学习真的
死了？而可微分编程又是什么呢？
LeCun又语出惊人了，这次直指深度学习——
好，深度学习作为一个流行词，现在时效已过。
深度学习已死，可微分编程万岁！
事情要回溯到前天。
1月4日，AAAI前主席Thomas Dietterich连发10条Twitter，驳斥纽约大学心理学家Gary
Marcus对深度学习的批评。其中，Dietterich提到，
“深度学习本质上是一种新的编程方式——可微分编程——而且这个领域正试图用这种
方式来制定可重用的结构。目前我们已经有：卷积，池化，LSTM，GAN，VAE，memory单
元，routing单元，等等。”
这个说法让英伟达的AI架构VP Clement Farabet深表赞同，Farabet还评价说，这是对
现今深度学习的最好总... 阅读全帖 |
|
f**********e
发帖数: 1994 | 23 是没办法比：这年头 CS 的科研基本上立刻能转化成生产力，“基础学
科科研”通常发展了几十年还是泡泡。人家做个有向图上随机游走的问题
就变出了个 google, 这点基础科学还真是没法比。
如果基础学科科研没法子有效地把知识转成生产力，社会为什么要在上面
持续投资？ 1950 年代基础物理的研究变出了沙皇炸弹，电晶体，超导体，
激光，这些都让人类的力量往上提升了几个数量级。现在的基础生物研究呢？
我真的不知道近代基础生物研究有什么能和以上几个相提并论的成果。面对
越来越差的社会投资，PI 们当然会越来越 BT. |
|
o****h
发帖数: 324 | 24 我需要算有向图中的min cut，而且我的edge capacity都是实数（即有小数点的），在
网上搜了一下， B. Cherkassky& A.B.Goldberg得算法应该是可以的，但是他们的相关
网页现在却不可以用了，请用过他们code的，或是由相关信息的同学帮助，或是知道其
他算法可以解决我的问题的都可以。万分感谢！！！ |
|
c*******t
发帖数: 1095 | 25 就是cycle detection
最好有现成的source能直接用的，没有的话请告诉我有没有稍微快一点的方法，我直接
用C语言 深度搜索 尝试了只有200个点的数据跑了一晚上都没出来，是在没辙了。有其
他方法请告知，例子如图：
谢谢了 |
|
|
|
g****t
发帖数: 31659 | 28 数学班有高人说了.google 哈密顿 cycle,看图论书. |
|
|
|
c*******t
发帖数: 1095 | 31 恩我也知道，我编出来的复杂度就是指数增长的
所以我只问问有没有稍微简单点的
的。 |
|
a*s
发帖数: 131 | 32 Yours sounds very slow.
I used to do it in a recursive way and it was quite fast. |
|
|
j****l
发帖数: 3356 | 34 【 以下文字转载自 USTC 讨论区 】
【 原文由 jollyl 所发表 】
我不知道下面的问题的难度如何，是不是某种NP的？
给定有向图，一个点s和若干点的集合D，要求判断有向steiner树的存在性。
一个约束是对每个点v，都规定了其孩子集合的所有可能，在steiner树中的
孩子集合必须是给定的若干可能中的一个。
我只知道，如果对无向图，当D包含剩下所有点，任意不超过k个孩子都允许，
问题称为degree limited spanning tree，是NPC
对我的这个问题，有没有高手知道答案？ |
|
|
o****h
发帖数: 324 | 36 我需要算有向图中的min cut，而且我的edge capacity都是实数（即有小数点的），在
网上搜了一下， B. Cherkassky& A.B.Goldberg得算法应该是可以的，但是他们的相关
网页现在却不可以用了，请用过他们code的，或是由相关信息的同学帮助，或是知道其
他算法可以解决我的问题的都可以。万分感谢！！！ |
|
B****n
发帖数: 11290 | 37 這應該屬於圖論的東西 比方像Hamiltonian Cycle等
隨便一本圖論的書 就可以確定他要的是那種cycle
如果知道cycle的名字 用google搜尋一下 example:Hamiltonian Cycle code就可以找
到了 這些都有很多現成的code支持 |
|
l******e
发帖数: 470 | 38 200个点的图里的cycle就有可能有非常非常多，exponential的
一晚上找不全也不奇怪
就找一个回路的话DFS，线性时间。 |
|
t***s
发帖数: 602 | 39 职位是quantitative analytics associate intern，第一面，组里的人直接面的嗯
1. 伊介绍伊们组
2. 过简历，问你的career打算
3. 问问题
斐波纳妾数列，给定位置，打印出该位置的数；
C++多态性，STL类，override和overload；
设计一个restaurant booking的类，都有啥要注意的；
有向图里打印所有从特定点出发可以visit到的节点；
在deconstructor里头throw exception的问题；
bet问题，俩队打七场比赛，一场一场bet和一次bet七场的结果能否得到相同的收益；
好像就这些了……伊问的东西很散，我就囧了... |
|
t*******y
发帖数: 637 | 40 有向图里打印所有从特定点出发可以visit到的节点；
这题怎么做？
益； |
|
|
t***s
发帖数: 602 | 42 职位是quantitative analytics associate intern，第一面，组里的人直接面的嗯
1. 伊介绍伊们组
2. 过简历，问你的career打算
3. 问问题
斐波纳妾数列，给定位置，打印出该位置的数；
C++多态性，STL类，override和overload；
设计一个restaurant booking的类，都有啥要注意的；
有向图里打印所有从特定点出发可以visit到的节点；
在deconstructor里头throw exception的问题；
bet问题，俩队打七场比赛，一场一场bet和一次bet七场的结果能否得到相同的收益；
好像就这些了……伊问的东西很散，我就囧了... |
|
t*******y
发帖数: 637 | 43 有向图里打印所有从特定点出发可以visit到的节点；
这题怎么做？
益； |
|
|
H****h
发帖数: 1037 | 45 假设考虑的是有限图。
如果是非周期任两点互相可达的有向图，根据马尔可夫定理，
随机游动一定有一个极限分配，而且处处概率为正。
但具体的数值可能没有简单的表示方法。
如果有周期d，d>1，但任两点可达，则kd+j(j不变，k增长)
步的极限对每个j都是存在的。
如果不是任两点互相可达，那么从任何地方出发，一定会到
达某一个“最低”的互相可达的有向子图，而且再也不会出
来。当然也可能有若干个不同的互相可达的有向子图，进入
每个子图的概率取决于出发点。 |
|
