谢谢回应 这次乌龙了 以下为 藉由这讨论的机缘 衍生的双态议题 将原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