Hướng dẫn find 3 largest numbers in an array in javascript - tìm 3 số lớn nhất trong một mảng trong javascript

Edit: Everything below is still valid. However, it was clarified to me in a comment that the original question did not ask for indexes, and many of the answers were responding to the preexisting question. Apologies for any curtness in my original post.

Even looking at the original question however, I still disagree with recommending sorting in general for this type of question.

---

I can't believe how many of these answers are worse than the OP's provided solution. Most are more concise, but either:

• Don't answer the question. Often only providing the top 3 values, when the question also asks for the indexes of the top 3 values.
• Suggest "sorting" but without even mentioning performance, side-effects or Big-O notation.

This may be a little too long for SO, but I feel like this is pertinent information.

---

1. I need a more optimized version of this javascript code to find the 3 largest values in an array.
2. I need to get the indexes of the largest numbers.
3. Are there any other easier methods to solve the problem?

I take (3) to mean "I want the method to be more concise / readable", (2) as "indices to be available in the output directly", and (1) to mean "I want the code to be as efficient as possible".

Starting from (3) as it'd be most useful to people: Your original algorithm is quite efficient, but you're basically duplicating code in each of the 3 loops; the only difference in each loop really is that the index changes. If you just wanted to cut down on the number of characters, you could re-write your algorithm (with a couple minor caveats1) as:

function findLargest3(arry) {
  const max = {
    indices: new Array(0, 0, 0),
    points : new Array(0, 0, 0)
  }
  
  // Inner private function to remove duplicate code
  // Modifies "max" as a side-effect
  function setLargest (idx) {
    const lastMax = max.points[idx - 1] || Number.MAX_VALUE;
    for (let i = 0; i < arry.length; i++) {
      if (arry[i] > max.points[idx] && arry[i] < lastMax) {
        max.points[idx] = arry[i];
        max.indices[idx] = i;
      }
    }
  }
  
  // Get's the 0'th, 1st, and 2nd largest items
  for (let i = 0; i < 3; i++) {
    setLargest(i);
  }
  
  return max;
}

let scoreByPattern = new Array(93, 17, 56, 91, 98, 33, 9, 38, 55, 78, 29, 81, 60);
let max = findLargest3(scoreByPattern);
console.log(scoreByPattern + "/******/" + max.points.join("/"));

Beyond the addition of the function, the only thing I really had to add was: const lastMax = max.points[idx - 1] || Number.MAX_VALUE;. This was just for the case where idx == 0. As there is no max.points[-1]. We want that second check to always return true, so if max.points[idx - 1] doesn't exist, set it to the highest possible value via ||.

This actually ends up being about 4 times slower than your implementation. That slowness is a result of not directly modifying global state (which is faster but harder to maintain) & including that inner function rather than the code duplication. Replacing the inner function with your original duplicated code & leaving every other change the same ends up being 40% faster to execute, because it avoids the creation & calling of the function entirely; but again is easier to read. It also makes extending findLargest3 to become findLargest5 or findLargestN much simpler.

Additionally, it should be the same Big-O as your original solution (see my answer to 1), unlike the solutions involving

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

0; which means it will scale as well as your original solution, while being easier to read & maintain. If you really need the performance, there's very little wrong with your original solution, and I'd even argue your original solution's better than some of the posted solutions. (For example, from rough testing, increasing the size of the array to ~100 elements makes my solution run about ~3x slower, but makes a solution using

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

0 run more than 6x slower).

---

1Note: There is one major issue with your algorithm, and that's that

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

2 is "globally scoped". If you wrote the following, it would run for

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

3 and then loop forever with

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

4 & would never finish:

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

That's because your

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

5 statements don't reference a "local" version of

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

2 & will fall back to one that's been defined in a previous scope (or global if it doesn't find one). Your loops always leave

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

2 set to

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

8 when they finish, which would change the value in this outer loop. Certain languages & language constructs (

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

9 in C# for example) actually won't compile if you've attempted to modify an iterator during a loop. The fix is actually really simple, & it's just to say const lastMax = max.points[idx - 1] || Number.MAX_VALUE;0 or const lastMax = max.points[idx - 1] || Number.MAX_VALUE;1 in your loop declaration & then

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

2 will only refer to a variable local to the function.

There's also the minor problem of your original algorithm ignoring duplicates in the array. If I add another const lastMax = max.points[idx - 1] || Number.MAX_VALUE;3 to the end of your original array, it still returns the top values as const lastMax = max.points[idx - 1] || Number.MAX_VALUE;4. I didn't change this in my solution, as it may be intentional (e.g. the top three "values" are 98, 93, and 91, but 93 just happens to occur twice). To fix, rather than checking that const lastMax = max.points[idx - 1] || Number.MAX_VALUE;5 you would just check that

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

2 isn't already in const lastMax = max.points[idx - 1] || Number.MAX_VALUE;7. Depending on the number of duplicates, this could slow the algorithm down (without a rewrite) but assuming const lastMax = max.points[idx - 1] || Number.MAX_VALUE;8 then it wouldn't be noticeably slower.

And while not being a "problem" per-se, it's generally not ideal to have "global state" (i.e. const lastMax = max.points[idx - 1] || Number.MAX_VALUE;9) & then have them be mutated by a function. It can be computationally faster, but harder to maintain. That's why I moved the declaration of idx == 00 into the function body & made it request idx == 01 as a parameter. There are plenty of scenarios where that'd be fine (e.g. Object member variables & mutator methods). But here, findLargest3 really seems like a helper function / functional in nature, & thus ideally shouldn't have side-effects (i.e. modify external state / the parameters that are passed to it).

---

Đề cập ngắn gọn (2): Nếu bản thân các chỉ mục, việc sắp xếp mảng không thực sự có ý nghĩa ngoại trừ trong một số trường hợp rất đặc biệt (xem câu trả lời của tôi cho điểm 1). Sắp xếp là thao tác "tại chỗ" bằng phương thức

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

0 của JavaScript trực tiếp trên mảng. Điều này có nghĩa là nó sẽ sửa đổi mảng ban đầu trong hầu hết các câu trả lời này; Vì vậy, các chỉ mục ban đầu thực sự bị mất và cũng có những hậu quả khác cho phần còn lại của chương trình. Để sử dụng sắp xếp để có được các giá trị N trên cùng, bạn phải sao chép mảng trước, sắp xếp bản sao, lấy 3 giá trị hàng đầu, sau đó lặp qua mảng gốc ~ 3 lần cố gắng khớp bằng cách sử dụng idx == 04 hoặc tương tự (và tương tự (và đối phó với các bản sao).

Đây rõ ràng là một sự lãng phí tài nguyên, vì một số câu trả lời này chậm hơn 30 lần so với bản gốc. Bạn có thể thử và tạo một danh sách các "chỉ mục" thay vì các giá trị, sắp xếp chúng dựa trên mảng gốc và điều đó sẽ nhanh hơn một chút. Nhưng trong trường hợp cụ thể này, nơi chúng tôi chỉ muốn "Top 3" (một lần nữa, hãy xem câu trả lời của tôi đến điểm 1) trừ khi tôi bị điên, việc sắp xếp hầu như sẽ luôn chậm hơn.

---

Cuối cùng, nhìn vào (1) thật hữu ích khi áp dụng một khái niệm gọi là "ký hiệu lớn" khi phân tích các thuật toán. Tôi đề nghị googling nó và có một lần đọc, nhưng rộng rãi: chúng tôi muốn xem một thuật toán hiệu quả như thế nào, khi độ dài của đầu vào tăng lên. Ví dụ. Trong ứng dụng của bạn, chúng tôi đã có mảng idx == 01 mà chúng tôi sẽ nói có độ dài idx == 06, cũng như một "3 chỉ mục / giá trị" rõ ràng được áp đặt bởi câu hỏi của bạn, nhưng thật hữu ích khi có thể nói "trả lại đầu idx == 07 chỉ mục / giá trị ". Nếu idx == 01 hoặc idx == 09 rất ngắn, thì sự phức tạp của thuật toán sẽ không thực sự quan trọng, nhưng nếu chúng có 100 đến 100 trong số hàng ngàn yếu tố, thì độ phức tạp tính toán của chúng trở nên thực sự đáng kể.

Ngoài ra, điều quan trọng là phải nói rằng với một mảng trong JS, nếu bạn biết chỉ mục, "tra cứu" thực sự là một hoạt động gần như tức thời max.points[-1]0. Ngoài ra, trong Big-O, chúng ta có xu hướng chỉ nhìn vào thuật ngữ "chi phối" của phân tích và bỏ qua bất kỳ yếu tố thời gian liên tục nào. Ví dụ. Nếu một giải pháp là max.points[-1]1 (10 thao tác thời gian không đổi + 2 cho mỗi mục trong danh sách độ dài idx == 06), chúng tôi nói rằng Big-O của giải pháp là max.points[-1]3. Điều này là do, đối với một danh sách dài hợp lý, nếu chúng ta tăng gấp đôi giá trị của N, thời gian thực hiện sẽ tăng gấp đôi. Nếu nó được giới hạn bởi một hoạt động O (N2) và chiều dài danh sách đã tăng gấp đôi, sẽ mất nhiều thời gian hơn 22 lần (nghĩa là chậm hơn 4 lần).

Vì vậy, giải pháp ban đầu của bạn là:

• Một số bước thời gian liên tục
• Lặp lại trong danh sách một lần, thực hiện hai kiểm tra boolean & hai bài tập
• Làm điều này một lần nữa
• Làm điều này lần thứ ba

Có nghĩa là nó sẽ giống như max.points[-1]4 trong đó max.points[-1]5 & max.points[-1]6 là một số hằng số, để lại nó như: max.points[-1]3 nói chung. Nếu chúng tôi muốn "các chỉ mục ____37 hàng đầu", bạn sẽ kết thúc với: max.points[-1]9 kết thúc là max.points[idx - 1]0 (tức là Big-O của max.points[idx - 1]1). Tại sao nó quan trọng?

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

0 là lớn của max.points[idx - 1]3 Điều này có nghĩa là nói rằng, một danh sách ~ 64 mặt hàng, sắp xếp sẽ mất khoảng max.points[idx - 1]4. Vì vậy, so sánh giải pháp của bạn với các giải pháp liên quan đến

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

0, trừ khi max.points[idx - 1]6, không phân loại là thích hợp hơn.

Để đưa nó vào quan điểm: Nếu danh sách của bạn có 100 mục, bạn cần phải cố gắng để có được hơn 6 mục "lớn nhất" để sắp xếp để hiệu quả hơn. Nếu đó là 100.000 mặt hàng, bạn cần phải cố gắng để có được hơn 16 mặt hàng "lớn nhất". Trong trường hợp sử dụng này, đặc biệt là khi bạn đã nói rõ ràng "3", hầu như luôn luôn có ý nghĩa hơn để không sắp xếp. Đặc biệt, bởi vì bạn đang cố gắng để có được các chỉ số; Nếu bạn chỉ muốn các giá trị, thì các giải pháp sắp xếp có thể thích hợp hơn chỉ vì chúng đơn giản.

Bạn có thể có thể điều chỉnh thuật toán của mình nhiều hơn một chút để tăng tốc độ hơn nữa, nhưng từ thử nghiệm thô: Tôi nghĩ rằng giải pháp của bạn đã là giải pháp nhanh nhất ở đây. Nếu bạn muốn làm cho nó dễ dàng hơn để duy trì / đọc / mở rộng, điều đó chắc chắn là có thể; Nhưng điều đó thực sự không nên đến với chi phí thực sự làm tăng "độ phức tạp thời gian" (tức là làm cho giải pháp tồi tệ hơn max.points[-1]3) trừ khi nó đơn giản hóa rất nhiều việc thực hiện.