Re: [閒聊] VC2005 的 qsort 好像有bug...

看板C_and_CPP作者zhim (zhim)時間14年前 (2009/12/05 00:34)推噓4(4推 0噓 14→)

留言18則, 7人參與討論串3/3 (看更多)

謝謝回應這次烏龍了以下為藉由這討論的機緣衍生的雙態議題將原qsort 改成採用回覆bool 型態的compare routine. 初步實驗 5, 6, 8, 10, 20, 30 個 double inputs 都還正確在sort doubles 異值多時會比3態的好些同值多時會慢些另外 shortsort() 也要改一下 (沒貼code) bool compare_record( const void *arg1, const void *arg2 ) { return ( (*(s_reorder *)arg2).value> (*(s_reorder *)arg1).value); } //把所有用到compare的地方改成採用 bool 邏輯 void qsort_ ( void *base, size_t num, size_t width, bool ( *comp)(const void *, const void *) ) { char *lo, *hi; /* ends of sub-array currently sorting */ char *mid; /* points to middle of subarray */ char *loguy, *higuy; /* traveling pointers for partition step */ size_t size; /* size of the sub-array */ char *lostk[STKSIZ], *histk[STKSIZ]; int stkptr; /* stack for saving sub-array to be processed */ if (num < 2) return; /* nothing to do */ stkptr = 0; /* initialize stack */ lo = (char *)base; hi = (char *)base + width * (num-1); /* initialize limits */ /* this entry point is for pseudo-recursion calling: setting lo and hi and jumping to here is like recursion, but stkptr is preserved, locals aren't, so we preserve stuff on the stack */ recurse: size = (hi - lo) / width + 1; /* number of el's to sort */ /* below a certain size, it is faster to use a O(n^2) sorting method */ if (size <= CUTOFF) { __SHORTSORT(lo, hi, width, comp, context); } else { /* First we pick a partitioning element. The efficiency of the algorithm demands that we find one that is approximately the median of the values, but also that we select one fast. We choose the median of the first, middle, and last elements, to avoid bad performance in the face of already sorted data, or data that is made up of multiple sorted runs appended together. Testing shows that a median-of-three algorithm provides better performance than simply picking the middle element for the latter case. */ mid = lo + (size / 2) * width; /* find middle element */ /* Sort the first, middle, last elements into order */ if (__COMPARE(context, lo, mid) ) { swap(lo, mid, width); } if (__COMPARE(context, lo, hi) ) { swap(lo, hi, width); } if (__COMPARE(context, mid, hi) ) { swap(mid, hi, width); } /* We now wish to partition the array into three pieces, one consisting of elements <= partition element, one of elements equal to the partition element, and one of elements > than it. This is done below; comments indicate conditions established at every step. */ loguy = lo; higuy = hi; /* Note that higuy decreases and loguy increases on every iteration, so loop must terminate. */ for (;;) { /* lo <= loguy < hi, lo < higuy <= hi, A[i] <= A[mid] for lo <= i <= loguy, A[i] > A[mid] for higuy <= i < hi, A[hi] >= A[mid] */ /* The doubled loop is to avoid calling comp(mid,mid), since some existing comparison funcs don't work when passed the same value for both pointers. */ if (mid > loguy) { do { loguy += width; } while (loguy < mid && !__COMPARE(context, loguy, mid) ); } if (mid <= loguy) { do { loguy += width; } while (loguy <= hi && !__COMPARE(context, loguy, mid) ); } /* lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy, either loguy > hi or A[loguy] > A[mid] */ do { higuy -= width; } while (higuy > mid && __COMPARE(context, higuy, mid) ); /* lo <= higuy < hi, A[i] > A[mid] for higuy < i < hi, either higuy == lo or A[higuy] <= A[mid] */ if (higuy < loguy) break; /* if loguy > hi or higuy == lo, then we would have exited, so A[loguy] > A[mid], A[higuy] <= A[mid], loguy <= hi, higuy > lo */ swap(loguy, higuy, width); /* If the partition element was moved, follow it. Only need to check for mid == higuy, since before the swap, A[loguy] > A[mid] implies loguy != mid. */ if (mid == higuy) mid = loguy; /* A[loguy] <= A[mid], A[higuy] > A[mid]; so condition at top of loop is re-established */ } /* A[i] <= A[mid] for lo <= i < loguy, A[i] > A[mid] for higuy < i < hi, A[hi] >= A[mid] higuy < loguy implying: higuy == loguy-1 or higuy == hi - 1, loguy == hi + 1, A[hi] == A[mid] */ /* Find adjacent elements equal to the partition element. The doubled loop is to avoid calling comp(mid,mid), since some existing comparison funcs don't work when passed the same value for both pointers. */ /* 這裡去掉 higuy += width; if (mid < higuy) { do { higuy -= width; } while (higuy > mid && __COMPARE(context, higuy, mid) == 0); } if (mid >= higuy) { do { higuy -= width; } while (higuy > lo && __COMPARE(context, higuy, mid) == 0); } */ /* OK, now we have the following: higuy < loguy lo <= higuy <= hi A[i] <= A[mid] for lo <= i <= higuy A[i] == A[mid] for higuy < i < loguy A[i] > A[mid] for loguy <= i < hi A[hi] >= A[mid] */ /* We've finished the partition, now we want to sort the subarrays [lo, higuy] and [loguy, hi]. We do the smaller one first to minimize stack usage. We only sort arrays of length 2 or more.*/ if ( higuy - lo >= hi - loguy ) { if (lo < higuy) { lostk[stkptr] = lo; histk[stkptr] = higuy; ++stkptr; } /* save big recursion for later */ if (loguy < hi) { lo = loguy; goto recurse; /* do small recursion */ } } else { if (loguy < hi) { lostk[stkptr] = loguy; histk[stkptr] = hi; ++stkptr; /* save big recursion for later */ } if (lo < higuy) { hi = higuy; goto recurse; /* do small recursion */ } } } /* We have sorted the array, except for any pending sorts on the stack. Check if there are any, and do them. */ --stkptr; if (stkptr >= 0) { lo = lostk[stkptr]; hi = histk[stkptr]; goto recurse; /* pop subarray from stack */ } else return; /* all subarrays done */ } 其一實驗結果 133.189934 1 133.189934 2 133.189934 0 -2.757893 27 -2.757893 29 -2.757893 28 -3.101130 26 -3.101130 25 -3.101130 24 -3.528712 23 -3.528712 22 -3.528712 21 -4.839155 20 -4.839155 19 -4.839155 18 -4.985885 16 -4.985885 17 -4.985885 15 -14.652165 14 -14.652165 13 -14.652165 12 -15.586037 11 -15.586037 10 -15.586037 9 -21.296681 8 -21.296681 7 -21.296681 6 -41.253111 3 -41.253111 5 -41.253111 4 對了我也試過用 (int) (double a - double b) 回傳因為順序不需用到太精確心想差異值小於1 的順序錯還可以忍受可是發現滿多錯的地方差異值都大於1 以致烏龍誤認謝謝指教 ※ 引述《zhim (zhim)》之銘言： : 標題: Re: [閒聊] VC2005 的 qsort 好像有bug... : 時間: Thu Dec 3 04:57:53 2009 : : 謝謝回應 : : 本人回應太慢對不起 : : 我也不是很有把握 : : 我用內建的IDE 測了不同的 data type, int, float, double : : 只有double 20個時發生問題 ( 測試個數 5, 6, 8, 10, 20) : : 我把code貼上來請各位指教一下 : : : : typedef struct _record_ : { : double value; : int position; : } s_reorder; : : int compare_record( const void *arg1, const void *arg2 ) : { : return (int) ( (*(s_reorder *)arg2).value> (*(s_reorder *)arg1).value); : } : : : int main(void) : { : // reorder 是一維陣列 , size= m> 20, 沒有相同的element : : qsort( (void *)( reorder), (size_t) m, sizeof( s_reorder), compare_record ); : : } : : 我用相同的資料結構自己寫一個 _qsort_ 沒再多呼叫compare 是正確的結果 : 我記得當初debug時有把structure 拿掉還是相同的情形 : 一兩個月前了又因為自己寫了_qsort_也還好 : 就沒再多做實驗也有些情況沒記那麼清楚好像 30, 40, 50 個double 都有錯 : 最近程式告一段落才想來問看看... : : 以下是錯的結果 : 0 121.714397 : 1 -0.785398 : 2 -2.520560 : 3 -0.791447 : 4 -0.855704 : 5 -1.695513 : 6 -1.455394 : 7 -1.857532 : 8 -2.066145 : 9 -3.284361 : 10 -2.275599 : 11 -3.423782 : 12 -3.641737 : 13 -5.068104 : 14 -6.149263 : 15 -7.107637 : 16 -10.794325 : 17 -15.191077 : 18 -17.749103 : 19 -35.001716 : : : 謝謝囉 : : : ※ 引述《zhim (zhim)》之銘言： : : 標題: [閒聊] VC2005 的 qsort 好像有bug... : : 時間: Wed Dec 2 06:08:56 2009 : : : : 用VC2005內建的qsort : : : : 幫20個 double排序好像會得出錯的順序 : : : : 不知是否有人有相同的經驗? : : : : 還是MS 已經有patch了... : : : : : : 希望 patch != VC2008 .... : : : : : : -- : : ※ 發信站: 批踢踢實業坊(ptt.cc) : : ◆ From: 140.115.51.64 : : → sunneo:你有在別的IDE測試嗎 12/02 08:38 : : 推 LPH66:你是怎麼寫的...? 12/02 08:39 : : 推 ledia:通常是自己寫錯 12/02 09:18 : : → ledia:(這裡的通常, 大約是 99.99%) 12/02 09:18 : : → VictorTom:寫程式結果有錯都不會先懷疑自己寫錯就覺得是環境給的 12/02 09:30 : : → VictorTom:lib有錯嗎Orz 這麼有自信的話直接貼code來看就知道了XD 12/02 09:30 : : → tomnelson:(99.9% + 0.1%)寫錯... 12/02 10:51 : : → tomnelson:我敢猜問題出在那個傳入qsort的cmpfunc(比較函式)... 12/02 10:55 : : → tomnelson:題外話,寫程式出問題就怪罪到IDE或compiler,不是好事,雖 12/02 10:57 : : → tomnelson:然這種事也真的有,但是在已經成熟而且在市面上的產品上 12/02 10:58 : : → tomnelson:來說,真的少見,頂多是在compiler最佳化那邊出問題,這種 12/02 11:00 : : → tomnelson:內建functions出問題的,還沒遇過. 12/02 11:00 : : → tomnelson:請參考別人"犯錯心得"如下兩網址: 12/02 11:12 : : → tomnelson:http://ppt.cc/kPN0 12/02 11:13 : : → tomnelson:http://ppt.cc/Ctst 12/02 11:13 : : 推 ledia:我隔空抓藥一下, 他大概回傳 *(double*)x-*(double*)y; 12/02 13:22 : : → ledia:當 x, y 差距太小, 回傳又 cast 成 int 就會變為 0 ... 12/02 13:22 : : → bugmens:原po都不吭聲,大家debug倒是解的很高興 12/02 18:07 : : 推 walker2009:樓上是bug, 抓到了 XD 12/02 18:44 : : → sunneo:大家都講得太明了 -.- 我反倒想看看他測了幾個IDE來下結論 12/02 22:27 : : -- : ※ 發信站: 批踢踢實業坊(ptt.cc) : ◆ From: 140.115.51.64 : 推 ducksteven:http://codepad.org/uYuEtII3 12/03 05:05 : 推 ducksteven:我在自己的電腦編譯也會跑錯，改成這樣就不會錯了 12/03 05:09 : → ducksteven:http://codepad.org/TLz5KfGt 12/03 05:09 : → ducksteven:上面有人提示了，因為它有 3 種 return value 12/03 05:10 : → zhim:謝謝您 VC要3種value不是變慢了, 我以前用BC3都沒注意到這個 12/03 05:33 : 推 VictorTom:果然被人抓藥抓對了, 應該回傳三態你只回傳兩態.... 12/03 09:13 : → VictorTom:http://0rz.tw/tR11X 12/03 09:14 : → VictorTom:只能說你以前沒遇到錯誤大概只是運氣好.... 12/03 09:15 : → VictorTom:效率會不會變差要看lib內部怎麼實作, 如果它本來就需要 12/03 09:18 : → VictorTom:三態你只給兩態, 結果錯了就更不用討論效率了XD 12/03 09:19 : → tomnelson:哈哈哈~~~ 12/03 11:38 : 推 ducksteven:它的定義本來就有三種回傳啊順便告訴你我編譯器是gcc 12/03 13:36 : 推 cplusplus:下次先看document會比較好... C的標準qsort本來就要三態 12/03 15:33 : → tomnelson:"man 3 qsort" for Linux/Unix/FreeBSD and etc. ! 12/03 17:48 : → sunneo:數字三態最簡單就是直接a-b了 12/03 21:52 : → zhim:這樣就會發生 a-b -> 0 的 round off error 12/04 14:11 : → zhim:雙態就夠了把qsort.c 檢查 ==0 的去掉 12/04 14:14 : → zhim:其他改成 bool 邏輯 12/04 14:18 : 推 ledia:bool ? 回傳 0, 1 就是會錯呀... 12/04 14:59 : → ledia:你可以只傳 -1, 1 啦, 我想沒有 0 大概不會有太大問題 12/04 14:59 : → ledia:只回傳 0, 1 就註定會錯了 12/04 14:59 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.115.51.64

推

ledia

12/05 01:03, , 1^F

12/05 01:03, 1^F

→

ledia

12/05 01:04, , 2^F

12/05 01:04, 2^F

→

tomnelson

12/05 01:11, , 3^F

12/05 01:11, 3^F