私は面白い問題に直面しています。私は(かなり大きい)ブロック数を持っています。ブロックは単にオフセットから始まり、長さと色を持つものです。オフセットと長さは制限されています。これらのブロックが存在するスペースは、< 0-N>です(Nは数十万から数百万の範囲です)。無効なブロックは、オフセットがNより大きい、またはオフセットと長さの合計がNより大きいブロックです。ブロックには約16種類の色があります(そのうちの1つだけです)。小さな重なりブロックをより大きな連続ブロックにマージするための効率的なアルゴリズム?
ブロックの数千人があるかもしれませんし、状況は次のように常にあります
block_X:オフ:100、LEN:50、色:青
block_Y:オフ:148、LEN:50 、色:青
block_Z:オフ:200、LEN:30、色:
赤あなたが見ることができるように、X及びYブロックは、この、その結果、単一の大きなブロックに接続することができます。
block_XY:オフ:100、98をlenは、色:青
block_Z:200オフ、30をlenは、色:赤
私はすべてを行くだろうアルゴリズムを作成したいです重複して同じ色を持つブロックを接続します。実際には、ブロック間の隙間がかなり小さい場合(定数は約16かそこらで選択できますが、任意の数でもかまいません)、とにかくそれらのブロックを接続したいと思います。上記の例では、接続するブロックが2つしかないことに注意してください。実際には、接続可能なブロックの順序はずっと長くなります。
興味深いひねりもあり、このことを考慮してください。
block_Aを:オフ:100、LEN:200、色:青
block_Bを:オフ:200、LEN:200、カラー:ブルー
block_C:オフ:300、LEN:150、色:赤
block_D:オフ:400、LEN:200、色:青
block_E:オフ:500、LEN:200、色:青
あなたが見ることができるように、我々は一つの大きな青色のブロックにマージすることができます青いブロックの素敵な配列を有します。しかし、その真ん中に小さな赤いブロックがあります。このアルゴリズムをだますべきではない、正しい結果は次のとおり
block_ABDE:オフ:100、LEN:600、色:青
block_C:オフ:300、LEN:150、色:赤
データはstd :: multimapに格納されます。ここで、キーはオフセットで、値はブロックの長さと色を含む構造体です(multimap<uint32_t,pair<uint32_t, uint8_t> >
)。同じオフセットから開始するブロックが存在する可能性があることに注意してください。しかし、このようなことが起こった場合、同じオフセットから始まるブロックは、異なる色と異なる長さを持つことが保証される。
誰もこの問題を効率的に解決するための良いアイデアを考え出すことができますか? アルゴリズムの目標は、ブロック数を減らすことですが、できるだけ小さくする必要はありません。
最初に色でソートしてから、オフセットでソートすることができます。 –
しかし、なぜ迷惑? – TonyK