Универсальная функция remove () vs Member Function remove () для связанного списка - PullRequest
Новая
       16

Универсальная функция remove () vs Member Function remove () для связанного списка

0 голосов
/ 31 октября 2018

Я читаю книгу «C ++ STL. Учебное пособие и ссылки», написанную Николаем М. Джозуттисом и в одной из глав, посвященных алгоритмам STL, автор утверждает следующее: Если вы вызываете remove () для элементы списка, алгоритм не знает, что он работает над списком и, следовательно, делает то, что он делает для любого контейнера: изменить порядок элементов, изменив их значения. Если, например, алгоритм удаляет первый элемент, все последующие элементы назначаются их предыдущим элементам. это поведение противоречит главному преимуществу списков: возможность вставлять, перемещать и удалять элементы изменение ссылок вместо значений. Чтобы избежать плохой работы, списки предоставляют специальные функции-члены для всех алгоритмов манипулирования. Вы должны всегда предпочитать их. Кроме того, эти функции-члены действительно удаляют «удаленные» элементы, как показано в следующем примере: 

#include <list>
#include <algorithm>
using namespace std;
int main()
{
list<int> coll;
// insert elements from 6 to 1 and 1 to 6
for (int i=1; i<=6; ++i) {
coll.push_front(i);
coll.push_back(i);
}
// remove all elements with value 3 (poor performance)
coll.erase (remove(coll.begin(),coll.end(),
3),
coll.end());
// remove all elements with value 4 (good performance)
coll.remove (4);
}

Конечно, это кажется достаточно убедительным для дальнейших рассуждений, но в любом случае я решил увидеть результат запуска аналогичного кода на моем ПК, особенно в среде MSVC 2013. Вот мой импровизированный код: 

int main()
{
    srand(time(nullptr));
    list<int>my_list1;
    list<int>my_list2;
    int x = 2000 * 2000;

    for (auto i = 0; i < x; ++i)
    {
        auto random = rand() % 10;
        my_list1.push_back(random);
        my_list1.push_front(random);
    }

    list<int>my_list2(my_list1);

    auto started1 = std::chrono::high_resolution_clock::now();
    my_list1.remove(5);
    auto done1 = std::chrono::high_resolution_clock::now();
    cout << "Execution time while using member function remove: " << chrono::duration_cast<chrono::milliseconds>(done1 - started1).count();

    cout << endl << endl;

    auto started2 = std::chrono::high_resolution_clock::now();
    my_list2.erase(remove(my_list2.begin(), my_list2.end(),5), my_list2.end());
    auto done2 = std::chrono::high_resolution_clock::now();
    cout << "Execution time while using generic algorithm remove: " << chrono::duration_cast<chrono::milliseconds>(done2 - started2).count();

    cout << endl << endl;
}

Я был удивлен, когда увидел следующий вывод: 

Execution time while using member function remove: 10773

Execution time while using generic algorithm remove: 7459

Не могли бы вы объяснить, в чем причина такого противоречивого поведения?

1 Ответ

0 голосов
/ 31 октября 2018

Это проблема с кешированием. Большинство проблем с производительностью - это проблемы с кэшированием. Мы всегда хотим думать, что алгоритм - это первое, на что стоит обратить внимание. Однако если вы намеренно заставите компилятор использовать память из разных мест за один прогон, а память - из следующего местоположения при следующем прогоне, вы увидите проблему с кэшированием.

Комментируя push_back или push_front при построении исходного списка, я заставил компилятор создать код для построения списка с непрерывными элементами памяти в my_list1.

my_list2 всегда находится в непрерывной памяти, потому что он размещен в одной копии.

Выполнить вывод: 

Execution time while using member function remove: 121

Execution time while using generic algorithm remove: 125


Process finished with exit code 0

Вот мой код с одним из закомментированных толчков. 

#include <list>
#include <algorithm>
#include <chrono>
#include <iostream>

using namespace std;

int main()
{
    srand(time(nullptr));
    list<int>my_list1;
//    list<int>my_list2;
    int x = 2000 * 2000;

    for (auto i = 0; i < x; ++i)
    {
        auto random = rand() % 10;
//        my_list1.push_back(random);  // avoid pushing to front and back to avoid cache misses.
        my_list1.push_front(random);
    }

    list<int>my_list2(my_list1);

    auto started1 = std::chrono::high_resolution_clock::now();
    my_list1.remove(5);
    auto done1 = std::chrono::high_resolution_clock::now();
    cout << "Execution time while using member function remove: " << chrono::duration_cast<chrono::milliseconds>(done1 - started1).count();

    cout << endl << endl;

    auto started2 = std::chrono::high_resolution_clock::now();
    my_list2.erase(remove(my_list2.begin(), my_list2.end(),5), my_list2.end());
    auto done2 = std::chrono::high_resolution_clock::now();
    cout << "Execution time while using generic algorithm erase: " << chrono::duration_cast<chrono::milliseconds>(done2 - started2).count();

    cout << endl << endl;
}

Увеличивая количество элементов и меняя порядок вызовов, чтобы сначала было выполнено удаление, а затем - удаление, удаление занимает больше времени. Опять же, это больше о кешировании, чем об алгоритме или объеме выполняемой работы. Если вы запускаете другую программу, которая загрязняет кэш, проверяет Интернет или перемещает мышь, ваш кэш L1 объемом 32 КБ будет загрязнен, и производительность для этого запуска снизится.

...