2

我发现 std::sort 仅对 1000 个项目进行排序非常慢。

在类模板template <typename T> class TableModel : public QAbstractTableModel中，我具有以下对表格进行排序的功能。

template<typename T>
void TableModel<T>::sort(int column, Qt::SortOrder order = Qt::AscendingOrder) {
    if(order == Qt::AscendingOrder) {
        qSort(m_list.begin(), m_list.end(), less<T>(column));
    } else {
        qSort(m_list.begin(), m_list.end(), greater<T>(column));
    }
    reset();
 }

我注意到如果我只有随机洗牌，我的桌子就是洗牌然后立即显示。所以这让我认为它的排序很慢。谁能帮我加快 QTable 的排序？

这是较少的结构。

template<typename T>
struct less {
    int index;
    less(int index) : index(index) {}
    bool operator()(const T& first, const T& second) {
        return T::less(first, second, index);
    }
};

T::less 是一个函数，它所做的只是根据给定的索引进行比较。

当我稍后需要处理大约 100,000 个项目时，慢被定义为仅 1000 个项目的 5 秒。

4

2 回答 2

2

我怀疑这m_list是按价值存储物品并且交换它们很昂贵。您可以尝试实现更快的交换或通过智能指针将它们存储在容器中。

当然，分析器可以帮助您更准确地查明问题。

于 2012-04-05T17:44:49.200 回答
1

由于 m_list 是一个 QList，它没有与普通列表相同的接口或性能特征。例如，显然 QList 在内部存储了一个 T* 数组。如果排序算法知道这个实现细节，这个表示可以在没有任何复制的情况下被排序。相比之下，std::sort 可能是对周围的值进行深度复制，或者可能是移动它们，这比在 QList 数组中排序指针要多。

最好将 Qt 容器与 Qt 算法一起使用，因为 Qt 算法更有可能专门用于 Qt 容器。或者您可以避免使用 Qt 容器而只使用标准库。

无论如何，尝试使用 Qt 的qSort算法：

template<typename T>
void TableModel<T>::sort(int column, Qt::SortOrder order = Qt::AscendingOrder) {
    if(order == Qt::AscendingOrder) {
        qSort(m_list.begin(), m_list.end(), less<T>(column));
    } else {
        qSort(m_list.begin(), m_list.end(), greater<T>(column));
    }
    reset();
}

原始答案

std::sort 不能利用列表中的节点可以在不复制元素的情况下移动的事实。假设您使用 std::list 或类似的东西，请使用 sort 成员函数。

template<typename T>
void TableModel<T>::sort(int column, Qt::SortOrder order = Qt::AscendingOrder) {
    std::random_shuffle(m_list.begin(), m_list.end());
    if(order == Qt::AscendingOrder) {
       m_list.sort(less<T>(column));
    } else {
       m_list.sort(greater<T>(column));
    }
    reset();
}

如果您不能这样做，那么您可以通过确保您的元素在使用 C++11 时启用移动来优化所有这些副本。

于 2012-04-05T17:55:14.507 回答