ListModel.move()非常慢

Question

我有一个TableView，它有一个动态填充的ListModel，我需要在“QML端”进行排序，最好不要替换列表中的任何元素，因为有相当多的逻辑附加到几个表信号(包括一些自定义的)。

我遇到的问题是，当表超过~1k元素时，元素的移动只需花费不合理的很长时间(参见下面的代码)。将排序放在WorkerScript中无助于改善UX，因为用户倾向于一次又一次地单击，如果没有任何事情发生~0.5s。因此，我想知道的是，是否有人知道如何提高ListModel.move()的性能，暂时抑制信号，或者有其他解决方案？

诚挚的问候

拉格纳

示例代码：

import QtQuick 2.7
import QtQuick.Layouts 1.3
import QtQuick.Controls 1.4

ColumnLayout {
    width: 400

    TableView {
        id: table
        Layout.fillHeight: true
        Layout.fillWidth: true
        model: ListModel { dynamicRoles: false }
        onSortIndicatorColumnChanged: sort();
        onSortIndicatorOrderChanged: sort();

        TableViewColumn {
            role: "num"
            title: "Numeric column"
            width: table.contentItem.width / 3
        }
        TableViewColumn {
            role: "str"
            title: "Text column"
            width: table.contentItem.width * 2/3
        }

        // functionality
        function sort() {
            if(model.count < 2) {
                console.log("No need to sort.");
                return true;
            }
            var r = getColumn(sortIndicatorColumn).role;
            var type = typeof(model.get(0)[r]);
            if(type != "string" && type != "number") {
                console.log("Unable to sort on selected column.");
                return false;
            }
            switch(sortMethod.currentIndex) {
                case 0: var sortFunc = _sortMoveWhileNoCache; break;
                case 1: sortFunc = _sortMoveWhile; break;
                case 2: sortFunc = _sortMoveAfter; break;
                case 3: sortFunc = _sortSetAfter; break;
                case 4: sortFunc = _sortAppendRemoveAfter; break;
                default:
                    console.log("Unknown sort method.");
                    return false;
            }
            console.time(sortFunc.name);
            sortFunc(r);
            console.timeEnd(sortFunc.name);
            return true;
        }

        // invokers
        function _sortMoveWhileNoCache(r) {
            console.time("sortMove");
            _qsortMoveNoCache(r, 0, model.count-1);
            console.timeEnd("sortMove");
        }
        function _sortMoveWhile(r) {
            console.time("setUp");
            var arr = [];
            for(var i = model.count-1; i > -1; i--) arr[i] = model.get(i)[r];
            console.timeEnd("setUp");
            console.time("sortMove");
            _qsortMove(arr, 0, arr.length-1);
            console.timeEnd("sortMove");
        }
        function _sortMoveAfter(r) {
            console.time("setUp");
            var arr = [];
            arr[0] = { "val": model.get(0)[r], "oldIdx": 0, "oldPrev": null };
            for(var i = 1; i < model.count; i++) {
                arr[i] = { "val": model.get(i)[r],
                           "oldIdx": i,
                           "oldPrev": arr[i-1] };
            }
            console.timeEnd("setUp");
            console.time("sort");
            _qsortVal(arr, 0, arr.length-1);
            console.timeEnd("sort");
            console.time("move");
            for(i = 0; i < arr.length; i++) {
                if(arr[i].oldIdx !== i) {
                    model.move(arr[i].oldIdx, i, 1);
                    for(var prev = arr[i].oldPrev;
                        prev !== null && prev.oldIdx >= i;
                        prev = prev.oldPrev)
                        prev.oldIdx++;
                }
            }
            console.timeEnd("move");
        }
        function _sortSetAfter(r) {
            console.time("setUp");
            var arr = [], tmp = [];
            for(var i = model.count-1; i > -1; i--) {
                var lmnt = model.get(i);
                // shallow clone
                tmp[i] = Object.create(lmnt);
                for(var p in lmnt) tmp[i][p] = lmnt[p];
                arr[i] = { "val": tmp[i][r], "oldIdx": i };
            }
            console.timeEnd("setUp");
            console.time("sort");
            _qsortVal(arr, 0, arr.length-1);
            console.timeEnd("sort");
            console.time("set");
            // set()ing invalidates get()ed objects, hence the cloning above
            for(i = 0; i < arr.length; i++) model.set(i, tmp[arr[i].oldIdx]);
            console.timeEnd("set");
            delete(tmp);
        }
        function _sortAppendRemoveAfter(r) {
            console.time("setUp");
            var arr = [], tmp = [];
            for(var i = model.count-1; i > -1; i--) {
                tmp[i] = model.get(i);
                arr[i] = { "val": tmp[i][r], "oldIdx": i };
            }
            console.timeEnd("setUp");
            console.time("sort");
            _qsortVal(arr, 0, arr.length-1);
            console.timeEnd("sort");
            console.time("appendRemove");
            // append()ing does not, on win10 x64 mingw, invalidate
            for(i = 0; i < arr.length; i++) model.append(tmp[arr[i].oldIdx]);
            model.remove(0, arr.length);
            console.timeEnd("appendRemove");
        }

        // sorting functions
        function _qsortMoveNoCache(r, s, e) {
            var i = s, j = e, piv = model.get(Math.floor((s+e)/2))[r];
            while(i < j) {
                if(sortIndicatorOrder == Qt.AscendingOrder) {
                    for(; model.get(i)[r] < piv; i++){}
                    for(; model.get(j)[r] > piv; j--){}
                } else {
                    for(; model.get(i)[r] > piv; i++){}
                    for(; model.get(j)[r] < piv; j--){}
                }
                if(i <= j) {
                    if(i !== j) {
                        model.move(i, j, 1);
                        model.move(j-1, i, 1);
                    }
                    i++;
                    j--;
                }
            }
            if(s < j) _qsortMoveNoCache(r, s, j);
            if(i < e) _qsortMoveNoCache(r, i, e);
        }
        function _qsortMove(arr, s, e) {
            var i = s, j = e, piv = arr[Math.floor((s+e)/2)];
            while(i < j) {
                if(sortIndicatorOrder == Qt.AscendingOrder) {
                    for(; arr[i] < piv; i++){}
                    for(; arr[j] > piv; j--){}
                } else {
                    for(; arr[i] > piv; i++){}
                    for(; arr[j] < piv; j--){}
                }
                if(i <= j) {
                    if(i !== j) {
                        model.move(i, j, 1);
                        model.move(j-1, i, 1);
                        var tmp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = tmp;
                    }
                    i++;
                    j--;
                }
            }
            if(s < j) _qsortMove(arr, s, j);
            if(i < e) _qsortMove(arr, i, e);
        }
        function _qsortVal(arr, s, e) {
            var i = s, j = e, piv = arr[Math.floor((s+e)/2)].val;
            while(i < j) {
                if(sortIndicatorOrder == Qt.AscendingOrder) {
                    for(; arr[i].val < piv; i++){}
                    for(; arr[j].val > piv; j--){}
                } else {
                    for(; arr[i].val > piv; i++){}
                    for(; arr[j].val < piv; j--){}
                }
                if(i <= j) {
                    if(i !== j) {
                        var tmp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = tmp;
                    }
                    i++;
                    j--;
                }
            }
            if(s < j) _qsortVal(arr, s, j);
            if(i < e) _qsortVal(arr, i, e);
        }
    }

    RowLayout {
        Button {
            Layout.fillWidth: true
            text: "Add 1000 elements (" + table.model.count + ")"
            onClicked: {
                var chars = " abcdefghijklmnopqrstuvxyzABCDEFGHIJKLMNOPQRSTUVXYZ";
                for(var i = 0; i < 1000; i++) {
                    var str = "";
                    for(var j = 0; j < Math.floor(Math.random()*20)+1; j++)
                        str += chars[Math.floor(Math.random()*chars.length)];
                    table.model.append({ "num": Math.round(Math.random()*65536),
                                         "str": str });
                }
            }
        }
        Button {
            text: "Clear list model"
            onClicked: table.model.clear();
        }
        ComboBox {
            id: sortMethod
            Layout.fillWidth: true
            editable: false
            model: ListModel {
                ListElement { text: "Move while sorting, no cache" }
                ListElement { text: "Move while sorting" }
                ListElement { text: "Move after sorting" }
                ListElement { text: "Set after sorting" }
                ListElement { text: "Append and remove after sorting" }
            }
        }
    }
}

当使用Qt- with 10-x64-mingw，5k元素运行上述操作时，在每种排序方法之间清除列表时，我得到以下结果(_sortSetAfter ~20倍于_sortMoveWhileNoCache)

// num
sortMove: 3224ms
_sortMoveWhileNoCache: 3224ms
// str
sortMove: 3392ms
_sortMoveWhileNoCache: 3392ms

// num
setUp: 20ms
sortMove: 4684ms
_sortMoveWhile: 4704ms
// str
setUp: 16ms
sortMove: 3421ms
_sortMoveWhile: 3437ms

// num
setUp: 18ms
sort: 15ms
move: 4985ms
_sortMoveAfter: 5018ms
// str
setUp: 8ms
sort: 20ms
move: 5200ms
_sortMoveAfter: 5228ms

// num
setUp: 116ms
sort: 21ms
set: 27ms
_sortSetAfter: 164ms
// str
setUp: 63ms
sort: 26ms
set: 25ms
_sortSetAfter: 114ms

// num
setUp: 20ms
sort: 19ms
appendRemove: 288ms
_sortAppendRemoveAfter: 328ms
// str
setUp: 22ms
sort: 26ms
appendRemove: 320ms
_sortAppendRemoveAfter: 368ms

Answer 1

虽然我同意Kevin Krammer和xander的观点，但您有多种方法来处理绑定。

您可以将它们与signal.connect(slotToConnect)绑定并直接与signal.disconnect(slotToDisconnect)断开连接，或者使用Connections与enabled-value一起更改排序的启动和完成。

此外，当您的一些操作花费的时间超过几ms时，您应该考虑显示一些BusyIndicator。

但我得承认，我看不出有什么理由在JS上这么做

Answer 2

实际上，有一个高性能的类型并不是那么重要。任何算法，不管它有多好，如果执行超过50 is，用户都会注意到主QML引擎线程中的阻塞，这会让用户感到应用程序有时没有响应。实际上，实际需要的是在达到50 is阈值后调用Qt.callLater来处理QML的排序算法，以便UI/UX能够保持响应性。为此，我们可以实现一个简单的二进制插入增量合并排序，将未排序的记录移动到它们的排序位置。由于这个50 of的阈值，它允许用户中断并更改排序条件。

简单的解决方案可能如下所示：

• 它有sortByDOB -用于对规范化的日期进行排序，就像使用ms epoch一样。
• 作为比较，我提供了sortByName
• 主循环有Date.now() < ts + 50设置一个50 has的阈值。
• 它对count属性绑定更改具有增量排序和QML友好特性，因此，外部代码可以附加到此ListModel并触发更多排序
• 在sortCompare属性上有一个属性绑定，因此如果条件被更改，它将重置增量排序
• ListModel中填充了示例数据，这说明了建议的日期存储，即将数据规范化为ms epoch。
• 当未排序的项被排序时，我们更新sortCount。
• 我们有一个bool sorted属性，它指示当sortCount >= count完成排序时
• 我们有另一个bool sorting属性，它指示排序在sorted === false时正在进行。

ListView {
    width: 200
    height: 200
    model: sortListModel
    delegate: Text { text: name }
}
ListModel {
    id: sortListModel
    property int sortCount: 0
    property var sortCompare: sortByDOB
    property var sortByName: (a, b) => a.name.localeCompare(b.name)
    property var sortByDOB: (a, b) => a.dob - b.dob
    readonly property bool sorted: sortCount >= count
    readonly property bool sorting: !sorted
    onSortCompareChanged: Qt.callLater(resort)
    onCountChanged: {
        if (count === 0) { sortCount = 0; return; }
        Qt.callLater(sortStep);
    }
    function resort() {
        sortCount = 0;
        Qt.callLater(sortStep);
    }
    function sortStep() {
        for (let ts = Date.now(); sortCount < count && Date.now() < ts + 50; ) sortItem(sortCount++);
        if (sortCount < count) Qt.callLater(sortStep);
    }
    function findInsertIndex(item, head, tail) {
        if (head >= count)  return head;
        let cmp = sortCompare(item, get(head));
        if (cmp <= 0) return head;
        cmp = sortCompare(item, get(tail));
        if (cmp === 0) return tail;
        if (cmp > 0) return tail + 1;
        while (head + 1 < tail) {
            let mid = (head + tail) >> 1;
            cmp = sortCompare(item, get(mid));
            if (cmp === 0) return mid;
            if (cmp > 0) head = mid; else tail = mid;
        }
        return tail;
    }
    function sortItem(index) {
       if (index === 0) return;
       let newIndex = findInsertIndex(get(index), 0, index - 1);
       if (newIndex === index) return;
       move(index, newIndex, 1);
    }
    Component.onCompleted: {
        append( { "name": "fred", dob: (new Date("1980-01-01")).getTime() } );
        append( { "name": "wilma", dob: (new Date("1985-01-01")).getTime() } );
        append( { "name": "barney", dob: (new Date("1981-01-01")).getTime() } );
        append( { "name": "betty", dob: (new Date("1983-01-01")).getTime() } );
    }
}

在此，我将更全面地执行上述解决方案：

• https://github.com/stephenquan/qt5-qml-sortlistmodel