[問題] 測資產生器

看板C_and_CPP作者 (請輸入暱稱)時間9年前發表 (2016/04/30 07:06), 9年前編輯推噓10(10推 0噓 36→)
留言46則, 9人參與, 最新討論串1/1
最近要寫份報告，分析Dijkstra和Bellman-Ford 演算法的效率 這兩個演算法並不難寫，但我對與生成測資卻毫無方向 報告希望我們測試在不同測資下演算法的表現 應該不是單純亂數生成吧，google很久也沒頭緒 想請大家給我些方向，感謝!! ----- Sent from JPTT on my LGE LG-D838. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.9.213 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1461999982.A.E8A.html
→
04/30 15:15, , 1F
方向主要是各自的 best case, worst case, average case
04/30 15:15, 1F
→
04/30 15:41, , 2F
抱歉 還是不太瞭解，可否告訴我如何生成一張圖 可以讓
04/30 15:41, 2F
→
04/30 15:41, , 3F
演算法運行
04/30 15:41, 3F
→
04/30 15:44, , 4F
用手畫好再做成你的程式能吃的格式啊
04/30 15:44, 4F
→
04/30 15:49, , 5F
小數據單然沒問題，可要比較程式的執行時間 需要極大的
04/30 15:49, 5F
→
04/30 15:49, , 6F
資料量，我不會生成
04/30 15:49, 6F
→
04/30 15:55, , 7F
大量的話，當然 random case 也是一種方法，但是 random
04/30 15:55, 7F
→
04/30 15:55, , 8F
對某些演算法是 best, 對另一些演算法是 worst 或都不是
04/30 15:55, 8F
→
04/30 15:56, , 9F
你找出不同 case 的生成規則就能寫程式生成
04/30 15:56, 9F
→
04/30 15:57, , 10F
像是一字長蛇陣等等，手畫只能畫十節，依樣產生一百萬節
04/30 15:57, 10F
→
04/30 15:57, , 11F
這你要自己去想一想啦，不同題目會有不同的 case 要考慮
04/30 15:57, 11F
→
04/30 16:03, , 12F
也許是我對演算法不夠熟悉才想不出規則吧， 我再研究
04/30 16:03, 12F
推
04/30 16:26, , 13F
在linux下可以用/dev/urandom生成亂數，那應該是真亂數
04/30 16:26, 13F
感謝，現在主要在煩惱生成圖的規則
→
04/30 16:35, , 14F
mt19937很夠用了，用machine的random會很慢
04/30 16:35, 14F
→
04/30 16:36, , 15F
題外話，想用真正的亂數，請找量子電腦 ^.<
04/30 16:36, 15F
哈哈 不需要那麼專業 ※ 編輯: kevin898y (180.217.9.213), 04/30/2016 16:39:04 ※ 編輯: kevin898y (180.217.9.213), 04/30/2016 16:40:19
推
04/30 20:34, , 16F
Linux上面那個也不是真亂數啦 除非你接的裝置可以偵測
04/30 20:34, 16F
→
04/30 20:35, , 17F
熱噪訊號或是上面說的量子電腦
04/30 20:35, 17F
→
04/30 20:35, , 18F
這個我不同意，Linux 會吸收多種亂源 (我不是說八卦板)
04/30 20:35, 18F
→
04/30 20:36, , 19F
所以 /dev/random 的不可預測性是很好的
04/30 20:36, 19F
→
04/30 20:36, , 20F
那所謂真亂數是相對 pseudo random number generator
04/30 20:36, 20F
→
04/30 20:37, , 21F
來說的，/dev/random 可以稱為真亂數沒錯啊
04/30 20:37, 21F
推
04/30 20:39, , 22F
可是跟數學上定義的隨機亂數好像又有差了??
04/30 20:39, 22F
→
04/30 20:40, , 23F
統計學上定義的隨機亂數根本不用具備不可預測性好嗎 XD
04/30 20:40, 23F
→
04/30 20:41, , 24F
/dev/random 和 /dev/urandom 也是有符合你要的統計特性
04/30 20:41, 24F
→
04/30 20:41, , 25F
它不是直接拿現實生活中的亂數源吐給你而已
04/30 20:41, 25F
推
04/30 20:42, , 26F
喔喔 長知識了
04/30 20:42, 26F
推
05/01 00:24, , 27F
要給seed就是pseudo吧?
05/01 00:24, 27F
推
05/01 12:42, , 28F
void *ptr = malloc(0);
05/01 12:42, 28F
→
05/01 12:42, , 29F
srand((unsigned)ptr);
05/01 12:42, 29F
→
05/01 12:42, , 30F
free(ptr); 如何？
05/01 12:42, 30F
→
05/01 12:47, , 31F
首先是 srand()/rand() 用的 LFSR 演算法很容易破解
05/01 12:47, 31F
→
05/01 12:48, , 32F
只要觀察 2N 個輸出亂數就能完整重現 N 個 register 的
05/01 12:48, 32F
→
05/01 12:49, , 33F
內部狀態，進而預測接下來吐出的每一個亂數
05/01 12:49, 33F
→
05/01 12:49, , 34F
等等歪樓了啦，原 PO 是要產生測資，為什麼我們在講
05/01 12:49, 34F
→
05/01 12:50, , 35F
不可預測性... 產生測資根本不需要不可預測好嗎
05/01 12:50, 35F
→
05/01 12:53, , 36F
malloc 能供應給你的 random bits 不算太多
05/01 12:53, 36F
→
05/01 12:54, , 37F
你在 PC 上第一次 malloc 得到的指標，尾巴永遠是一樣的
05/01 12:54, 37F
→
05/01 12:55, , 38F
仔細探討下去可能要長篇連載了，總之 /dev/urandom 萬歲
05/01 12:55, 38F
推
05/01 16:10, , 39F
歪樓好像是我的錯....(眼殘看錯)
05/01 16:10, 39F
推
05/02 11:36, , 40F
05/02 11:36, 40F
→
05/02 11:36, , 41F
05/02 11:36, 41F
→
05/02 11:37, , 42F
生成測資是滿冷門的問題 目前我想到的方法 一種是找現成的
05/02 11:37, 42F
→
05/02 11:37, , 43F
一種是random生成的 就是上面兩個網址
05/02 11:37, 43F
推
05/02 11:40, , 44F
如果還要更深入的話 可以設定diameter、connectivity諸如此
05/02 11:40, 44F
太感謝你回答我的問題了 我在研究看看
→
05/02 11:42, , 45F
類的統計指標 不過這個就複雜得多了 我也不是很懂
05/02 11:42, 45F
※ 編輯: kevin898y (180.217.1.240), 05/03/2016 09:40:47
推
05/03 15:24, , 46F
同學是哪位阿
05/03 15:24, 46F
‣ 更多 kevin898y 的文章
文章代碼(AID): #1N95bkwA (C_and_CPP)