検索
ホームページバックエンド開発PHPチュートリアルPHPソートの安定性についての考察!

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 環境ではテスト結果が元の順序を保持しているのはなぜですか。 世界中のデフォルトの並べ替えはすべてクイック ソートであると理解していたのは間違っていますか?

さて、PHP ソース コードがこの問題をどのように解決するかを簡単に見てみましょう。 github の公式 php-src にアクセスし、このリポジトリで

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() です。引き続き検索を続けます:

PHPソートの安定性についての考察!

そして、この関数が

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 を使用して、元の配列要素の添字へのマッピングを保持します。

しかし、このコードの提出情報を検索したところ、問題が見つかりました: 安定したソートに関連する rfc は https://wiki.php.net/rfc/stable_sorting にあります。今年の 5 月に起こりました。そして php8.0 についてです。

?? 以前の php7 のソートの安定性はどうなりましたか?

すぐに例を構築します:

$count = 10;
$cc = [];
for ($i=0; $i<$count; $i++) {
    $cc[] = [
        &#39;id&#39; => $i,
        &#39;default&#39; => rand(0, 10),
    ];
}
$cc = Arr::sort($cc, function ($i) {
   return $i[&#39;default&#39;];
});
dd($cc);

php7 で多くのテストを行った結果、

$count が比較的小さい場合、ソートは安定していますが、 $count大規模な場合、並べ替えは再び不安定になります。つまり、ユースケースの配列長が短すぎるため、オンラインソートは不安定であり、ローカルで再現することはできません。

これを見て、クイックソート長閾値最適化の問題であると判断し、最終的に関連情報を確認しました。 php7 の

sort は、LLVMlibc std::sort 実装に基づいています。要素の数が 16 以下の場合、特別な最適化が行われます。要素の数が 16 を超える場合、クイック ソートが実行されますが、php5 は直接クイック ソートを使用します。

<?php

$count = 100;
$cc = [];
for ($i=0; $i<$count; $i++) {
    $cc[] = [
        &#39;id&#39; => $i,
        &#39;default&#39; => rand(0, 10),
    ];
}
usort($cc, function($a, $b){
    if ($a[&#39;default&#39;] == $b[&#39;default&#39;]) return 0;
    return ($a[&#39;default&#39;] < $b[&#39;default&#39;]) ? 1 : -1;
});
print_r($cc);

最終的にphp8環境で試してみましたが、ソートは非常に安定しています

以上がPHPソートの安定性についての考察!の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明
この記事はjuejinで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。
PHPセッションの概念を簡単に説明してください。PHPセッションの概念を簡単に説明してください。Apr 26, 2025 am 12:09 AM

phpssionsStrackuserdataacrossmultiplepagerequestsusingauniqueidstoredinacookie.here'showtomanageetheemefectively:1)Startassession withsession_start()andstoredatain $ _ session.2)RegeneratesseSsessidafterloginwithsession_id(the topreventes_id)

PHPセッションに保存されているすべての値をどのようにループしますか?PHPセッションに保存されているすべての値をどのようにループしますか?Apr 26, 2025 am 12:06 AM

PHPでは、次の手順を通じてセッションデータを繰り返すことができます。1。session_start()を使用してセッションを開始します。 2。$ _Sessionアレイのすべてのキー価値ペアを介してforeachループを反復します。 3.複雑なデータ構造を処理する場合、is_array()またはis_object()関数を使用し、print_r()を使用して詳細情報を出力します。 4.トラバーサルを最適化する場合、ページングを使用して、一度に大量のデータの処理を避けることができます。これにより、実際のプロジェクトでPHPセッションデータをより効率的に管理および使用するのに役立ちます。

ユーザー認証にセッションを使用する方法を説明します。ユーザー認証にセッションを使用する方法を説明します。Apr 26, 2025 am 12:04 AM

このセッションは、サーバー側の状態管理メカニズムを介してユーザー認証を実現します。 1)セッションの作成と一意のIDの生成、2)IDはCookieを介して渡されます。3)サーバーストアとIDを介してセッションデータにアクセスします。

PHPセッションにユーザーの名前を保存する方法の例を挙げてください。PHPセッションにユーザーの名前を保存する方法の例を挙げてください。Apr 26, 2025 am 12:03 AM

tostoreauser'snameInappession、starthessession withsession_start()、thensignthenameto $ _session ['username']。1)ousession_start()toinitializethessession.2)assighttheuser'snameto $ _ session ['username']

PHPセッションを失敗させる可能性のあるいくつかの一般的な問題は何ですか?PHPセッションを失敗させる可能性のあるいくつかの一般的な問題は何ですか?Apr 25, 2025 am 12:16 AM

PHPSESSIONの障害の理由には、構成エラー、Cookieの問題、セッションの有効期限が含まれます。 1。構成エラー:正しいセッションをチェックして設定します。save_path。 2.Cookieの問題:Cookieが正しく設定されていることを確認してください。 3.セッションの有効期限:セッションを調整してください。GC_MAXLIFETIME値はセッション時間を延長します。

PHPでセッション関連の問題をどのようにデバッグしますか?PHPでセッション関連の問題をどのようにデバッグしますか?Apr 25, 2025 am 12:12 AM

PHPでセッションの問題をデバッグする方法は次のとおりです。1。セッションが正しく開始されるかどうかを確認します。 2.セッションIDの配信を確認します。 3.セッションデータのストレージと読み取りを確認します。 4.サーバーの構成を確認します。セッションIDとデータを出力し、セッションファイルのコンテンツを表示するなど、セッション関連の問題を効果的に診断して解決できます。

session_start()が複数回呼び出されるとどうなりますか?session_start()が複数回呼び出されるとどうなりますか?Apr 25, 2025 am 12:06 AM

session_start()への複数の呼び出しにより、警告メッセージと可能なデータ上書きが行われます。 1)PHPは警告を発し、セッションが開始されたことを促します。 2)セッションデータの予期しない上書きを引き起こす可能性があります。 3)session_status()を使用してセッションステータスを確認して、繰り返しの呼び出しを避けます。

PHPでセッションのライフタイムをどのように構成しますか?PHPでセッションのライフタイムをどのように構成しますか?Apr 25, 2025 am 12:05 AM

PHPでのセッションライフサイクルの構成は、session.gc_maxlifetimeとsession.cookie_lifetimeを設定することで達成できます。 1)session.gc_maxlifetimeサーバー側のセッションデータのサバイバル時間を制御します。 0に設定すると、ブラウザが閉じているとCookieが期限切れになります。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

mPDF

mPDF

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

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

VSCode Windows 64 ビットのダウンロード

VSCode Windows 64 ビットのダウンロード

Microsoft によって発売された無料で強力な IDE エディター

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Eclipse を SAP NetWeaver アプリケーション サーバーと統合します。