如何改进仅垂直的 Masonry 网格算法？

Question

我刚刚为仅垂直 Masonry 网格制作了简单的核心算法，该算法采用项目数据数组并创建所需数量的列，其中项目被排序以“使用”尽可能多的可用 space 尽可能。我不确定如何以最详细的方式解释它，但一般来说，在每一列中，嵌套项的高度总和应尽可能等于其他项。

这是一个例子：

所有未排序项的源数组

// represents an array of data that will be a base to render UI elements
const items = [{
        "id": 0,
        "height": 100
    },
    {
        "id": 1,
        "height": 200
    },
    {
        "id": 2,
        "height": 250
    },
    {
        "id": 3,
        "height": 110
    },
    {
        "id": 4,
        "height": 50
    },
    {
        "id": 5,
        "height": 160
    },
    {
        "id": 6,
        "height": 70
    },
    {
        "id": 7,
        "height": 90
    }
]

因此，我需要接收 3 列，但此值是动态的，因此 3 只是一个示例。这些列应包含按高度排序的项目以使用最可用的 space 像这样：

[
    [
        {
            "id": 0,
            "height": 100
        },
        {
            "id": 3,
            "height": 110
        },
        {
            "id": 5,
            "height": 160
        }
    ],
    [
        {
            "id": 1,
            "height": 200
        },
        {
            "id": 4,
            "height": 50
        },
        {
            "id": 7,
            "height": 90
        }
    ],
    [
        {
            "id": 2,
            "height": 250
        },
        {
            "id": 6,
            "height": 70
        }
    ]
]

如您所见，列的总和“尽可能相同”：
1 列 = 370
2 列 = 340
3 列 = 320

我实现了一个解决方案，但我想知道是否有更好的方法来解决这个问题：这是 link 到 JSFiddle 及其完整源代码下方：

如有任何idea/example改进方法，我将不胜感激

// need to create 3 arrays sorted by height. Each array should contain ~equal height as much as possible
const requiredArrays = 3;

// represents an array of data that will be a base to render UI elements
const items = [{
        "id": 0,
        "height": 100
    },
    {
        "id": 1,
        "height": 200
    },
    {
        "id": 2,
        "height": 250
    },
    {
        "id": 3,
        "height": 110
    },
    {
        "id": 4,
        "height": 50
    },
    {
        "id": 5,
        "height": 160
    },
    {
        "id": 6,
        "height": 70
    },
    {
        "id": 7,
        "height": 90
    }
]




const cols = Array.from({
    length: requiredArrays
}, () => []);


// it sorts the columns by most "empty" or "most smallest sum height" and pushes the items into it to use as much available space as possible
function sorter(item) {
    let lowest = Number.POSITIVE_INFINITY;
    let highest = Number.NEGATIVE_INFINITY;
    let tmp;
    // the column where sum of its items is the lowest
    let mostEmptyCol;

    const colsDataWithTotalH = [];

    cols.forEach(col => {
        const totalH = col.reduce((acc, o) => acc + o.height, 0);
        // calculates the items sum of the single columns
        colsDataWithTotalH.push({
            col: col,
            totalH: totalH
        })
    })

    // looking for the most "empty" column by height
    for (var i = colsDataWithTotalH.length - 1; i >= 0; i--) {
        const currentCoItem = colsDataWithTotalH[i];
        tmp = currentCoItem.totalH;
        if (tmp < lowest) {
            lowest = tmp;
            // lets assign the Col array into this var to use it in future
            mostEmptyCol = currentCoItem.col;
        };
        if (tmp > highest) highest = tmp;
    }

    // fill the most empty column
    mostEmptyCol.push(item)
}


items.forEach(item => {

    const col = cols.find(o => {
        return !o.length;
    });

    // at the start columns are empty so we should just push items into them
    if (col) {
        col.push(item);
    } else {
        // the columns contain the items so we need to run the sorter algorhytm
        sorter(item);
    }

});

console.log('Result', cols);

Answer 1

这是一种方法：

const sumHeights = (ns) =>
  ns.reduce ((a, {height}) => a + height, 0)

const _equalGroups = ([x, ... xs], [g, ... gs]) =>
  x == undefined
    ? [g, ... gs]
  : _equalGroups (
      xs, 
      [[... g, x], ... gs] .sort ((as, bs) => sumHeights (as) - sumHeights (bs))
    )

const equalGroups = (n, xs) => 
  _equalGroups (xs .sort ((a, b) => b.height - a.height), [...Array(n)] .map (_ => []))

const items = [{id: 0, height: 100}, {id: 1, height: 200}, {id: 2, height: 250}, {id: 3, height: 110}, {id: 4, height: 50}, {id: 5, height: 160}, {id: 6, height: 70}, {id: 7, height: 90}]

console .log (equalGroups (3, items))

.as-console-wrapper {max-height: 100% !important; top: 0}

这不是一个优化解决方案，只是一个粗略的匹配。我猜任何优化解决方案也可以解决许多版本的背包问题，所以我不会去那里！

这个想法很简单。我们有一个辅助函数来对数组元素的高度求和，我们有 public 函数 equalGroups，它接受组数和项目数组，然后简单地调用我们的主要递归函数 _equalGroups，向其传递一个按高度降序排列的项目数组和适当数量的空数组。

当我们没有更多的项目要插入时，主函数停止。在所有其他时间，它将下一个数字存储在第一组中，然后在剩余数字和更新的组集合上重复出现，按大小排序。

如何改进仅垂直的 Masonry 网格算法？

How to improve the vertical-only Masonry grid algorithm?

javascript

algorithm

masonry