排序在每个对象上具有BeforeID和AfterID的对象数组

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.

我正在使用API​​返回一个对象数组。每个对象都有一个ID,它还指定哪个对象在自身之前和之后具有beforeId和afterId属性。如果它是列表中的第一个对象,则beforeId为null(因为列表中没有任何内容),如果它是列表中的最后一个对象,则afterId为null。

Example response from API:

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.

订购这些物品的最佳方法是什么?目前,我的应用程序实现了自己的排序逻辑,该逻辑与API分开。我想让它们保持一致。到目前为止,我的一般方法是通过在beforeId上识别出一个带空值的对象来找到第一个对象,然后查找并查找afterId中指定的每个对象,但这看起来有点......垃圾。

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

我的应用程序使用Underscore.js,所以我很高兴能够使用这个库的任何答案。

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

我在两个答案之间进行了快速的性能测试。 Nina Scholz的答案是最快的,也是我甚至没有考虑过的方法。 http://jsperf.com/order-objects-with-beforeid-and-afterid

4 个解决方案

#1

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.

Yury Tarabanko向我指出了Chrome 46的一个问题,他是对的,前一个版本并不顺利。所以这里有一个更新版本,它使用散列表和sort函数的递归调用。

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>');

#2

Since the ids are just arbitrary numbers you cannot generate any kind of object index from them that might be used for sorting. Starting with beforeId null and following the afterId fields is a reasonable solution. If this is how you get the data from the API, there is nothing wrong with your approach of ordering the objects.

由于id只是任意数字,因此无法从它们生成可用于排序的任何类型的对象索引。从beforeId null开始并跟随afterId字段是一个合理的解决方案。如果这是从API获取数据的方式,那么您对对象进行排序的方法没有任何问题。

#3

This would do it:

这样做:

function findElementWithPropertyValue (array, property, value) {
  var index = array.map(function (element) {
    return element[property];
  }).indexOf(value);

  return array[index];
}

function reorderResults (unsorted) {
  var sorted = [];

  sorted.push(findElementWithPropertyValue(unsorted, 'beforeId', null));

  while (sorted.length < unsorted.length) {
    sorted.push(findElementWithPropertyValue(unsorted, 'beforeId', sorted[sorted.length - 1].id));
  }

  return sorted
}

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: 893 }
    ],
    myOrderedObjects = reorderResults(myUnorderedObjects);

console.log(myOrderedObjects);

#4

As I have written in comment @Nina's answer is just wrong. Given function fails to compare 2 non-sibling items and returning 0 is not an option here.

正如我在评论中写的那样@Nina的答案是错的。给定函数无法比较2个非兄弟项目,并且返回0不是此处的选项。

First incorrect result comes for arrays of length 5.

对于长度为5的数组,首先出现错误结果。

var shuffled = [
    {"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}
];

was sorted to

被分类到

[
    {"id": 0, "beforeId": null, "afterId": 1},
    {"id": 2, "beforeId": 1, "afterId": 3},
    {"id": 3, "beforeId": 2, "afterId": 4},
    {"id": 1, "beforeId": 0, "afterId": 2},
    {"id": 4, "beforeId": 3,"afterId": null}
]

Actually @Jon's solution was right. His naive implementation might be optimized to be O(n) instead of O(n^2). Which is a micro optimization you should not worry about unless you have hundreds of items in your list. Perf.

实际上@ Jon的解决方案是正确的。他的天真实现可能被优化为O(n)而不是O(n ^ 2)。除非您的列表中有数百个项目,否则您不应该担心这是微优化。逆足

/**
 * Using for loops for *micro* optimization and explicit O(n) estimates.
 * http://jsperf.com/order-objects-with-beforeid-and-afterid/2
 */
function linkSort(array) {
    var head, 
        cache = {},
        i,
        len = array.length,
        linked = new Array(len),
        item;

    //indexing
    for(i = 0; i < len; i++) { //O(n) index and find head
        item = array[i];

        if(item.beforeId === null) { //is head
            head = item;
        }
        else { //index by id
            cache[item.id] = item;            
        }
    }

    //linking
    linked[0] = head; 

    for(i = 1; i < len; i++) { //O(n) construct linked list
        linked[i] = head = cache[head.afterId]; //Lookup is O(1) unlike map+indexOf
    }

    return linked;
}