問題タブ [programming-pearls]

今日から「ProgrammingPearls」を読み始めましたが、その演習をしているときに、「独自のビットベクトルをどのように実装しますか？」という質問に出くわしました。私が解決策を見たとき、それは次のようでした：

私が混乱しているのはこの声明です

誰かがここで何が起こっているのか説明してもらえますか？

「Programming Pearls」を読んでいましたが、解決策の説明の 1 つで本当に混乱しています。

質問は次のとおりです。「最大 n 個の正の整数を含むファイルで、それぞれが n 未満で、n = 10^7 です。各正の整数は最大 10 回出現する可能性があります。ファイルをどのように並べ替えますか?」

本で与えられた解決策: "各整数が最大 10 回出現する場合、4 ビットのハーフバイトでその出現を数えることができます。問題 5 (下記) の解決策を使用して、完全なファイルを 1 回のパスで並べ替えることができます。 10,000,000/2 バイト、または 10,000,000/2k バイトの k パス」

問題 5の解決策: 2 パス アルゴリズムは、最初に 5,000,000/8 = 625,000 ワードのストレージを使用して整数 0 ～ 4,999,999 を並べ替え、次に 2 番目のパスで 5,000,000 ～ 9,999,999 を並べ替えます。k-pass アルゴリズムは、時間 kn および空間 n/k で n 未満の最大 n 個の繰り返されない正の整数をソートします。)

著者がどのようにして 10,000,000/2k のスペースをソートするのかわかりません。つまり、問題 5 の解決策に基づいて、最初のパスでソートするために 625K バイトのスペースと、カウントを格納するために整数ごとに追加の 1/2 バイトが必要ですよね?

誰かがこれを理解するのを手伝ってくれませんか?

どうもありがとう。

Programming Pearls には、さまざまな長さの配列をソートするアルゴリズムがありますが、それらの長さの合計に比例して時間でソートします。たとえば、レコード arrayx[0...n-1]があり、各レコードに整数の長さと array へのポインタがあるとしますbit[0...length-1]。

コードは次のように実装されています。

私の質問は、記録を考えると、次のとおりです。

文字列の長さを取得する方法はわかっていますが、ビット配列の場合はどうでしょうか。この文字列配列に適したビット配列を作成するにはどうすればよいですか? そして、x[i].bit[depth]どうすればこれを実装できますか?

真珠のプログラミング 問題 7 は、磁気テープ4000 x 4000に保存された行列の転置に関するものです。私の解決策は、単純に一時変数を使用して、との内容を交換することでした。 著者によって与えられた解決策は、私を少し混乱させました。彼は私たちがすべきだと言います：
a[i][j]a[j][i]

1. 行と列のインデックスをそれぞれに追加します
2. マトリックス内のレコードを行ごとに並べ替える
3. 追加されたインデックスを削除します。

なぜこれを成し遂げるのにそんなに苦労しなければならないのですか？磁気テープと関係ありますか？

最適化アプローチに関するいくつかの問題を読んでいます。
特定の範囲で数値をソートする方法の問題では、解決策はビットマップを使用することです。また、数値が最大 10 回表示される場合は、半バイトを使用して数値をマップし、発生回数を表すカウンターとして使用します。
コンセプトよくわかります。私の問題は、これをJavaで簡単に実装する方法です。

私はビット操作で立ち往生しています。
たとえば、カウンターを 1 ずつインクリメントする最初の部分については、次のように考えることができました。

バイトを見つけます。
たとえば、下位ビットを取得するためにbitValue[i]
実行byte tmp = bitValue[i] & 0x0Fします (カウンターが下位カウンターの場合)。
次に dotmp = tmp + 1で 1 ずつインクリメントします。
次に dobitValue[i] >> 2で下位ビットをクリアしbitValue[i] <<2てから元に戻します。これで、オリジナルと同じ上位ビットと下位ビットがクリアされました。
次にbitValue[i] |= tmp、下位ビットを設定します。これで、下位ビット カウンターが 1 ずつインクリメントされました
。bitValue

上位ビットの場合は同じプロセスになりますが、上位ビットの場合です。

次に、カウンターの数を確認する必要があります。

bitmasks:
0x0 0x1 0x2etc を使用ORして、現在のカウンター番号を確認することを考えました。

これらはすべて複雑すぎるようです。私は正しい軌道に乗っていますか？これらの操作は、Javaコーディングでどのように対処するのが最適ですか?

これに関する任意の入力、ガイダンスは大歓迎です。

このソフトウェアは Web アップロード フォルダを作成し、それを FTP クライアント (具体的には WS_FTP) を使用してサイトにアップロードしました。pearl ファイルの最初の行は、"#!usr/bin/pearl" で、これを "/home/calakpsi/pearl" に変更しました。ただし、html ファイルを実行すると、「/C:/Users/myname/AppData/Roaming/Ipswitch/WS_FTP/Storage/cgi-bin/ciwweb.pl」でコンピューターが検索されます。探しているファイルがそのフォルダーにあることを確認しましたが、何らかの理由で Web ページがまだ実行されません。

ヘルプまたは段階的な解決策 (詳細な技術的背景がないため) をいただければ幸いです。

私は「Programming Pearls」を読んでいましたが、解決策の説明の 1 つ (列 1 の問題 9) で本当に混乱しています。

問題は、ビットマップ データを使用して整数のセットを表す場合、最初のフェーズでセットを空に初期化することでした。ただし、スペースの初期化自体にはかなりの時間がかかる場合があります。最初のアクセス時にベクトルのエントリをゼロに初期化する手法を設計して、この問題を回避する方法を示してください。

答えは次のとおりです。ベクトルデータ[0...n-1] を初期化する効果は、2 つの追加の n 要素ベクトルfromとto、および整数topに含まれるシグネチャで実現できます。要素 データ[i] が初期化されている場合、from [i] < top and to [*from*[i]] = i. したがって、fromは単純な署名であり、toとtopを組み合わせることで、メモリのランダムな内容によってfromが誤って署名されないようにすることができます。

この回答を何度か読みました。わかりません。

誰かがそれを説明できますか？

ありがとう、

内容が以下のコンマ区切りのフラットファイルがあります。

全員の名前と連絡先のみを取得する必要があります。区切り文字を「」として使用すると、AとDの連絡先はバンガロールとランチになりますが、これは正しくありません。1番目と4番目のフィールドを取得するにはどうすればよいですか。また、awkコマンドを使用して必要な詳細を取得できるかどうかをお知らせください。

編集 これを追加するだけでサンプルデータになります。元のデータにはさらにいくつかのフィールドがあり、引用符で囲まれた任意のフィールドにコンマを含めることもできます。

「プログラミングパール」のコラム8にあります。最大部分配列の問題があります。

問題 ：

入力は n 個の浮動小数点数のベクトル x です。出力は、入力の連続するサブベクトルで見つかった最大合計です。問題の定義を完成させるために、すべての入力が負の場合、最大合計部分ベクトルは合計がゼロの空のベクトルであると言います。

最も効率的なソリューション:

このコラムには演習があります。 負の数の配列の最大サブベクトルを、空のサブベクトルの合計であるゼロと定義しました。代わりに、最大のサブベクトルを最大の要素の値として定義したとします。さまざまなプログラムをどのように変更しますか？

この演習について 2 つの質問があります (1) 「代わりに、最大のサブベクトルを最大の要素の値として定義したと仮定してください」ということでちょっと混乱しています。負の数の配列の最大サブベクトルが配列内の最大の要素になることを意味しますか?

例: 配列: [-1 -2 -3]、最大サブベクトル: -1 配列: [-1 2 3]、最大サブベクトル: [2 3]

このダミーの質問で申し訳ありません。英語は私の素朴な言語ではありません。

(2) 著者は、「割り当て maxsofar=0 を maxsofar = -infinity に置き換えます」という解決策を示しました。質問に対する私の理解に基づいて、この解決策は正しくないようです。

例: Array : [-1 -2 -3]、答えは -1 である必要があります。しかし、解決策によると、それは 0 です。

ありがとう、

プログラミングパール第2版（8.7章）の問題は次のとおりです。

要素が範囲から均一に描画される実数シーケンスを考える[-1, 1]と、予想される最大連続サブシーケンスの合計はいくつですか？（すべての要素が負の場合、最大合計は0です。）

シーケンスの長さがであると仮定するとN、予想される最大サブシーケンスの合計の閉じた形はありf(N)ますか？シミュレーションを試みましたが、手がかりが見つかりませんでした。

手伝ってくれてありがとう。