javascript - 在 Array A 之后对 Array B 排序,这样引用和相等的 Primitives 保持准确的位置

标签 javascript arrays sorting

更新 2

我在排序函数中添加了权重查找,将性能和稳定性提高了大约 100%,因为之前的排序函数没有考虑所有类型,并且作为 1 == "1"正如@Esailija 指出的那样,结果取决于数组的初始顺序。

问题的目的是改进 Answer我的,我喜欢这个问题,因为它被接受了,我觉得有一些性能可以挤出排序功能。我在这里问了这个问题,因为我没有太多线索可以从哪里开始。
也许这也让事情变得更清楚

更新

我改写了完整的问题,因为很多人说我不够具体,我尽力说明我的意思。另外,我重写了 sort功能以更好地表达问题的意图。

  • 设 arrayPrev 为 Array (A) ,其中 A 由 0 到 n 个元素组成' (E)
  • 让一个元素要么是
  • 原始类型
  • bool ,字符串,数字,未定义,空
  • 对对象 O 的引用,其中 O.type = [object Object] 和 O 可以由
  • 0 到 n 属性 P,其中 P 定义为 Element plus
  • 对 O 中任何 P 的循环引用
  • 其中任何 O 可以包含 1 到 n 次。在 GetReferencedName(E1) === GetReferencedName(E2) 的意义上...
  • a 对 O 的引用,其中 O.type = [object Array] 并且 O 的定义类似于 A
  • 对 A 中任何 E 的循环引用
  • 令arrayCurr 为与arrayPrev
  • 长度相同的数组

    如下例所示
    var x = {
        a:"A Property",
        x:"24th Property",
        obj: {
            a: "A Property"
        },
        prim : 1,
    }
    x.obj.circ = x;
    
    var y = {
        a:"A Property",
        x:"24th Property",
        obj: {
            a: "A Property"
        },
        prim : 1,
    }
    y.obj.circ = y;
    var z = {};
    
    var a = [x,x,x,null,undefined,1,y,"2",x,z]
    var b = [z,x,x,y,undefined,1,null,"2",x,x]    
    console.log (sort(a),sort(b,a))
    

    问题是,如何有效地对数组 B 进行排序,以便对对象的任何引用或基元的值,通过相同的 compareFunction、排序的数组 A 共享与以前完全相同的位置。

    就像上面的例子

    Console Log

    结果数组应符合规则的地方。
  • 让 arrayPrev 包含 a 的元素'和 arrayCurr 包含 b 的元素
  • 让arrayPrev 按CompareFunction C 排序。
  • 让 arrayCurr 按相同的 C 排序。
  • 令arrayCur排序的结果是这样的,当在位置n访问arrayCur中的E时,让n例如为5
  • 如果 E 的类型是 Object GetReferencedName(arrayCurr[n]) === GetReferencedName(arrayPrev[n])
  • 如果 E 的类型是 Primitive GetValue(arrayCurr[n]) === GetValue(arrayPrev[n])
  • b[n] === a[n]例如 b[5] === a[5]
  • 这意味着所有元素都应按类型分组,并按值排序。
  • 在 C 中对函数 F 的任何调用至少应在 ES5 之前实现,这样就可以在不需要任何 shim 的情况下提供兼容性。

  • 我目前的方法是在 arrayPrev 中标记对象,以便在 arrayCurr 中对它们进行相应的排序,然后再次删除标记。但这似乎没有那么有效。
    这是当前sort使用的功能。
    function sort3 (curr,prev) {
             var weight = {
                "[object Undefined]":6,         
                "[object Object]":5,
                "[object Null]":4,
                "[object String]":3,
                "[object Number]":2,
                "[object Boolean]":1
            }
            if (prev) { //mark the objects
                for (var i = prev.length,j,t;i>0;i--) {
                    t = typeof (j = prev[i]);
                    if (j != null && t === "object") {
                         j._pos = i;   
                    } else if (t !== "object" && t != "undefined" ) break;
                }
            }
    
            curr.sort (sorter);
    
            if (prev) {
                for (var k = prev.length,l,t;k>0;k--) {
                    t = typeof (l = prev[k]);
                    if (t === "object" && l != null) {
                        delete l._pos;
                    } else if (t !== "object" && t != "undefined" ) break;
                }
            }
            return curr;
    
            function sorter (a,b) {
    
                 var tStr = Object.prototype.toString
                 var types = [tStr.call(a),tStr.call(b)]
                 var ret = [0,0];
                 if (types[0] === types[1] && types[0] === "[object Object]") {
                     if (prev) return a._pos - b._pos
                     else {
                         return a === b ? 0 : 1;
                     }
                 } else if (types [0] !== types [1]){
                         return weight[types[0]] - weight[types[1]]
                 }
    
    
    
                return a>b?1:a<b?-1:0;
            }
    
        }
    

    继承人 Fiddle以及 JSPerf (随意添加您的片段)
    和老Fiddle

    最佳答案

    如果您知道数组包含相同的元素(重复次数相同,可能顺序不同),那么您可以将旧数组复制到新数组中,如下所示:

    function strangeSort(curr, prev) {
        curr.length = 0;             // delete the contents of curr
        curr.push.apply(curr, prev); // append the contents of prev to curr
    }
    

    如果您不知道数组包含相同的元素,那么按照您的要求去做是没有意义的。

    从您链接的内容来看,您可能正在尝试确定数组是否包含相同的元素。在这种情况下,您要问的问题并不是您要问的问题,基于排序的方法可能根本不是您想要的。相反,我推荐一种基于计数的算法。
  • 比较数组的长度。如果它们不同,则数组不包含相同的元素;返回假。如果长度相等,继续。
  • 遍历第一个数组并将每个元素与您看到它的次数相关联。现在 ES6 Maps存在, map 可能是跟踪计数的最佳方式。如果您不使用 Map,则可能需要或方便地以不同方式维护不同数据类型的项目的计数。 (如果您通过赋予对象新属性来维护对象的计数,请在返回之前删除新属性。)
  • 遍历第二个数组。对于每个元素,
  • 如果没有记录元素的计数,则返回 false。
  • 如果元素的计数为正,则将其减 1。
  • 如果元素的计数为 0,则该元素在第二个数组中出现的次数比在第一个数组中出现的次数多。返回假。
  • 返回真。

  • 如果达到第 4 步,则每个项目在第一个数组中出现的次数至少与在第二个数组中出现的次数一样多。否则,它会在步骤 3.1 或 3.3 中检测到。如果任何项目在第一个数组中出现的次数比在第二个数组中出现的次数多,那么第一个数组会更大,并且算法会在步骤 1 中返回。因此,数组必须包含相同元素且重复次数相同。

    关于javascript - 在 Array A 之后对 Array B 排序,这样引用和相等的 Primitives 保持准确的位置,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16969241/

    相关文章:

    javascript - 如何判断某个符号是否被用作 key ?

    javascript - Node.js azure-storage TableService 没有方法

    javascript - 对数组中的数据进行分组

    javascript - 函数未作为函数传递

    Javascript:将数据分配给多维数组

    java - 井字游戏 'X' 直到第二个 'O' 被点击后才出现

    python - 使用比较器函数进行排序

    php - MySQL 中的日期排序

    PHP 数组排序和输出行为

    javascript - asp.net如何打开新窗口?