4

ファイルに の配列がchar*あります。私が働いている会社では、データをフラット ファイルに保存しています。データが並べ替えられている場合もあれば、そうでない場合もあります。ファイル内のデータを並べ替えたい。

これで、これを行うコードを最初から書くことができました。もっと簡単な方法はありますか？

もちろん、その場での並べ替えが最適なオプションです。私は大きなファイルを扱っていて、RAM がほとんどありません。しかし、私はすべてのオプションを検討します。

すべての文字列は同じ長さです。

これはいくつかのサンプルデータです:

the data is of fixed length
the Data is of fixed length
thIS data is of fixed lengt

これは、長さ 28 の 3 つのレコードを表します。アプリは長さを認識しています。各レコードは CRLF ( \r\n) で終わりますが、この並べ替えには関係ありません。

4

9 に答える 9

15 
template<size_t length> int less(const char* left, const char* right) {
    return memcmp(left, right, length) < 0;
}

std::sort(array, array + array_length, less<buffer_length>);
于 2008-11-24T15:45:24.840 に答える
6

データを RAM に収めることができない場合は、GNU sort プログラム (外部) を使用します。これは、任意のサイズのファイルをソートし、ファイルが大きいほど、プロセス作成の追加コストが小さくなります。

于 2008-11-24T15:59:04.330 に答える
5

STLコンテナだけでなく、配列のネイティブデータ型でもSTLのアルゴリズムを使用できます。std :: sortを使用する他の提案は、投稿されたとおりには機能しません。ただし、strcmpは、文字列が同じでない場合、左側が右側よりも小さい場合だけでなく、すべての比較でtrueと評価される値を返すためです。手側-これはstd::sortが望んでいるものです。左側のtrueを返すバイナリ述語は右側よりも小さくなります。

これは機能します：

struct string_lt : public std::binary_function<bool, char, char>
{
    bool operator()(const char* lhs, const char* rhs)
    {
        int ret = strcmp(lhs, rhs);
        return ret < 0;
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    char* strings [] = {"Hello", "World", "Alpha", "Beta", "Omega"};
    size_t numStrings = sizeof(strings)/sizeof(strings[0]);

    std::sort(&strings[0], &strings[numStrings], string_lt());

    return 0;
}
于 2008-11-24T15:54:47.270 に答える
3

boost::bind出来る：

// ascending
std::sort(c, c + size,  boost::bind(std::strcmp, _1, _2) < 0); 

// descending
std::sort(c, c + size,  boost::bind(std::strcmp, _1, _2) > 0);

編集：文字列はnullで終了していません：

// ascending
std::sort(c, c + array_size,  boost::bind(std::memcmp, _1, _2, size) < 0); 

// descending
std::sort(c, c + array_size,  boost::bind(std::memcmp, _1, _2, size) > 0);
于 2008-11-24T16:09:28.660 に答える
2

おそらく最も簡単な方法は、古いstdlib.h関数qsortを使用することです。これは機能するはずです：

qsort( array, num_elements, sizeof( char* ), strcmp )

これは標準のCであり、英語のテキストでのみ信頼できることに注意してください。

Stringオブジェクトのリストがある場合、C++では他のことが可能です。

Linuxを使用していて、gtkまたはQtアプリケーションを作成している場合は、事前にこれらのライブラリを確認することをお勧めします。

于 2008-11-24T15:46:42.717 に答える
2

ファイルが大きく、RAMに収まらない場合は、ビン/バケットソートを使用してデータを小さなファイルに分割し、最終的に結果ファイルに分割することができます。他の応答は、個々のバケットファイルを並べ替える方法を示しています。

于 2008-11-24T15:50:34.160 に答える
0

Cで文字列の配列をソートするための標準的な方法、したがってC ++でこれを行うために利用可能であるが必ずしも推奨される方法ではなく、次のレベルの間接参照を使用しますstrcmp()。

static int qsort_strcmp(const void *v1, const void *v2)
{
    const char *s1 = *(char * const *)v1;
    const char *s2 = *(char * const *)v2;
    return(strcmp(s1, s2));
}

static void somefunc(void)   // Or omit the parameter altogether in C++
{
    char **array = ...assignment...
    size_t num_in_array = ...number of char pointers in array...
    ...
    qsort(array, num_in_array, sizeof(char *), qsort_strcmp);
    ...more code...
}
于 2008-11-24T17:19:19.893 に答える
0

いくつかのことが思い浮かびます：

  1. データが大きすぎてメモリに収まらない場合は、メモリ内にファイル オフセットのインデックスを作成し、ファイルをメモリ マッピングして文字列にアクセスすることができます (OS によって異なります)。
  2. インプレースでは、大量のメモリ コピーが必要になります。可能であれば、シェルソートを使用してください。その後、最終的な順序がわかれば、線形時間で文字列をその場で並べ替えるのがはるかに簡単になります。
  3. 文字列がすべて同じ長さの場合は、基数ソートが必要です。基数ソートに慣れていない場合は、基本的な考え方を次に示します。比較ベースのソート ( std::sort、qsort、およびその他の汎用ソート) には、常に O(N log N) の時間が必要です。基数の並べ替えでは、一度に 1 桁ずつ ( K の長さの文字列の場合はstr[0]で始まり で終わるstr[K-1]) 比較され、全体として実行に O(N) 時間しかかからない可能性があります。

私が提供できるよりもはるかに詳細な基数ソート アルゴリズムの説明については、インターネットを参照してください。私が言ったことは別として、標準的なライブラリーのソート機能を使用する他のすべてのソリューションは避けたいと思います。残念ながら、それらはあなたの特定の問題のために設計されたものではありません。

于 2008-11-25T13:46:41.477 に答える
0

おそらく、POSIX のメモリ マップ ファイル ( http://en.wikipedia.org/wiki/Memory-mapped_fileを参照)、mmap() 関数 ( http://en.wikipedia.org/wiki/Mmap ) を調べる必要があります。苦情OS。基本的に、ファイルの内容を表す連続したメモリへのポインターを取得します。

良い面は、OS がファイルの一部をメモリにロードし、必要に応じて再度アンロードすることです。

欠点の 1 つは、複数のプロセスがファイルにアクセスする可能性が高い場合、破損を回避するために何らかの形式のファイル ロックに解決する必要があることです。

もう 1 つの欠点は、これが優れたパフォーマンスを保証しないことです。そのためには、常にページをロードおよびアンロードしないようにするソート アルゴリズムが必要になります (もちろん、ファイル全体をメモリにロードするのに十分なメモリがない場合)。

これがあなたにいくつかのアイデアを与えたことを願っています!

于 2008-11-26T17:58:00.377 に答える