Re: [問題] 從幾筆資料中挑出資格符合者

[abliou (把青春freeze)]

※ 引述《Hyozero (123)》之銘言：
: 假如現在有兩筆男生和女生的身高體重資料
: 要從男生裡面挑三個出來，從女生裡面挑兩個出來
: 挑選標準是身高最矮者，如果身高一樣矮則以體重來比較，若體重又一樣則選編號較小者
: 舉例：
: 編號01~06是男生，07~12是女生
: 編號  01  02  03  04  05  06    07  08  09  10  11  12
: 身高 177 168 167 180 168 168   162 155 172 158 165 158
: 體重  55  60  65  63  62  58    47  48  49  45  45  45
: 所以結果會挑選出男生：02 03 06
:                 女生：08 10 (編號10比編號12小，所以選編號10)
: 當遇到這樣的問題時，我是想先個別以vector來儲存資料
: 例如：vectorM[0]表示01號男生，vectorM[5]表示06號男生
:       vectorW[0]表示07號女生，vectorW[5]表示12號女生
:       vectorMh[0]是01號男生的身高，vectorMh[5]是06號男生的身高
:       vectorMw[0]是01號男生的體重，vectorMw[5]是06號男生的體重
:       vectorWh[0]是07號女生的身高，vectorWh[5]是12號女生的身高
:       vectorWw[0]是07號女生的體重，vectorWw[5]是12號女生的體重
: 以男生而言
: 先比較vectorMh，原本vectorMh的資料依序是 177 168 167 180 168 168
: 我是想以sort ( vectorMh.begin(), vectorMh.end() ) 來排出順序大小
: 這樣的話，vectorMh中的資料排序會變成 167 168 168 168 177 180
: 此時，167一定會被選中，但是三個168必須比較 體重 ，再從中選出兩個
: 問題來了，我要怎麼知道身高168的人是哪三位呢？
: 我只知道必須用for loop 去把所有男生的身高資料掃一次，才能抓出誰是身高168
: 但是當資料數量非常多的時候，這樣去掃會變得非常浪費時間
: 請問遇到這樣的問題時，有什麼特別的方法可以節省程式的執行時間呢？
: 感恩~~~

我也是新手..如果有違反版規..我會馬上刪文...

我的問題是這樣的..剛剛看完文章跟下面的推文...

我想知道vector的library所用的sort方法有比較特殊嘛?

因為我如果是從特定資料群中挑特定一筆資料...那直接用for loop的話...

比如說資料十筆...那回圈跑十次就能得到當中的最大最小值

但是以vector內建的sort...以目前我所知道的qick sort...

在best case下要跑10次(10 X log 10)..worst case要跑100次(10^2)...

然後只取前面的第一個元素...

如果vector的內建寫法也是用c的for loop..而不是組語的寫法

那跑比較多次的時間會花比較多吧?

所以用vector的sort除了可以減少程式碼外..所用去的代價會大一些

還不如用for loop重寫....我不知道這樣的想法對不對...


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.113.239.44
→ loveme00835:sort 演算法是採用 introsort 最壞時間複雜度是
→ loveme00835:O(NlogN), 只取最小元素可以用min/max_element, 只取
→ loveme00835:前n個最小元素有nth_element, 前n個最小元素作排序有
→ loveme00835:partial_sort, STL主要還是以通用性為考量, 對效能有
→ loveme00835:強烈要求的話, 至少泛型演算法要選對
→ abliou:所以以目前這case自己寫會好一些嘛？我只是比較疑惑這問題
→ abliou:還是感謝您的回答...!!
→ loveme00835:不要自己寫, 遇到相關問題時先找函式庫有沒有合用的,
→ loveme00835:沒有合用的才來考慮自己寫, 現在的電腦執行速度都很快
→ loveme00835:所以優先考量的應該是正確性而不是速度，先寫對再來求
→ loveme00835:快, 自己寫一個排序開發時間長又容易寫錯當機, 而且就
→ loveme00835:算你自己寫一個, 也很難比標準庫還要快...
→ abliou:我知道了，謝謝你!