Cara menghindari Time Complexity O(n²) saat mapping data

ok disini saya menganjurkan kalian untuk memahami dulu apa itu time complexity, jika kalian tertarik ada sebuah artikel yang cukup bagus untuk kalian baca Essential Programming | Time Complexity.

mari kita mulai pembahasannya, disini saya akan memberikan contoh mapping data sebuah kelas dan murid, dimana kelas itu mempunyai banyak murid

// ini adalah contoh struktur data kelas dengan murid yang masih kosong
const classes = [
  {
    name: 'Class 1',
    id: 1,
    students: [],
  },
  {
    name: 'Class 2',
    id: 2,
    students: [],
  },
];

// ini adalah contoh data murid
const students = [
  {
    name: 'Sarah',
    id: 1,
    classId: 1,
  },
  {
    name: 'Rudi',
    id: 2,
    classId: 1,
  },
  {
    name: 'Azka',
    id: 3,
    classId: 2,
  },
  {
    name: 'Ainun',
    id: 4,
    classId: 2,
  },
];

sebagai contoh kita akan mapping data students dan memasukannya ke dalam array yang ada pada di property ‘students’ pada ‘class’.

saya akan memberi contoh code yang menyentuh Time Complexity O(n²)

const data = classes.map(item => {
  const student = [];

  for (let i = 0; i < students.length; i++) {
    const s = students[i];

    if (s.classId === item.id) {
      student.push(s);
    }
  }

  return {
    ...item,
    students: student,
  };
});

jika kalian lihat lebih dalam, code tersebut menjalankan looping pada array students sebanyak banyaknya jumlah data dari ‘classes’, bisa saja si student dengan id 1 akan keluar lagi pada looping ‘classes’ selanjutnya, maka code ini tidak efisien.

cara paling gampang adalah dengan menggunakan ‘Map’, lalu kenapa kita menggunakan map?, singkat saja karena ketika kita mengakses data pada map Time Complexity nya adalah O (1).

tapi harus ada beberapa hal harus kalian perhatikan, pertama kalian harus cek terlebih dahulu property apa pada object tersebut yang bisa di jadikan key untuk mengambil datanya, untuk contoh data di atas kita bisa menggunakan classId pada student, karena property classId memiliki value yang sama dengan id yang ada pada data ‘classes’, kalo kalian masih bingung, logic ini seperti join pada sql, harus ada field dengan value yang sama.

ok sekarang kita akan masukan data student kepada map dengan key value dari property classId

const mappedStudents = new Map();

// loop students
for (let i = 0; i < students.length; i++) {
  const student = students[i];

  // check if key with classId is not in the map
  if (!mappedStudents.has(student.classId)) {
    // create new key with classId and empty array as value
    mappedStudents.set(student.classId, []);
  }

  // push student to the array
  mappedStudents.get(student.classId).push(student);
}

setelah kita memindahkan data students kepada Map, kita akan lebih mudah unutk mengambil datanya.

for (let i = 0; i < classes.length; i++) {
  const classItem = classes[i];

  // check if key with classId is in the map
  if (mappedStudents.has(classItem.id)) {
    // assign students to the class
    classItem.students = mappedStudents.get(classItem.id);
  }
}

code di atas adalah cara untuk mengakses data student pada Map

dibawah ini adalah contoh code yang lengkap

const classes = [
  {
    name: 'Class 1',
    id: 1,
    students: [],
  },
  {
    name: 'Class 2',
    id: 2,
    students: [],
  },
];

const students = [
  {
    name: 'Sarah',
    id: 1,
    classId: 1,
  },
  {
    name: 'Rudi',
    id: 2,
    classId: 1,
  },
  {
    name: 'Azka',
    id: 3,
    classId: 2,
  },
  {
    name: 'Ainun',
    id: 4,
    classId: 2,
  },
];

const mappedStudents = new Map();

// loop students
for (let i = 0; i < students.length; i++) {
  const student = students[i];

  // check if key with classId is not in the map
  if (!mappedStudents.has(student.classId)) {
    // create new key with classId and empty array as value
    mappedStudents.set(student.classId, []);
  }

  // push student to the array
  mappedStudents.get(student.classId).push(student);
}

for (let i = 0; i < classes.length; i++) {
  const classItem = classes[i];

  // check if key with classId is in the map
  if (mappedStudents.has(classItem.id)) {
    // assign students to the class
    classItem.students = mappedStudents.get(classItem.id);
  }
}

console.log(classes)

perlu diperhatikan jika dengan data sedikit ini tidak akan terlalu terasa perubahan performanya, tapi jika kalian memiliki data yang cukup besar ini adalah teknik yang bisa dipakai dan mudah digunakan untuk mengoptimasi code kalian.