Re: [問題] 傳輸時間非線性

[wwwc (secret)]

※ 引述《yzugsr (Bird)》之銘言：
: ※ 引述《wwwc (secret)》之銘言：
: :         tmp = alice.gets
: 我不是很確定
: 但我看Ruby source code中gets的實作 (在io.c)
: 他應該是每次最多讀8192 bytes
: 然後附加到之前的字串上
: 所以一次讀1M左右  可能會造成不斷的allocate memory & copy data
: 而且看到這行
:                 rb_str_resize(str, last + len);
: 似乎每次讀取  只會allocate剛剛好的memory
: 所以看樣子  當資料足夠大的時候
: 這個演算法會有O(N^2)的time complexity
: ==
: 其實手邊沒有灌ruby的環境
: 以上純屬嘴炮 XD
: gets看起來是用在讀取一般文字輸入
: 資料量大的時候最好不要用gets
: 試試用別的function還會不會這樣
: P.S. write我有稍微看一下  應該是O(N)沒問題
string_length   time(seconds)
10000000        9.915431
20000000        42.183346
30000000        97.629504
40000000        164.325812
50000000        213.681785
60000000        395.54032
70000000        468.580234
80000000
90000000
100000000

以上是把gets改成read後的結果
不但非線性關係
而且花的時間遠超過gets !?
(空白的部分還沒跑完)
很納悶...

會不會是ruby版本的問題？(兩台電腦的版本不同)
我把code交換放在不同的機器上後
似乎就是線性關係
而且時間大幅減少
gets跟read也沒有什麼差異了!?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.109.16.218
→ godfat:那可能是某台的 ruby 壞了？對了，引言盡量不要放在最後面
推 godfat:比較不方便閱讀
已修改！
※ 編輯: wwwc            來自: 140.109.16.218       (06/21 15:01)
推 godfat:啊，感謝你 @_@b
→ wwwc:但如果把string length再加大十倍 無論用gets或read
→ wwwc:結果都不是線性 所以資料長度超過一定值就會失去線性關係嗎？
→ godfat:我又試了一下，好像跨到某個臨界值時間就會怪掉
→ godfat:我在時間開始暴走的長度，大約是256MB, 跟記憶體配置有關吧
→ godfat:要那麼巨大的資料量又要保持線性關係，應該不能這樣做
→ wwwc:感謝解答！