BeforeID

BeforeID

关注
发信
关注(28)粉丝(399)

订购有每个对象的BeforeID和AfterID对象数组

本文介绍了订购有每个对象的BeforeID和AfterID对象数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我与它返回一个对象数组的API工作。每个对象都有一个ID，而且还指定哪个对象来自己之前和之后本身就带有 beforeId 和 afterId 属性。如果它在列表中的第一个对象，那么 beforeId 为空（因为没有什么是之前在列表中），如果它在列表中的最后一个对象，那么 afterId 为空。

从API示例响应：

  VAR myUnorderedObjects = [
    {ID：896，beforeId：392，afterId：955}，
    {ID：955，beforeId：896，afterId：空}
    {ID：451，beforeId：空，afterId：392}，
    {ID：392，beforeId：451，afterId：896}，
]

有序阵列的示例：

  VAR myOrderedObjects = [
    {ID：451，beforeId：空，afterId：392}，
    {ID：392，beforeId：451，afterId：896}，
    {ID：896，beforeId：392，afterId：955}，
    {ID：955，beforeId：896，afterId：空}
]

什么是订购这些物品的最佳方式？目前，我的应用程序实现其自己的排序逻辑，是从API的分离。我想使它们保持一致。我一般的做法迄今通过识别与空一对 beforeId ，然后将找到的第一个对象查找和发现每个人在指定的 afterId ，但只是似乎有点......垃圾。

我的应用程序使用Underscore.js，所以我很高兴任何答案要利用这个库。

修改的

我做了两个答案之间的快速性能测试。尼娜肖尔茨的回答是最快的，也是一种方法我还没有考虑。


解决方案

此解决方案，如果所有项目都链接工作。

\r
\r

函数怪（A，B）{\r
    如果（\r
        a.beforeId ===空||\r
        b.afterId ===空||\r
        a.id === b.beforeId ||\r
        a.afterId === b.id\r
    ）{\r
        返回-1;\r
    }\r
    如果（\r
        b.beforeId ===空||\r
        a.afterId ===空||\r
        a.id === b.afterId ||\r
        a.beforeId === b.id\r
    ）{\r
        返回1;\r
    }\r
    返回0;\r
}\r
\r
VAR unsorted1 = [\r
        {ID：896，beforeId：392，afterId：955}，\r
        {ID：955，beforeId：896，afterId：空}，\r
        {ID：451，beforeId：空，afterId：392}，\r
        {ID：392，beforeId：451，afterId：893}，\r
    ]\r
    unsorted2 = [\r
        {ID：3，beforeId：2，afterId：4}，\r
        {ID：4，beforeId：3，afterId：空}，\r
        {ID：0，beforeId：空，afterId：1}，\r
        {ID：2，beforeId：1，afterId：3}，\r
        {ID：1，beforeId：0，afterId：2}\r
    ]\r
    sorted1 = unsorted1.slice（）排序（怪），\r
    sorted2 = unsorted2.slice（）排序（怪）。\r
\r
的document.write（'＆LT; pre＆GT;'+ JSON.stringify（sorted1，0,4）+'＆LT; / pre＆GT;'）;\r
的document.write（'＆LT; pre＆GT;'+ JSON.stringify（sorted2，0,4）+'＆LT; / pre＆GT;'）;

\r

\r
\r

更新：

尤里Tarabanko向我指出一个问题，铬46，他是对的，前一个版本没有那种好。因此，这里的更新版本，它使用一个哈希表和排序功能的递归调用。

\r
\r

函数排序（阵列）{\r
\r
    函数s（A，B）{\r
        如果（a.beforeId ===空|| b.afterId ===空|| a.id === b.beforeId || a.afterId === b.id）{\r
            返回-1;\r
        }\r
        如果（b.beforeId ===空|| a.afterId ===空|| a.id === b.afterId || a.beforeId === b.id）{\r
            返回1;\r
        }\r
        返回S（O [a.beforeId]，B）|| S（一，邻[b.afterId]）|| 0;\r
    }\r
\r
    VAR O = {};\r
    阵= array.slice（）;\r
    array.forEach（函数（）{\r
        Ø[a.id] = A;\r
    }）;\r
    中的Array.sort（S）;\r
    返回数组;\r
}\r
\r
VAR unsorted1 = [\r
        {ID：896，beforeId：392，afterId：955}，\r
        {ID：955，beforeId：896，afterId：空}，\r
        {ID：451，beforeId：空，afterId：392}，\r
        {ID：392，beforeId：451，afterId：896}，\r
    ]\r
    unsorted2 = [\r
        {ID：3，beforeId：2，afterId：4}，\r
        {ID：4，beforeId：3，afterId：空}，\r
        {ID：0，beforeId：空，afterId：1}，\r
        {ID：2，beforeId：1，afterId：3}，\r
        {ID：1，beforeId：0，afterId：2}\r
    ]\r
    unsorted3 = [\r
        {ID：7，beforeId：6，afterId：8}，\r
        {ID：11，beforeId：10，afterId：空}，\r
        {ID：0，beforeId：空，afterId：1}，\r
        {ID：1，beforeId：0，afterId：2}，\r
        {ID：4，beforeId：3，afterId：5}，\r
        {ID：8，beforeId：7，afterId：9}，\r
        {ID：2，beforeId：1，afterId：3}，\r
        {ID：9，beforeId：8，afterId：10}，\r
        {ID：10，beforeId：9，afterId：11}，\r
        {ID：3，beforeId：2，afterId：4}，\r
        {ID：5，beforeId：4，afterId：6}，\r
        {ID：6，beforeId：5，afterId：7}，\r
    ];\r
\r
的document.write（'＆LT; pre＆GT;'+ JSON.stringify（排序（unsorted1），0,4）+'＆LT; / pre＆GT;'）;\r
的document.write（'＆LT; pre＆GT;'+ JSON.stringify（排序（unsorted2），0,4）+'＆LT; / pre＆GT;'）;\r
的document.write（'＆LT; pre＆GT;'+ JSON.stringify（排序（unsorted3），0,4）+'＆LT; / pre＆GT;'）;

\r

\r
\r

更新2：

我会用：一个哈希表，为启动一个指针，然后重新组装阵列

。

\r
\r

函数链（阵列）{\r
    变种O = {}，指针;\r
    array.forEach（函数（）{\r
        Ø[a.id] = A;\r
        如果（a.beforeId === NULL）{\r
            指针= a.id;\r
        }\r
    }）;\r
    数组= [];\r
    做{\r
        的Array.push（O [指针]）;\r
        指针= O [指针] .afterId;\r
    }而（指针== NULL！）;\r
    返回数组;\r
}\r
\r
VAR unsorted1 = [\r
        {ID：896，beforeId：392，afterId：955}，\r
        {ID：955，beforeId：896，afterId：空}，\r
        {ID：451，beforeId：空，afterId：392}，\r
        {ID：392，beforeId：451，afterId：896}，\r
    ]\r
    unsorted2 = [\r
        {ID：3，beforeId：2，afterId：4}，\r
        {ID：4，beforeId：3，afterId：空}，\r
        {ID：0，beforeId：空，afterId：1}，\r
        {ID：2，beforeId：1，afterId：3}，\r
        {ID：1，beforeId：0，afterId：2}\r
    ]\r
    unsorted3 = [\r
        {ID：7，beforeId：6，afterId：8}，\r
        {ID：11，beforeId：10，afterId：空}，\r
        {ID：0，beforeId：空，afterId：1}，\r
        {ID：1，beforeId：0，afterId：2}，\r
        {ID：4，beforeId：3，afterId：5}，\r
        {ID：8，beforeId：7，afterId：9}，\r
        {ID：2，beforeId：1，afterId：3}，\r
        {ID：9，beforeId：8，afterId：10}，\r
        {ID：10，beforeId：9，afterId：11}，\r
        {ID：3，beforeId：2，afterId：4}，\r
        {ID：5，beforeId：4，afterId：6}，\r
        {ID：6，beforeId：5，afterId：7}，\r
    ];\r
\r
的document.write（'＆LT; pre＆GT;'+ JSON.stringify（链（unsorted1），0,4）+'＆LT; / pre＆GT;'）;\r
的document.write（'＆LT; pre＆GT;'+ JSON.stringify（链（unsorted2），0,4）+'＆LT; / pre＆GT;'）;\r
的document.write（'＆LT; pre＆GT;'+ JSON.stringify（链（unsorted3），0,4）+'＆LT; / pre＆GT;'）;

\r

\r
\r

I am working with an API which returns an array of objects. Each object has an ID, and it also specifies which object comes before itself and after itself with a beforeId and afterId property. If it's the first object in the list, then the beforeId is null (since nothing is before it in the list) and if it's the last object in the list, then the afterId is null.

Example response from API:

var myUnorderedObjects = [
    { id: 896, beforeId: 392, afterId: 955 },
    { id: 955, beforeId: 896, afterId: null }
    { id: 451, beforeId: null, afterId: 392 },
    { id: 392, beforeId: 451, afterId: 896 },
]

Example of an ordered array:

var myOrderedObjects = [
    { id: 451, beforeId: null, afterId: 392 },
    { id: 392, beforeId: 451, afterId: 896 },
    { id: 896, beforeId: 392, afterId: 955 },
    { id: 955, beforeId: 896, afterId: null }
]

What is the best way to order these objects? Currently, my application implements its own ordering logic which is separate from the API's. I'd like to make them consistent. My general approach so far is to find the first object by identifying the one with null set on the beforeId, and then look up and find each one specified in the afterId, but that just seems a bit... rubbish.

My application uses Underscore.js, so I'm happy for any answers to make use of this library.

Edit

I did a quick performance test between the two answers. Nina Scholz's answer was the fastest, and also an approach I hadn't even considered. http://jsperf.com/order-objects-with-beforeid-and-afterid

解决方案

This solution works if all items are chained.

function strange(a, b) {
    if (
        a.beforeId === null ||
        b.afterId === null ||
        a.id === b.beforeId ||
        a.afterId === b.id
    ) {
        return -1;
    }
    if (
        b.beforeId === null ||
        a.afterId === null ||
        a.id === b.afterId ||
        a.beforeId === b.id
    ) {
        return 1;
    }
    return 0;
}

var unsorted1 = [
        { id: 896, beforeId: 392, afterId: 955 },
        { id: 955, beforeId: 896, afterId: null },
        { id: 451, beforeId: null, afterId: 392 },
        { id: 392, beforeId: 451, afterId: 893 },
    ],
    unsorted2 = [
        { id: 3, beforeId: 2, afterId: 4 },
        { id: 4, beforeId: 3, afterId: null },
        { id: 0, beforeId: null, afterId: 1 },
        { id: 2, beforeId: 1, afterId: 3 },
        { id: 1, beforeId: 0, afterId: 2 }
    ],
    sorted1 = unsorted1.slice().sort(strange),
    sorted2 = unsorted2.slice().sort(strange);

document.write('<pre>' + JSON.stringify(sorted1, 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(sorted2, 0, 4) + '</pre>');

Update:

Yury Tarabanko pointed me to a problem with Chrome 46 and he is right, the former version does not sort well. So here an updated version which uses a hash table and a recursive call of the sort function.

function sort(array) {

    function s(a, b) {
        if (a.beforeId === null || b.afterId === null || a.id === b.beforeId || a.afterId === b.id) {
            return -1;
        }
        if (b.beforeId === null || a.afterId === null || a.id === b.afterId || a.beforeId === b.id) {
            return 1;
        }
        return s(o[a.beforeId], b) || s(a, o[b.afterId]) || 0;
    }

    var o = {};
    array = array.slice();
    array.forEach(function (a) {
        o[a.id] = a;
    });
    array.sort(s);
    return array;
}

var unsorted1 = [
        { id: 896, beforeId: 392, afterId: 955 },
        { id: 955, beforeId: 896, afterId: null },
        { id: 451, beforeId: null, afterId: 392 },
        { id: 392, beforeId: 451, afterId: 896 },
    ],
    unsorted2 = [
        { id: 3, beforeId: 2, afterId: 4 },
        { id: 4, beforeId: 3, afterId: null },
        { id: 0, beforeId: null, afterId: 1 },
        { id: 2, beforeId: 1, afterId: 3 },
        { id: 1, beforeId: 0, afterId: 2 }
    ],
    unsorted3 = [
        { id: 7, beforeId: 6, afterId: 8 },
        { id: 11, beforeId: 10, afterId: null },
        { id: 0, beforeId: null, afterId: 1 },
        { id: 1, beforeId: 0, afterId: 2 },
        { id: 4, beforeId: 3, afterId: 5 },
        { id: 8, beforeId: 7, afterId: 9 },
        { id: 2, beforeId: 1, afterId: 3 },
        { id: 9, beforeId: 8, afterId: 10 },
        { id: 10, beforeId: 9, afterId: 11 },
        { id: 3, beforeId: 2, afterId: 4 },
        { id: 5, beforeId: 4, afterId: 6 },
        { id: 6, beforeId: 5, afterId: 7 },
    ];

document.write('<pre>' + JSON.stringify(sort(unsorted1), 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(sort(unsorted2), 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(sort(unsorted3), 0, 4) + '</pre>');

Update 2:

What I would use: a hash table, a pointer for the start and then reassembling the array.

function chain(array) {
    var o = {}, pointer;
    array.forEach(function (a) {
        o[a.id] = a;
        if (a.beforeId === null) {
            pointer = a.id;
        }
    });
    array = [];
    do {
        array.push(o[pointer]);
        pointer = o[pointer].afterId;
    } while (pointer !== null);
    return array;
}

var unsorted1 = [
        { id: 896, beforeId: 392, afterId: 955 },
        { id: 955, beforeId: 896, afterId: null },
        { id: 451, beforeId: null, afterId: 392 },
        { id: 392, beforeId: 451, afterId: 896 },
    ],
    unsorted2 = [
        { id: 3, beforeId: 2, afterId: 4 },
        { id: 4, beforeId: 3, afterId: null },
        { id: 0, beforeId: null, afterId: 1 },
        { id: 2, beforeId: 1, afterId: 3 },
        { id: 1, beforeId: 0, afterId: 2 }
    ],
    unsorted3 = [
        { id: 7, beforeId: 6, afterId: 8 },
        { id: 11, beforeId: 10, afterId: null },
        { id: 0, beforeId: null, afterId: 1 },
        { id: 1, beforeId: 0, afterId: 2 },
        { id: 4, beforeId: 3, afterId: 5 },
        { id: 8, beforeId: 7, afterId: 9 },
        { id: 2, beforeId: 1, afterId: 3 },
        { id: 9, beforeId: 8, afterId: 10 },
        { id: 10, beforeId: 9, afterId: 11 },
        { id: 3, beforeId: 2, afterId: 4 },
        { id: 5, beforeId: 4, afterId: 6 },
        { id: 6, beforeId: 5, afterId: 7 },
    ];

document.write('<pre>' + JSON.stringify(chain(unsorted1), 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(chain(unsorted2), 0, 4) + '</pre>');
document.write('<pre>' + JSON.stringify(chain(unsorted3), 0, 4) + '</pre>');

这篇关于订购有每个对象的BeforeID和AfterID对象数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

10-29 13:20
Powered by LMLPHP ©2024 BeforeID 0.006220