問題タブ [median-of-medians]

まず第一に、これは宿題の質問であり、私はかなりの量の試みを行った.

Java でクイックソートを変更して、式を使用して配列内の 9 つの値の疑似中央値としてピボットを設定するように依頼されました。i * (n-1) /8

computeMedian3 つの整数を受け取り、最高値を決定してからその値を返すメソッドを作成しました。

コード：

次に、現在の値を取得し、それらを使用してピボットを構築するfindPivotメソッドでそれを使用しましたarray, from, to

そのコードは次のとおりです。

このメソッドは、サイズが 40 以下の配列の並べ替えには問題なく機能しますが、サイズが 40 を超えるとすぐにスタック オーバーフロー エラーが発生し、その部分のcomputeMedianメソッドに戻ります。else {}そこに置くと> 40の部分で機能することに注意してください。ただしreturn computeMedian(a[from], a[(to)/2] , a[to]);、3セットの中央値の中央値ではなく、3つの値の中央値にすぎません。

現在、これは私がfindPivotクイックソートパーティショニングメソッドにプラグインした方法です:

computeMedian私の方法がより大きなデータセットで機能しない理由について、私はかなり困惑しています。i * (n-1) / 8forループを介して値を配列に配置し、それらをソートして途中で値を返すこと、および値を配列に配置pして呼び出すことを試みましたcomputeMedian(computeMedian(p[0], p[1], p[2]), computeMedian(p[3],p[4],p[5]),...etcが、同じスタックオーバーフローの問題が発生しますが、移動する傾向があります私のコードのさまざまな部分と私を輪に導きます。

必要に応じてスニペットを投稿できますが、私の問題はおそらくここにあると思います。

助けてくれてありがとう。私はまだ学んでいますが、これを理解することは、将来的に自分で問題を解決するのに完全に役立つと思います.

スタック トレースの問題行は次のとおりです。 行 16:int p = modPartition(a, from, to); 行 18modSort(a, p+1, to); 行 23int pivot = findPivot(a, from, to);

私のmodSortメソッド全体もここにあります：

最悪の場合の線形時間で k 番目に小さい要素を見つけるために、Median of Medians アルゴリズムの C コードを書いています。コードのクイック ソート、スワッピングなどをチェックしました。

与えられた入力 -

出力 -

しかし、出力は

関数呼び出し -

コード -

ウィキペディアの記事を使用して、algs4 quickselectに基づいて中央値選択アルゴリズムの中央値を実装しましたが、私のコードはうまく機能しません。

1) 中央値の中央値は、k 番目に大きい要素を見つけると言われています。ただし、私のコードは k 番目に小さい要素を見つけます。

2) 私の実装は、quickselect よりも 1 倍から 20 倍遅く実行されますが、中央値アルゴリズムの中央値は漸近的に高速になるはずです。

何度も確認しましたが、問題が見つかりません。

JUnit テスト:

最悪の場合、T がアルゴリズムの実行時間である場合、サイズ 3 のブロックで中央値アルゴリズムの中央値を使用すると、次の再帰関係が得られる理由がわかりました。

T(n) = T(2n / 3) + T(n / 3) + O(n)

median-of-medians アルゴリズムに関するウィキペディアの記事では、サイズ 3 のブロックでは、n 個の要素すべてをチェックする必要があるため、実行時間は O(n) ではないと述べています。私はこの説明をよく理解していません.私の宿題では、帰納法でそれを示す必要があると書かれています.

この場合、中央値の中央値に時間 Ω(n log n) がかかることをどのように示しますか?

私がすでに理解していること

Median of medians アルゴリズム (MoM と表記します) は、高定数係数 O(N) アルゴリズムであることを理解しています。k グループ (通常は 5) の中央値を見つけ、それらを次の反復のセットとして使用して中央値を見つけます。これを見つけた後のピボットは、元のセットの 3/10n から 7/10n の間になります。ここで、n は、1 つの中央値ベース ケースを見つけるのにかかった反復回数です。

MoM でこのコードを実行すると、セグメンテーション エラーが発生し続けますが、その理由はわかりません。私はそれをデバッグしましたが、問題は私が呼び出しているという事実にあると信じていますmedianOfMedian(medians, 0, medians.size()-1, medians.size()/2);。しかし、それ自体を呼び出して再帰的に中央値を見つけることになっていたので、これは論理的に正しいと思いました。おそらく私の基本的なケースは正しくありませんか？YouTube の YogiBearian によるチュートリアル (スタンフォード大学の教授、リンク: https://www.youtube.com/watch?v=YU1HfMiJzwg ) で、彼は O(N/5) を処理するための追加の基本ケースについて述べていません。 MoM での再帰の操作。

完全なコード

注: 提案に従って、基本ケースを追加し、ベクターで .at() 関数を使用しました。

単体テストを支援するためのいくつかの追加機能

これらの 2 つの関数に対して作成した単体テストを次に示します。うまくいけば、彼らは助けてくれます。

取得している出力に関する追加セクション

セグメンテーション違反までは、大丈夫でダンディに見えます。私のパーティション関数も同様に機能すると確信しています（リートコードの質問の実装の1つでした）。

免責事項: これは宿題の問題ではなく、leetcode 問題セットで quickSelect を使用した後のアルゴリズムに関する私自身の好奇心です。

提案された質問で MVCE についてさらに詳しく説明する必要がある場合はお知らせください。ありがとうございます。

編集:コードで再帰パーティションスキームが間違っていることがわかりました。プラダンが指摘したように、私はどういうわけか、開始と終了がそれぞれ0と-1になる空のベクトルを持っているため、それを呼び出す無限ループからセグメンテーション違反が発生します。まだこの部分を理解しようとしています。

1 つのプログラムで同時に複数の操作を実行しようとしています。開始と終了の手がかりがないデータフレームがありDates、見つけたい：

1. データセットの合計日数
2. 総時間数
3. 伯爵の中央値
4. 日/日付ごとの中央値の個別の出力を書き込みます。
5. 可能であれば、最も単純な方法で中央値の中央値。

入力: GB サイズの大きなファイルから数行

開始日と終了日は不明です。

編集： 期待される出力：1には結果が1行しかありません

medianMedian-of-Median は、出力 2 の列の中央値です。

期待される出力:2、中央値の中央値を見つけるために使用されるすべての日付の中央値が含まれます

コード：

明らかに、コードは想定どおりの結果を提供しません。

エラーを以下に示します。

エラー：