Cấu trúc dữ liệu -Tổng quan về Big-O


 


Ký hiệu Big-O là ký hiệu toán học được sử dụng để mô tả hiệu suất hoặc độ phức tạp của thuật toán, cụ thể là thời gian chạy của thuật toán khi kích thước đầu vào tăng lên. Hiểu ký hiệu Big-O là điều cần thiết đối với các kỹ sư phần mềm vì nó cho phép họ phân tích và so sánh hiệu quả của các thuật toán khác nhau và đưa ra quyết định sáng suốt về việc nên sử dụng thuật toán nào trong một tình huống nhất định. Trong hướng dẫn này, chúng tôi sẽ đề cập đến những kiến ​​thức cơ bản về ký hiệu Big-O và cách sử dụng nó để phân tích hiệu suất của các thuật toán.


Big-O là gì?

Ký hiệu Big-O là cách thể hiện độ phức tạp về thời gian (hoặc không gian) của thuật toán. Nó cung cấp ước tính sơ bộ về thời gian chạy của một thuật toán (hoặc lượng bộ nhớ mà nó sử dụng), dựa trên kích thước của đầu vào. Ví dụ: một thuật toán có độ phức tạp về thời gian có nghĩa là thời gian chạy tăng tuyến tính theo kích thước của đầu vào.


Độ phức tạp theo thời gian là gì?

Độ phức tạp về thời gian là thước đo thời gian chạy của một thuật toán, dựa trên kích thước của đầu vào. Nó được thể hiện bằng ký hiệu Big-O, cung cấp ước tính sơ bộ về thời gian chạy. Thuật toán có độ phức tạp thời gian thấp hơn thường sẽ nhanh hơn thuật toán có độ phức tạp thời gian cao hơn.


Độ phức tạp theo không gian là gì?

Độ phức tạp của không gian là thước đo lượng bộ nhớ mà thuật toán yêu cầu, dựa trên kích thước của đầu vào. Giống như độ phức tạp về thời gian, nó được thể hiện bằng ký hiệu Big-O. Thuật toán có độ phức tạp không gian thấp hơn thường sẽ yêu cầu ít bộ nhớ hơn thuật toán có độ phức tạp không gian cao hơn.


Ví dụ về độ phức tạp theo thời gian?

Dưới đây là một số ví dụ về cách thể hiện độ phức tạp thời gian khác nhau bằng cách sử dụng ký hiệu Big-O:

  • O(1): Thời gian không đổi. Thời gian chạy không phụ thuộc vào kích thước của đầu vào.
  • O(n): Thời gian tuyến tính. Thời gian chạy tăng tuyến tính với kích thước của đầu vào, nói một cách dễ hiểu thì nếu dữ liệu tăng gấp 10 lần thì thời gian tốn gấp 10 lần
  • O(n^2): Thời gian bậc hai. Thời gian chạy tỷ lệ thuận với bình phương kích thước của đầu vào.
  • O(logn): Thời gian logarit. Thời gian chạy tăng logarit theo kích thước của đầu vào.
  • O(2^n): Thời gian theo cấp số nhân. Thời gian chạy tăng theo cấp số nhân theo kích thước của đầu vào.


Điều quan trọng cần lưu ý là ký hiệu Big-O chỉ cung cấp giới hạn trên về thời gian chạy của thuật toán. Điều này có nghĩa là một thuật toán có độ phức tạp về thời gian O(n) có khả năng chạy nhanh hơn thuật toán có độ phức tạp về thời gian O(logn) trong một số trường hợp, tùy thuộc vào cách triển khai cụ thể và phần cứng đang được sử dụng.

Ngoài ra, ký hiệu Big-O chỉ xem xét thuật ngữ chiếm ưu thế trong phương trình thời gian chạy. Ví dụ: một thuật toán có thời gian chạy O(n^2 +n) sẽ được đơn giản hóa thành O(n^2).


Các thuật toán mẫu và độ phức tạp về thời gian của chúng

Dưới đây là một số ví dụ về thuật toán cùng với độ phức tạp về thời gian của chúng được biểu thị bằng ký hiệu Big-O:

1. Linear search - O(n)

 function linearSearch(arr, x) {  
   for (let i = 0; i < arr.length; i++) {  
     if (arr[i] === x) {  
       return i;  
     }  
   }  
   return -1;  
 }  
 // Usage  
 const arr = [3, 5, 7, 9, 11];  
 const x = 7;  
 console.log(linearSearch(arr, x));  // => 2

Thuật toán tìm kiếm tuyến tính này có độ phức tạp về thời gian là O(n) , vì thời gian chạy tỷ lệ thuận với kích thước của đầu vào. Nếu kích thước đầu vào là n , tìm kiếm tuyến tính sẽ mất n bước để hoàn thành.

2. Binary search - O(logn)

 class Solution {  
   static binarySearch(arr, x) {  
     let low = 0;  
     let high = arr.length - 1;  
     while (low <= high) {  
       let mid = Math.floor((low + high) / 2);  
       if (arr[mid] < x) {  
         low = mid + 1;  
       } else if (arr[mid] > x) {  
         high = mid - 1;  
       } else {  
         return mid;  
       }  
     }  
     return -1;  
   }  
 }  
 // Usage  
 const arr = [2, 3, 4, 10, 40];  
 const x = 10;  
 console.log(Solution.binarySearch(arr, x));

Thuật toán tìm kiếm nhị phân này có độ phức tạp về thời gian là O(logn) , vì thời gian chạy tăng logarit theo kích thước của đầu vào. Nếu kích thước đầu vào là n, sẽ mất khoảng logn các bước để hoàn thành tìm kiếm nhị phân.

Tại sao thời gian chạy là O(log n)?

Trong tìm kiếm nhị phân, tại mỗi bước, phạm vi tìm kiếm giảm đi một nửa. Giả sử mảng có kích thước n:

  • Bước đầu tiên: n phần tử.
  • Bước thứ hai: n/2 phần tử.
  • Bước thứ ba: n/4 phần tử.
  • ...

Quá trình này tiếp tục cho đến khi phạm vi tìm kiếm chỉ còn 1 phần tử. Số bước để đạt được điều này là số lần chia n cho 2 cho đến khi còn lại 1, tức là log cơ số 2 của n (log₂(n)). Do đó, số bước là O(log n).

Nếu mảng arr có 16 phần tử (n = 16):

  1. Lần 1: Phạm vi tìm kiếm là 16 phần tử.
  2. Lần 2: Phạm vi tìm kiếm là 8 phần tử.
  3. Lần 3: Phạm vi tìm kiếm là 4 phần tử.
  4. Lần 4: Phạm vi tìm kiếm là 2 phần tử.
  5. Lần 5: Phạm vi tìm kiếm là 1 phần tử.

Số bước cần thiết là log⁡2(16)=4\log_2(16) = 4

Với mảng có 5 phần tử, thuật toán tìm kiếm nhị phân sẽ cần khoảng log⁡2(5)\log_2(5) bước.

log2​(5)≈2.32

Làm tròn lên, chúng ta sẽ cần 3 bước để hoàn thành tìm kiếm.


3. Bubble sort -O(n^2)

 class Solution {  
   static bubbleSort(arr) {  
     let n = arr.length;  
     for (let i = 0; i < n; i++) {  
       for (let j = 0; j < n - i - 1; j++) {  
         if (arr[j] > arr[j + 1]) {  
           [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];  
         }  
       }  
     }  
   }  
 }  
 // Usage  
 const arr = [64, 34, 25, 12, 22, 11, 90];  
 Solution.bubbleSort(arr);  
 console.log("Sorted array is:", arr);

Độ phức tạp thời gian

  1. Vòng lặp ngoài (for loop với i):

    • Chạy từ 0 đến n-1.
    • Tổng số lần lặp là n.

  2. Vòng lặp trong (for loop với j):

    • Trong mỗi lần lặp của vòng lặp ngoài, vòng lặp này chạy từ 0 đến n-i-2.
    • Tổng số lần lặp của vòng lặp trong phụ thuộc vào giá trị của i và là n-i-1.

Tổng số lần lặp

Để tính tổng số lần lặp của vòng lặp trong qua tất cả các lần lặp của vòng lặp ngoài:

∑i=0n−1(n−i−1)\sum_{i=0}^{n-1} (n - i - 1)

Đây là một chuỗi số học và có thể được tính như sau:

∑i=0n−1(n−i−1)=(n−1)+(n−2)+…+1+0\sum_{i=0}^{n-1} (n - i - 1) = (n - 1) + (n - 2) + \ldots + 1 + 0


Áp dụng công thức tính tổng của n số nguyên liên tiếp chúng ta sẽ được:

n(n−1)2\frac{n(n - 1)}{2}

Độ phức tạp bậc lớn nhất

Khi tính toán độ phức tạp, chúng ta chỉ quan tâm đến bậc lớn nhất, vì nó chiếm ưu thế khi n lớn. Trong trường hợp này, bậc lớn nhất là n2n^2.


4. Quick Sort - O(n*logn)

 class Solution {  
   static quickSort(arr) {  
     if (arr.length <= 1) return arr;  
     let pivot = arr[Math.floor(arr.length / 2)];  
     let left = arr.filter(x => x < pivot);  
     let middle = arr.filter(x => x === pivot);  
     let right = arr.filter(x => x > pivot);  
     return [...Solution.quickSort(left), ...middle, ...Solution.quickSort(right)];  
   }  
 }  
 // Usage  
 const arr = [3, 6, 8, 10, 1, 2, 1];  
 const sortedArr = Solution.quickSort(arr);  
 console.log("Sorted array:", sortedArr);


Phân tích độ phức tạp

  • Trong mỗi bước phân chia, thuật toán Quicksort chọn một pivot và phân chia mảng thành hai phần: phần bên trái và phần bên phải của pivot.
  • Độ dài của các phần này trong trường hợp lý tưởng sẽ là gần như bằng nhau.

Chi Phí của Một Phân Chia

  • Chi phí của việc phân chia một mảng có n phần tử là O(n), vì mỗi phần tử trong mảng phải được so sánh với pivot.

Số bước đệ quy

  • Tổng số cấp độ phân chia là log n vì bạn cần log n lần phân chia để giảm kích thước của mảng từ n phần tử xuống còn 1.
  • Ở mỗi cấp độ phân chia, mảng được chia thành hai phần nhỏ hơn. Số cấp độ phân chia là log n (trong trường hợp lý tưởng), vì mỗi phân chia làm giảm kích thước của mảng còn khoảng một nửa.

Tổng độ phức tạp

  • Số cấp độ phân chia là O(log n)
  • Chi phí phân chia mỗi cấp là O(n)

5. Fibonacci sequence - O(2^n)

 class Solution {  
   static fibonacci(n) {  
     if (n === 0) return 0;  
     if (n === 1) return 1;  
     return Solution.fibonacci(n - 1) + Solution.fibonacci(n - 2);  
   }  
 }  
 // Usage  
 const n = 10; // Example input  
 console.log(`Fibonacci number at position ${n} is ${Solution.fibonacci(n)}`);


Phân tích độ phức tạp

Khi n=5, cây đệ quy của các lời gọi hàm trông như sau

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3)
│   │   ├── fibonacci(2)
│   │   │   ├── fibonacci(1) -> 1
│   │   │   └── fibonacci(0) -> 0
│   │   └── fibonacci(1) -> 1
│   └── fibonacci(2)
│       ├── fibonacci(1) -> 1
│       └── fibonacci(0) -> 0
└── fibonacci(3)
    ├── fibonacci(2)
    │   ├── fibonacci(1) -> 1
    │   └── fibonacci(0) -> 0
    └── fibonacci(1) -> 1

  • Mỗi lời gọi hàm: Mỗi lời gọi hàm sẽ tạo ra hai lời gọi con, do đó số lượng lời gọi tăng theo cấp số nhân
  • Cấp độ n: Ở cấp độ n, số lượng lời gọi là 2^n

Các thuật toán mẫu và độ phức tạp về không gian của chúng

1.Linear search-O(1)
 class Solution {  
   static linearSearch(arr, x) {  
     for (let i = 0; i < arr.length; i++) {  
       if (arr[i] === x) {  
         return i;  
       }  
     }  
     return -1;  
   }  
 }  
 // Usage  
 const arr = [3, 4, 2, 7, 9];  
 const x = 7;  
 const result = Solution.linearSearch(arr, x);  
 console.log(result !== -1 ? `Element found at index ${result}` : "Element not found");
  • arr và x là các tham số đầu vào của hàm. Bộ nhớ để lưu trữ các tham số này không tính vào độ phức tạp không gian vì chúng là bộ nhớ đầu vào.
  • Biến i trong vòng lặp for là một biến đơn. Bộ nhớ cho một biến đơn là cố định, không phụ thuộc vào kích thước của arr.
  • Trong toàn bộ quá trình thực hiện của hàm, không có cấu trúc dữ liệu bổ sung nào khác được tạo ra. Chỉ có một biến đơn i được sử dụng để duyệt qua mảng.
2. Fibonacci sequence -O(n)
 class Solution {  
   static fibonacci(n) {  
     if (n === 0) return 0;  
     if (n === 1) return 1;  
     return Solution.fibonacci(n - 1) + Solution.fibonacci(n - 2);  
   }  
 }  
 // Usage  
 const n = 10; // Example input  
 console.log(`Fibonacci number at position ${n} is ${Solution.fibonacci(n)}`);
  • Ngăn xếp đệ quy (Recursive Call Stack): Mỗi lần gọi hàm đệ quy, trạng thái của hàm hiện tại được lưu trữ trên ngăn xếp để sau khi hoàn thành các lời gọi hàm con, chương trình có thể tiếp tục thực hiện hàm hiện tại. Do đó, bộ nhớ cần thiết cho ngăn xếp đệ quy phụ thuộc vào chiều sâu của cây đệ quy.
  • Chiều sâu của cây đệ quy: Trong trường hợp xấu nhất, độ sâu tối đa của cây đệ quy là n, vì chúng ta phải thực hiện các lời gọi hàm fibonacci(n-1), fibonacci(n-2),... cho đến fibonacci(0).
Vì vậy độ phức tạp không gian (Space Complexity): Mỗi lời gọi đệ quy chiếm một lượng bộ nhớ nhất định trên ngăn xếp. Chiều sâu của cây đệ quy tối đa là n, do đó độ phức tạp không gian là O(n).

3. Merge sort -O(n)
 class Solution {  
   static mergeSort(arr) {  
     if (arr.length > 1) {  
       let mid = Math.floor(arr.length / 2);  
       let left = arr.slice(0, mid);  
       let right = arr.slice(mid);  
       Solution.mergeSort(left);  
       Solution.mergeSort(right);  
       let i = 0, j = 0, k = 0;  
       while (i < left.length && j < right.length) {  
         if (left[i] < right[j]) {  
           arr[k++] = left[i++];  
         } else {  
           arr[k++] = right[j++];  
         }  
       }  
       while (i < left.length) {  
         arr[k++] = left[i++];  
       }  
       while (j < right.length) {  
         arr[k++] = right[j++];  
       }  
     }  
   }  
 }  
 // Usage  
 const arr = [12, 11, 13, 5, 6, 7];  
 Solution.mergeSort(arr);  
 console.log("Sorted array is:", arr);

Phân tích độ phức tạp không gian

Bộ nhớ bổ sung cho các mảng con
  • Chia mảng thành hai nửa: Tại mỗi bước của thuật toán, mảng đầu vào được chia thành hai mảng con left và right với kích thước tổng cộng bằng kích thước của mảng gốc.
  • Hợp nhất mảng: Quá trình hợp nhất sử dụng các biến i, j, k để theo dõi các vị trí trong các mảng con và mảng gốc. Các biến này là cố định và không phụ thuộc vào kích thước của mảng đầu vào, do đó không đóng góp vào độ phức tạp không gian.
Ngăn xếp đệ quy
  • Đệ quy: Merge Sort là một thuật toán đệ quy, do đó mỗi lời gọi hàm đệ quy yêu cầu một lượng bộ nhớ bổ sung trên ngăn xếp gọi hàm.
  • Chiều sâu của ngăn xếp đệ quy: Merge Sort chia mảng thành hai nửa tại mỗi bước, dẫn đến chiều sâu của ngăn xếp đệ quy tối đa là log(n) (vì mảng được chia đôi cho đến khi mỗi mảng con chỉ có một phần tử).
Kết hợp các yếu tố
  • Bộ nhớ cho các mảng con: Tại mỗi mức độ sâu của đệ quy, tổng kích thước của các mảng con là bằng kích thước của mảng gốc. Vì vậy, nếu không tính bộ nhớ dùng để lưu trữ mảng đầu vào ban đầu, mỗi lần chia mảng sẽ tạo ra một lượng bộ nhớ bổ sung tương đương với mảng gốc.
  • Ngăn xếp đệ quy: Chiều sâu tối đa của ngăn xếp đệ quy là log(n), mỗi mức độ sâu yêu cầu bộ nhớ bổ sung cho việc lưu trữ trạng thái của các biến và mảng con.
Độ phức tạp không gian tổng thể
  • Bộ nhớ bổ sung cho các mảng con: Mỗi bước chia mảng tạo ra các mảng con có tổng kích thước bằng kích thước của mảng gốc, dẫn đến độ phức tạp không gian là O(n).
  • Ngăn xếp đệ quy: Chiều sâu của ngăn xếp đệ quy là O(log(n)), nhưng không yêu cầu bộ nhớ bổ sung đáng kể so với các mảng con.
Vì vậy, tổng thể, độ phức tạp không gian của thuật toán Merge Sort là O(n).

4. Quick Sort -O(n)  or O(log n)
 class Solution {  
   static quickSort(arr) {  
     if (arr.length <= 1) return arr;  
     let pivot = arr[Math.floor(arr.length / 2)];  
     let left = arr.filter(x => x < pivot);  
     let middle = arr.filter(x => x === pivot);  
     let right = arr.filter(x => x > pivot);  
     return [...Solution.quickSort(left), ...middle, ...Solution.quickSort(right)];  
   }  
 }  
 // Usage  
 const arr = [3, 6, 8, 10, 1, 2, 1];  
 const sortedArr = Solution.quickSort(arr);  
 console.log("Sorted array:", sortedArr);


Phân tích độ phức tạp không gian

Bộ nhớ bổ sung cho các mảng con
  • Phân chia mảng: Tại mỗi bước của thuật toán, mảng đầu vào được chia thành ba mảng con: left, middle, và right. Mỗi mảng con này được tạo ra bằng cách lọc mảng ban đầu, do đó cần bộ nhớ bổ sung để lưu trữ chúng.
  • Hợp nhất mảng: Quá trình hợp nhất các mảng con left, middle, và right sử dụng toán tử trải (spread operator) ..., tạo ra một mảng mới từ các mảng con. Do đó, cần bộ nhớ bổ sung để lưu trữ mảng kết quả.
Ngăn xếp đệ quy
  • Đệ quy: QuickSort là một thuật toán đệ quy, do đó mỗi lời gọi hàm đệ quy yêu cầu một lượng bộ nhớ bổ sung trên ngăn xếp gọi hàm.
  • Chiều sâu của ngăn xếp đệ quy: Chiều sâu của ngăn xếp đệ quy phụ thuộc vào cách chọn chốt và phân chia mảng. Trong trường hợp trung bình, chiều sâu của ngăn xếp đệ quy là log(n), nhưng trong trường hợp xấu nhất (khi chốt luôn là phần tử lớn nhất hoặc nhỏ nhất), chiều sâu có thể lên tới n.
Kết hợp các yếu tố
  • Bộ nhớ cho các mảng con: Tại mỗi bước chia mảng, cần bộ nhớ bổ sung để lưu trữ các mảng con left, middle, và right. Tổng kích thước của các mảng con này bằng kích thước của mảng gốc, dẫn đến bộ nhớ bổ sung cần thiết là O(n).
  • Ngăn xếp đệ quy: Chiều sâu của ngăn xếp đệ quy trong trường hợp trung bình là O(log(n)), nhưng trong trường hợp xấu nhất có thể là O(n). Tuy nhiên, yếu tố này thường không đóng góp nhiều vào độ phức tạp không gian tổng thể so với bộ nhớ cho các mảng con.

5. Create Matrix -O(n^2)
 class Solution {  
   static createMatrix(n) {  
     return Array.from({ length: n }, () => Array(n).fill(0));  
   }  
 }  
 // Usage  
 const n = 3; // Example size  
 const matrix = Solution.createMatrix(n);  
 matrix.forEach(row => console.log(row));

Phân tích độ phức tạp không gian

Bộ nhớ cần thiết để tạo ma trận

1. Mảng chính:

  • Array.from({ length: n }, ...) tạo ra một mảng gồm n phần tử.
  • Mỗi phần tử của mảng này là một mảng con có n phần tử.
2. Mảng con:

  • Array(n).fill(0) tạo ra một mảng con gồm n phần tử, tất cả đều được khởi tạo là 0.
  • Có n mảng con như vậy, mỗi mảng con có kích thước n.
Tổng bộ nhớ cần thiết
  • Tổng số phần tử trong ma trận là n x n.
  • Mỗi phần tử là một số nguyên 0, yêu cầu một lượng bộ nhớ cố định.
Kết luận về độ phức tạp không gian
  • Độ phức tạp không gian (Space Complexity): Bộ nhớ bổ sung cần thiết để tạo ra ma trận là tỷ lệ thuận với tổng số phần tử trong ma trận. Vì ma trận có kích thước n x n, nên độ phức tạp không gian là O(n²).
Kết luận

Độ phức tạp không gian của đoạn mã createMatrix là O(n²), do cần tạo và lưu trữ một ma trận có n x n phần tử, mỗi phần tử đều là một số nguyên 0.

Qua bài viết tôi đã giới thiệu về Big-O của cấu trúc dữ liệu, chúc các bạn có một ngày làm việc vui vẻ.Thanks all!


Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

Cài đặt SSL cho website sử dụng certbot

Hình ảnh
1. SSL là gì. Trước khi nói về ssl chúng ta nhắc lại về HTTP là gì đã nhé.HTTP là giao thức dùng để truyền nhận dữ liệu.Nhược điểm của http là dữ liệu được truyền dưới dạng plain text, không hề được mã hóa hay bảo mật nên nếu gói tin chúng ta gửi bằng http bị tin tặc bắt được thì mọi thông tin sẽ bị lộ. SSL viết tắt của cụm từ Secure Sockets Layer là tiêu chuẩn về an ninh công nghệ trên toàn cầu, nói dễ hiểu thì ssl thực hiện mã hóa thông tin truyền nhận, các dữ liệu được gửi qua phương thức này sẽ được mã hóa, website của bạn nếu sử dụng ssl thì sẽ có https trên url.Nhìn chung phương thức https có độ bảo mật cao hơn nhiều so với http, mặc dù không phải tuyệt đối. 2.Cài đặt SSL. A.Trước tiên chúng ta cần cài đặt nginx để làm web server Đối với ubuntu thì các bạn chạy các lệnh sau: $ sudo apt update $ sudo apt install nginx $ sudo ufw allow 'Nginx HTTP' Đối với Centos thì các bạn chạy lệnh : $ sudo yum install epel-release $ sudo yum install nginx $ sudo systemctl start nginx N
Read more »

Xây dựng một hệ thống comment real-time hoặc chat đơn giản sử dụng Pusher

Hình ảnh
Hế lô các bạn, các bạn khỏe không?Sau một thời gian nghỉ ngơi vì dịch nên mình đã quên hết code rồi :)).Sợ code không nổi nữa nên nay lên mò mò làm một app chat đơn giản cho đỡ lụt nghề.Lên mạng đọc tới đọc lui thấy khó thực sự =)).Bất ngờ đọc được một vài bài giới thiệu pusher nên mình cũng lọ mọ thử viết một cái ai ngờ nó chạy được nên tranh thủ viết lại cho cho các bạn cùng xem cho vui. 1.Pusher là gì? Pusher là một dịch vụ cloud, tạo ra một server trung gian giúp chúng ta có thể xử lý các tác vụ thời gian thực. Dữ liệu được gửi tới pusher, và pusher lại gửi nó đi tới các client đã subscribe (đăng ký) và các channel. Trong đó Pusher Channel cung cấp giao tiếp thời gian thực giữa các máy chủ, ứng dụng và thiết bị. Các kênh được sử dụng cho các biểu đồ thời gian thực, danh sách người dùng thời gian thực, bản đồ thời gian thực, chơi trò chơi nhiều người chơi và nhiều loại cập nhật giao diện người dùng khác. Nó có một thư viện hỗ trợ mọi thứ như trình duyệt web, ứng dụng iOS và Andr
Read more »

CÁC BÀI TẬP SQL CƠ BẢN - PART 1

Hình ảnh
  Thời gian gần đây mình có được nhờ giải mấy bài SQL cho các em, lâu không làm lại, thấy khá thú vị nên hôm nay lên mạng tìm mấy bài làm cho zui.Mình viết lại đây coi như note lại để lưu lại,các bạn cùng làm với mình nhé Đề 1: Giải thích qua về đề bài. Query 2 thành phố có tên ngắn nhất và dài nhất  cùng với số ký tự trong tên của 2 thành phố ấy trong bảng STATION. Đáp án : SELECT CITY, LENGTH (CITY) FROM STATION ORDER BY LENGTH (CITY) ASC , CITY LIMIT 1; SELECT CITY, LENGTH (CITY) FROM STATION ORDER BY LENGTH (CITY) DESC , CITY LIMIT 1; Đề 2: Giải thích qua về đề bài : Query danh sách tên thành phố bắt đầu bằng các nguyên âm (a, e, i, o, u) Đáp án : SELECT DISTINCT CITY FROM STATION WHERE CITY LIKE "A%" OR CITY LIKE "E%" OR CITY LIKE "I%" OR CITY LIKE "O%" OR CITY LIKE "U%" ; Đề 3:  Giải thích đề bài : Query danh sách tên thành phố kết thúc bằng các nguyên âm (a, e , i, o,u), tương tự bài trên chỉ cần đổi logi
Read more »

Xây dựng một hệ thống tracking hành vi người dùng (phần 1)

Hình ảnh
 Hiện nay trên các trang thương mại điện tử việc tracking hành vi người dùng rất là phổ biến vậy nên hôm nay mình sẽ viết một bài viết về hệ thống tracking đơn giản đã từng được sử dụng trên một website thương mại điện tử nhé.Ngôn ngữ mình sử dụng trong bài viết này là ruby(ruby on rails) 1.Sơ đồ tổng quan hệ thống <Image invalid> 2.Triển khai project Mô tả sơ qua về cách xây dựng hệ thống(bỏ qua các giai đoạn xây dựng xác thực tài khoản và phân quyền,vì chỉ là thành phần phụ trợ). Tạo tag -> lưu tag vào database -> render thành file js với đầu vào là các tag được tạo từ  trước 2.1.Các model tương ứng Tag model class Tag include Mongoid::Document include Mongoid::Timestamps belongs_to :user field :name, type: String, default: "" field :selector, type: Hash, default: {} field :trigger, type: Hash, default: {} field :handle, type: Hash, default: {} field :author, type: String, default: "" end User
Read more »

Xây dựng một hệ thống tracking hành vi người dùng (phần 2)

Hình ảnh
Các bạn có thể xem lại phần 1 tại đây. Sau khi đã có được các tag tiến hành xây dựng các Helper để hỗ trợ việc render ra file tracking.js Helper này có nhiệm vụ xử lý các logic của file tracking.js nhưng nếu xử lý trực tiếp trên file js thì nó quá dài dòng và dễ bị lộ logic của file. JS helper module JsHelper def renderBindClicks(tags) click_tags = tags.inject([]) do |click_tags, tag| if tag&.trigger[:value] == 'click' event_type = tag&.selector[:dom] selector = if event_type == "classes element" ".#{tag&.selector[:value]}" elsif event_type == "id element" "\##{tag&.selector[:value]}" end if selector.present? click_tags << "'#{selector}'" end end click_tags end if click_tags.present? return "[#{click_tags.uniq.join(', ')}].forEach(bindClick);".html_safe end
Read more »

Enterprise architecture trên 1 tờ A4

Hình ảnh
Enterprise architecture là một chủ đề rộng và có rất nhiều quan điểm chi phối và thực thi. Trên thực tế có rất nhiều quan điểm về vấn đề này, mình xin giới thiệu qua một quan điểm khá hay ho trong hình dưới đây. Nếu khó nhìn các bạn có thể tải về máy và phóng to lên nhé !
Read more »

Web caching (P2)

Hình ảnh
Sau khi đọc Web caching (P1), chúng ta đã hiểu đường tác dụng, cơ chế của việc caching và đi chi tiết về Browser caching và CDN caching. Ở phần 2 chúng ta sẽ tìm hiểu về server caching và cách vận dụng linh hoạt caching để giải quyết các bài toàn performance. Mục lục Reverse proxy caching. Application caching. Áp dụng bài toán thực tế. Lời kết 1.Reverse proxy caching Reverse Proxy là gì? - Là một loại proxy server trung gian giữa một server và các clients gửi request. - Nó kiểm soát yêu cầu của các clients, nếu hợp lệ, sẽ luân chuyển đến các servers thích ứng. - Ưu điểm lớn nhất của việc sử dụng Reverse proxy là khả năng quản lý tập trung. Nó giúp kiểm soát mọi requests do clients gửi lên servers. Cơ chế: - Tương tự như Browser caching và CDN caching. Reverse proxy cache lại tất cả các request resources(image, css, js, ...) và trả lại client ở tầng Proxy. Ưu điểm: - Giảm lượng request lên server. - Có thể quản lý được cache. Nhược điểm:
Read more »

Bàn về async/await trong vòng lặp javascript

Hình ảnh
  Lâu nay mình đang phải làm một dự án sdk javascript nên khá đau đầu với cái bất đồng bộ trong vòng lặp của  javascript.Để tránh quên nên mình viết lên đây cho đỡ quên.Bài viết này mình chỉ viết về một số ví dụ sử dụng async/await cho dễ hiểu nhé. 1. Chuẩn bị cho ví dụ sắp tới Giả sử chúng ta có một giỏ trái cây và số lượng của từng trái cây trong giỏ const fruitBasket = { apple: 27, grape: 0, pear: 14 } Bây giờ mình muốn lấy số lượng hoa quả trong giỏ mình sẽ viết một hàm như sau  const getNumFruit = fruit => { return fruitBasket[fruit] } const numApples = getNumFruit('apple') console.log(numApples) Giờ giả sử fruitBasket được lấy từ server chứ không phải mình khai báo biến như trên nữa việc lấy dữ liệu sẽ mất một vài giây, mình sẽ giả lập công việc lấy dữ liệu từ server như sau const sleep = ms => { return new Promise(resolve => setTimeout(resolve, ms)) } const getNumFruit = (s, fruit) => { return sleep(s).then(v =&
Read more »

Web caching (P1)

Hình ảnh
Câu chuyện hư cấu 1: A: *** hiểu sao code tao chỉnh sửa rồi mà deploy lên *** thấy thay đổi gì? B: Mày đã xóa cache chưa vậy? A: Làm sao để biết có cache hay không. Mà cache làm *** gì để suốt ngày phải xóa. Mất công, mất việc. One few moments later ... A: Xóa hết cache trình duyệt rồi, sao vẫn ko thay đổi code đã chỉnh sửa mày ơi. B: Ờ, cũng *** biết, đọc bài ở dưới xem sao :)) Câu chuyện hư cấu 2: C: Sao dạo này con web của tao nó chạy chậm thế nhờ? Có cách nào ko mày? D: Thế mày đã caching cho nó chưa? C: Tao đang nói web chạy chậm mà, có khi do code lởm mà, cache ciếc gì ở đây. Mà cache là cái gì vậy? D: Thôi đọc bài ở dưới đi rồi nói chuyện tiếp :)) Ok, qua 2 câu chuyện hư cấu trên, chắc các bạn cũng mường tượng được ưu, nhược điểm của Caching rồi đúng không? Vậy trong bài viết này, mình sẽ trình bày về Caching để các bạn hiểu vì sao nó lại quyền năng mà cũng lại rắc rối như thế.Hôm nay chúng ta cùng tìm hiểu về vấn đề này nhé. Mục lục Đường đi của 1 reques
Read more »

Cài đặt môi trường để code website Rails

Hình ảnh
Để xây dựng một website bẳng rails đầu tiên chúng ta cần phải xây dựng môi trường đúng chứ.Bài này mình sẽ hướng dẫn các bạn cài đặt môi trường để làm việc nhé. 1.Hệ điều hành Để làm việc được đơn giản mình gợi ý là dùng ubuntu,nếu bạn nào dùng mac thì quá tuyệt rồi.Mình không có tiền mua mac để code nên mình cài ubuntu để làm việc nhé,bạn nào có sử dụng window mà không muốn đổi hệ điều hành thì mình gợi ý nên sử dụng wubi để cài song song ubuntu nghịch cho biết, đây là bài hướng dẫn cài wubi nhé các bạn . 2.Cài đặt ruby Rails là một framework xây dựng website của ngôn ngữ ruby nên chắc chắn chúng ta phải cài ruby để làm việc rồi.Để cài đặt ruby chúng ta làm như sau: +,Bước đầu cần cài node và các công cụ phụ trợ của node curl -sL https://deb.nodesource.com/setup_8.x | sudo -E bash - curl -sS https://dl.yarnpkg.com/debian/pubkey.gpg | sudo apt-key add - echo "deb https://dl.yarnpkg.com/debian/ stable main" | sudo tee /etc/apt/sources.list.d/yarn.list s
Read more »