问找到有最便宜座位的物体
EN

Code Review用户

提问于 2019-08-20 12:38:24

回答 1查看 61关注 0票数 1

我有以下json对象

    const file = [
  {
    "seatNumber": "1A",
    "price": "£19.99",
    "available": true,
    "disabilityAccessible": true
  },
  {
    "seatNumber": "2A",
    "price": "£19.99",
    "available": false,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "3A",
    "price": "£19.99",
    "available": false,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "4A",
    "price": "£19.99",
    "available": true,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "5A",
    "price": "£19.99",
    "available": false,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "1B",
    "price": "£12.99",
    "available": true,
    "disabilityAccessible": true
  },
  {
    "seatNumber": "2B",
    "price": "£12.99",
    "available": false,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "3B",
    "price": "£12.99",
    "available": false,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "4B",
    "price": "£12.99",
    "available": false,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "5B",
    "price": "£12.99",
    "available": true,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "1C",
    "price": "£12.99",
    "available": true,
    "disabilityAccessible": true
  },
  {
    "seatNumber": "2C",
    "price": "£12.99",
    "available": true,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "3C",
    "price": "£12.99",
    "available": true,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "4C",
    "price": "£12.99",
    "available": true,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "5C",
    "price": "£12.99",
    "available": true,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "1D",
    "price": "£12.99",
    "available": true,
    "disabilityAccessible": true
  },
  {
    "seatNumber": "2D",
    "price": "£12.99",
    "available": false,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "3D",
    "price": "£12.99",
    "available": true,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "4D",
    "price": "£12.99",
    "available": true,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "5D",
    "price": "£12.99",
    "available": true,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "1E",
    "price": "£8.99",
    "available": true,
    "disabilityAccessible": true
  },
  {
    "seatNumber": "2E",
    "price": "£8.99",
    "available": true,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "3E",
    "price": "£8.99",
    "available": false,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "4E",
    "price": "£8.99",
    "available": true,
    "disabilityAccessible": false
  },
  {
    "seatNumber": "5E",
    "price": "£8.99",
    "available": false,
    "disabilityAccessible": false
  }
]

我正在尝试显示最便宜的对象的seatNumber。到目前为止，我有以下工作，但想知道是否有更好的方法遵循es6格式的大o符号

const seats = file.filter( seat => seat.price.replace(/[^0-9.-]+/g,"") == Math.min(...file.map(function ( seat ) { return Number(seat.price.replace(/[^0-9.-]+/g,"")) }) ) ).map(seat => seat.seatNumber);
        console.log(seats)

输出是

[ '1E', '2E', '3E', '4E', '5E' ]

javascript

ecmascript-6

回答 1

Code Review用户

回答已采纳

发布于 2019-08-20 17:33:53

跟在小O.

后面

你问

"...if有一个更好的方法来遵循大的o表示法.“(?)

大O表示法是一种形式化的数学惯例，用来表达函数(数学函数)在接近无穷远时的行为方式。

它在计算机科学中被用来分类算法的复杂性与一个可定义的输入度量，通常是输入阵列的大小时处理数组。

您不能“遵循”大O表示法，因为除了比较之外，它无法提供关于如何降低算法复杂性的洞察力。

找到大O

要使用Big对您的函数进行分类，首先我们需要使其至少具有可读性，并将其转换为一个函数。见小片段。

现在，计算函数循环在输入数组数据中每个项上的次数。经验允许您在头脑中执行此操作，但为了演示我们修改了函数，每次处理输入数组中的项时，我们都会对函数进行计数。

因为我们需要拟合一条曲线，我们需要至少3种不同的输入大小，这是我用一些随机数据做的。

function bestSeats(data) {
     var c = 0; // the counter
     const seats = data.filter( seat => 
         (c++,  // count the filter iterations
         seat.price.replace(/[^0-9.-]+/g, "") == Math.min(
                 ...data.map(function ( seat ) { 
                     c += 2;  // this counts as two
                              // once each to map to the arguments of Math.min
                              // once each to find the min                                   
                     return Number(seat.price.replace(/[^0-9.-]+/g, "")) 
                 }
             )
         ))).map(seat => (
             c++,  // count each result
             seat.seat
         )); 
     return "O(n) = O(" + data.length + ") = " + c;
}

function randomData(size) { 
    const data = [];
    while (size--) { data.push({seat:size, price: "$"+(Math.random() * 100 | 0)})}
    return data;
}
console.log("Eval complexity A:" + bestSeats(randomData(10)));
console.log("Eval complexity B:" + bestSeats(randomData(100)));
console.log("Eval complexity C:" + bestSeats(randomData(500)));

我们可以用三个点来找出最适合的曲线

 O(10) ~= 211
 O(100) ~= 20,102
 O(500) ~= 500,005

经验告诉我，这是一个多项式的一些(不太高)的秩序。使用图形计算器，我在2.15找到了一个合理的匹配点，使您的函数变得非常复杂

`O(n^{2.15})`

这是疯狂的低效。哦！

所以保持

"...in es6格式“(?)

考虑到一种更干净、更易读、更少CO2产生海平面上升的方法是对座位进行两次扫描。第一次通过查找最小价格，第二次提取最小价格座位号。

这个例子使用的是for of循环，而不是像filter和map这样的Array方法，因为这些数组方法有一种令人讨厌的方法，使人们无法理解他们所做的复杂程度的疯狂，而且for of比数组方法更快一些，并且经常允许更好的优化，所以它是for of的胜利。

示例在`O(n)`线性时间.

中

 function bestSeats(seats) {
     var min = Infinity, minVal;
     const result = [];
     for (const seat of seats) {
         const price = Number(seat.price.slice(1));
         if (price < min) {
             min = price;
             minVal = seat.price;
         }
     }
     for (const seat of seats) {
         if (seat.price === minVal) { result.push(seat.seatNumber) }
     }
     return result;
 }

如果必须使用数组方法。

 function bestSeats(seats) {
     const price2Num = seat => Number(seat.price.slice(1));
     const min = (min, seat) => price2Num(seat) < min ? price2Num(seat) : min;
     const minPrice = "$" + seats.reduce(min, Infinity);
     return seats.filter(seat => seat.price === minPrice).map(seat => seat.seatNumber);
 }