Benchmark: indexOf lookup vs initial map then sort

Script Preparation code:

var unsorted = [168,252,410,60,18,233,189,244,179,487,383,461,7,150,30,429,16,394,153,404,250,288,147,400,269,278,467,433,326,127,264,17,280,275,199,441,408,86,417,359,177,64,422,425,361,322,54,435,349,386,105,92,133,462,73,247,214,493,445,281,384,446,497,25,412,259,260,125,14,268,124,75,471,235,178,319,351,113,26,272,8,403,407,460,162,76,135,182,66,129,256,206,82,382,85,449,277,473,155,297,137,149,118,228,339,255,330,401,320,468,334,32,31,38,3,344,194,243,71,119,227,222,348,175,192,483,477,111,378,267,350,134,354,56,47,481,389,285,77,325,420,218,472,465,143,258,238,494,253,90,130,302,5,232,459,304,33,409,246,62,81,176,165,466,303,341,317,123,91,212,112,266,249,366,148,103,59,489,245,451,152,160,336,265,61,469,356,183,375,390,418,27,51,395,371,139,431,438,159,485,296,273,241,184,331,216,353,202,142,486,315,70,343,314,13,58,117,367,328,495,324,262,132,381,96,369,499,114,240,376,360,271,201,80,15,470,55,242,498,169,146,347,37,365,327,52,211,492,226,298,145,46,453,274,166,200,6,79,316,357,74,102,463,293,346,488,426,43,254,380,391,364,229,34,294,69,335,110,144,289,170,21,57,414,109,188,35,9,338,20,448,190,450,87,287,158,204,121,437,1,455,399,230,213,309,136,312,101,270,180,491,484,313,342,44,490,406,29,402,370,100,49,128,140,220,151,24,223,416,363,427,12,397,72,340,398,436,251,310,154,434,411,307,197,39,323,332,28,443,458,167,234,428,156,457,283,318,452,263,421,396,419,286,447,423,224,161,475,358,99,195,63,442,388,225,352,65,393,141,209,237,219,231,257,373,50,181,387,196,116,131,171,104,377,301,345,0,198,379,164,424,115,95,276,97,208,248,282,186,83,19,300,415,40,385,4,207,337,413,474,215,138,67,439,482,355,36,84,187,22,464,98,239,368,405,372,41,392,430,311,321,193,440,374,329,89,292,444,78,88,45,68,299,157,362,108,163,205,210,106,221,203,217,191,94,478,305,279,2,496,476,308,290,53,480,479,122,120,291,295,173,23,93,42,185,454,172,261,432,126,333,174,10,306,456,284,236,107,11,48];
var sortedIndices = [];
for(i=0; i<500; i++){
  sortedIndices.push(i);  
}

Tests:

unsorted sorting via indexOf lookup
[...unsorted].sort( (a, b) => sortedIndices.indexOf(a) - sortedIndices.indexOf(b) )
map then sort
sortedIndices.map((o, i) => { return {i, o}; }).sort((a, b) => a.o - b.o).map(io => unsorted[io.i])

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
unsorted sorting via indexOf lookup
map then sort

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Linux; Android 12; M2102J20SG) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/110.0.5481.192 Mobile Safari/537.36 OPR/74.1.3922.71199

Browser/OS: Opera Mobile 74 on Android

View result in a separate tab

Test name	Executions per second
unsorted sorting via indexOf lookup	752.0 Ops/sec
map then sort	14562.0 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated 2 months ago):

LLMs can make mistakes. Check important info.

I'll break down the provided benchmark and explain what's being tested, compared options, pros and cons of those approaches, and other considerations.

**Benchmark Definition**

The benchmark is testing two different approaches to sort an array:

1. **Unsorted sorting via indexOf lookup**: This approach uses the `indexOf` method to find the index of each element in the sorted array (`sortedIndices`) and then uses that index to retrieve the corresponding element from the original unsorted array (`unsorted`). The elements are sorted based on their indices.
2. **Map then sort**: This approach first maps the `sortedIndices` array to an array of objects with two properties: `i` (the index) and `o` (the value). Then, it sorts this new array by the `o` property using the `sort()` method. Finally, it maps the sorted array back to the original unsorted array (`unsorted`) using the `indexOf` method.

**Comparison Options**

The benchmark is comparing two approaches:

1. **Unsorted sorting via indexOf lookup**: This approach uses the `indexOf` method to find elements in the sorted array.
2. **Map then sort**: This approach first maps the sorted indices to an array of objects and then sorts this new array using the `sort()` method.

**Pros and Cons**

Here are some pros and cons for each approach:

1. **Unsorted sorting via indexOf lookup**:
	* Pros: Simple and efficient, as it only requires a single pass through the sorted array.
	* Cons: The performance of `indexOf` can be slow for large arrays, especially if the elements are not present in the sorted array.
2. **Map then sort**:
	* Pros: Can be more efficient than the first approach, as it avoids the overhead of repeated `indexOf` calls.
	* Cons: Requires an additional pass through the sorted array to create the mapping objects, which can be slower.

**Other Considerations**

1. **Libraries**: The benchmark uses the `sortedIndices` array and the `unsorted` array, but no external libraries are mentioned.
2. **Algorithm complexity**: Both approaches have a time complexity of O(n log n), where n is the length of the sorted array.
3. **Cache friendliness**: The first approach may be more cache-friendly, as it only requires a single pass through the sorted array, while the second approach requires multiple passes.

**Latest Benchmark Results**

The latest results show that:

1. The **map then sort** approach performs better than the **unsorted sorting via indexOf lookup** approach.
2. Both approaches have similar performance on mobile devices (Opera Mobile 74) compared to desktop browsers.

Please note that benchmarking results can vary depending on various factors, such as hardware, software, and testing conditions.

Related benchmarks:

indexOf lookup vs initial map then sort (version: 0)

Comparing performance of: unsorted sorting via indexOf lookup vs map then sort

Created: one year ago by: Guest

Jump to the latest result

unsorted sorting via indexOf lookup

map then sort

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 2 months ago):