2

Windows Embedded Compact 7 で使用するプログラムを C++ で作成しています。埋め込みコードを作成するときは、配列を動的に割り当てない方がよいと聞いています。0 から 50 個のオブジェクトを追跡するので、最初に 50 個のオブジェクトを割り当てます。

Object objectList[50];
int activeObjectIndex[50];
static const int INVALID_INDEX = -1;
int activeObjectCount=0;

activeObjectCount は実際に使用しているオブジェクトの数を示し、activeObjectIndex は使用しているオブジェクトを示します。0 番目、7 番目、および 10 番目のオブジェクトが使用されていた場合、 さまざまなオブジェクトがアクティブまたは非アクティブになるときに、activeObjectIndex リストを順序付けたままにしたいと思いますactiveObjectIndex = [0,7,10,-1,-1,-1,...,-1];。activeObjectCount=3;

現在、値が変更される可能性のある各ループの最後で、activeObjectIndex を並べ替えているだけです。

まず、組み込みシステムでオブジェクト (アクティブであるかどうかに関係なく) を追跡する方法として、私が行っているよりも良い方法はありますか? そうでない場合、アクティブなオブジェクトを追加または削除するたびにオブジェクトを並べ替えるために使用できるアルゴリズムはありますか? それとも、定期的にバブルソートなどを行って、それらを整理する必要がありますか?

4

5 に答える 5

1

インデックスのリストでアクティブなものを検索するメソッドを作成すると、リストがソートされることを心配する必要はありません。特定のケースでは、配列がこの小さな値に対して十分に小さいように見えるため、O(N)に償却されます。O(1)追加の検証。

制限に達するまで、最後にチェックした要素のインデックスを維持できます。

unsigned int next(const unsigned int& last) {

    for (unsigned int i = last + 1; i < MAX_ARRAY_SIZE; i++) {
        if (activeObjectIndex[i] != -1) {
            return i;
        }
    }

    return -1;

}

ただし、本当にサイドインデックスが必要な場合は、配列のサイズを2倍にするだけで、要素への二重リンクリストを作成できます。

activeObjectIndex[MAX_ARRAY_SIZE * 3] = {-1};
activeObjectIndex[i] = "element id";
activeObjectIndex[i + 1] = "position of the previous element";
activeObjectIndex[i + 2] = "position of the next element";
于 2012-12-24T21:26:19.880 に答える
1

システムに関するかなりの知識が必要な難しい質問があります。その知識がなければ、私が与えることができる答えは完全ではありません。しかし、組み込み設計の 15 年間の経験から、次のことを学びました。

  1. あなたは正しいです。通常、実行時にオブジェクトを割り当てたくありません。すべてのオブジェクトを事前に割り当て、それらをアクティブ/非アクティブ キューに移動します。
  2. 物事を整理しておくことは、一般的に難しいことです。おそらく、その必要はありません。あなたはそれについて言及していませんが、オブジェクトを「使用済み」プールと「空き」プールに保持する必要があるだけで、インデックスを使用してオブジェクトをすばやく検索/削除していると思います。

次の解決策を提案します。オブジェクトを次のように変更します。

class Object {
  Object *mNext, *mPrevious;
public:
  Object() : mNext(this), mPrevious(this) { /* etc. */ }

  void insertAfterInList(Object *p2) {
    mNext->mPrev = p2;
    p2->mNext = mNext;
    mNext = p2;
    p2->mPrev = this;
  }

  void removeFromList() {
    mPrev->mNext = mNext;
    mNext->mPrev = mPrev;
    mNext = mPrev = this;
  }

  Object* getNext() {
    return mNext;
  }

  bool hasObjects() {
    return mNext != this;
  }
};

そしてあなたのオブジェクトを使用してください：

#define NUM_OBJECTS (50)
Object gObjects[NUM_OBJECTS], gFree, gUsed;

void InitObjects() {
  for(int i = 0; i < NUM_OBJECTS; ++i) {
    gFree.insertAfter(&mObjects[i]);
  }
}

Object* GetNewObject() {
  assert(mFree.hasObjects());
  Object obj = mFree->getNext();
  obj->removeFromList();
  gUsed.insertAfter(obj);
  return obj;
}

void ReleaseObject(Object *obj) {
  obj->removeFromList();
  mFree.insertAfter(obj);
}

小さな不具合を修正するために編集しました。テストされていませんが、今すぐ動作するはずです。:)

于 2012-12-24T21:39:43.197 に答える
1

std::vector のオーバーヘッドは非常に小さいです。発生する可能性のある問題は、動的なサイズ変更によって必要以上のメモリが割り当てられることです。ただし、50 個の要素があるため、これはまったく問題にはなりません。試してみて、強い影響が見られる場合にのみ変更してください。

未使用のオブジェクトを std::vector から削除できない/削除したくない場合は、オブジェクトがアクティブかどうかを示すブール値をオブジェクトに追加できますか? これは、activeObjectIndex を使用するよりも多くのメモリを必要としません (アライメントの問題によってはさらに少ないかもしれません)。

ブール値でデータをソートするには (最後にアクティブではない)、関数を記述します。

bool compare(const Object & a, const Object & b) {
    if(a.active && !b.active) return true;
    else return false;
}

std::sort(objectList,objectList + 50, &compare); // if you use an array
std::sort(objectList.begin(),objectList.end(), &compare); // if you use std::vector

activeObjectIndex を使用して並べ替えたい場合は、より複雑になります。常に順序付けされた構造を使用する場合は、std::set を使用します。ただし、より多くのメモリが必要になります (ただし、50 要素の場合は問題になりません)。

理想的には、次の関数を実装します。

bool operator<(const Object & a, const Object & b) {
    if(a.active && !b.active) return true;
    else return false;
}

これにより、 std::sort(objectList.begin(), objectList.end()) を直接使用するか、ソートされたままになる std::set を宣言できます。

于 2012-12-24T21:16:20.733 に答える
1

アクティブ/非アクティブを追跡する 1 つの方法は、アクティブなオブジェクトを二重にリンクされたリストに置くことです。オブジェクトが非アクティブからアクティブになると、リストに追加され、アクティブから非アクティブになり、リストから削除されます。これらをオブジェクトに追加できます

Object * next, * prev;

したがって、これにはメモリ割り当ては必要ありません。

于 2012-12-24T21:22:40.487 に答える
1

動的メモリ割り当てが許可されていない場合は、単純な c-array またはstd::arrayインデックスを使用します。これは、last+1 オブジェクトを指します。オブジェクトは常にソートされた順序で保持されます。

追加は、ソートされたリストの正しい位置に新しいオブジェクトを挿入することによって行われます。挿入位置を見つけるためにlower_bound、またはfind_if使用することができます。要素数が 50 の場合は、おそらく 2 番目の方が速くなります。取り外しも同様です。

于 2012-12-24T21:22:56.433 に答える