1

I have 20-items array which contains decimal numbers. They are unsorted. On every iteration only several items of the array change (~1-3 items of 20-items array). After each iteration I need to have the same array but "sorted".

I shouldn't modify original array, instead I need to maintain "parallel" structure which represents the same array, but sorted. It's allowed to use pointers.

I do care about latency so I need straighforward solution! Obviously I can use double-linked list to "remember" sort order, but I will spent K*O(n) (with pretty big K) to update this list what sound a little bit to expensive. I'm looking for something better that two-linked list.

i will implement this on c# if this matter

4

2 に答える 2

3

1 ～ 3 個の変更された要素を追跡していると仮定すると、 merge-sort の単一ステップと、配列に対する追加の反復を使用して、かなり効率的に実行できます。

  1. すべての要素を 2 つの配列changedとnotChanged1つにまとめます- 順番に。
  2. 並べ替えchanged(1 ～ 3 個の要素の場合、かなり簡単かつ迅速に行う必要があります)。
  3. merge(changed,notChanged)ソートされた配列を取得するために使用します

複雑さは、1 回の反復で行われ、コレクション フェーズも行われるためO(n)、かなり良い定数を使用していると思います。merge()また、まだ配列を使用しているため、このアプローチはかなりキャッシュ効率が良いはずです。

(1)notChangedがソートされていることに注意してください。変更されていない要素がそれらの間でソートされているためです!

于 2012-12-05T16:50:00.523 に答える
0

2 つの構造を使用するだけです。これは、既存の適切に機能するコレクションを使用するため、簡単で堅牢であり、実装コストが安価です。

2 つのコレクションを使用します。

ソートされていないもの: たとえば、動的に成長する配列である Java ArrayList の場合
ソートされているもの: 好きなものを使用してください。
どちらの「コレクション」も通常どおり、コンテンツ オブジェクトを指します。

マルチスレッドの場合に物事をスレッドセーフにするには：

両方のコレクションを 1 つのクラスにカプセル化し、すべてのアクセスを同期して、両方のコレクションへの読み取りと書き込みが常に同期されるようにします。

于 2012-12-05T16:45:28.147 に答える