БЛОГ НА HUSL


Замер времени работы различных сортировок в оконном приложении Qt

Автор вопроса: nyekitka

я только недавно начал использовать Qt Creator, поэтому я новичок. Но со старта решил замахнутсья на реализацию приложения, в котором есть возможность замерить время работы различных сортировок. Проводится 10 тестов с массивами различной длины и результаты записываются в таблицу. Как только я нажимаю кнопку Старт, то программа зависает и ничего не происходит. Но если уменьшить размеры массивов, которые используются в замерах, то программа просто сразу же вылетает. Помогите пожалуйста разобраться что я делаю не так:

Хэдер

#ifndef TIMETESTING_H
#define TIMETESTING_H

#include <QDialog>
#include <QtWidgets>
#include <QTableWidget>
#include "sorts.h"
class TimeTesting : public QDialog
{
    Q_OBJECT
public:
    explicit TimeTesting(QWidget *parent = nullptr);
private slots:
    void start_test();
    void stop_test();
private:
    QTableWidget* table;
    QPushButton* start;
    QPushButton* stop;
    bool isProcessing;
};

#endif // TIMETESTING_H

cpp-файл

#include "timetesting.h"

TimeTesting::TimeTesting(QWidget *parent): QDialog{parent}
{
    isProcessing = false;
    start = new QPushButton("Старт");
    stop = new QPushButton("Стоп");
    table = new QTableWidget;
    table->setColumnCount(10);
    table->setRowCount(13);
    table->setHorizontalHeaderLabels(QStringList() << 
        "1000 элементов" <<
        "2000 элементов" <<
        "3000 элементов" << 
        "4000 элементов" <<
        "5000 элементов" <<
        "6000 элементов" <<
        "7000 элементов" <<
        "8000 элементов" <<
        "9000 элементов" <<
        "10000 элементов"
    );
    table->setVerticalHeaderLabels(QStringList() <<
        "Сортировка пузырьком" <<
        "Шейкерная сортировка" <<
        "Метод простых вставок" <<
        "Сортировка выбором" <<
        "Сортировка подсчётом" <<
        "Сортировка двоичными вставками" <<
        "Двухсторонняя сортировка выбором" <<
        "Сортировка деревом" <<
        "Сортировка слиянием" <<
        "Пирамидальная сортировка" <<
        "Быстрая сортировка" <<
        "Битонная сортировка" <<
        "Сортировка Шелла"
    );
    table->setEditTriggers(QAbstractItemView::NoEditTriggers);

    connect(start, SIGNAL(clicked()), this, SLOT(start_test()));
    connect(stop, SIGNAL(clicked()), this, SLOT(stop_test()));

    QVBoxLayout *layout = new QVBoxLayout;
    layout->addWidget(table);
    layout->addWidget(start);
    layout->addWidget(stop);
    setLayout(layout);
    setWindowTitle("Тестирование на время");
}
void TimeTesting::start_test() {
    start->setDisabled(true);
    start->setText("В процессе...");
    isProcessing = true;
    void (*list_of_sortings[])(Sequence<int>*, int (*)(int, int))  = {
        bubble_sort<int>,
        shaker_sort<int>,
        insertion_sort<int>,
        selection_sort<int>,
        counting_sort<int>,
        bin_insertion_sort<int>,
        double_selection_sort<int>,
        tree_sort<int>,
        merge_sort<int>,
        heap_sort<int>,
        quick_sort<int>,
        bitonic_sort<int>
    };
    ArraySequence<int> arrays[10];
    for (size_t i = 0; i < 10; ++i) {
        for (size_t j = 0; j < (i + 1)*1000; ++j) {
            arrays[i].append(rand());
        }
    }
    for (size_t i = 0; i < 12; ++i) {
        for (size_t j = 0; j < 10; ++j) {
            if (!isProcessing) {
                start->setEnabled(true);
                start->setText("Старт");
                return;
            }
            clock_t start_time = clock();
            list_of_sortings[i](&arrays[j], [](int a, int b) {return a - b;});
            size_t time = clock() - start_time;
            QTableWidgetItem* item = new QTableWidgetItem(tr("%1 мс").arg(time));
            table->setItem(i, j, item);
            if (!isProcessing) {
                start->setEnabled(true);
                stop->setEnabled(true);
                start->setText("Старт");
                return;
            }
            for (size_t k = 0; k < (j + 1)*1000; ++k) {
                arrays[j][k] = rand();
            }
        }
    }
    start->setEnabled(true);
    start->setText("Старт");
}
void TimeTesting::stop_test() {
    isProcessing = false;
    stop->setDisabled(true);
}

Заголовки по типу rand или ctime уже подключены в sorts.h, все сортировки работают корректно (проверял с помощью unit-тестов), коллекции тоже. Если найдёте ещё какие-нибудь косяки, не связанные с проблемой, то можете и на них ткнуть, чтобы я в дальнейшем их не допускал)

Update

Ошибка была в неправильном for'е:

for (size_t i = 0; i < 13; ++i) {

Вместо 13, должно было быть 12. Но есть и другие проблемы:

  1. Программа всё равно вылетает в режиме Run, но работает в режиме Debug
  2. Я изначально хотел последовательный вывод, т.е. отработала одна сортировка на одном массиве - вывела результат, идёт дальше. Однако программа выводит результаты все сразу только когда все сортировки отработают. Как реализовать задуманное?
  3. Ошибка из пункта 1) возникла из-за того, что я исключил ShellSort, т.к. это единственная сортировка, у которой есть дополнительный аргумент по умолчанию - последовательность сортировки (последовательности степеней двойки, последовательность Седжвика, Пратта, Фибоначчи и т.д.). Все эти последовательности были объявлены в sorts.h как глобальные переменные (плохой стиль, знаю). И из-за них возникало переопределение:
:-1: error: CMakeFiles/sorts.dir/main.cpp.obj:D:/Nick/Prog projects/Qt/sorts/sorts.h:17: multiple definition of `DefaultSequence'; CMakeFiles/sorts.dir/sorts_autogen/mocs_compilation.cpp.obj:D:/Nick/Prog projects/Qt/sorts/sorts.h:17: first defined here

Хотя #ifndef SORTS_H там прописано


Источник

Ответы (1 шт):

Автор решения: Alexander Chernin

Можно сделать проще и надежнее при помощи std::function (C++11), а для того, чтобы получать замеры в процессе; надо все сортировки поместить в поток (например, QThread).

Функция сортировки имеет вид (вместо T* поставьте свой Sequence<T>*):

template<typename T>
void mysort(T* array, const std::function<T(T, T)>& fun) {
    Q_UNUSED(array)
    Q_UNUSED(fun)

    // Для примера использую здоровый сон в 2 секунды
    QThread::sleep(2);
}

Чтобы жизнь стала немного слаще, заведем синоним для типа функций сортировки целых:

typedef  std::function< void(int*, const std::function<int(int, int)>&) > SortFunc;

Здесь int* надо заменить на Sequence<int>*

А теперь сам поток в котором будут производиться все вызовы и расчеты:

class SortThread: public QThread {
    Q_OBJECT
public:
    SortThread(QObject *parent = nullptr);
signals:
    // Сигнал завершения сортировки
    // title - название сортировки
    // time - время
    void sortComplete(const QString& title, size_t time);

    // или, в если у нас еще разные длины массивов сортировки
    // void sortComplete(const QString& title, int len, size_t time);
public:
    void run() override {
        QList<SortFuncDescription> sortsList = {
            {"Сортировка 1", mysort<int>},
            {"Сортировка 2", mysort<int>},
            {"Сортировка 3", mysort<int>},
        };

        QListIterator<SortFuncDescription> i(sortsList);
        while(i.hasNext()) {
            SortFuncDescription sortFuns = i.next();

            clock_t t0 = clock();
            // Вызываем сортировку. Вместо nullptr - подставьте массив значений 
            sortFuns.func(nullptr, [](int a, int b) {return a - b;});
            size_t t = clock() - t0;

            // Отсортировали 
            emit sortComplete(sortFuns.title, t);
        }
    }
};

Здесь SortFuncDescription это структура такого вида:

struct SortFuncDescription {
    QString title; // Название сортировки
    SortFunc func; // функция сортировки
}

Для массивов различных длин можно, например сделать так:

while(i.hasNext()) {
    SortFuncDescription sortFuns = i.next();
    for(int k = 0; k < 10; k++) {
        clock_t t0 = clock();
        // Вызываем сортировку. 
        // Вместо nullptr - подставьте массив значений соответствующей длины
        sortFuns.func(nullptr, [](int a, int b) {return a - b;});
        size_t t = clock() - t0;

        // Отсортировали 
        emit sortComplete(sortFuns.title, k*1000, t);
    }
}

Теперь запуск и вывод результата:

TimeTesting::TimeTesting(QWidget *parent) :
    QDialog(parent),
    ui(new Ui::TimeTesting)
{
    ui->setupUi(this);

    // Поток сортировок
    SortThread* thread = new SortThread();

    // Сигнал "Начать" 
    connect(ui->pushButtonStart, &QPushButton::clicked, [&, thread]() {
        // Очищаем таблицу
        ui->tableWidget->setRowCount(0);
        // Запускаем поток сортировок
        thread->start();
    });

    // Очередная сортировка завершена
    connect(thread, &SortThread::sortComplete, [&](const QString& title, size_t time)    {
        // Получаем результат и выводим в таблицу, в конец
        ui->tableWidget->insertRow(ui->tableWidget->rowCount());
        ui->tableWidget->setItem(...);
    });

    // Или для массивов разной длины
    connect(thread, &SortThread::sortComplete, 
            [&](const QString& title, int len, size_t time) {
        // По вертикальным заголовкам находим нужную сортировку
        // Добавляем новое значение в колонку, с соответствующим количеством элементов
    });

    // Поток отработал - очищаем память (помечаем на удаление)
    connect(thread, &QThread::finished, [&, thread]() {
        thread->deleteLater();
    });
}
→ Ссылка

licensed under cc by-sa 3.0 with attribution.