ประสิทธิภาพของ JavaScript Set กับ Array

มันอาจเป็นเพราะ Set ค่อนข้างใหม่สำหรับ JavaScript แต่ฉันยังไม่สามารถหาบทความใด ๆ ทั้งบน Stack Overflow หรือที่อื่น ๆ ที่พูดถึงความแตกต่างด้านประสิทธิภาพระหว่างทั้งสองใน JavaScript ดังนั้น ความแตกต่างด้านประสิทธิภาพระหว่างทั้งสองคืออะไร โดยเฉพาะเมื่อพูดถึงการลบ การเพิ่ม และการวนรอบ

คำตอบ #1

ตกลง ฉันได้ทดสอบการเพิ่ม การวนซ้ำ และการลบองค์ประกอบจากทั้งอาร์เรย์และเซตแล้ว ฉันได้ทำการทดสอบ "เล็ก" โดยใช้ 10,000 องค์ประกอบ และการทดสอบ "ใหญ่" โดยใช้ 100,000 องค์ประกอบ นี่คือผลลัพธ์

การเพิ่มองค์ประกอบลงในคอลเล็กชัน

ดูเหมือนว่าวิธีการอาเรย์ .push จะเร็วกว่าวิธีการเซ็ต .add ประมาณ 4 เท่า ไม่ว่าจะเพิ่มจำนวนองค์ประกอบเท่าใดก็ตาม

การวนซ้ำและการแก้ไของค์ประกอบในคอลเลกชัน

สำหรับส่วนนี้ของการทดสอบ ฉันใช้ for ลูปเพื่อวนซ้ำผ่านอาร์เรย์ และใช้ for of ลูปเพื่อวนซ้ำผ่านเซ็ต อีกครั้ง การวนซ้ำผ่านอาร์เรย์เร็วกว่าการวนซ้ำผ่านเซ็ต ในครั้งนี้ดูเหมือนว่าจะเร็วขึ้นอย่างทวีคูณเนื่องจากใช้เวลานานกว่าถึงสองเท่าในระหว่างการทดสอบ "ขนาดเล็ก" และเกือบสี่เท่าในระหว่างการทดสอบ "ขนาดใหญ่"

การลบองค์ประกอบออกจากคอลเลกชัน

ตอนนี้นี่แหละที่มันเริ่มน่าสนใจ ผมใช้การผสมผสานระหว่างลูป for และ .splice เพื่อเอาบางสมาชิกออกจากอาร์เรย์ และผมใช้ for of และ .delete เพื่อเอาบางสมาชิกออกจากเซต สำหรับการทดสอบแบบ "เล็ก" การเอาไอเท็มออกจากเซตเร็วกว่าการเอาออกจากอาร์เรย์ประมาณสามเท่า (2.6 มิลลิวินาที กับ 7.1 มิลลิวินาที) แต่สิ่งต่าง ๆ เปลี่ยนไปอย่างมากสำหรับการทดสอบแบบ "ใหญ่" ซึ่งต้องใช้เวลา 1955.1 มิลลิวินาทีในการเอาไอเท็มออกจากอาร์เรย์ ในขณะที่เอาออกจากเซตใช้เวลาเพียง 83.6 มิลลิวินาที เร็วกว่าถึง 23 เท่า

ข้อสรุป

ที่ 10k อิลิเมนต์ ทั้งสองการทดสอบใช้เวลาใกล้เคียงกัน (อาร์เรย์: 16.6 มิลลิวินาที, เซ็ต: 20.7 มิลลิวินาที) แต่เมื่อทำงานกับ 100k อิลิเมนต์ เซ็ตเป็นฝ่ายชนะอย่างชัดเจน (อาร์เรย์: 1974.8 มิลลิวินาที, เซ็ต: 83.6 มิลลิวินาที) แต่เป็นเพียงเพราะการลบเท่านั้น มิฉะนั้นอาร์เรย์จะเร็วกว่าครับ ฉันไม่สามารถบอกได้ว่าทำไมถึงเป็นแบบนั้น

ฉันได้ลองเล่นกับบางสถานการณ์ผสมซึ่งมีการสร้างอาร์เรย์และเติมข้อมูล จากนั้นแปลงเป็นเซตซึ่งจะมีการลบบางองค์ประกอบออก จากนั้นเซตก็จะถูกแปลงกลับเป็นอาร์เรย์ แม้ว่าการทำเช่นนี้จะให้ประสิทธิภาพที่ดีกว่าการลบองค์ประกอบในอาร์เรย์โดยตรง แต่เวลาประมวลผลเพิ่มเติมที่ใช้ในการโอนย้ายไปและกลับจากเซตนั้นมากกว่าผลประโยชน์ของการเติมข้อมูลในอาร์เรย์แทนการใช้เซต สุดท้าย การจัดการกับเซตเพียงอย่างเดียวจะเร็วกว่า อย่างไรก็ตาม นี่เป็นไอเดียที่น่าสนใจ ว่าหากใครเลือกที่จะใช้แอเรย์เป็นที่เก็บข้อมูลสำหรับข้อมูลขนาดใหญ่ที่ไม่มีค่าซ้ำ อาจจะเป็นประโยชน์ในแง่ประสิทธิภาพ หากเคยมีความจำเป็นต้องลบหลายองค์ประกอบในหนึ่งการดำเนินการ การแปลงอาร์เรย์เป็นเซต ทำการลบ แล้วแปลงเซตกลับเป็นอาร์เรย์ก็สามารถช่วยได้

รหัสอาเรย์:

var timer = function(name) {
  var start = new Date();
  return {
    stop: function() {
      var end = new Date();
      var time = end.getTime() - start.getTime();
      console.log('Timer:', name, 'finished in', time, 'ms');
    }
  }
};

var getRandom = function(min, max) {
  return Math.random() * (max - min) + min;
};

var lastNames = ['SMITH', 'JOHNSON', 'WILLIAMS', 'JONES', 'BROWN', 'DAVIS', 'MILLER', 'WILSON', 'MOORE', 'TAYLOR', 'ANDERSON', 'THOMAS'];

var genLastName = function() {
  var index = Math.round(getRandom(0, lastNames.length - 1));
  return lastNames[index];
};

var sex = ["Male", "Female"];

var genSex = function() {
  var index = Math.round(getRandom(0, sex.length - 1));
  return sex[index];
};

var Person = function() {
  this.name = genLastName();
  this.age = Math.round(getRandom(0, 100))
  this.sex = "Male"
};

var genPersons = function() {
  for (var i = 0; i < 100000; i++)
    personArray.push(new Person());
};

var changeSex = function() {
  for (var i = 0; i < personArray.length; i++) {
    personArray[i].sex = genSex();
  }
};

var deleteMale = function() {
  for (var i = 0; i < personArray.length; i++) {
    if (personArray[i].sex === "Male") {
      personArray.splice(i, 1)
      i--
    }
  }
};

var t = timer("Array");

var personArray = [];

genPersons();

changeSex();

deleteMale();

t.stop();

console.log("Done! There are " + personArray.length + " persons.")

ตั้งรหัส:

var timer = function(name) {
    var start = new Date();
    return {
        stop: function() {
            var end  = new Date();
            var time = end.getTime() - start.getTime();
            console.log('Timer:', name, 'finished in', time, 'ms');
        }
    }
};

var getRandom = function (min, max) {
  return Math.random() * (max - min) + min;
};

var lastNames = ['SMITH','JOHNSON','WILLIAMS','JONES','BROWN','DAVIS','MILLER','WILSON','MOORE','TAYLOR','ANDERSON','THOMAS'];

var genLastName = function() {
    var index = Math.round(getRandom(0, lastNames.length - 1));
    return lastNames[index];
};

var sex = ["Male", "Female"];

var genSex = function() {
    var index = Math.round(getRandom(0, sex.length - 1));
    return sex[index];
};

var Person = function() {
	this.name = genLastName();
	this.age = Math.round(getRandom(0,100))
	this.sex = "Male"
};

var genPersons = function() {
for (var i = 0; i < 100000; i++)
	personSet.add(new Person());
};

var changeSex = function() {
	for (var key of personSet) {
		key.sex = genSex();
	}
};

var deleteMale = function() {
	for (var key of personSet) {
		if (key.sex === "Male") {
			personSet.delete(key)
		}
	}
};

var t = timer("Set");

var personSet = new Set();

genPersons();

changeSex();

deleteMale();

t.stop();

console.log("Done! There are " + personSet.size + " persons.")

คำตอบ #2

ข้อสังเกต:

• การดำเนินการชุดสามารถเข้าใจได้เหมือนภาพสแนปช็อตภายในกระแสการประมวลผล
• เรายังไม่ได้อยู่ต่อหน้าตัวทดแทนที่แน่นอน
• องค์ประกอบของ คลาสเซต ไม่มีดัชนีที่เข้าถึงได้
• คลาสเซต เป็น คลาสอาร์เรย์ ที่เสริมเติม ซึ่งมีประโยชน์ในสถานการณ์ที่เราจำเป็นต้องเก็บชุดข้อมูลเพื่อใช้ในการดำเนินการพื้นฐานเช่น การเพิ่ม ลบ การตรวจสอบ และการวนซ้ำ

ฉันจะแชร์การทดสอบประสิทธิภาพบางอย่าง ลองเปิดคอนโซลของคุณแล้วคัดลอกโค้ดด้านล่างไปวาง

การสร้างอาร์เรย์ (125000)

var n = 125000;
var arr = Array.apply( null, Array( n ) ).map( ( x, i ) => i );
console.info( arr.length ); // 125000

1. การค้นหาดัชนี

เราทำการเปรียบเทียบเมทอด has ของ Set กับ indexOf ของ Array:

Array/indexOf (0.281มิลลิวินาที) | Set/has (0.053มิลลิวินาที)

// Helpers
var checkArr = ( arr, item ) => arr.indexOf( item ) !== -1;
var checkSet = ( set, item ) => set.has( item );

// Vars
var set, result;

console.time( 'timeTest' );
result = checkArr( arr, 123123 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
checkSet( set, 123123 );
console.timeEnd( 'timeTest' );

2. การเพิ่มองค์ประกอบใหม่

เราจะเปรียบเทียบเมธอด add และ push ของออบเจ็กต์ Set และ Array ตามลำดับ:

อาร์เรย์/push (1.612มิลลิวินาที) | เซ็ต/add (0.006มิลลิวินาที)

console.time( 'timeTest' );
arr.push( n + 1 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
set.add( n + 1 );
console.timeEnd( 'timeTest' );

console.info( arr.length ); // 125001
console.info( set.size ); // 125001

3. การลบองค์ประกอบ

เมื่อการลบองค์ประกอบ เราต้องจำไว้ว่ามิเตอร์และเซ็ตไม่ได้เริ่มต้นภายใต้เงื่อนไขที่เท่าเทียมกัน อาร์เรย์ไม่มีวิธีการมาตรฐานในตัว ดังนั้นจึงจำเป็นต้องใช้ฟังก์ชันภายนอก

Array/deleteFromArr (0.356มิลลิวินาที) | Set/remove (0.019มิลลิวินาที)

var deleteFromArr = ( arr, item ) => {
    var i = arr.indexOf( item );
    i !== -1 && arr.splice( i, 1 );
};

console.time( 'timeTest' );
deleteFromArr( arr, 123123 );
console.timeEnd( 'timeTest' );

set = new Set( arr );

console.time( 'timeTest' );
set.delete( 123123 );
console.timeEnd( 'timeTest' );

อ่านบทความฉบับเต็มที่นี่

คำตอบ #3

เพียงแค่การค้นหาอสังหาริมทรัพย์ เขียนน้อยหรือแทบไม่มี

ถ้าการค้นหาทรัพย์สินเป็นความกังวลหลักของคุณ นี่คือตัวเลขบางส่วน

การทดสอบ JSBench

• v2: https://jsbench.me/3pkjlwzhbr/2
• v1: https://jsbench.me/3pkjlwzhbr/1

// https://jsbench.me/3pkjlwzhbr/1
// https://docs.google.com/spreadsheets/d/1WucECh5uHlKGCCGYvEKn6ORrQ_9RS6BubO208nXkozk/edit?usp=sharing
// JSBench forked from https://jsbench.me/irkhdxnoqa/2

var theArr = Array.from({ length: 10000 }, (_, el) => el)
var theSet = new Set(theArr)
var theObject = Object.assign({}, ...theArr.map(num => ({ [num]: true })))
var theMap = new Map(theArr.map(num => [num, true]))

var theTarget = 9000


// Array

function isTargetThereFor(arr, target) {
  const len = arr.length
  for (let i = 0; i < len; i++) {
    if (arr[i] === target) {
      return true
    }
  }
  return false
}
function isTargetThereForReverse(arr, target) {
  const len = arr.length
  for (let i = len; i > 0; i--) {
    if (arr[i] === target) {
      return true
    }
  }
  return false
}

function isTargetThereIncludes(arr, target) {
  return arr.includes(target)
}

// Set

function isTargetThereSet(numberSet, target) {
  return numberSet.has(target)
}

// Object 

function isTargetThereHasOwnProperty(obj, target) {
  return obj.hasOwnProperty(target)
}
function isTargetThereIn(obj, target) {
  return target in obj
}
function isTargetThereSelectKey(obj, target) {
  return obj[target]
}

// Map

function isTargetThereMap(numberMap, target) {
  return numberMap.has(target)
}

อาเรย์

• ลูป for
• ลูป for (ย้อนกลับ)

• array.includes(target)

ชุด

• set.has(target)

วัตถุ

• obj.hasOwnProperty(target)

• target in obj <- เร็วที่สุด
• obj[target] <- เร็วที่สุด

แผนที่

• map.has(target)

ผลลัพธ์จาก มกราคม 2024, Chrome 121

สิ่งที่น่าสนใจในผลลัพธ์นี้คือ map.has กลายเป็นช้าลงอย่างกะทันหันจนมีความเร็วเท่ากับ set.has (ความคิดเห็น)

ผลลัพธ์จาก กุมภาพันธ์ 2022, Chrome 98

ผลลัพธ์จาก มกราคม 2021, Chrome 87

ผลลัพธ์จากเบราว์เซอร์อื่น ๆ ยินดีต้อนรับมาก โปรดอัปเดตคำตอบนี้
คุณสามารถใช้สเปรดชีตนี้เพื่อสร้างภาพหน้าจอที่สวยงามได้

การทดสอบ JSBench แยกออกมาจากคำตอบของ Zargold.

คำตอบ #4

มาพิจารณากรณีที่คุณต้องการเก็บชุดของค่าที่ไม่ซ้ำกัน คุณสามารถจำลองการทำงานเกือบทั้งหมดของ Set โดยใช้ array: เพิ่ม, ลบ, มี, ล้าง, และ ขนาด.

เราสามารถทำซ้ำได้เช่นกัน แต่โปรดทราบว่ามันจะไม่ทำงานเหมือนกับ Set สิ่งที่คุณสามารถทำได้ใน Set คือสามารถปรับเปลี่ยนได้อย่างปลอดภัยในระหว่างการทำซ้ำโดยไม่พลาดองค์ประกอบ แต่สิ่งเดียวกันนี้ไม่เป็นจริงสำหรับอาร์เรย์ ดังนั้นการเปรียบเทียบตรงนั้นจึงไม่ยุติธรรมสำหรับทุกกรณีการใช้งาน

/** Set implemented using an array internally */
class ArraySet{
    constructor(){
        this._arr = [];
    }
    add(value){
        if (this._arr.indexOf(value) === -1)
            this._arr.push(value);
        return this;
    }
    delete(value){
        const idx = this._arr.indexOf(value);
        if (idx !== -1){
            this._arr.splice(idx,1);
            return true;
        }
        return false;
    }
    has(value){
        return this._arr.indexOf(value) !== -1;
    }
    clear(){
        this._arr.length = 0;
    }
    // Note: iterating is not safe from modifications
    values(){   
        return this._arr.values();
    }
    [Symbol.iterator](){
        return this._arr[Symbol.iterator]();
    }
}

แม้ว่า Set จะมีความซับซ้อนเชิงอัลกอริทึมที่ดีกว่า (O(1) เทียบกับการดำเนินการ O(n) ของ ArraySet) แต่มันมีภาระเพิ่มเติมเล็กน้อยในการดูแลโครงสร้างต้นไม้/แฮชภายในของมัน ขนาดเท่าใดที่ภาระของ Set จะคุ้มค่า? นี่คือข้อมูลที่ฉันรวบรวมจากการทดสอบประสิทธิภาพ NodeJS v18.12 สำหรับกรณีการใช้งานทั่วไป (ดูโค้ด benchmarking)

ตามที่คาดไว้ เราจะเห็นข้อได้เปรียบด้านอัลกอริธึม O(n) สำหรับ Set เมื่อมีหลายองค์ประกอบ สำหรับค่าใช้จ่ายเบื้องต้น:

• ขนาด: ความเร็วเท่ากัน
• add: รูปแบบที่น่าสนใจเกิดขึ้น ซึ่งประสิทธิภาพของ Set จะขึ้นลงขึ้นอยู่กับขนาดของมัน โดยทั่วไป array จะเร็วกว่าเมื่อมีสมาชิกน้อยกว่า 33 ตัว และ Set จะเร็วกว่าเสมอเมื่อมีสมาชิกมากกว่า 52 ตัว
• delete: อาร์เรย์เร็วกว่าสำหรับ < 10 อิลิเมนต์
• has: อาร์เรย์เร็วกว่าสำหรับ < 20 อิลิเมนต์
• values: เซ็ตมักจะเร็วกว่าตลอดเวลา
• ตัวทำซ้ำ (เช่น ลูป for-of): Set มักจะเร็วกว่าตลอด

ในการปฏิบัติจริง คุณมีแนวโน้มที่จะไม่สร้างคลาส ArraySet ของคุณเอง และแทนที่จะทำเช่นนั้นจะฝังการดำเนินการเฉพาะที่คุณสนใจสมมติว่าการดำเนินการบนอาเรย์ถูกฝัง การทำงานจะเปลี่ยนแปลงไปอย่างไร?

ผลลัพธ์เกือบจะเหมือนกันทั้งหมด ยกเว้นตอนนี้ประสิทธิภาพการวนซ้ำได้ดีขึ้นสำหรับ Array วงวน for-of ที่ฝังตัว (ไม่ผ่านคลาสห่อหุ้ม ArraySet) ตอนนี้เร็วกว่าการใช้ Set เสมอ ตัววนซ้ำ values มีความเร็วประมาณเท่ากัน