Nắm vững cấu trúc dữ liệu & thuật toán bằng c và c ++ github

Alexei. Tuần này, chúng ta sẽ nói về các thuật toán. Chúng tôi có một vị khách đặc biệt, Marcello. Marcello là kỹ sư phần mềm cao cấp tại Tundra. Và ông là tác giả cuốn "Advanced Algorithms and Data Structures". Tôi nghĩ rằng nó đã được phát hành gần đây, phải không? . Xin chúc mừng. Đó là một cuốn sách về các thuật toán. Marcello làm việc với đồ thị, tối ưu hóa, thuật toán, thuật toán di truyền, máy học và điện toán lượng tử. Chào mừng. (1. 51)

Marcello. Xin chào. Cảm ơn rất nhiều vì đã mời tôi. Đó là một vinh dự. (2. 52)

lý lịch của Marcello

Alexei. Niềm vui của tôi cũng vậy. Trước khi chúng ta đi vào chủ đề chính về thuật toán, hãy bắt đầu với nền tảng của bạn. Bạn có thể cho chúng tôi biết về hành trình sự nghiệp của bạn cho đến nay? . 59)

Marcello. Tôi đã làm việc với tư cách là nhà phát triển web và cơ sở hạ tầng dữ liệu. Tôi bắt đầu với việc phát triển web. Sau đó, tôi làm việc 5 năm trong một công ty thuộc sở hữu của chính phủ ở Ý. Sau đó, tôi bắt đầu làm việc từ xa với các công ty khởi nghiệp và sau đó chuyển đến Ireland để tham gia Twitter. Sau đó tôi làm việc cho Microsoft, Apple. Và năm ngoái, tôi đã tham gia Tundra — một cửa hàng trực tuyến. (3. 11)

Alexei. Tundra có liên quan gì đến rừng ở Nga không? . 06)

Marcello. Không, tôi không biết. Không ai biết tên chính xác đến từ đâu. Nhưng đó là một công ty tốt. (4. 12)

Học thuật toán và cấu trúc dữ liệu

Alexei. Mọi người nên tiếp cận thuật toán học như thế nào? . 51)

Marcello. Nó có thể được học ở các cấp độ rất khác nhau, tùy thuộc vào mức độ bạn cần học sâu. Khi tôi bắt đầu học, tôi được gợi ý rằng điều quan trọng là không nên tập trung vào chi tiết. Bạn cần biết rằng có một thuật toán như vậy, khi nào thì sử dụng nó — trong tình huống nào và nó có thể giải quyết vấn đề gì. Cũng có lẽ, nó hiệu quả như thế nào. Khi biết rằng có một thuật toán giải quyết một vấn đề nào đó, bạn có thể tìm thấy nó khi cần tại nơi làm việc — khi nào bạn nên áp dụng nó. Nếu bạn không nhớ thuộc lòng thuật toán cũng không sao. Không ai có thể nhớ tất cả các thuật toán. Nhưng nếu bạn biết nơi để tìm nó, nó là hoàn hảo. (5. 19)

Alexei. Tôi không có thuật toán trong quá trình học, vì vậy tôi đã tự học chúng bên ngoài trường đại học. Tôi đã tham gia nhiều khóa học tập trung vào đạo hàm và chứng minh toán học. Có vẻ như đó là một điều quan trọng — để thực sự hiểu cách thức hoạt động của thuật toán và chứng minh rằng nó là O(N log N) bằng cách sử dụng một số công cụ toán học khó. Vì vậy, đây không phải là thứ chúng ta nên tập trung vào, chúng ta nên tập trung nhiều hơn vào các ứng dụng, phải không? . 47)

Marcello. Đúng. Cũng có một câu chuyện vui về điều này. Google được tạo ra bởi Page và Brin. Khi bắt đầu nghiên cứu, họ đã nói chuyện với một nhà nghiên cứu người Ý về ý tưởng về trình thu thập thông tin này. Nó thực hiện tìm kiếm theo một cách khác với chỉ lập chỉ mục như Yahoo hoặc Altavista. Anh chàng này đã đến Đại học Ý của mình và đề xuất ý tưởng này. Họ nói với anh ấy rằng, nó sẽ không bao giờ có tương lai vì bạn không thể chứng minh rằng điều đó là đúng. Vì vậy, tập trung vào chứng minh toán học có thể khó khăn và nguy hiểm. Tất nhiên, điều quan trọng là nếu bạn đang làm bài báo để chứng minh rằng thuật toán hoạt động. Nhưng điều đó không có nghĩa là nếu bạn không biết nó hoạt động như thế nào, hoặc không tính toán, thì nó sẽ trở nên vô dụng. (7. 30)

Tài nguyên để học các thuật toán và cấu trúc dữ liệu

Alexey. Vì vậy khi học thuật toán chúng ta nên tập trung vào ứng dụng nhiều hơn là chứng minh. Bạn có biết bất kỳ tài liệu tham khảo tốt nào cho các thuật toán cơ bản, chẳng hạn như sắp xếp không? . 00)

Marcello. Có rất nhiều tài nguyên trực tuyến - các khóa học và trang web. Có một loạt video từ MIT, nó rất hay. Có khóa học Tim Roughgarden trên Coursera. Nó giải thích mọi thứ rõ ràng và nó đơn giản như nó được. Nếu bạn thích sách hơn, tôi có thể đề xuất Thuật toán Grokking do Manning xuất bản, đây cũng là phần giới thiệu chung về các thuật toán và cấu trúc dữ liệu cơ bản. (9. 23)

Cấu trúc dữ liệu quan trọng nhất

Alexei. Theo bạn, các thuật toán và cấu trúc dữ liệu quan trọng nhất mà chúng ta nên biết là gì? . Vì vậy, đối với bất kỳ ai lập trình, loại cấu trúc dữ liệu thuật toán nào họ nên biết? . 08)

Marcello. Tầm quan trọng là tương đối. Nó phụ thuộc vào lĩnh vực của bạn và những gì bạn đang thực sự làm. Các cấu trúc dữ liệu cơ bản có thể là quan trọng nhất. Họ là những người có thể tạo ra tác động lớn hơn. Việc lạm dụng một mảng hoặc một danh sách có thể ảnh hưởng rất nhiều đến hiệu suất của ứng dụng của bạn. Và điều rất phổ biến là bạn đang sử dụng các cấu trúc dữ liệu này, vì vậy chúng là những cấu trúc quan trọng nhất. (10. 34)

Alexei. Vì vậy, bạn cần biết mảng, danh sách, khi nào sử dụng chúng, khi nào sử dụng tập hợp, khi nào sử dụng từ điển, phải không? . 20)

Marcello. Ví dụ: biết khi nào bạn nên sử dụng một mảng hoặc khi nào bạn nên sử dụng một danh sách, tùy thuộc vào những gì bạn phải làm. Nếu bạn cần truy cập ngẫu nhiên, mảng là sự lựa chọn tốt nhất. Nhưng nếu bạn luôn thêm các phần tử ở phía trước, thì mảng rất phức tạp — bạn sẽ phải thực hiện nhiều thao tác sao chép và di chuyển bộ nhớ. Nó trở thành một mớ hỗn độn. Bên cạnh mảng và danh sách, mức tối thiểu đối với tôi sẽ là ngăn xếp, hàng đợi, các loại cấu trúc này. (11. 30)

Alexei. Và bộ là tốt? . 09)

Marcello. Bộ, vâng, tất nhiên. (12. 12)

Học trừu tượng

Alexei. Giả sử nếu chúng ta sử dụng Python, thì nó đi kèm với một tập hợp các cấu trúc dữ liệu khác nhau. Vì vậy, biết — ít nhất là có một số ý tưởng — cách chúng được triển khai trong nội bộ là hữu ích. Giống như, nếu bạn muốn thêm một cái gì đó, nó hoạt động như thế nào bên trong? . (12. 17)

Marcello. Phải, chắc chắn rồi. Với thuật toán, bạn phải phân biệt cấu trúc dữ liệu hiện thực và trừu tượng. Bước đầu tiên là hiểu được sự trừu tượng đằng sau nó là gì. Và sau đó bạn có thể thực hiện nó theo nhiều cách. Ví dụ: bạn có thể triển khai từ điển với bất kỳ thứ gì — với danh sách hoặc mảng, cây hoặc bảng băm. Tất cả những triển khai này đều có ưu và nhược điểm. Họ thực hiện tốt một số thao tác và thực hiện kém ở các thao tác khác. (12. 54)

Marcello. Nếu bạn sử dụng một ngôn ngữ như Python, bạn sẽ quan tâm hơn đến việc hiểu sự trừu tượng đằng sau nó. API của từ điển là gì, các thao tác bạn làm là gì? . Hiểu cách chúng ta có thể tận dụng những điều đó hoặc liệu chúng có thể gây ra bất kỳ vấn đề hoặc bất kỳ tắc nghẽn nào không. (13. 36)

Alexey. Vì vậy, bạn có thể lấy tất cả các cấu trúc dữ liệu mà bạn nên sử dụng, từ Python hoặc bất kỳ ngôn ngữ nào khác và bạn tìm hiểu các API của chúng. Các phương pháp có thể là gì? . 13)

Marcello. Đúng. Ví dụ, bạn đã đề cập đến bộ. Điều quan trọng cần biết là các hợp đồng mà khách hàng có với cấu trúc dữ liệu giống như một tập hợp là gì — bạn có thể thêm các phần tử, bạn có thể xóa các phần tử nhưng sẽ không có phần tử trùng lặp. Bạn có thể mong đợi rằng việc chèn và kiểm tra khá nhanh so với một mảng. Mặc dù điều này cũng phụ thuộc vào việc thực hiện. (14. 33)

Học các thuật toán nếu chúng không cần thiết tại nơi làm việc

Alexei. Bạn đã đề cập rằng bạn đã làm việc với tư cách là nhà phát triển web vào một thời điểm nào đó. Tôi đã nghe điều này từ nhiều nhà phát triển web và cả từ các nhà khoa học dữ liệu. Hãy nói về các nhà phát triển web. Ngày nay, họ làm những việc đơn giản — họ tạo ra các ứng dụng web đơn giản. Họ nói, "Tôi thực sự không cần thuật toán cho điều đó. Tất cả những gì tôi cần là thư viện này React. Nó hoạt động và tôi không cần sử dụng thuật toán. " (15. 09)

Alexei. Vậy làm cách nào để học các thuật toán nếu tôi không cần đến chúng trong công việc? . (15. 45)

Marcello. Đầu tiên, tôi muốn thách thức giả định rằng bạn không cần thuật toán cho điều đó. Nếu bạn là nhà phát triển web, nhà phân tích dữ liệu hoặc nhà khoa học dữ liệu, bạn sử dụng thuật toán nhiều hơn bạn nghĩ. Ngay cả cái cơ bản mà chúng tôi đã đề cập trước đó - tôi không thể tin rằng bạn không sử dụng mảng hoặc danh sách. Điều đó có thể tạo nên sự khác biệt lớn. Là một nhà phát triển web, bạn có thể gặp hạn chế về thời gian hoặc hạn chế về tài nguyên. Hoặc bạn có thể phải xử lý các tập dữ liệu lớn với tư cách là nhà khoa học dữ liệu. Các nhà phát triển web có thể ở trong tình huống sử dụng cấu trúc dữ liệu phù hợp sẽ tạo ra sự khác biệt. Ví dụ: nếu bạn phải cung cấp một số chức năng kiểm tra chính tả. Nếu bạn biết bộ lọc hoặc thử Bloom là gì, thì bạn đang ở một vị trí tốt hơn. Nếu không, cuối cùng bạn có thể phát minh lại bánh xe hoặc cung cấp giải pháp dưới mức tối ưu, cho dù bạn có sử dụng thư viện của bên thứ ba hay không. (15. 57)

Marcello. Quay trở lại câu hỏi của bạn, làm thế nào để bạn thành thạo các thuật toán nếu bạn không có cơ hội làm việc hàng ngày với điều này trong công việc của mình? . 40)

Alexei. Vâng, tôi không triển khai trình kiểm tra chính tả mỗi ngày. Làm cách nào để học cách sử dụng bộ lọc Bloom? . 51)

Marcello. Có một vài điều. Nếu bạn quan tâm đến chủ đề này, có rất nhiều tài nguyên. Bạn có thể tự học, bạn có thể đặt mục tiêu. Nhưng nếu bạn đang tìm kiếm thêm động lực, tham gia một số cuộc thi như Google Code Jam hoặc đại loại như vậy, có thể là một động lực tốt cho bạn. Bạn có thể có động lực để tìm hiểu thêm. Và hơn thế nữa, nó mang đến cho bất kỳ ai cơ hội học hỏi trong lĩnh vực này và có một số kinh nghiệm thực tế với các thuật toán này — không chỉ biết lý thuyết mà còn thực sự học cách sử dụng chúng và tận dụng các cấu trúc dữ liệu này. (18. 01)

Alexei. Vì vậy, nếu bạn không thể làm điều này tại nơi làm việc, hãy cố gắng làm điều này bên ngoài công việc. (19. 07)

Marcello. Chà, không phổ biến khi tại nơi làm việc, bạn cần triển khai các thuật toán này từ đầu. Nhưng bạn có thể học cách sử dụng chúng trong công việc. Một điều bạn có thể làm — nếu bạn thấy có nút thắt cổ chai hoặc thấy có chỗ cần cải thiện khi định hình ứng dụng của mình, bạn có thể cố gắng tìm hiểu thuật toán nào có thể trợ giúp trong các tình huống tương tự và thử áp dụng chúng. Đặc biệt nếu bạn sử dụng một ngôn ngữ lập trình chính tại nơi làm việc, bạn sẽ dễ dàng tìm thấy các thư viện triển khai các thuật toán phổ biến và nâng cao. Sau đó, bạn sẽ thấy làm thế nào họ có thể tạo ra sự khác biệt. (19. 14)

Các lỗi thường gặp khi sử dụng sai cấu trúc dữ liệu

Alexey. Một sai lầm tôi thường nhận thấy trong mã là mọi người vô tình sử dụng một danh sách để kiểm tra ngăn chặn thay vì sử dụng một tập hợp. Những điều đơn giản như vậy rất phổ biến đối với các nhà phát triển web và các nhà khoa học dữ liệu. Đây là một hoạt động rất phổ biến. Bạn có thứ gì đó đến và bạn muốn kiểm tra xem đây có phải là thứ mà bạn đã biết hay không. Đối với điều đó, bạn kiểm tra xem X này có nằm trong bộ sưu tập những thứ đã nhìn thấy không. Nếu chúng ta chỉ thay thế một danh sách bằng một tập hợp, thì chúng ta sẽ thấy thứ tự cải thiện về tốc độ. (20. 14)

Marcello. Chính xác. Tương tự như vậy, tôi đã thấy rằng để theo dõi các phần tử, để thêm các phần tử vào danh sách, người ta thêm phần tử đó vào sai phần cuối của danh sách. Ví dụ: trong Scala hoặc Haskell, việc thêm nó vào sai phần cuối của danh sách có thể khiến thao tác đơn giản này trở nên chậm và khiến máy chủ của bạn hết thời gian chờ. (20. 58)

Tầm quan trọng của cấu trúc dữ liệu đối với các nhà khoa học dữ liệu

Alexey. Quay trở lại câu hỏi, "Những cấu trúc dữ liệu này quan trọng như thế nào đối với các nhà khoa học dữ liệu?" . Và là một nhà khoa học dữ liệu, tôi thực hiện thao tác này rất thường xuyên. Theo bạn, có trường hợp nào khác mà việc biết cấu trúc dữ liệu là rất quan trọng đối với các nhà khoa học dữ liệu không? . 38)

Marcello. Bất cứ khi nào bạn đang làm việc trên các tập dữ liệu khổng lồ, ngay cả một cải tiến nhỏ nhất cũng có thể tạo ra sự khác biệt về thời gian. Và nếu bạn có thứ tự cải thiện cường độ, điều đó sẽ tạo ra sự khác biệt to lớn. Nó có thể tăng tốc độ tìm kiếm — sử dụng bộ lọc Bloom thay vì từ điển để theo dõi những gì bạn đã xem. Nó có thể là tìm kiếm hàng xóm gần nhất để tìm kiếm trong bộ dữ liệu đa chiều khổng lồ này. Tôi nghĩ rằng chúng thậm chí còn quan trọng hơn đối với các nhà khoa học dữ liệu. (22. 12)

Cuốn sách của Marcello - Thuật toán nâng cao và cấu trúc dữ liệu

Alexey. Bạn đã đề cập đến bộ lọc nở hoa và tìm kiếm hàng xóm gần đúng. Đây thực sự là một cái gì đó tôi muốn nói chuyện với bạn về. Bạn bao gồm chúng trong cuốn sách của bạn. Vì vậy, có lẽ chúng ta hãy nói một chút về cuốn sách của bạn. Trước hết, có gì trong cuốn sách của bạn? . 10)

Marcello. Ý tưởng viết cuốn sách này là cung cấp một cầu nối giữa kiến ​​thức lý thuyết về thuật toán trong sách giáo khoa và kiến ​​thức thực tế hơn từ sách thực hành. Cuốn sách của tôi bao gồm cả lý thuyết và các khía cạnh thực tế hơn về cách sử dụng các thuật toán. Đối với mỗi cấu trúc dữ liệu hoặc thuật toán trong cuốn sách, trọng tâm là đưa ra trường hợp sử dụng thực tế, nơi bạn có thể tạo ra sự khác biệt bằng cách sử dụng thuật toán phù hợp. Vấn đề cũng có thể ngược lại. bạn có thể tạo ra sự khác biệt tiêu cực bằng cách sử dụng sai cấu trúc dữ liệu ở sai vị trí. Nếu bạn học cách tránh điều đó, điều đó thật tuyệt và bạn có thể cải thiện hiệu suất của các ứng dụng của mình. (23. 39)

Marcello. Có 18 chương và 3 phần. Phần đầu tiên và các phụ lục bao gồm các cấu trúc dữ liệu cơ bản - chúng bao gồm nền tảng. Sau đó, chúng tôi đi vào các thuật toán phức tạp hơn. Trong phần thứ hai, chúng tôi đề cập đến tìm kiếm hàng xóm gần nhất, phân cụm máy học, giải thích mô hình lập trình MapReduce. Trong phần thứ ba, chúng tôi đề cập đến đồ thị, thuật toán tiến hóa và tối ưu hóa nói chung — các tùy chọn khác nhau cho các bài toán hoán vị từ thuật toán ngẫu nhiên và lấy mẫu ngẫu nhiên đến thuật toán giảm độ dốc, ủ mô phỏng và thuật toán di truyền. (25. 04)

Alexey. Nó được gọi là "thuật toán nâng cao". Nó có yêu cầu một số kiến ​​​​thức về thuật toán không? . 19)

Marcello. Chúng tôi cố gắng trình bày những điều cơ bản trong phần phụ lục trong một vài chương đầu tiên. Bạn không cần thêm gì nữa. Tất nhiên, nếu bạn đã có "Thuật toán 101" hoặc nếu bạn đã có kinh nghiệm trước đây về chủ đề này, thì bạn đang ở trạng thái tốt hơn. (26. 31)

Alexei. Tôi đoán nếu ai đó xem khóa học MIT mà bạn đề xuất này hoặc khóa học Coursera của Tim Roughgarden, thì những điều này sẽ cung cấp đủ nền tảng để tiếp tục với cuốn sách của bạn. Nhưng ngay cả khi họ không tham gia các khóa học này, bạn sẽ đề cập đến mọi thứ trong các phụ lục cũng như các chương đầu tiên, phải không? . 08)

Marcello. Có, chúng tôi bao gồm mọi thứ bạn cần để bắt đầu. Bạn không cần toán học phức tạp, kiến ​​thức về đại số tuyến tính và bạn cần kiến ​​thức ban đầu về lập trình. Chúng tôi không sử dụng một ngôn ngữ lập trình duy nhất, chúng tôi sử dụng mã giả, vì vậy bất kỳ ai có kiến ​​thức cơ bản đều có thể hiểu cách thức hoạt động của các thuật toán. Điều duy nhất có ích là biết vòng lặp for hoặc điều kiện là gì. (27. 38)

Alexey. Tôi biết rằng bạn cũng có một kho lưu trữ GitHub, nơi tất cả các thuật toán này được triển khai bằng mọi ngôn ngữ có thể. (28. 37)

Marcello. Không phải mọi thứ đều có thể, nhưng mục tiêu của tôi là có chúng bằng càng nhiều ngôn ngữ càng tốt. Hiện tại, hầu hết chúng được triển khai bằng Java, JavaScript và Python. Chẳng bao lâu nữa, trong Scala, và tôi hy vọng sẽ thêm C++ và Rust sau. (28. 49)

Alexei. Vì vậy, bạn cũng đã có rất nhiều niềm vui khi triển khai nó bằng tất cả các ngôn ngữ khác nhau này. (29. 11)

Marcello. Đúng. Nó vui. (29. 17)

Alexei. Bạn có định cover Go sau khi cover những cái này không? . 20)

Marcello. Vâng, tại sao không? . (29. 27)

bộ lọc hoa

Alexei. Khi tôi nhìn vào mục lục, tôi quan tâm đến các bộ lọc Bloom và ước tính các hàng xóm gần nhất, và thật trùng hợp, đây là những gì chúng ta đã nói trước đây. Tôi nghĩ có lẽ chúng ta có thể bao quát một chút những cấu trúc dữ liệu này một chút? . 43)

Alexey. Hãy bắt đầu với bộ lọc Bloom. Vậy họ giải quyết vấn đề gì? . 09)

Marcello. Không phải ngẫu nhiên, chúng rất hữu ích cho khoa học dữ liệu. Bộ lọc Bloom là một cấu trúc dữ liệu khá thú vị. Đáng ngạc nhiên, nó không phổ biến như tôi mong đợi. Bộ lọc Bloom giải quyết vấn đề từ điển truyền thống. Từ điển là một thùng chứa. Bạn có thể lưu các mục ở đó và truy xuất chúng khá nhanh. Có nhiều cách khác nhau mà bạn có thể thực hiện. Ví dụ: bạn có thể triển khai nó dưới dạng cây — dưới dạng cây cân bằng hoàn toàn hoặc cây tìm kiếm nhị phân. Sau đó, bạn có thể nhận được hiệu suất tốt cho hầu hết các ứng dụng. Nhưng những gì mọi người thường kết hợp với từ điển là bảng băm - chúng là từ đồng nghĩa trong nhiều ngôn ngữ. (30. 17)

Marcello. Bộ lọc Bloom hoạt động tương tự như bảng băm - chúng tận dụng các hàm băm. Nhưng chúng tuân theo một cách tiếp cận khác so với bảng băm, cho phép chúng sử dụng bộ nhớ hạn chế. Nếu bạn có một tập dữ liệu lớn, bạn có thể không có đủ bộ nhớ hoặc dung lượng ổ đĩa để sử dụng bảng băm. Điều này đặc biệt xảy ra khi bạn lưu trữ dữ liệu có kích thước thay đổi, chẳng hạn như chuỗi trong vùng chứa của mình. Trong trường hợp đó, bạn có thể lưu trữ từng mục nhập trong bộ lọc Bloom bất kể chúng yêu cầu bao nhiêu dung lượng. Bạn có thể lưu trữ chúng với cùng một dung lượng. Và chúng tôi cần một số lần tra cứu cố định để tìm các phần tử đó. (31. 42)

Marcello. Tất nhiên, bạn phải trả giá cho việc này. Giá có thể là hiệu suất, bởi vì mỗi lần bạn tra cứu hoặc lưu trữ nó, bạn phải băm cùng một mục nhập nhiều lần. Nhược điểm lớn khác là bạn có thể có kết quả dương tính giả với bộ lọc Bloom. Nếu bạn tìm kiếm một mục nhập, bộ lọc Bloom có ​​thể cho bạn biết rằng nó đã được lưu trữ mặc dù thực tế không phải vậy. Điều này là do cách thức hoạt động bên trong. Tôi giải thích những điều này trong chương tám. Tôi không biết nếu chúng ta có thời gian để giải thích nó. (33. 12)

Alexei. Chắc là không. Tôi chỉ muốn hỏi, chúng được sử dụng để làm gì? . chúng ta cần sử dụng cấu trúc dữ liệu này khi chúng ta có một lượng bộ nhớ hạn chế. Nó sử dụng hàm băm để tra cứu mọi thứ. Chúng tôi sử dụng nó để kiểm tra xem thứ gì đó có trong bộ lọc Bloom của chúng tôi hay không — để ngăn chặn. Nhưng cách nó hoạt động, đôi khi nó cho chúng ta kết quả dương tính giả. Nó có thể nói "mặt hàng này là có", nhưng thực sự nó không đúng. (34. 03)

Bộ lọc Bloom hữu ích ở đâu

Marcello. Đôi khi nó không phải là một vấn đề lớn. Bộ lọc Bloom được sử dụng ở rất nhiều nơi. Ví dụ: trong trình thu thập thông tin để kiểm tra xem một trang đã được truy cập chưa — bằng cách xem URL hoặc thậm chí nội dung của trang. Chúng đã được sử dụng trong trình kiểm tra chính tả, nhưng bây giờ chúng được đặt bằng cách thử. Nhưng trong một thời gian dài, chúng đã được sử dụng cho việc đó. Chúng được sử dụng rất nhiều trong các bảng định tuyến để kiểm tra xem địa chỉ IP đã được truy cập hay chưa. Trong tất cả các trường hợp này, nếu bạn có kết quả dương tính giả, thì đó không phải là vấn đề lớn. Trong trình thu thập thông tin, bạn sẽ xử lý lại trang. Với bộ lọc Bloom, bạn có thể cân bằng dung lượng bộ nhớ sử dụng với tỷ lệ dương tính giả. Bạn có thể kiểm soát tần suất xảy ra thông báo sai và tần suất bạn phải trả tiền phạt này. (34. 43)

Alexey. Có lẽ tôi cũng có thể kể về một trường hợp sử dụng mà tôi đã có cách đây vài năm tại công ty trước đây. Công ty là công ty adtech. Họ đang làm quảng cáo. Họ đang bán quảng cáo trên thiết bị di động — tất cả những quảng cáo gây phiền nhiễu mà bạn nhìn thấy khi chơi trò chơi, chúng tôi đã góp phần tạo nên điều đó. (35. 59)

Alexei. Mọi điện thoại đều có một số OF - ID thiết bị. Giả sử tôi là người dùng cũ của một ứng dụng. Tôi đã sử dụng ứng dụng này rồi và chủ sở hữu của ứng dụng muốn đưa tôi trở lại. Ví dụ, tôi đã chơi 10 cấp độ và dừng lại. Họ muốn cho tôi xem một quảng cáo có nội dung: "Này, quay lại, kết thúc trò chơi của bạn". Vì vậy, họ có ID thiết bị của tất cả những người đã chơi trò chơi nhưng đã dừng — và có hàng trăm nghìn ID thiết bị nếu một trò chơi phổ biến. (36. 25)

Alexey. Khi tôi mở một ứng dụng khác, nó đang gửi yêu cầu. Có một cuộc đấu giá diễn ra bí mật, nhưng nó không còn quan trọng nữa. Nhưng chúng tôi muốn kiểm tra xem chúng tôi có biết người này hay không — đó có phải là người dùng cũ hay không? . Chúng tôi chỉ muốn một nhóm nhỏ những người đó — chỉ những người dùng cũ. Vì vậy, chúng tôi sử dụng bộ lọc Bloom để kiểm tra xem chúng tôi có biết người dùng này hay không. Bởi vì không thể lưu trữ mọi thứ trong bộ nhớ. Nếu hóa ra chúng tôi thực sự không biết người dùng này, mặc dù chúng tôi nghĩ rằng chúng tôi biết, thì đó không phải là vấn đề lớn. Chúng tôi chỉ hiển thị cho người đó một quảng cáo. Chúng ta mất một phần nhỏ của một xu, nhưng thế giới không dừng lại vì điều này. (37. 25)

Alexey. Nó được sử dụng rất nhiều trong các ngành như tiếp thị. Mỗi khi bạn muốn mang lại một người dùng, bạn cần lưu trữ tất cả những người dùng này. Đây là lúc tôi biết tại sao bộ lọc Bloom tồn tại và tại sao chúng ta thực sự cần chúng. Trước đó, tôi không biết. Trước đây, tôi chỉ xem khóa học này trên Coursera của Tim Roughgarden. Nó trông phức tạp và tôi không biết tại sao thứ này lại thực sự cần thiết. (38. 32)

Marcello. Đó là một trường hợp sử dụng hoàn hảo. (39. 04)

Xấp xỉ hàng xóm gần nhất

Alexey. Còn cây tìm kiếm thì sao? . Có lẽ chúng ta cũng có thể nói về trường hợp sử dụng này. Tại sao chúng ta cần cây tìm kiếm gần đúng cho các hàng xóm gần nhất? . 10)

Marcello. Chúng tôi cần tìm kiếm hàng xóm gần nhất trong nhiều lĩnh vực, đặc biệt là trong khoa học dữ liệu - khi chúng tôi cần tìm kiếm trong dữ liệu đa chiều. Cây tìm kiếm nhị phân là một cách nhanh chóng để tìm kiếm trong một tập hợp tĩnh hoặc thay đổi chậm. Bạn cũng có thể sử dụng các cây tìm kiếm cân bằng tự động như cây đỏ đen để giải quyết các tập hợp động hơn. Nhưng chúng hoạt động đối với tập dữ liệu một chiều và chúng ta thường phải xử lý dữ liệu đa chiều. Ngay cả dữ liệu địa lý với vị trí địa lý. Và còn có các bộ dữ liệu khác với hàng trăm tính năng. (39. 33)

Marcello. Cây tìm kiếm nhị phân không tổng quát hóa tốt cho các tập hợp đa chiều. Có thể sử dụng nó, nó vẫn nhanh hơn so với việc xem qua tất cả các điểm dữ liệu, nhưng đối với các tập hợp đa chiều, việc so sánh một điểm dữ liệu với phần còn lại của dữ liệu có thể trở nên tốn kém. (40. 59)

Marcello. Cách chúng ta có thể giải quyết vấn đề này là sử dụng tìm kiếm hàng xóm gần nhất. Có các cấu trúc dữ liệu khác nhau cho điều đó. Thứ đầu tiên được phát minh để giải quyết vấn đề đặc biệt này là cây KD. Đó là 40-50 tuổi và trong một thời gian dài, đó là giải pháp tốt nhất cho việc này. Tuy nhiên, bây giờ, có những cấu trúc thậm chí còn tốt hơn — cây KD có một số vấn đề. Chúng hoạt động tốt với một số chiều nhất định của dữ liệu và chúng không hoạt động tốt với các tập dữ liệu nhiều chiều. Và họ cũng có vấn đề với các tập hợp động. (41. 37)

Marcello. Trong cuốn sách, chúng tôi đi qua một ví dụ về rủi ro tín dụng để kích thích sự thèm ăn, để giải thích những điều cơ bản và giải thích tại sao tìm kiếm hàng xóm gần nhất lại quan trọng. Sau đó, chúng tôi xem xét một trường hợp thực tế về việc sử dụng định vị địa lý cho hệ thống phân phối của một cửa hàng trực tuyến — để xử lý hàng triệu đơn đặt hàng và đối với mỗi đơn đặt hàng, hãy tìm nhà kho gần nhất để vận chuyển hàng hóa. Sau đó, chúng tôi duyệt qua các cây R và cây SS (cây tìm kiếm tương tự), xử lý không gian nhiều chiều tốt hơn và cho phép tìm kiếm "láng giềng gần nhất" này. (42. 44)

Marcello. Đôi khi chúng ta không cần kết quả thực sự tốt nhất có thể, chúng ta có thể tốt với kết quả gần như tối ưu. Ví dụ: nếu hai nhà kho cách điểm đến khoảng 10 km, thì một nhà kho gần hơn 100 mét cũng không thành vấn đề. Nếu chúng ta có thể thực hiện tìm kiếm này nhanh hơn và tìm ra giải pháp tối ưu phụ chỉ 1% và 0. Xa hơn 1% so với giải pháp tốt nhất có thể thì trong nhiều, rất nhiều lĩnh vực, đối với nhiều, rất nhiều vấn đề, nó gần như giống nhau. (43. 44)

Alexei. Tôi có một ví dụ trong đầu, nhưng tôi không chắc đây có phải là một ví dụ tuyệt vời cho cây tìm kiếm không. Tôi làm việc tại OLX. OLX là một thị trường trực tuyến và chúng tôi có một hệ thống giới thiệu ở đó. Trong hệ thống giới thiệu, chúng tôi muốn giới thiệu cho một người những thứ mà họ có thể quan tâm. Hãy nghĩ về Amazon nữa — dựa trên những gì bạn đã thấy trước đây, chúng tôi muốn đề xuất một thứ gì đó mà người dùng có thể quan tâm. Vì vậy, chúng tôi biểu thị từng mục bằng một vectơ 16 chiều — một mảng có 16 số. Sau đó, chúng tôi làm điều tương tự với người dùng — chúng tôi biểu diễn mỗi người dùng dưới dạng một mảng 16 chiều. Bạn có một mảng cho người dùng và bạn có một mảng cho từng mục. Sau đó, đối với mỗi người dùng, chúng tôi muốn tìm mảng mục có thể gần nhất với mảng người dùng. Chúng tôi xem xét tất cả các mục và chúng tôi cố gắng tìm mục gần nhất. Thông thường, chúng ta không cần cái gần nhất. Chúng ta chỉ cần một cái gì đó đủ gần. Nó có phải là một trường hợp sử dụng tốt cho điều đó? . 46)

Marcello. Vâng, đó là một trường hợp sử dụng hoàn hảo. Điều này hoặc tìm hình ảnh tương tự, nếu hình ảnh được dịch sang vectơ đặc trưng. Ví dụ: chúng tôi có thể muốn tìm các hình ảnh tương tự với một sản phẩm mà người dùng — hoặc những người dùng tương tự — đã xem. Thậm chí không chỉ tìm kiếm hồ sơ gần nhất mà cả năm hồ sơ gần nhất với một số người dùng hoặc năm hình ảnh gần nhất. Đó là một trường hợp sử dụng hoàn hảo. (46. 16)

Alexei. Chúng tôi sử dụng một thư viện cho điều đó. Nó được gọi là "faiss", nó đến từ Facebook. Thành thật mà nói, tôi không biết những gì nó thực sự sử dụng bên trong. Tôi chỉ biết rằng nó hoạt động nhanh hơn tìm kiếm vũ phu. Nó có thể sử dụng một trong những cấu trúc dữ liệu bên trong. (46. 50)

Marcello. nó có thể. Các cấu trúc dữ liệu này được sử dụng rất nhiều trong machine learning. Ví dụ: trong phân cụm, K-means hoặc các thuật toán phân cụm khác có thể sử dụng tìm kiếm hàng xóm gần nhất này để tăng tốc thuật toán. (47. 11)

Biết các khung so với biết nội bộ của cấu trúc dữ liệu

Alexey. Chúng tôi có một câu hỏi có thể khá liên quan đến điểm tôi vừa nêu ra — về việc sử dụng thư viện và không nhất thiết phải biết bên trong có gì. Đó là một câu hỏi từ WingCode. Có cần thiết phải biết cấu trúc dữ liệu? . Chúng ta có cần biết những thứ này hoạt động bên trong như thế nào không? . 47)

Marcello. Điều quan trọng nhất là phải biết họ làm việc bên ngoài như thế nào. Những gì bạn có thể mong đợi? . Bạn chỉ cần điều đó nếu bạn phải cải thiện hiệu suất của mình hoặc nếu bạn gặp sự cố. Một trường hợp khác mà bạn có thể muốn biết mọi thứ hoạt động như thế nào là khi bạn phải tùy chỉnh — khi bạn không thể sử dụng thứ gì đó có sẵn và bạn phải tự viết. Một trường hợp khác có thể xảy ra là khi bạn đang sử dụng một ngôn ngữ lập trình mới chưa có thư viện như vậy. Vì vậy, bạn phải viết của riêng bạn. Bạn phải là người đầu tiên. Nhưng phổ biến hơn là bạn phải tự triển khai giải pháp tùy chỉnh. (48. 23)

Nối tiếp bộ lọc Bloom

Alexey. Tôi đang nói về trường hợp sử dụng này của một công ty adtech. Cuối cùng, chúng tôi đã tự triển khai các bộ lọc Bloom. Chúng tôi cần triển khai chính xác như nhau cho nhiều ngôn ngữ — cho Go, cho Java và cho JavaScript. Và đối với Python cũng vậy - bởi vì chúng tôi là nhà khoa học dữ liệu và nhà khoa học dữ liệu làm việc trên Python. Nếu chúng tôi tạo bộ lọc Bloom, chúng tôi cần đảm bảo rằng bộ lọc Bloom này có thể được sử dụng bởi bất kỳ ngôn ngữ nào khác mà chúng tôi đang chạy. Cuối cùng, chúng tôi đã tự triển khai các bộ lọc Bloom. tôi đã làm điều đó. Tôi nhớ rằng tôi đã triển khai từ đâu đó và chỉ triển khai lại nó. Tôi không thể khẳng định rằng tôi thực sự biết nó hoạt động như thế nào. Nhưng nó có vẻ hiệu quả. (49. 52)

Alexey. Trong các bộ lọc Bloom, bạn có kết quả dương tính giả. Vì vậy, bạn cần biết ít nhất một chút về phần bên trong của bộ lọc nở hoa — để hiểu rằng bạn có thể kiểm soát kết quả dương tính giả dựa trên kích thước tập hợp của bạn và dựa trên tỷ lệ lỗi dương tính giả mà bạn muốn. Làm thế nào bạn có thể chắc chắn rằng bạn có thể giảm thiểu tỷ lệ lỗi này? . Nhưng có thể đối với trường hợp sử dụng đầu tiên, bạn có thể tiếp tục và sử dụng thứ gì đó như Google Guava. Đó là một thư viện trong Java, họ sử dụng một cấu hình cài sẵn khá tốt. Bạn không cần quan tâm đến những gì bên trong. Nó chỉ cung cấp cho bạn một bộ lọc Bloom ổn. Sau đó, nếu hiệu suất không tốt, bạn có thể cố gắng hiểu những gì đang diễn ra bên trong và điều chỉnh nó. (50. 44)

Marcello. Đúng. Trường hợp sử dụng này là một ví dụ lý tưởng. Bạn cần tuần tự hóa bộ lọc Bloom này và bạn cần có cùng hạt giống cho các hàm băm. Đó là một trường hợp khác mà bạn có thể muốn kiểm soát những thứ này. (51. 56)

Alexey. Chúng tôi đang sản xuất các bộ lọc Bloom trong công việc Python — chúng tôi là nhà khoa học dữ liệu, đó là ngôn ngữ duy nhất chúng tôi biết. Nhưng sau đó, nó đã được sử dụng bởi các hệ thống sản xuất được viết bằng Java, Go và vì lý do nào đó là JavaScript. Nhưng chúng tôi cần phải đọc những bộ lọc bùng nổ này. đó là niềm vui. tôi thích làm điều đó. (52. 23)

Các vấn đề về thuật toán trong các cuộc phỏng vấn xin việc

Alexey. Bạn nghĩ gì về các cuộc phỏng vấn việc làm? . Bạn đã làm việc tại Twitter, tại Microsoft nữa. Tôi có ấn tượng rằng nếu bạn muốn vào những công ty này, bạn thực sự cần phải biết tất cả "Thuật toán 101" và bạn cũng cần biết các thuật toán nâng cao hơn. Bạn cần biết cây cối, đồ thị, v.v. Bạn nghĩ gì về điều này? . 55)

Marcello. Những công ty này có nhiều kinh nghiệm phỏng vấn người. Thật khó cho tôi để nói. Khi tôi ở Twitter, chúng tôi đã làm việc tích cực để thay đổi cách thực hiện các cuộc phỏng vấn. Khi bạn chỉ tập trung vào các thử thách và thuật toán, bạn sẽ không phỏng vấn những ứng viên có kiến ​​thức và kỹ năng phù hợp. Có lẽ họ sẽ sử dụng chúng. Chắc chắn, thật tốt nếu ứng viên biết về tắc nghẽn hiệu suất và cách họ có thể làm hỏng mọi thứ bằng cách lạm dụng một mảng. Nhưng nó không phải là phần duy nhất của công việc. Có nhiều hơn nữa. Tôi đã từng thấy những ứng viên đã thể hiện xuất sắc trong cuộc phỏng vấn về thuật toán và sau đó họ không thể sử dụng Git. Họ phải bắt kịp rất nhiều trong tháng đầu tiên đi làm. tôi nghĩ nó quá nhiều. Thật tốt khi có một số câu hỏi về những điều này, nhưng cũng tốt để kiểm tra một loạt các kỹ năng khác trong cuộc phỏng vấn. Tôi thích kết hợp các loại phỏng vấn khác nhau. thực hiện một số chương trình cặp hoặc thậm chí một số sửa lỗi trong các cuộc phỏng vấn. Bạn có thể thấy nó thực sự hoạt động như thế nào với người này và những gì họ có thể làm trong công việc. (53. 47)

Alexei. Giống như gỡ lỗi bộ lọc Bloom? . 37)

Marcello. Đó có thể là một khó khăn. (55. 42)

Alexei. Có thể là. Tôi nhớ tôi đã có một cuộc phỏng vấn với Facebook. Tôi không nhớ chính xác các câu hỏi. Nhưng bạn cần phải giải quyết hai vấn đề trong 35 phút. Hai, không chỉ một. Nếu bạn dành 30 phút để giải một câu thì bạn chỉ có năm phút để giải câu thứ hai. Nó quá tàn nhẫn. (55. 45)

Marcello. Khi bạn có thời gian hạn chế, có thể bạn không có ý tưởng ngay lập tức. Cũng vì áp lực. (56. 20)

Alexey. Đối với tôi, họ đã có hai cuộc phỏng vấn như vậy liên tiếp. Vì vậy, hai lần như vậy. Đó là quá nhiều. (56. 32)

Cấu trúc dữ liệu quan trọng cho các nhà khoa học dữ liệu và kỹ sư dữ liệu

Alexei. Tôi không nhận thấy một câu hỏi thú vị. Có khá nhiều thuật toán và cấu trúc dữ liệu. Đối với các kỹ sư dữ liệu, nhà khoa học dữ liệu và tất cả những người khác làm việc với máy học, những thứ cần thiết nhất là gì? . Có điều gì khác mà mọi nhà khoa học dữ liệu và kỹ sư dữ liệu nên ghi nhớ không? . 43)

Marcello. Chắc chắn, những điều cơ bản. Ít nhất là biết tìm kiếm nhị phân là gì - đó là điều bắt buộc. (57. 20)

Alexei. Đặc biệt nếu bạn muốn truy cập Facebook. (57. 33)

Marcello. Nếu bạn chuẩn bị phỏng vấn cho những công ty này, tôi phải chia sẻ rằng tôi cũng từng có trải nghiệm tương tự như bạn. Bạn cũng cần biết tất cả những điều cơ bản và đồ thị — như DFS, BFS, thậm chí cả Dijkstra. Nhưng có lẽ không nhiều hơn thế. Đôi khi tôi gặp những câu hỏi có thể giải được bằng cây xen kẽ hoặc những câu hỏi kỳ lạ hơn. (57. 40)

Alexey. Có các cuộc thi lập trình. Bạn cần sử dụng một số cấu trúc dữ liệu rất thông minh để giải quyết vấn đề ở đó, chẳng hạn như cây khoảng. Những người này sẽ không gặp vấn đề gì khi vào Facebook. (58. 17)

Marcello. Thật ra, tôi đã từng được phỏng vấn bởi một trong những nhà cựu vô địch. (58. 34)

Vừa học vừa làm

Alexei. Có lẽ cái cuối cùng. Bạn có thể đề xuất các tài nguyên tốt để xây dựng các dự án để tìm hiểu cấu trúc dữ liệu và thuật toán không? . Nhưng có lẽ chúng ta có thể xây dựng dự án thú cưng của riêng mình để tìm hiểu cấu trúc dữ liệu và thuật toán? . 53)

Marcello. Có những trang web như leetcode. Bạn có vấn đề ở đó và bạn có thể cố gắng giải quyết chúng. Bạn cũng có thể xem các giải pháp của người khác. Bạn có thể học các kỹ thuật mới để giải quyết các vấn đề tương tự. Một đề xuất khác đang làm việc trên một dự án mã nguồn mở. Bạn có thể tham gia một hoặc bắt đầu của riêng bạn. Bạn cũng có thể nhận phản hồi, đặc biệt nếu bạn tham gia một dự án hiện có. Nếu bạn bắt đầu công việc của mình, bạn sẽ cần phải đặt mình ra khỏi đó để nhận được một số phản hồi. (59. 44)

Tầm quan trọng của các ngôn ngữ được biên dịch đối với các nhà khoa học dữ liệu

Alexey. Cảm ơn bạn. Một câu hỏi khác xuất hiện. Bạn có khuyến nghị các nhà khoa học dữ liệu quan tâm đến cấu trúc dữ liệu và thuật toán chuyển sang các ngôn ngữ được biên dịch như C++ hoặc Java thay vì sử dụng Python không? . 00. 39)

Marcello. Tôi nghĩ Python hoàn hảo cho các nhà khoa học dữ liệu. Nó có các thư viện tốt nhất cho dữ liệu. Nó giống như Esperanto cho khoa học dữ liệu. Nhưng bạn có thể cần triển khai mô hình sản xuất, sau đó bạn có thể cần C++ hơn Java. Nó sẽ cho phép bạn viết mã hiệu suất cao hơn, với đa luồng và kiểm soát tốt hơn đối với các chi tiết cấp thấp. Có lẽ đôi khi đó là sự khác biệt giữa nhà khoa học dữ liệu và kỹ sư dữ liệu. Các kỹ sư dữ liệu có thể thiên về C++ hơn là các nhà khoa học dữ liệu. Nó có thể hữu ích. Nhưng tôi sẽ không đề nghị đổi cái này lấy cái kia. Nhưng có thể tìm hiểu về nó. (1. 01. 09)

Alexey. Và có một thứ gọi là "Cython". Bạn không cần phải bỏ Python hoàn toàn, bạn có thể sử dụng Cython - nó gần như là C. Bạn có thể có mã khá hiệu quả và đã nhập để xử lý số. Bạn vẫn có thể ở trong lĩnh vực Python, nhưng bạn cũng nhận được những lợi ích của việc viết bằng mã gốc. (1. 02. 25)

kết thúc

Alexei. Tôi đoán đó là tất cả cho ngày hôm nay. Làm thế nào mọi người có thể tìm thấy bạn? . 03. 01)

Marcello. Trên Twitter và cả trên Slack. (1. 03. 07)

Alexei. Cảm ơn vì cuộc trò chuyện. Cảm ơn vì đã tham gia cùng chúng tôi hôm nay, vì đã chia sẻ kinh nghiệm của bạn với chúng tôi. Thật tuyệt khi trò chuyện với bạn. (1. 03. 32)

Marcello. Cảm ơn bạn. Cảm ơn bạn một lần nữa vì đã có tôi. (1. 03. 41)

Alexey. Tôi cũng muốn cảm ơn tất cả mọi người đã tham gia với chúng tôi ngày hôm nay và đặt câu hỏi. Đó là nó. Có một ngày cuối tuần tuyệt vời. (1. 03. 42)

Cách tốt nhất để học cấu trúc dữ liệu là gì?

5 cấu trúc dữ liệu chính là gì?

Tôi có thể học cấu trúc dữ liệu trong 3 tháng không?

Bạn có thể dạy mình cấu trúc dữ liệu được không?