12
4

6 に答える 6

2

最も実用的な解決策はqsort、あなたが言及したCスタイルを使用することです。

template <unsigned S>
struct my_obj {
    enum { SIZE = S; };
    const void *p_;
    my_obj (const void *p) : p_(p) {}
    //...accessors to get data from pointer
    static int c_style_compare (const void *a, const void *b) {
        my_obj aa(a);
        my_obj bb(b);
        return (aa < bb) ? -1 : (bb < aa);
    }
};

template <unsigned N, typename OBJ>
void my_sort (const char (&large_array)[N], const OBJ &) {
    qsort(large_array, N/OBJ::SIZE, OBJ::SIZE, OBJ::c_style_compare);
}

（または、必要に応じて呼び出すことができますqsort_r。）STLsortは比較呼び出しをインライン化するため、可能な限り最速のソートが得られない場合があります。システムがソートのみを行う場合は、カスタムイテレータを機能させるためのコードを追加する価値があるかもしれません。ただし、ほとんどの場合、システムが並べ替え以外のことを行っている場合、得られる追加のゲインは、システム全体のノイズにすぎない可能性があります。

于 2012-07-19T16:23:16.710 に答える
1

オブジェクトをバッファにオーバーレイできる場合はstd::sort、オーバーレイタイプがコピー可能である限り、を使用できます。（この例では、4つの64ビット整数）。ただし、 4 GBのデータを使用すると、大量のメモリが必要になります。

コメントで説明されているように、いくつかの固定サイズのテンプレートに基づいて、可能なサイズを選択できます。実行時にこれらのタイプから選択する必要があります（switchたとえば、ステートメントを使用）。さまざまなサイズのテンプレートタイプの例と64ビットサイズの並べ替えの例を次に示します。

簡単な例を次に示します。

#include <vector>
#include <algorithm>
#include <iostream>
#include <ctime>

template <int WIDTH>
struct variable_width
{
   unsigned char w_[WIDTH];
};

typedef variable_width<8> vw8;
typedef variable_width<16> vw16;
typedef variable_width<32> vw32;
typedef variable_width<64> vw64;
typedef variable_width<128> vw128;
typedef variable_width<256> vw256;
typedef variable_width<512> vw512;
typedef variable_width<1024> vw1024;

bool operator<(const vw64& l, const vw64& r)
{
   const __int64* l64 = reinterpret_cast<const __int64*>(l.w_);
   const __int64* r64 = reinterpret_cast<const __int64*>(r.w_);

   return *l64 < *r64;
}

std::ostream& operator<<(std::ostream& out, const vw64& w)
{
   const __int64* w64 = reinterpret_cast<const __int64*>(w.w_);
   std::cout << *w64;
   return out;
}

int main()
{
   srand(time(NULL));
   std::vector<unsigned char> buffer(10 * sizeof(vw64));
   vw64* w64_arr = reinterpret_cast<vw64*>(&buffer[0]);

   for(int x = 0; x < 10; ++x)
   {
      (*(__int64*)w64_arr[x].w_) = rand();
   }

   std::sort(
      w64_arr,
      w64_arr + 10);

   for(int x = 0; x < 10; ++x)
   {
      std::cout << w64_arr[x] << '\n';
   }

   std::cout << std::endl;

   return 0;
}
于 2012-07-19T13:57:12.320 に答える
1

std::sortカスタムイテレータ、参照、値型を使用することに同意します。可能な場合は標準の機械を使用するのが最善です。

メモリの割り当てについて心配しますが、最近のメモリアロケータは、特に繰り返し再利用される場合に、メモリの小さなチャンクを非常に効率的に配布します。独自の（ステートフル）アロケータを使用して、小さなプールから長さsのチャンクを配布することも検討できます。

于 2012-07-19T14:20:10.930 に答える
1

巨大なサイズ（4GB）を考えると、動的なコード生成を真剣に検討したいと思います。カスタムソートを共有ライブラリにコンパイルし、動的にロードします。インライン化されていない呼び出しは、ライブラリへの呼び出しのみである必要があります。

プリコンパイル済みヘッダーを使用すると、コンパイル時間は実際にはそれほど悪くない場合があります。ヘッダー全体<algorithm>は変更されず、ラッパーロジックも変更されません。毎回単一の述語を再コンパイルする必要があります。そして、それはあなたが得る単一の関数なので、リンクは簡単です。

于 2012-07-19T16:33:55.270 に答える
1

オブジェクトのバリエーションは31種類（1〜32バイト）しかないため、それぞれのオブジェクトタイプを簡単に作成std::sortし、switchステートメントに基づいて呼び出し先を選択できます。各呼び出しはインライン化され、高度に最適化されます。

一部のオブジェクトサイズでは、コンパイラがネイティブオブジェクトをパディングしてアドレス境界に揃えることを要求するため、カスタムイテレータが必要になる場合があります。ポインターはイテレーターのすべてのプロパティを持っているため、他の場合にはポインターをイテレーターとして使用できます。

于 2012-07-19T18:18:51.673 に答える
0 
#define OBJECT_SIZE 32
struct structObject
{
    unsigned char* pObject;
    bool operator < (const structObject &n) const
    {
        for(int i=0; i<OBJECT_SIZE; i++)
        {
            if(*(pObject + i) != *(n.pObject + i))
                return (*(pObject + i) < *(n.pObject + i));
        }

        return false;       
    }
};

int _tmain(int argc, _TCHAR* argv[])
{       
    std::vector<structObject> vObjects;
    unsigned char* pObjects = (unsigned char*)malloc(10 * OBJECT_SIZE); // 10 Objects


    for(int i=0; i<10; i++)
    {
        structObject stObject;
        stObject.pObject = pObjects + (i*OBJECT_SIZE);      
        *stObject.pObject = 'A' + 9 - i; // Add a value to the start to check the sort
        vObjects.push_back(stObject);
    }

    std::sort(vObjects.begin(), vObjects.end());


    free(pObjects);

#defineをスキップするには

struct structObject
{
    unsigned char* pObject; 
};

struct structObjectComparerAscending 
{
    int iSize;

    structObjectComparerAscending(int _iSize)
    {
        iSize = _iSize;
    }

    bool operator ()(structObject &stLeft, structObject &stRight)
    { 
        for(int i=0; i<iSize; i++)
        {
            if(*(stLeft.pObject + i) != *(stRight.pObject + i))
                return (*(stLeft.pObject + i) < *(stRight.pObject + i));
        }

        return false;       
    }
};

int _tmain(int argc, _TCHAR* argv[])
{   
    int iObjectSize = 32; // Read it from somewhere

    std::vector<structObject> vObjects;
    unsigned char* pObjects = (unsigned char*)malloc(10 * iObjectSize);

    for(int i=0; i<10; i++)
    {
        structObject stObject;
        stObject.pObject = pObjects + (i*iObjectSize);      
        *stObject.pObject = 'A' + 9 - i; // Add a value to the start to work with something...  
        vObjects.push_back(stObject);
    }

    std::sort(vObjects.begin(), vObjects.end(), structObjectComparerAscending(iObjectSize));


    free(pObjects);
于 2012-07-19T15:12:04.983 に答える