問題タブ [programming-pearls]

使用可能なノードのコレクションを独自の構造に保持することで、ストレージ アロケーターへの多くの呼び出しを回避できます。

この考え方は、二分探索木のデータ構造に適用できます。

著者は次のように述べています。「ノードを一度にすべて割り当てると、ツリーに必要なスペースが大幅に削減され、実行時間が約 3 分の 1 に短縮されます。」

このトリックがスペース要件をどのように削減できるのか、私は興味があります。つまり、4 つのノードを持つ二分探索木を構築したい場合、ノードを 1 つずつ割り当てても、一度に割り当てても、これら 4 つのノードにメモリを割り当てる必要があります。

「真珠のプログラミング」：真珠の文字列、セクション15.3（テキストの生成）では、作成者が入力ドキュメントからランダムなテキストを生成する方法を紹介しています。ソースコードには、わからないことがいくつかあります。

著者は次のように説明しています。「入力を読み取った後、k個のヌル文字を追加します（比較関数が最後から実行されないようにします）。」この説明は、これらの2行にコメントした後でもうまく機能するため、私を本当に混乱させます。なぜこれが必要なのですか？

プログラミングパールのセクション15.2から

C コードはここで見ることができます: http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c

suffix-array を使用して Python で実装すると、次のようになります。

ステップが非常に遅いことがわかりましたidx.sort。Python は (上記の C コードのように) ポインターではなく値で部分文字列を渡す必要があるため、遅いと思います。

テストしたファイルはここからダウンロードできます

C コードは 0.3 秒で終了します。

しかし、Python コードの場合、私のコンピューターでは決して終了しません (10 分間待って強制終了しました)。

コードを効率的にする方法を知っている人はいますか? (例: 10 秒未満)

私は最近、せいぜいバグのように見える状況に遭遇しました。との両方が、比較で使用された場合、負の無限大よりも低く評価されているようnullにfalse見えますが、等しくはありません。

私の現在のテストケース：

これは、さまざまなPHPバージョンと、私がアクセスしたいくつかのWindowsマシンで実行されました。すべてが驚くべき同じ結果をもたらしました。

最初の2つのデバッグダンプを無視すると、次の6つの結果は、経験豊富なPHP開発者であれば期待できるものです。最初の2つは型ジャグリングによるもので、最後の4つはPHPと数学によるものです。

さて、最後の4つは私を悩ませているものです。

負の無限大よりも低いものを持つことが数学でさえ有効であるかどうかはわかりません。

さらに奇妙なのは、最初の2つと最後の2つの比較の組み合わせです。どういうわけか、同じタイプのジャグリングアルゴリズムがこれを有効にします。

これらの型キャストがどのように異なって評価されているのか、そしてなぜそれが大いに評価されるのかについて誰かが洞察を与えることができれば。

PS私は何度も何度もSOを検索しようとしましたが、 PHPマニュアル、さらにはPHPバグトラッカーでさえも役に立ちませんでした。私はCのソースコードを調べて、このコードをそのように機能させるための要素を特定してみました。まだサイコロはありません。

質問: 入力は順次ファイルにあります。ファイルには、最大で 40 億の整数が含まれています。欠落している整数を見つけます。

私の理解による解決策：

1. 先頭が 0 の 2 つの一時ファイルと先頭が 1 の一時ファイルを作成する

2. 2 つの MUST (4.3B ピジョンホールと 4B ピジョン) のうちの 1 つは 2B 未満です。ファイルを選択し、ステップ 1 と 2 を 2 番目のビットで繰り返し、次に 3 番目のビットで繰り返します。

この反復の終了条件は何ですか?

また、この本ではアルゴリズムの効率がO(n)であると言及されていますが、

1 回目の繰り返し => n 回のプローブ操作
2 回目の繰り返し => n/2 回のプローブ操作
.
.
.
n + n/2 + n/4 +... 1 => nlogn??

何か不足していますか？