作者kevin898y (请输入昵称)
看板C_and_CPP
标题[问题] 测资产生器
时间Sat Apr 30 15:06:20 2016
最近要写份报告，分析Dijkstra和Bellman-Ford 演算法的效率
这两个演算法并不难写，但我对与生成测资却毫无方向
报告希望我们测试在不同测资下演算法的表现
应该不是单纯乱数生成吧，google很久也没头绪
想请大家给我些方向，感谢!!
-----
Sent from JPTT on my LGE LG-D838.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 180.217.9.213
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1461999982.A.E8A.html
1F：→ Schottky: 方向主要是各自的 best case, worst case, average case 04/30 15:15
2F：→ kevin898y: 抱歉 还是不太了解，可否告诉我如何生成一张图 可以让 04/30 15:41
3F：→ kevin898y: 演算法运行 04/30 15:41
4F：→ Schottky: 用手画好再做成你的程式能吃的格式啊 04/30 15:44
5F：→ kevin898y: 小数据单然没问题，可要比较程式的执行时间 需要极大的 04/30 15:49
6F：→ kevin898y: 资料量，我不会生成 04/30 15:49
7F：→ Schottky: 大量的话，当然 random case 也是一种方法，但是 random 04/30 15:55
8F：→ Schottky: 对某些演算法是 best, 对另一些演算法是 worst 或都不是 04/30 15:55
9F：→ Schottky: 你找出不同 case 的生成规则就能写程式生成 04/30 15:56
10F：→ Schottky: 像是一字长蛇阵等等，手画只能画十节，依样产生一百万节 04/30 15:57
11F：→ Schottky: 这你要自己去想一想啦，不同题目会有不同的 case 要考虑 04/30 15:57
12F：→ kevin898y: 也许是我对演算法不够熟悉才想不出规则吧， 我再研究 04/30 16:03
13F：推 wtchen: 在linux下可以用/dev/urandom生成乱数，那应该是真乱数 04/30 16:26
感谢，现在主要在烦恼生成图的规则
14F：→ Caesar08: mt19937很够用了，用machine的random会很慢 04/30 16:35
15F：→ Caesar08: 题外话，想用真正的乱数，请找量子电脑 ^.< 04/30 16:36
哈哈 不需要那麽专业
※ 编辑: kevin898y (180.217.9.213), 04/30/2016 16:39:04
※ 编辑: kevin898y (180.217.9.213), 04/30/2016 16:40:19
16F：推 Clangpp: Linux上面那个也不是真乱数啦 除非你接的装置可以侦测 04/30 20:34
17F：→ Clangpp: 热噪讯号或是上面说的量子电脑 04/30 20:35
18F：→ Schottky: 这个我不同意，Linux 会吸收多种乱源 (我不是说八卦板) 04/30 20:35
19F：→ Schottky: 所以 /dev/random 的不可预测性是很好的 04/30 20:36
20F：→ Schottky: 那所谓真乱数是相对 pseudo random number generator 04/30 20:36
21F：→ Schottky: 来说的，/dev/random 可以称为真乱数没错啊 04/30 20:37
22F：推 Clangpp: 可是跟数学上定义的随机乱数好像又有差了?? 04/30 20:39
23F：→ Schottky: 统计学上定义的随机乱数根本不用具备不可预测性好吗 XD 04/30 20:40
24F：→ Schottky: /dev/random 和 /dev/urandom 也是有符合你要的统计特性 04/30 20:41
25F：→ Schottky: 它不是直接拿现实生活中的乱数源吐给你而已 04/30 20:41
26F：推 Clangpp: 喔喔 长知识了 04/30 20:42
27F：推 mike0227: 要给seed就是pseudo吧? 05/01 00:24
28F：推 CoNsTaR: void *ptr = malloc(0); 05/01 12:42
29F：→ CoNsTaR: srand((unsigned)ptr); 05/01 12:42
30F：→ CoNsTaR: free(ptr); 如何？ 05/01 12:42
31F：→ Schottky: 首先是 srand()/rand() 用的 LFSR 演算法很容易破解 05/01 12:47
32F：→ Schottky: 只要观察 2N 个输出乱数就能完整重现 N 个 register 的 05/01 12:48
33F：→ Schottky: 内部状态，进而预测接下来吐出的每一个乱数 05/01 12:49
34F：→ Schottky: 等等歪楼了啦，原 PO 是要产生测资，为什麽我们在讲 05/01 12:49
35F：→ Schottky: 不可预测性... 产生测资根本不需要不可预测好吗 05/01 12:50
36F：→ Schottky: malloc 能供应给你的 random bits 不算太多 05/01 12:53
37F：→ Schottky: 你在 PC 上第一次 malloc 得到的指标，尾巴永远是一样的 05/01 12:54
38F：→ Schottky: 仔细探讨下去可能要长篇连载了，总之 /dev/urandom 万岁 05/01 12:55
39F：推 wtchen: 歪楼好像是我的错....(眼残看错) 05/01 16:10
42F：→ DJWS: 生成测资是满冷门的问题 目前我想到的方法 一种是找现成的 05/02 11:37
43F：→ DJWS: 一种是random生成的 就是上面两个网址 05/02 11:37
44F：推 DJWS: 如果还要更深入的话 可以设定diameter、connectivity诸如此 05/02 11:40
太感谢你回答我的问题了
我在研究看看
45F：→ DJWS: 类的统计指标 不过这个就复杂得多了 我也不是很懂 05/02 11:42
※ 编辑: kevin898y (180.217.1.240), 05/03/2016 09:40:47
46F：推 leo850319: 同学是哪位阿 05/03 15:24