問題タブ [contiguous]

背景（入力）

Global Historical Climatology Networkは、気象測定値のコレクションで無効または誤ったデータにフラグを立てました。これらの要素を削除した後、連続した日付のセクションがなくなった一連のデータがあります。データは次のようになります。

問題（出力）

欠落しているデータを推定して (たとえば、他の年から平均することによって) 連続した範囲を提供することは可能ですが、システムを簡素化するために、月を埋める連続した日付範囲があるかどうかに基づいて、連続していないセグメントにフラグを立てたいと考えています。

1843 年にいくつかの測定が行われました。

質問

すべての測候所について、1 日以上欠落している月のすべての日をどのようにマークしますか?

ソースコード

データを選択するコードは次のようになります。

関連するアイデア

連続した日付で満たされたテーブルを生成し、それらを測定データの日付と比較します。

• (mysql または perl 側で) SQL の結果に空の日付を埋め込む最も簡単な方法は何ですか?
• 連続範囲でグループ化する方法
• http://msdn.microsoft.com/en-us/library/aa175780%28v=sql.80%29.aspx

アップデート

この問題は、このセクションの SQL を使用して再現できます。

テーブル

テーブルは次のように作成されます。

データの生成

次の SQL は、テーブルにデータを挿入します ( id[int]、name [varchar]、date [date]、valid[boolean]):

～の値は、特定の日に測定を行った気象観測所の名前'A'を表します。'F'

ランダムな行を削除

次のようにいくつかの行を削除します。

試み #1

次の例では、月に 1 日以上欠落しているすべての日に対してvalidフラグを切り替えません。false

試み #2

次の SQL は、空の結果セットを生成します。

試み #3

次の SQL は、駅名と日付の可能な組み合わせをすべて生成します。

ただし、実際のデータには数百の測点があり、日付は 1800 年代半ばまでさかのぼるため、すべての測点のすべての日付のデカルトは大きすぎます。このようなアプローチは、十分な時間があればうまくいくかもしれません...もっと速い方法があるはずです。

試み #4

PostgreSQL にはウィンドウ関数があります。

postgres でウィンドウ関数を使用して特定の変更を選択する方法

ありがとうございました！

次のような 2 次元配列があります。

横方向または下方向に連続する 1 の最長のチェーンを特定する方法を見つけようとしています。この場合、列 4、行 2 から始まり、その長さは 4 で下に向かっています。

再帰を使用することを考えていましたが、特に 0 に遭遇したときに、位置を追跡する際に問題が発生しています。

これまでのところ、私はこれに沿ったものを持っています（全体をチェックするためだけに）：

ここG[][]で、 は 1 と 0 を含む 2 次元配列n、 は行/列のi数、 は行番号、jは列番号です。

事前にご協力いただきありがとうございます。

C++ でグローバル配列または静的配列を定義する場合、そのメモリはプログラムの開始時にすぐに予約されるのではなく、配列に書き込むと一度だけ予約されます。私が驚いたのは、配列のごく一部に書き込むだけでは、メモリ全体を確保できないことです。グローバル配列にまばらに書き込む次の小さな例を考えてみましょう。

さまざまなステップ サイズに対してこれを実行し、たとえば次のような top の出力を確認します。

RES 列は、メモリが小さなブロックでのみ予約されていることを示しています。これは、配列が物理メモリ内で連続している可能性が低いことも意味します。物事のより低いレベルについてより多くの洞察を得た人はいますか?

これには、RES の合計が以下である限り、すべての VIRT の合計が物理メモリを超える多くのプログラムを簡単に実行できるというマイナスの副作用もあります。ただし、それらがすべてグローバル配列に書き込まれるとすぐに、システムは物理メモリを使い果たし、プログラムに sigkill または何かが送信されます。

理想的には、最初にグローバル変数と静的変数のメモリを予約するようにコンパイラに指示したいと思います。可能？

編集

@Magnus: 行は実際には正しい順序になっています。:) たとえば、最初の行./a.out 1000000は、配列の 100 万番目のエントリごとに書き込みを行っていることを意味するため、合計で 250 しかありません。これは、わずか 1868k の RES に相当します。最後の例./a.out 100では、100 エントリごとに書き込まれ、合計メモリも RES=VIRT=1.9g に物理的に割り当てられます。数値から、エントリが配列に書き込まれるたびに、完全な 4k ブロックのようなものが物理メモリに予約されているように見えます。

@Nawaz：配列は仮想アドレス空間で連続していますが、私が理解しているように、OSは怠惰で、実際に必要なときにのみ物理メモリを予約する可能性があります。これは一度に配列全体ではなく小さなブロックで行われるため、物理メモリ内で連続していることをどのように保証できますか?

@Nemo: ありがとうございます。実際にa.out、最初に一時停止してから配列に書き込む複数のインスタンスを呼び出したときに、oom-killerメッセージが表示されました/var/log/messages。実際、あなたのコマンドにより、最初からインスタンスがsysctrl多すぎるのを防ぐことができます。a.outありがとう！

最後の 2 行は少し気になります。:)

@doron: ありがとう、すばらしい説明です。申し訳ありませんが、賛成/選択できません。

標準では連続したメモリ ブロックの割り当てが強制されていないことはわかっていstd::vectorますが、それでもすべての実装がこれに従います。

多次元の静的配列のベクトルを作成したいとします。簡単にするために 2 次元と長さ N のベクトルを考えてみましょうint[5]。

すべての N*5 整数がメモリ内で連続していると確信できますか? 原則として、最初の要素のアドレスを知るだけですべての整数にアクセスできるようにするには? この実装は依存していますか?

参考までに、私が現在連続したメモリ ブロックに 2D 配列を作成する方法は、最初に長さ N の float* の (動的) 配列を作成し、1 つの配列にすべての N*5 個の float を割り当ててから、5 番目ごとの要素のアドレスをの最初の配列float*。

記憶はstd::array連続していますか？次の有効/グッドプラクティスはありますか？

ptr次に、cスタイルの配列を期待する関数に渡すことができますか？

重複の可能性：
std :: vector要素は連続していることが保証されていますか？

要素をメモリに連続して格納すると言われているように、人々がC++のベクトルを使用してMPI操作のデータを送受信する手法に出くわしました。

ただし、特にベクトルが特定のサイズに成長し、この仮定が崩れる可能性がある場合に、このアプローチが任意のサイズのベクトルに対して堅牢であり続けるかどうかについては懐疑的です。

以下は私が話していることの例です：

潜在的なラテン方陣を読み取り、それが有効なラテン方陣かどうかを判断するプログラムを作成しています。今、選択したリージョンが連続したリージョンかどうかを確認しようとしています。

潜在的なラテン スクエアと地域の場所が同時に読み込まれます。リージョン[0,1][0,2][1,1][1,2]は連続しているため、有効なリージョンになります。 到達できない[0,0][0,2][1,1][1,2]ため、連続または有効ではありません。[0,0]それらが連続しているかどうかはどうすればわかりますか？

このアプリケーションは、幾何学的座標の大きなstd :: vector <>を割り当てます
。これは、モデルを描画するために最終的にOpenGLに送信されるため、ベクトル（連続していることを意味します）である必要があります。
また、OpenGLは連続したデータを処理します。
ある時点で割り当てが失敗します。これは、メモリを予約するとstd::bad_alloc例外がスローされることを意味します。ただし、現時点ではまだ多くのメモリが空いています。
問題は、隣接するブロックを割り当てることができないことです。
したがって、最初の2つの質問は次のとおりです。

• CRTがメモリを割り当てる方法を制御する方法はありますか？またはそれを最適化する方法（クレイジーなアイデア））。

• おそらく、実行時に何らかのサイズのメモリのブロックを割り当てることができるかどうかを確認する方法があります（try / catchを使用しない）。

上記の問題は、この1つの大きなベクトルを複数のベクトルにフラグメント化し、それぞれに対してOpenGLを1回呼び出すことで部分的に解決されました。
ただし、それぞれの小さいベクトルのサイズを定義する方法にはまだ疑問があります。かなり小さいサイズのベクトルがたくさんある場合は、ほぼ確実にメモリに適合しますが、OpenGLの呼び出しが多くなり、視覚化が遅くなります。

連続した一連の日付から始める場合:

この配列をソートして、順番にすべての日付が少なくとも 1 日離れているようにするにはどうすればよいですか?

もちろん、これは2つの連続する日付の配列では不可能であることを認識しています。