2

すべてを読み取ってからソートするのではなく、ヒープベースの C スタイルの名前の配列を読み取り中にソートする必要がある割り当てがあります。これには、配列の内容を 1 つずつシフトして、新しい名前を挿入できるようにする必要があります。以下のコードを使用していますが、非常に遅いです。ストレージのタイプを変更せずに最適化するために他にできることはありますか?

//the data member
string *_storedNames = new string[4000];

//together boundary and index define the range of elements to the right by one
for(int k = p_boundary - 1;k > index;k--)
   _storedNames[k]=_storedNames[k - 1];

EDIT2: Cartroo が提案したように、malloc を使用する動的データで memmove を使用しようとしています。現在、これはデータを正しくシフトしますが、割り当て解除プロセスで再び失敗します。何か不足していますか？

int numberOfStrings = 10, MAX_STRING_SIZE = 32;

char **array = (char **)malloc(numberOfStrings);

for(int i = 0; i < numberOfStrings; i++)
    array[i] = (char *)malloc(MAX_STRING_SIZE);

array[0] = "hello world",array[2] = "sample";   

    //the range of data to move
int index = 1, boundary = 4;
int sizeToMove = (boundary - index) * sizeof(MAX_STRING_SIZE);

memcpy(&array[index + 1], &array[index], sizeToMove);

free(array);
4

4 に答える 4

1

アプローチに最小限の変更を加えている場合は、この関数を使用できますmemmove()。これは、独自の手動バージョンよりも高速になる可能性があります。memcpy()メモリの領域が重複することは許可されていないため、あるコメンターのアドバイスに従って使用することはできません(重複した場合の動作は未定義です)。

ストレージのタイプやアルゴリズムを変更せずにできることは他にあまりありません。ただし、リンクされたリストを使用するように変更すると、より多くのメモリ割り当てを行うことになりますが、操作は大幅に効率的になります。割り当てが本当に問題である場合 (限られた組み込みシステムを使用している場合を除き、おそらくそうではないでしょう)、プール アロケーターまたは同様のアプローチが役立つ可能性があります。

編集: あなたの質問を読み直して、あなたが実際に Heapsort を使用していないと推測しています。配列がヒープに割り当てられ(つまり、 を使用malloc())、単純な挿入 sortを行っていることを意味します。その場合、以下の情報は直接的にはあまり役に立ちませんが、挿入ソートは、一括挿入の後に優れたソート アルゴリズム (たとえば、標準ライブラリ関数を使用して実装できるクイックソートqsort()) に比べて非常に非効率的であることに注意してください。 ）。完全にソートされた順序ではなく、最下位 (または最上位) の項目のみが必要な場合でも、Heapsort は有用な読み物です。

標準のヒープソートを使用している場合、この操作はまったく必要ありません。項目は配列の最後に追加され、「ヒープ化」操作を使用してそれらをヒープ内の正しい位置にスワップします。各スワップには、2 つのアイテムを交換するための一時変数が 1 つ必要です。コード スニペットのようにシャッフルする必要はありません。char配列内のすべてが同じサイズ（固定サイズのインプレース文字列、またはおそらくポインターのいずれか）である必要がありますが、コードはすでにそれを想定しているようです（そして、標準配列で可変長文字列を使用するとやっているのはかなり奇妙なことです）。

厳密に言えば、ヒープソートは二分木で動作することに注意してください。配列を扱っているので、インデックスのノードの子がそれぞれインデックスに格納される連続した配列が使用される実装を使用していると思いnます。そうでない場合、またはヒープソートをまったく使用していない場合は、より役立つ回答を得るために何をしようとしているのかを詳しく説明する必要があります。2n2n+1

編集: 以下は、上記の更新されたコードへの応答です。

解放中に問題が発生する主な理由は、メモリを踏みにじった場合です。つまり、割り当てた領域のサイズを超えて何かをコピーしている場合です。システムが割り当てを追跡するために使用している値を上書きし、通常はプログラムのクラッシュにつながるあらゆる種類の問題を引き起こすため、これは非常に悪いことです。

まず、メモリの割り当てと割り当て解除の性質について、少し混乱しているようです。の配列を割り当てますがchar*、それ自体は問題ありません。char次に、文字列ごとに配列を割り当てますが、これも問題ありません。free()ただし、最初の配列を呼び出すだけです。これでは十分ではありません。free()への各呼び出しに対応する への呼び出しがmalloc()必要なので、割り当てた各文字列を解放してから初期配列を解放する必要があります。

次に、sizeToMoveの倍数に設定しますがsizeof(MAX_STRING_SIZE)、これはほぼ確実に望んでいるものではありません。MAX_STRING_SIZEこれは、定数を格納するために使用される変数のサイズです。代わりに、必要ですsizeof(char*)。一部のプラットフォームでは、これらは同じである可能性があり、その場合でも機能しますが、その保証はありません。たとえば、32 ビット プラットフォーム (intとchar*は同じサイズ) では動作すると思いますが、64 ビット プラットフォーム (同じサイズではない) では動作しません。

第三に、文字列定数 (例: "hello world") を割り当てられたブロックに割り当てることはできません。ここで行っているのは、ポインターの置き換えです。strncpy()またはのようなものを使用memcpy()して、割り当てられたブロックに文字列をコピーする必要があります。結果を無効にすることを保証しないという問題があるsnprintf()ため、便宜上お勧めしますが、それはあなた次第です。strncpy()

第 4 に、アイテムをシャッフルするmemcpy()のではなく、まだ使用しています。memmove()

new最後に、 andを使用する必要があるというコメントを見ましたdelete。これらに相当するものはありませんがrealloc()、すべてが事前にわかっていれば問題ありません。あなたがやろうとしていることは次のようなものです：

bool addItem(const char *item, char *list[], size_t listSize, size_t listMaxSize)
{
    // Check if list is full.
    if (listSize >= listMaxSize) {
        return false;
    }
    // Insert item inside list.
    for (unsigned int i = 0; i < listSize; ++i) {
        if (strcmp(list[i], item) > 0) {
            memmove(list + i + 1, list + i, sizeof(char*) * (listSize - i));
            list[i] = item;
            return true;
        }
    }
    // Append item to list.
    list[listSize] = item;
    return true;
}

私はそれをコンパイルしてチェックしていないので、off-by-one エラーなどに気をつけてください。この関数はmalloc()、 andfree()またはnewandを使用するかどうかに関係なく機能するはずですが、もちろんポインターを格納するだけなので、保持する割り当てられたバッファーにdelete文字列が既にコピーされていることを前提としています。item

もちろん、この関数の外で自分自身を更新する必要があることを思い出してくださいlistSize。これは、配列内の正しいポイントにアイテムを挿入するだけです。関数が返された場合はtrue、のコピーをlistSize1 増やします。返されfalseた場合は、十分なメモリを割り当てなかったため、アイテムは追加されませんでした。

また、C と C++ では、配列listの構文&list[i]とlist + iは完全に同等であることに注意してくださいmemmove()。理解しやすい場合は、呼び出し内で代わりに最初のものを使用してください。

于 2013-03-31T23:32:33.770 に答える
0

配列はソートされており、他のデータ構造を使用できないため、バイナリ検索を実行する可能性が高いため、配列を1つ上にシフトして挿入位置のスペースを解放し、その位置に新しい要素を挿入します.

于 2013-03-31T23:31:17.003 に答える
0

配列をシフトするコストを最小限に抑えるには、文字列へのポインターの配列にすることができます。

string **_storedNames = new string*[4000];

これで使用できます(memmoveただし、要素ごとのコピーが十分に高速であることに気付くかもしれません)。ただし、個々の文字列の割り当てと削除を自分で管理する必要があり、これは多少エラーが発生しやすくなります。

元の配列での使用を推奨する他の投稿者memmoveは、各配列要素が a string( string*! ではない) であることに気づいていないようです。このようなクラスではmemmoveorを使用できません。memcpy

于 2013-04-01T08:49:13.640 に答える
0

あなたが探しているのはヒープソートだと思います: http://en.wikipedia.org/wiki/Heapsort#Pseudocode

配列は、二分探索木 (つまり、左の子が現在のノードよりも小さく、右の子が現在のノードよりも大きいツリー) を実装する一般的な方法です。

ヒープソートは、指定された長さの配列をソートします。あなたの場合、配列のサイズは「オンライン」で増加するため、ヒープソートに渡す入力サイズの変更を呼び出すだけです（つまり、考慮される要素の数を1増やします）。

于 2013-03-31T23:28:58.777 に答える