c++ - stdsortは永遠にループしているようです

Question

現在、二分探索を行うクラスがあります。クラスはベクトルを受け入れますが、それからクラスにソートするように指示します。

潜在的に名または姓のみで並べ替えることができる必要があるため、そのクラスの選択肢として文字引数を設定して、ベクトルの並べ替え方法を変更します。私もそのクラスで、ベクトルをソートするためのクラスポインタとして* thisを使用するoperator（）関数を作成しました。しかし、それは永遠にループしているようです。誰か教えてもらえますか？以下のコード。

*私が従わない一般的な慣行がある場合は、遠慮なくお知らせください。私は今、悪い習慣を作り始めたくありません。

リクエストによる：Getname

void personType::getName(string& first, string& last)
{
    // get the name and set it
    first = firstName;
    last = lastName;
}


bool sBinary::operator()(studentType student1, studentType student2){
    string toCheck1, toCheck2, fName1,lName1 ,fName2 , lName2;
    student1.getName(fName1, lName1);
    student2.getName(fName2, lName2);
    toCheck1=checkStr(fName1, lName1);
    toCheck2=checkStr(fName2,lName2);
    return toCheck1<toCheck2;
}

string sBinary::checkStr(string fName, string lName){
    string toCheck;
    switch (choice){
    case 'f':
    case 'F':
        toCheck=fName;
        break;
    case 'l':
    case 'L':
        toCheck=lName;
        break;
    case 'r':
    case 'R':
        toCheck=fName+lName;
        break;
    default:
        toCheck=lName+fName;

    }

    return toCheck;

}


sBinary::sBinary(vector<studentType> _sList, char _choice){
    sList=_sList;
    steps=0;
    choice=_choice;
    sort(sList.begin(),sList.end(), *this);
}

score 6 · Accepted Answer

そのため、永遠にループしないように見えますが、実行時間が長すぎます。全く別の話です。あなたのコードにはいくつかのペシミゼーションがあります: 主な懸念は*this、ソートアルゴリズムに , を渡すことです:

sort(sList.begin(),sList.end(), *this);

std::sort比較述語を値で取り、それを何度もコピーします。コピーコンストラクターを定義すると、それを見ることができます：

sBinary(const sBinary& r):choice(r.choice), sList(r.sList)
{
    std::cout << "copied\n";
}

そして、ベクトルはオブジェクト自体とともにコピーされます。

たとえば、配列サイズが 200 の場合、オブジェクトを13646 回std::sortコピーします。つまり、2700000 回の生徒のコピー操作が関係していることになります。

*thisしたがって、に渡すべきではありませんstd::sort。lessThen代わりに静的関数を定義operator()して、並べ替えアルゴリズムに渡す方がよいでしょう。

さらなる改良:

値渡しではなく参照渡し。たとえば、lessThen関数宣言では次のようになります

static bool lessThen(const studentType& student1, const studentType& student2);
                   //^^^^^            ^
                   //constant         reference

studentTypeクラスをリファクタリングします。

姓名を返す 2 つの別個の関数を使用することをお勧めします (定数参照による)。この場合、一時変数への名前のコピーを取り除くことができます。単一の機能を使用する場合は、姓と名の両方をコピーする必要があることに注意してください。たとえ 1 つの名前が使用されない場合でも、次のようになります。
```
const std::string& first_name() const { return _fname; }
const std::string& last_name() const { return _lname; }
```

score 3 · Accepted Answer

これを含めているのは、このリストを並べ替える方法に代わる方法を知っている必要があるためです. Lol4t0 は、コピーするのにコストがかかるコンパレータを持つことの恐ろしさについてすでに話しました (そして、元の実装よりもコストのかかるコンパレータを持つことは難しいでしょう)。

アルゴリズムは、可能な限り単純なコンパレーターを指定したときに最適に機能し、そのstd::sort実装をインライン化する可能性ができるだけ高くなります。理想的には、次のような比較演算子関数を実装します。

struct cmpObjects
{
    bool operator ()(const Object& left, const Object& right) const
    {
        return (left compared to right somehow);
    }
}

まず、const 参照の使用に注意してください。これを行わないことを考慮する必要があるのは、基になるデータがネイティブの組み込み型 ( 、など) である場合のみintですchar。そのような場合、実際には値渡しの方が高速です。ただし、この場合、学生の記録は、参照によってアクセスする方が確実に効率的です (コピーする必要はありません)。

あなたの特定のタスクに関しては、ソート基準が選択ベースであるという事実に基づいて、あなたのタスクはもう少し複雑です。ソート速度を最大化したい場合は、理想的には、選択ケースごとに、タイトで安価にコピー可能なコンパレーターを 1 つ用意します。次に、を呼び出す前に決定された、その選択に基づいて適切なコンパレーターを使用しますstd::sort。

たとえば、姓で並べ替えていることがわかっている場合は、次のようになります。

// compares last name
struct cmp_LName
{
    bool operator ()(const studentType& left, const studentType& right) const
    {
        return left.lastName < right.lastName;
    }
}

または、次のような名、姓の可能性があります。

// compares first name, then last name only if first name is identical.
struct cmp_FNameLName
{
    bool operator ()(const studentType& left, const studentType& right) const
    {
        int res = left.firstName.compare(right.firstName);
        return res < 0 || (res == 0 && left.lastName < right.lastName);
    }
}

これにより、sBinaryコンストラクターの部分的な外観が次のようになります。

sBinary(const std::vector<studentType>& sList_, char choice)
    : sList(sList_)
{
    switch (choice)
    {
        case 'L':
        case 'l':
            std::sort(sList.begin(), sList.end(), cmp_LName());
            break;

        case 'R':
        case 'r':
            std::sort(sList.begin(), sList.end(), cmp_FNameLName());
            break;

        ....
    }
}

まず、実際にを呼び出す前に、選択する比較手法を選択していることに注意してくださいstd::sort。これを行うと、使用しているカスタムコンパレーター内でその基準が正確に何であるかが明確に定義され、それを管理するオーバーヘッドがゼロになります。

それで、トレードオフは何ですか？4 つのコンパレータ (cmp_LName、cmp_FName、cmp_FNameLName、および cmp_LNameFName) が必要であり、受信した選択に基づいてどれを使用するかをトリガーします。ただし、そうすることの利点は誇張することはできません。これは、選択に基づいてリストをソートする最速の方法です。

補遺:シングルコンパレータ

単一のコンパレータを使用するという考えに完全に積極的に同意している場合は、可能な限り安価にコピーし、ソート条件で行われた選択をその中に埋めてconst、コンパイラがコードをクリーンアップする可能性を最大限に高めます。これを行う方法を示すために、以下の完全な展開を含めましたが、速度が主な関心事である場合、これは最適ではないsBinaryことを強調します.

class sBinary
{
    // compare student based on fixed choice determine at construction.
    struct cmp_student
    {
        const char choice;
        cmp_student(char choice) : choice(choice) {};

        bool operator()(const studentType& left, const studentType& right) const
        {
            switch (choice)
            {
                case 'F':
                case 'f':
                    return left.firstName < right.firstName;

                case 'L':
                case 'l':
                    return left.lastName < right.lastName;

                case 'R':
                case 'r':
                {
                    int res = left.firstName.compare(right.firstName);
                    return res < 0 || (res == 0 &&  left.lastName < right.lastName);
                }

                default:
                {
                    int res = left.lastName.compare(right.lastName);
                    return res < 0 || (res == 0 &&  left.firstName < right.firstName);
                }
            }
        }
    };

public:
    sBinary(const std::vector<studentType>& sList, char choice)
        : sList(sList)
    {
        std::sort(sList.begin(), sList.end(), cmp_student(choice));
    }

    std::vector<studentType> sList;
};

c++ - stdsortは永遠にループしているようです

2 に答える 2

さらなる改良:

Related

Reference