wehub-skill-sync
84 lines
2.3 KiB
Markdown
84 lines
2.3 KiB
Markdown
---
|
||
|
||
title: Use Loop for Min/Max Instead of Sort
|
||
impact: LOW
|
||
impactDescription: O(n) 替代 O(n log n)
|
||
tags: javascript, arrays, performance, sorting, algorithms
|
||
---
|
||
|
||
## Use Loop for Min/Max Instead of Sort
|
||
|
||
寻找最小或最大元素只需遍历数组一次。排序既浪费又低效。
|
||
|
||
**错误做法（O(n log n)——通过排序找最新值）：**
|
||
|
||
```typescript
|
||
interface Project {
|
||
id: string
|
||
name: string
|
||
updatedAt: number
|
||
}
|
||
|
||
function getLatestProject(projects: Project[]) {
|
||
const sorted = [...projects].sort((a, b) => b.updatedAt - a.updatedAt)
|
||
return sorted[0]
|
||
}
|
||
```
|
||
|
||
仅仅为了找到最大值就对整个数组进行排序。
|
||
|
||
**错误做法（O(n log n)——通过排序找最旧和最新值）：**
|
||
|
||
```typescript
|
||
function getOldestAndNewest(projects: Project[]) {
|
||
const sorted = [...projects].sort((a, b) => a.updatedAt - b.updatedAt)
|
||
return { oldest: sorted[0], newest: sorted[sorted.length - 1] }
|
||
}
|
||
```
|
||
|
||
当只需要最小/最大值时，仍然进行了不必要的排序。
|
||
|
||
**正确做法（O(n)——单次循环）：**
|
||
|
||
```typescript
|
||
function getLatestProject(projects: Project[]) {
|
||
if (projects.length === 0) return null
|
||
|
||
let latest = projects[0]
|
||
|
||
for (let i = 1; i < projects.length; i++) {
|
||
if (projects[i].updatedAt > latest.updatedAt) {
|
||
latest = projects[i]
|
||
}
|
||
}
|
||
|
||
return latest
|
||
}
|
||
|
||
function getOldestAndNewest(projects: Project[]) {
|
||
if (projects.length === 0) return { oldest: null, newest: null }
|
||
|
||
let oldest = projects[0]
|
||
let newest = projects[0]
|
||
|
||
for (let i = 1; i < projects.length; i++) {
|
||
if (projects[i].updatedAt < oldest.updatedAt) oldest = projects[i]
|
||
if (projects[i].updatedAt > newest.updatedAt) newest = projects[i]
|
||
}
|
||
|
||
return { oldest, newest }
|
||
}
|
||
```
|
||
|
||
只需单次遍历数组，无需复制，无需排序。
|
||
|
||
**备选方案（对小型数组使用 Math.min/Math.max）：**
|
||
|
||
```typescript
|
||
const numbers = [5, 2, 8, 1, 9]
|
||
const min = Math.min(...numbers)
|
||
const max = Math.max(...numbers)
|
||
```
|
||
|
||
这种方法适用于小型数组，但对于非常大的数组，由于展开运算符的限制，可能会变慢甚至抛出错误。Chrome 143 中的最大数组长度约为 124000，Safari 18 中约为 638000；具体数值可能有所不同——详见 [jsfiddle](https://jsfiddle.net/qw1jabsx/4/)。为了可靠性，请使用循环方案。
|