在Chrome和Firefox中使用Array.sort(比较函数)的结果不同

ct3nt3jp  于 2022-12-06  发布在  Go
关注(0)|答案(4)|浏览(260)

我使用的是anArrayOfObjects.sort((a, b) => a.value - b.value),其中一些对象没有value属性。
这在Firefox和Chrome中导致了不同的结果,Chrome似乎会对没有value属性/未定义值的对象进行排序,而Firefox不会。
是规范没有规定Chrome给出的结果,意味着Firefox的结果是错误的?还是sort结果的一部分取决于特定的实现?

const data2 = [
  { 'name' : 'a', 'value' : 5 },
  { 'name' : 'b', 'value' : 2 },
  { 'name' : 'c' },
  { 'name' : 'd', 'value' : 1 }
];

console.log('before sorting: ', data2);

data2.sort((a, b) => a.value - b.value);

console.log('after sorting: ', data2);
ddhy6vgd

ddhy6vgd1#

两者都不是“错误”。
undefined - undefinedundefined - 11 - undefined都返回NaN,而NaN与某物相比 * 总是 * false
这两种浏览器之间的差异可能是由于排序实现的原因。
所使用的排序算法可以给予不同的结果,这取决于预先的值的顺序以及实现如何处理NaN

7vux5j2d

7vux5j2d2#

不要让浏览器引擎决定如何在有疑问的情况下处理你的代码,只写你的代码没有它:

data2.sort((a, b) => (a?.value || 0) - (b?.value || 0));

(默认值可以是某个较小或较大的数字,以便按您需要的顺序进行排序。)

yhxst69z

yhxst69z3#

比较函数的工作方式如下:
| compareFn(a, b)返回值|排序顺序|
| - -|- -|
| < 0|将a排序在b之后|
| > 0|将a排在b之前|
| === 0|保留ab的原始顺序|
任何涉及undefined的减法都会给予NaN的返回值,根据规范,该值会立即转换为0。然而,顺序将取决于实现所使用的特定算法,因为该算法决定了以这种方式比较哪些值。
当您注销比较时,问题变得更加明显:

const data2 = [
  { 'name' : 'a', 'value' : 5 },
  { 'name' : 'b', 'value' : 2 },
  { 'name' : 'c' },
  { 'name' : 'd', 'value' : 1 }
];

console.log('before sorting: ', data2);

data2.sort((a, b) => (console.log(a.value, b.value), a.value - b.value));

console.log('after sorting: ', data2);

1.Firefox似乎在问> 0

5 2
5 undefined
undefined 1
  1. a'a'b'b',返回值是3,因此'a'必须在'b'之后。
  2. a'a'b'c',返回值是0,因此'a'位于'c'之前。
  3. a'c',而b'd',返回值是0,因此'c'位于'd'之前。
    1.Chrome似乎在问< 0
2 5
undefined 2
undefined 5
1 5
1 2
  1. a'b'b'a',返回值是-3,因此'b'必须在'a'之前。
  2. a'c'b'b',返回值是0,因此'c'位于'b'之后
  3. a'c'b'a',返回值是0,因此'c'位于'a'之后
  4. a'd'b'a',返回值是-4,因此'd'必须在'a'之前
  5. a'd'b'b',返回值是-1,因此'd'必须在'b'之前
    特别是Chrome从来没有直接比较'c''d',所以从来没有告诉他们保持相同的顺序。
kqlmhetl

kqlmhetl4#

众所周知,排序算法是特定于浏览器实现的,此外,由于不存在“银”算法,因此特定浏览器可以将不同排序算法用于不同的数据形状作为优化技术。
在Firefox中查看以下示例结果时,这一点变得很明显:

const arr1 = [
  { 'value' : 5 },
  { 'value' : 2 },
  { 'value': undefined },
  { 'value' : 4 },
  { 'value' : 3 },
  { 'value': undefined },
  { 'value' : 1 },
  { 'value' : 0 }
];

const arr2 = [5, 2, undefined, 4, 3, undefined, 1, 0];

arr1.sort((a, b) => a.value - b.value);

arr2.sort((a, b) => a - b);

console.log(arr1.map(v => `${v.value}`).join());

console.log(arr2.map(v => `${v}`).join());

实际上,上述示例的Chrome结果符合规范:
1.设SortCompare为一个新的Abstract Closure,它带有参数(x,y),用于捕获比较fn,并在调用时执行以下步骤:
a.如果x和y都未定义,则返回+0𝔽。
B.如果x未定义,则返回1𝔽。
c.如果y未定义,则返回-1𝔽。
从上面的语句可以得出结论,undefined的值总是比较起来大于其他任何值,这就是为什么它们被排序在末尾的原因。
这个结果可以通过merge sort算法实现,该算法对未定义值进行特殊处理,下面是该算法的伪代码:

const mergeSort = arr => {
    let voids = 0;
    const merge = (l, r) => {
        const out = [];
        l.length && l[0] === undefined && (l.shift(), voids++);
        while (l.length && r.length) out.push(l[0] <= r[0] ? l.shift() : r.shift());
        while(l.length) out.push(l.shift());
        while(r.length) out.push(r.shift());
        return out;
    };
    const sort = arr => {
        if (arr.length < 2)
            return arr;
        const m = Math.floor(arr.length / 2);
        const l = arr.slice(0, m), r = arr.slice(m);
        return merge(sort(l), sort(r));
    };
    const result = sort(arr);
    while (voids--) result.push(undefined);
    return result;
};

const arr = [5, 2, undefined, 4, 3, undefined, 1, 0];

console.log(mergeSort(arr).map(v => `${v}`).join());

关于Firefox中的 sorted array of objects 结果,在第一个例子中,可以通过一个简单的insertion sort算法得到,如下:

const insertionSort = arr => {
    for (let i = 1; i < arr.length; i++) {
        let x = i - 1, n = arr[i];
        for (; x >= 0 && arr[x] > n; x--)
            arr[x + 1] = arr[x];
        arr[x + 1] = n;
    }
    return arr;
};

const arr = [5, 2, undefined, 4, 3, undefined, 1, 0];

console.log(insertionSort(arr).map(v => `${v}`).join());

相关问题