View profile

#232 - Cải thiện tốc độ tìm kiếm text trong Postgres

Grokking Vietnam
Grokking Vietnam
Trong số này, chúng ta cùng tìm hiểu về:
  • Cách giám sát một hệ thống phân tán phức tạp
  • Cách cải thiện tốc độ tìm kiếm text trong Postgres của CharityAPI
  • Lịch sử của Macintosh Portable
  • Lời giải bài Time Based Key-Value Store
Ngoài ra các bạn vẫn có thể tiếp tục đặt mua ấn phẩm Dijkstra tập 2 tại đây.

Những bài viết hay
Góc Lập Trình
Đề ra tuần này: Snapshot Array
(by ndaadn)
Cài đặt cấu trúc dữ liệu SnapshotArray hỗ trợ những hàm sau:
  • Hàm khởi tạo SnapshotArray(int length): khởi tạo một cấu trúc dữ liệu tương tự mảng, với độ dài là “length”. Ban đầu, tất cả các giá trị đều là 0.
  • Hàm set(index, val): gán giá trị “val” tại vị trí “index”.
  • Hàm snap(): lưu lại các giá trị hiện tại của mảng và trả lại “snap_id” - số lần gọi hàm snap() - 1.
  • Hàm get(index, snap_id): trả lại giá trị tại vị trí “index” tại thời điểm “snap_id”.
Lời giải đề bài tuần trước: Time Based Key-Value Store
(by phucnh)
Với dạng bài yêu cầu lưu trữ và tìm kiếm theo khóa, ta có thể nghĩ ngay tới cấu trúc dữ liệu bảng băm (hashtable). Tuy nhiên trong bài này, ta còn cần lưu trữ và tìm kiếm theo giá trị tuyến tính: thời gian dữ liệu được cập nhật. Để tìm kiếm nhanh giá trị có thời gian cập nhật gần nhất với biến timestamp của hàm get, ta có thể sử dụng cây tìm kiếm nhị phân (Binary Search Tree).
Với những phân tích trên, ta có giải thuật như sau: https://pastebin.com/76Pta6vu
Việc thêm và tìm kiếm trong bảng băm có độ phức tạp thời gian là O(1), còn trong cây tìm kiếm nhị phân là O(logn). Vì vậy, độ phức tạp về thời gian của hàm set và get đều là O(logn).
Trong bài này, ta có một rằng buộc “thời gian của hàm set là tăng dần”. Như vậy, ta không cần thiết phải sử dụng cây tìm kiếm nhị phân để lưu trữ cặp “thời gian, giá trị”, mà có thể sử dụng mảng. Mỗi khi thêm dữ liệu, ta chỉ cần thêm vào cuối mảng có khoá tương ứng. Với việc tìm kiếm theo giá trị thời gian, ta có thể áp dụng binary search. Bằng cách này, ta có thể tối ưu độ phức tạp về thời gian của hàm set còn O(1).
History
Vào ngày 28 tháng 8 năm 1991, trên tàu con thoi Atlantis, email đầu tiên từ không gian đã được gửi từ một máy Macintosh Portable thông qua Apple Link. Apple Link là một dịch vụ trực tuyến của Apple trước khi Internet được thương mại hóa.
Các phi hành gia Shannon Lucid và James C. Adamson đã gửi thông điệp sau:
Hello Earth! Greetings from the STS-43 Crew. This is the first AppleLink from space. Having a GREAT time, wish you were here,…send cryo and RCS! Hasta la vista, baby,…we’ll be back!
Người nhận là Marcia Ivins, tại trung tâm vũ trụ Johnson
Macintosh Portable là máy tính chạy pin đầu tiên do Apple sản xuất. Mặc dù thu hút được nhiều sự chú ý vào thời điểm đó nhưng lại không thành công mấy vì pin của nó quá nặng với hơn 7kg. (source)
(by lpv)
Macintosh Portable
Macintosh Portable
Code & Tools
  • SurrealDB - một hệ thống document-graph database cho realtime web
  • Supabase - một phần mềm mở thay thế cho Firebase
Feedback
Bạn đánh giá nội dung số newsletter này thế nào?
(1 = Rất tệ / 5 = Rất tốt)
👎 1 —— 2 —— 3 —— 4 —— 5 👍 
(Việc đánh giá của các bạn là rất quan trọng, sẽ giúp chúng tôi liên tục cải thiện nội dung newsletter tốt hơn)
Grokking mang lại cho các bạn những kiến thức mới mẻ và hữu ích thông qua:
  • Tech Talk: Là một hoạt động thường xuyên của Grokking từ những ngày đầu thành lập. Tại đây các diễn giả chia sẻ kiến thức xoay quanh Computer Science và Software Engineer. Các buổi Tech Talk đều được record và upload lên kênh youtube của Grokking.
  • Grokking Knowledge Graph: Tập hợp những nguồn kiến thức phong phú với hơn 1000 bài viết chọn lọc, các đầu sách, khóa học, v.v… Các bài viết đều được gán nhãn để giúp bạn đọc dễ dàng tìm kiếm.
  • Webinar: Là chương trình kết nối các kỹ sư Việt Nam và các kỹ sư đang làm việc tại các công ty công nghệ hàng đầu thế giới.
  • Dijkstra: Một ấn phẩm được xuất bản bởi các thành viên của Grokking. Với những bài viết đào sâu vào kỹ thuật và kiến thức khoa học máy tính.
  • Kipalog: Nền tảng chia sẻ kiến thức dành cho các lập trình viên.
  • Newsletter: Những bài viết hay về công nghệ sẽ được gửi tới bạn hàng tuần qua email.
Chúc các bạn sẽ tìm được nhiều điều mới mẻ khi đến với Grokking và xin hẹn gặp lại các bạn vào tuần sau.
Quotes
A computer is like a violin. You can imagine a novice trying first a phonograph and then a violin. The latter, he says, sounds terrible. That is the argument we have heard from our humanists and most of our computer scientists. Computer programs are good, they say, for particular purposes, but they aren’t flexible. Neither is a violin, or a typewriter, until you learn how to use it.
― Marvin Minsky
Did you enjoy this issue? Yes No
Grokking Vietnam
Grokking Vietnam

Cảm ơn bạn đã dành thời gian đọc newsletter kỳ này và chúng tôi hi vọng rằng bạn đã khám phá ra một số điều mới mẻ từ các bài viết trên. Các bạn có thể đọc lại các số cũ tại website newsletter.grokking.org

In order to unsubscribe, click here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.
Viet Nam