Shulou(Shulou.com)06/01 Report--

Today, I would like to share with you the relevant knowledge points of PHP ranking stability case analysis, the content is detailed, the logic is clear, I believe most people still know too much about this knowledge, so share this article for your reference, I hope you can get something after reading this article, let's take a look at it.

PHP sorting stability problem. Markdown-body {word-break:break-word;line-height:1.75;font-weight:400;font-size:16px;overflow-x:hidden;color:#333}. Markdown-body h _ 2jue. Markdown _ house _ body h _ 3 _ Margin-bottom:5px}. Markdown-body h3. Markdown ececec body h4. Markdown house body h5. Markdown house body h6.. Markdown house body h7 {font-size:20px}. Markdown-body h3 {padding-bottom:12px;border-bottom:1px solid # ececec}. Markdown-body h4 {font-size:18px;padding-bottom:0}. Markdown-body H7 {margin-top:5px}. Markdownhouse p {line-height:inherit;margin-top:22px Margin-bottom:22px}. Markdown-body img {max-width:100%}. Markdown-body hr {border:none;border-top:1px solid # ddd;margin-top:32px;margin-bottom:32px}. Markdown-body code {word-break:break-word;border-radius:2px;overflow-x:auto;background-color:#fff5f5;color:#ff502c;font-size:.87em Padding:.065em .4em}. Markdown-body code,.markdown-body pre {font-family:Menlo,Monaco,Consolas,Courier New,monospace}. Markdown-body pre {overflow:auto;position:relative;line-height:1.75}. Markdown-body pre > code {font-size:12px;padding:15px 12pxport Edge Variety 0There are words on the words, colors, etc. Markdown-body a {text-decoration:none;color:#0269c8 Border-bottom:1px solid # d1e9ff}. Markdown-body aavoractive.markdownbody a:hover {color:#275b8c}. Markdown-body table {displaylement markdown-body tr:nth-child blockplay importantFontMaxWidthRod 100% markdown-body thead overflowautoborderRod 1px background-color:#fcfcfc # f6f6f6}. Markdown-body thead {background:#f6f6f6;color:#000;text-align:left}. Markdown-body tr:nth-child (2n) {background-color:#fcfcfc}. Line-height:24px}. Markdown-body td {min-width:120px}. Markdown-body blockquote {color:#666;padding:1px 23px Portal Vane 22px 0borderlyleftPart 4px solid # cbcbcb;background-color:#f8f8f8}. Markdown-body blockquote:after {display:block;content: ""}. Markdown-body blockquote > p {margin:10px 0}. Markdown-body ol,.markdown-body ul {padding-left:28px}. Markdown-body ol li,.markdown-body ul li {margin-bottom:0 List-style:inherit} .markdown-body ol li .task-list-item,.markdown-body ul li .task-list-item {list-style:none}. Markdown-body ol li .task-list-item ol,.markdown-body ol li .task-list-item ul,.markdown-body ul li .task-list-item ol,.markdown-body ul li .task-list-item ul {margin-top:0} .markdown-body ol ol,.markdown-body ol ul,.markdown-body ul ol .markdown-body ul ul {margin-top:3px} .markdown-body ol li {padding-left:6px} .markdown-body .task-task-list {padding-left:0} .markdown-body .task-list-item {list-style:none} @ media (max-width:720px) {.markdown-body H2 {font-size:24px} .markdown-body h3 {font-size:20px} .markdown-body h4 {font-size:18px}}

Recently, I have encountered an interesting problem in my work. The online input is a series of ordered associative arrays, but the output array after a series of processing is out of order, and the local operation cannot be reproduced. After looking at the relevant code, what people care about most is this paragraph:

$categories = Arr::sort ($categories, function ($node) {return $node ['default'];}, true)

The function is to raise the element to the front according to default priority. First, make sure that the illuminate/support version on the offline is consistent with the local version, and check the Arr::sort () source code:

... $descending? Arsort ($results, $options): asort ($results, $options)

In the end, the asort of php is called, online is php5, and the local and test are replaced by php7 because of the recent upgrade. Finally, it is successfully reproduced in the php5 environment, and it is determined that it is a sort problem.

The relative position of equal elements before and after sorting remains unchanged, that is to say, the algorithm is stable.

If you have some knowledge of quick sorting, you can know that quick sorting is unstable, so if the element default priority is the same, the output of this code will not be in the previous order, but why will the test results retain the original order in the php7 environment. Is it wrong for me to understand that all default sorting in the world is quick sort?

Well, let's take a quick look at how the php source code solves this problem. Go to github's official php-src to search asort in this repository directly, find the c file, and find the function defined in arr.c:814.

PHP_FUNCTION (asort) {zval * array; zend_long sort_type = PHP_SORT_REGULAR; bucket_compare_func_t cmp; ZEND_PARSE_PARAMETERS_START (1,2) Z_PARAM_ARRAY_EX (array, 0,1) Z_PARAM_OPTIONAL Z_PARAM_LONG (sort_type) ZEND_PARSE_PARAMETERS_END () / / set the comparison function cmp = php_get_data_compare_func (sort_type, 0); zend_hash_sort (Z_ARRVAL_P (array), cmp, 0); RETURN_TRUE;}

You can see that the final call is zend_hash_sort (), and we continue to search:

It is found that this function is the nesting doll of zend_hash_sort_ex (), and finally find zend_hash.c:2497

ZEND_API void ZEND_FASTCALL zend_hash_sort_ex (HashTable * ht, sort_func_t sort, bucket_compare_func_t compar, zend_bool renumber) {Bucket * p; uint32_t I, j; IS_CONSISTENT (ht); HT_ASSERT_RC1 (ht) If (! (ht- > nNumOfElements > 1) & &! (renumber & & ht- > nNumOfElements > 0)) {/ * Doesn't require sorting * / return;} / / the hole if (HT_IS_WITHOUT_HOLES (ht)) {/ * Store original order of elements in extra space to allow stable sorting produced by the unset of the hole index group elements here. * / for (I = 0; I

NNumUsed; iTunes +) {Z_EXTRA (ht- > ardata [I] .val) = I;}} else {/ * Remove holes and store original order. * / for (j = 0, I = 0; j

NNumUsed; jacks +) {p = ht- > arData + j; if (UNEXPECTED (Z_TYPE (p-> val) = = IS_UNDEF)) continue; if (I! = j) {ht- > arData [I] = * p } Z_EXTRA (ht- > ardata [I] .val) = I; iTunes;} ht- > nNumUsed = I } sort ((void *) ht- > arData, ht- > nNumUsed, sizeof (Bucket), (compare_func_t) compar, (swap_func_t) (renumber? Zend_hash_bucket_renum_swap: (HT_FLAGS (ht) & HASH_FLAG_PACKED)? Zend_hash_bucket_packed_swap: zend_hash_bucket_swap));...

Yes! The official comments explain how to achieve the stability of sorting, using this Z_EXTRA to retain the mapping of the original array elements to subscripts before sorting.

But when I searched for the submission information of this code, I found a problem: the stable sorting related rfc in https://wiki.php.net/rfc/stable_sorting, you can see that it happened in May this year and aimed at php8.0.

?? How was the php7 ranking stable before that?

Construct an example right away:

$count = 10 default' cc = []; for ($iS0; $I $I, 'default' = > rand (0,10),];} $cc = Arr::sort ($cc, function ($I) {return $I [' default'];}); dd ($cc)

After many tests under php7, it is found that the sorting is stable when the $count is small, but the sorting becomes unstable when the $count is larger. That is, the online ordering is unstable and the local non-reproduction is actually due to the fact that the array length of the use case is too short.

See here can be determined to be the problem of quick sort length threshold optimization, and finally check the relevant information. Sort in php7 is based on the std::sort implementation of libc++ in LLVM. When the number of elements is less than or equal to 16, there is a special optimization. When the number of elements is greater than 16, the quick sort is taken, while the php5 is directly in the quick sort.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.