Javascript:如何最有效地将数组连接到少于 64 个字符的 block 中？

Question

我有一长串这样的名字:

namelist = [ "Andrew Alexander Brown", "Charlie Christopher Drake", "Edward Elsevier Furlong", "Gareth Gates Harper", "Indiana Chewbacca Jones", "Kevin M Lamarr", "Michael Randy Newman", "Oliver Terry Pratchett", "Queen Liz Regina", "Stuart Townsend", "Umar Vespa", "Woodford X Xanadu", "Yanick Zebra" ];

我想将列表中的名称提取为字符串，每个名称由竖线字符 (|) 分隔。每个新字符串应小于 48 个字符，例如输出应如下所示(但小于或等于 48 个字符):

Andrew Alexander Brown|Charlie Christopher Drake|Edward Elsevier Furlong
Gareth Gates Harper|Indiana Chewbacca Jones|Kevin M Lamarr
Michael Randy Newman|Oliver Terry Pratchett|Queen Liz Regina
Stuart Townsend|Umar Vespa|Woodford X Xanadu|Yanick Zebra

我希望新字符串的数量尽可能少，可能不需要维护数组中字符串的顺序 - 但我不知道如何在 javascript 中执行此操作。

我知道我可以做一些事情，比如遍历名单并将下一个名字添加到一个临时字符串中。检查这个临时字符串的长度，如果超过 48 个字符就输出。继续循环直到我们用完名称，但这似乎不是很有效。例如，如果一个短名称后跟一个非常长的名称，那么字符(可以由临时字符串中的另一个较小的名称填充)将被浪费。

关于如何最好地实现这一目标的任何指示？

Answer 1

这就是所谓的 The Bin Packing Problem

解决方案将取决于您对高效 的定义，更高效的装箱往往需要更长的计算时间。但效率较低的装箱往往会占用更少的计算资源(就计算资源而言，可以认为效率更高)。

这是我使用 ECMA5 规范的解决方案，它牺牲了计算资源以支持更高效的装箱。

我选择将 powerSet 函数保留为通用函数，这意味着它可以重复用于其他目的。正如@Bergi 强调的那样，如果您创建了一个自定义函数，该函数包含来自 joinStringsMaxCharacters

的第一个 filter，那么您可能会在计算资源方面获得更高的效率

Javascript

一般 Power Set功能

function powerSet(array) {
    var lastElement,
        sets;

    if (!array.length) {
        sets = [[]];
    } else {
        lastElement = array.pop();
        sets = powerSet(array).reduce(function (previous, element) {
            previous.push(element);
            element = element.slice();
            element.push(lastElement);
            previous.push(element);

            return previous;
        }, []);
    }

    return sets;
}

辅助函数

function isString(element) {
    return typeof element === 'string';
}

function isNotUsed(element) {
    return this.every(function (u) {
        return u.indexOf(element) === -1;
    });
}

function sumLength(s, el) {
    return s + el.length;
}

带连接字符串的包装箱

function joinStringsMaxCharacters(arrayOfStrings, numberOfCharacters, separator) {
    if (!Array.isArray(arrayOfStrings) || !arrayOfStrings.every(isString)) {
        throw new TypeError('arrayOfStrings is not an array of strings!');
    }

    numberOfCharacters = numberOfCharacters >>> 0;
    if (!separator || !isString(separator)) {
        separator = '|';
    }

    var arrayLength = arrayOfStrings.length;

    return powerSet(arrayOfStrings).filter(function (set) {
        return set.length && (set.length === 1 || set.reduce(sumLength, set.length - 1) <= numberOfCharacters);
    }).sort(function (a, b) {
        return b.reduce(sumLength, b.length) - a.reduce(sumLength, a.length) || b.length - a.length;
    }).reduce(function (used, cur) {
        if (used.reduce(sumLength, 0) < arrayLength && cur.every(isNotUsed, used)) {
            used.push(cur);
        }

        return used;
    }, []).map(function (bin) {
        return bin.join(separator);
    });
}

要打包到 bin 中的字符串数组

var nameList = [
    "Andrew Alexander Brown",
    "Charlie Christopher Drake",
    "Edward Elsevier Furlong",
    "Gareth Gates Harper",
    "Indiana Chewbacca Jones",
    "Kevin M Lamarr",
    "Michael Randy Newman",
    "Oliver Terry Pratchett",
    "Queen Liz Regina",
    "Stuart Townsend",
    "Umar Vespa",
    "Woodford X Xanadu",
    "Yanick Zebra"];

打包垃圾箱并显示每个垃圾箱的内容

joinStringsMaxCharacters(nameList, 48).forEach(function (bin) {
    console.log(bin);
});

输出

    Kevin M Lamarr|Stuart Townsend|Woodford X Xanadu    Michael Randy Newman|Queen Liz Regina|Umar Vespa    Charlie Christopher Drake|Oliver Terry Pratchett    Edward Elsevier Furlong|Indiana Chewbacca Jones    Andrew Alexander Brown|Gareth Gates Harper    Yanick Zebra

关于 jsFiddle