問題タブ [localityofreference]

私が理解していることから、空間的局所性は、近い将来に使用される近くのメモリと関係があります。しかし、ループが何度も実行されるかどうか疑問に思っていましたが、これは良い空間的局所性につながりますか? 事前に感謝します。わかりにくい場合は申し訳ありません。

概念的にではなく、地域性に基づいてクラスを編成する必要がありますか?

仮説として、車、道路、木という 3 つのオブジェクトを持つ現実世界の環境をシミュレートするプログラムを作成するとします。従来の OOP 設計では、これら 3 つの別個のクラスを概念的に分離することが提案されています。

しかし、車と道路のオブジェクトが、クラス メンバーのデータとメソッドの間で何百万もの計算を行うとします。参照の局所性のために、Car と Road を CarRoad クラスに混ぜてパフォーマンスを向上させることはできますか? または、その例がばかげている場合、Car に密接に関連する別の別の Wheel クラスがある場合、クラス メンバーが非常に頻繁に対話する場合、Car クラスと Wheel クラスをごちゃまぜにする必要がありますか?

パーティション関数は、その参照の局所性をすばやくソートしますか? もしそうなら、どのように？

マージソートやヒープソートなどの他のアルゴリズムと比較して、参照の局所性を与えるクイックソートには何がありますか?

私もそれを読みました

「クイックソートのパーティショニングステップは、前後にある連続した配列要素にアクセスするため、通常、優れた局所性を持っています」.

よくわからなかった ？

この質問とこの回答を読むと、フィールドにアクセスするとAOTコンパイラでパフォーマンスが低下することがわかります（JVMのおかげで忘れることができます）

このシナリオについて教えてください：

と の両方barMethod1()でbarMethod2()同じことを行います。問題は、次の場合にどちらが (パフォーマンスの点で) 優れているかです。

1. fooObjectプリミティブ型です
2. fooObjectオブジェクトインスタンスです

PS アクセスコストとキャッシュミスの両方を考慮してください。

局所性の原理を議論する際に、私の教科書は次のように述べています。

すべてのプログラム命令のほんの一部を構成する分岐命令と呼び出し命令を除いて、プログラムの実行は順次実行されます。したがって、ほとんどの場合、フェッチされる命令は、最後にフェッチされた命令の直後に続きます。

初心者として、私はこれを信じるのが難しいと思います。私が遭遇したすべてのコードには、呼び出し命令が大量に含まれています。実際、呼び出し命令は実際にはプログラム内で最も重要なアクションを実行するように思えます。

プログラム内での呼び出し命令の実質的な役割にもかかわらず、この概念が正しい理由を誰かが詳しく説明していただければ幸いです。

この問題では、局所性の期待値を求めるよう求められます。問題の答えがどのようになっているかを理解しています

(n - 1) * (expected value of |π(i) − π(i − 1)|).

問題の解は、

|π(i) − π(i − 1)| is (n + 1) / 3.

ソリューションのこの部分がわかりません。誰かがこの理由を説明してもらえますか? ありがとうございました。

2 つの合計の問題を解決するには、O(n) の複雑さのアルゴリズムを使用して実装できますが、私は O(n^2) の複雑さを試しました。これは、i 番目の整数の合計をそれぞれのターゲット値に対する残りの整数。以下は O(n^2) の実装です。2 つの実装では、numsは整数の配列、nは nums のサイズ、indexs はインデックスを保持するサイズ 2 の配列です。 2 つの整数の

この実装は、140ms で問題を解決します。別の O(n^2) アプローチを試しました。これは、1 から n-1 までの各 k 値について、i 番目の整数と (i + k) 番目の整数の合計をターゲット値に対してチェックするというものです。実装は次のとおりです。

ご覧のとおり、同じループ本体ですが、これははるかに高速に実行され、実行時間は 8 ミリ秒です。何故ですか？それは空間的局所性に関連していますか？