PHP ソートの安定性の問題
私は最近、仕事中に非常に興味深い問題に遭遇しました。オンライン入力は、ソートされた連想配列のシーケンスです。一連の後の配列出力です。処理の順序が乱れているため、ローカルで実行すると再現できません。関連するコードを確認した後、最も懸念されるのはこの段落です:
$categories = Arr::sort($categories, function ($node) { return $node['default']; }, true);
は、default
の優先順位に従って要素を最前面に移動するために使用されます。 /supportバージョンはローカルのものと一致しています。
Arr::sort()ソースコード:
... $descending ? arsort($results, $options) : asort($results, $options);を確認してください。最終的には、php の
asort が呼び出され、オンラインが php5 です。最近のアップグレードの考慮により、ローカルとテストの両方が php7 に置き換えられました。最終的には、php5 環境で正常に再現され、
sort の問題であることが判明しました。
ソートの前後で等しい要素の相対位置は変化しません。これは、このアルゴリズムが安定していることを意味します。クイック ソートについてある程度の理解がある場合は、クイック ソートが不安定であることがわかるため、要素
default が同じである場合には、このコードの出力は行われません。前の順序ですが、php7 環境ではテスト結果が元の順序を保持しているのはなぜですか。
世界中のデフォルトの並べ替えはすべてクイック ソートであると理解していたのは間違っていますか?
asort を直接検索し、c ファイルを見つけて、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(); // 设置比较函数 cmp = php_get_data_compare_func(sort_type, 0); zend_hash_sort(Z_ARRVAL_P(array), cmp, 0); RETURN_TRUE; }で定義されているこの関数を見つけます。最後の呼び出しは
zend_hash_sort() です。引き続き検索を続けます:
zend_hash_sort_ex() の入れ子人形であることがわかります。 、そして最後に 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; } // 这里的hole指数组元素被unset掉产生的洞 if (HT_IS_WITHOUT_HOLES(ht)) { /* Store original order of elements in extra space to allow stable sorting. */ for (i = 0; i < ht->nNumUsed; i++) { Z_EXTRA(ht->arData[i].val) = i; } } else { /* Remove holes and store original order. */ for (j = 0, i = 0; j < ht->nNumUsed; j++) { 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; i++; } 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))); ...わかりました!公式コメントでは、ソートの安定性を実現する方法について説明しています。ソートの前に、この
Z_EXTRA を使用して、元の配列要素の添字へのマッピングを保持します。
$count = 10; $cc = []; for ($i=0; $i<$count; $i++) { $cc[] = [ 'id' => $i, 'default' => rand(0, 10), ]; } $cc = Arr::sort($cc, function ($i) { return $i['default']; }); dd($cc);php7 で多くのテストを行った結果、
$count が比較的小さい場合、ソートは安定していますが、
$count大規模な場合、並べ替えは再び不安定になります。つまり、ユースケースの配列長が短すぎるため、オンラインソートは不安定であり、ローカルで再現することはできません。
sort は、
LLVM の
libc の
std::sort 実装に基づいています。要素の数が 16 以下の場合、特別な最適化が行われます。要素の数が 16 を超える場合、クイック ソートが実行されますが、php5 は直接クイック ソートを使用します。
<?php $count = 100; $cc = []; for ($i=0; $i<$count; $i++) { $cc[] = [ 'id' => $i, 'default' => rand(0, 10), ]; } usort($cc, function($a, $b){ if ($a['default'] == $b['default']) return 0; return ($a['default'] < $b['default']) ? 1 : -1; }); print_r($cc);
最終的にphp8環境で試してみましたが、ソートは非常に安定しています
以上がPHPソートの安定性についての考察!の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

php把负数转为正整数的方法:1、使用abs()函数将负数转为正数,使用intval()函数对正数取整,转为正整数,语法“intval(abs($number))”;2、利用“~”位运算符将负数取反加一,语法“~$number + 1”。

实现方法:1、使用“sleep(延迟秒数)”语句,可延迟执行函数若干秒;2、使用“time_nanosleep(延迟秒数,延迟纳秒数)”语句,可延迟执行函数若干秒和纳秒;3、使用“time_sleep_until(time()+7)”语句。

php除以100保留两位小数的方法:1、利用“/”运算符进行除法运算,语法“数值 / 100”;2、使用“number_format(除法结果, 2)”或“sprintf("%.2f",除法结果)”语句进行四舍五入的处理值,并保留两位小数。

判断方法:1、使用“strtotime("年-月-日")”语句将给定的年月日转换为时间戳格式;2、用“date("z",时间戳)+1”语句计算指定时间戳是一年的第几天。date()返回的天数是从0开始计算的,因此真实天数需要在此基础上加1。

php判断有没有小数点的方法:1、使用“strpos(数字字符串,'.')”语法,如果返回小数点在字符串中第一次出现的位置,则有小数点;2、使用“strrpos(数字字符串,'.')”语句,如果返回小数点在字符串中最后一次出现的位置,则有。

方法:1、用“str_replace(" ","其他字符",$str)”语句,可将nbsp符替换为其他字符;2、用“preg_replace("/(\s|\ \;||\xc2\xa0)/","其他字符",$str)”语句。

php字符串有下标。在PHP中,下标不仅可以应用于数组和对象,还可应用于字符串,利用字符串的下标和中括号“[]”可以访问指定索引位置的字符,并对该字符进行读写,语法“字符串名[下标值]”;字符串的下标值(索引值)只能是整数类型,起始值为0。

在PHP中,可以利用implode()函数的第一个参数来设置没有分隔符,该函数的第一个参数用于规定数组元素之间放置的内容,默认是空字符串,也可将第一个参数设置为空,语法为“implode(数组)”或者“implode("",数组)”。


ホットAIツール

Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

AI Hentai Generator
AIヘンタイを無料で生成します。

人気の記事

ホットツール

ドリームウィーバー CS6
ビジュアル Web 開発ツール

SecLists
SecLists は、セキュリティ テスターの究極の相棒です。これは、セキュリティ評価中に頻繁に使用されるさまざまな種類のリストを 1 か所にまとめたものです。 SecLists は、セキュリティ テスターが必要とする可能性のあるすべてのリストを便利に提供することで、セキュリティ テストをより効率的かつ生産的にするのに役立ちます。リストの種類には、ユーザー名、パスワード、URL、ファジング ペイロード、機密データ パターン、Web シェルなどが含まれます。テスターはこのリポジトリを新しいテスト マシンにプルするだけで、必要なあらゆる種類のリストにアクセスできるようになります。

Safe Exam Browser
Safe Exam Browser は、オンライン試験を安全に受験するための安全なブラウザ環境です。このソフトウェアは、あらゆるコンピュータを安全なワークステーションに変えます。あらゆるユーティリティへのアクセスを制御し、学生が無許可のリソースを使用するのを防ぎます。

EditPlus 中国語クラック版
サイズが小さく、構文の強調表示、コード プロンプト機能はサポートされていません

mPDF
mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。
