it-swarm-vi.com

Big-O có thực sự phù hợp khi làm việc trong ngành không?

Trong tất cả các cuộc phỏng vấn tôi đã tham gia, tôi đã được hỏi về phân tích toán học về độ phức tạp, bao gồm cả ký hiệu big-O.

Làm thế nào có liên quan là phân tích big-O để phát triển trong công nghiệp? Bạn có thường xuyên sử dụng nó không, và cần thiết như thế nào để có một tư duy mài giũa cho vấn đề?

66
MM01

Câu hỏi của tôi là, thử nghiệm này có liên quan như thế nào để phát triển trong ngành công nghiệp?

Một sự hiểu biết vững chắc về lý thuyết phức tạp tính toán (ví dụ: ký hiệu O lớn) là điều cần thiết để thiết kế các thuật toán, ứng dụng và hệ thống có thể mở rộng. Vì khả năng mở rộng có liên quan cao đến điện toán trong công nghiệp, ký hiệu O lớn cũng vậy.

Bạn có thường xuyên sử dụng nó một cách thường xuyên không, và nó cần thiết như thế nào để có một tư duy được mài giũa cho vấn đề này?

Phụ thuộc vào những gì bạn có nghĩa là "sử dụng nó một cách thực sự". Một mặt, tôi không bao giờ làm bằng chứng chính thức về độ phức tạp tính toán cho phần mềm tôi viết. Mặt khác, hầu hết các ngày tôi phải xử lý các ứng dụng trong đó khả năng mở rộng là mối quan tâm tiềm năng và các quyết định thiết kế bao gồm lựa chọn (ví dụ) các loại bộ sưu tập phù hợp dựa trên các đặc điểm phức tạp của chúng.

(Tôi không biết liệu có thể thực hiện nhất quán các hệ thống có thể mở rộng không không có một sự hiểu biết vững chắc về lý thuyết phức tạp. Tôi sẽ có khuynh hướng nghĩ rằng nó không phải.)

76
Stephen C

Lý do cho điều này là vì nó chỉ ra khả năng mở rộng .

Một quá trình là O (n ^ 2) sẽ có quy mô tồi tệ hơn một quy trình là O (n log n), nhưng tốt hơn một quy trình trong O (n ^ 3) hoặc thậm chí O (n!).

Nếu bạn không biết sự khác biệt và khi chúng được áp dụng, bạn sẽ không phù hợp để chọn các triển khai đúng chức năng, cũng như ngoại suy hiệu suất thử nghiệm thành hiệu suất sản xuất.


EDIT: So sánh 48n với n ^ 3 từ http: //www.codinghorror.com/blog/2007/09/everything-is-fast-for-small-n.html (trong đó lần lượt là từ Ngọc trai lập trình)

enter image description here

36
user1249

Nó phụ thuộc vào những gì bạn đang làm.

Đối với các nhà phát triển web (như tôi), điều này thường rất quan trọng. Bạn muốn các ứng dụng web mở rộng quy mô. Nếu ứng dụng của bạn có nút cổ chai mở rộng theo O (n ^ 2) và bạn nghĩ rằng điều này là tốt, bởi vì máy chủ của bạn có thể xử lý 1000 người dùng đồng thời, có vẻ như bạn không cần quan tâm. Vấn đề là, để xử lý gấp đôi số lượng (có thể xảy ra hợp lý chỉ xảy ra trong một đêm), bạn sẽ cần gấp 4 lần sức mạnh tính toán. Lý tưởng nhất là bạn muốn các ứng dụng web mở rộng ở O (n), vì phần cứng rẻ ở tỷ lệ người dùng/máy chủ không đổi hợp lý.

Nói chung trong các ứng dụng, nơi bạn có 100000 đối tượng, O lớn sẽ đến và ăn thịt bạn. Bạn rất dễ bị tổn thương đến đỉnh điểm. Ví dụ: tôi hiện đang làm việc trên một trò chơi 3D, đây là một ứng dụng xử lý vô số dữ liệu. Ngoài kết xuất, bạn có kiểm tra va chạm, điều hướng, v.v. Bạn không đủ khả năng chỉ đi theo cách rõ ràng. Bạn cần các thuật toán hiệu quả, bạn cần rất nhiều bộ nhớ đệm để những cái kém hiệu quả hơn được khấu hao. Và như thế.

Tất nhiên, nếu những gì bạn làm là một cái gì đó giống như tạo một ứng dụng di động bằng cách kết hợp GUI trong một nhà thiết kế giao diện, kết nối với một số dịch vụ web và đó là nó, thì bạn sẽ không bao giờ gặp vấn đề phức tạp. Bởi vì các dịch vụ web bạn gọi đã chăm sóc nó.

32
back2dos

Tôi chưa bao giờ thực sự áp dụng chính thức quy tắc trong cuộc sống làm việc của mình.

Tuy nhiên, bạn phải làm quen với khái niệm đó và áp dụng nó một cách trực quan mỗi khi bạn thiết kế một thuật toán.

Quy tắc là :

Bạn nên đủ quen thuộc với ký hiệu O để có thể xác định, đối với một nhiệm vụ nhất định, nếu cần phải tính toán chính thức hoặc chỉ đủ để đánh giá nó bằng trực giác hoặc nếu bạn có thể bỏ qua hoàn toàn. Cũng giống như nhiều khái niệm toán học cơ bản khác.

22
Wizard79

Chà, có lẽ một câu chuyện nhỏ đã khai sáng cho bạn lý do tại sao nó HOÀN TOÀN IS cần thiết:

Trong một dự án tôi đang làm việc, có một chương trình chịu trách nhiệm in tất cả các loại tài liệu (nhãn, chọn danh sách, v.v.) Chương trình này bao gồm hai phần, một phần đọc tất cả dữ liệu cần thiết từ cơ sở dữ liệu và viết nó vào một tệp kiểu .ini và một phần khác đọc các tệp đó và điền vào các mẫu. Điều này hoạt động khá tốt đối với các nhãn và danh sách nhỏ (chỉ có một vài trường) nhưng nó đã chạy được gần 10 phút khi phải in một danh sách "lớn" gồm ~ 20 trang. Bởi vì việc truy cập các tệp ini này dẫn đến thời gian truy cập O (n²), n là số lượng trường cần in.

Nếu các lập trình viên ban đầu của chương trình này hiểu ký hiệu O, họ sẽ không bao giờ thực hiện theo cách đó. Thay thế sự ngu ngốc đó bằng hashtable khiến nó trở nên nhanh hơn rất nhiều.

10
user281377

Hiệu suất Big-O rất quan trọng, nhưng phần lớn được nội hóa hóa.

Hiệu suất phân loại và tìm kiếm của Big-O không thành vấn đề, bởi vì mọi người thường sử dụng những thứ được cung cấp bởi hệ thống, và những thứ đó sẽ tốt nhất có thể (với điều kiện là chúng cần phải hữu ích). Có các cấu trúc dữ liệu hiệu quả hơn cho những thứ khác nhau, nhưng chúng thường có thể được chọn theo các nguyên tắc chung (và thường được xây dựng thành các ngôn ngữ hiện đại). Có một số ý nghĩa của các thuật toán làm hoặc không mở rộng quy mô.

Kết quả là các vấn đề chính thức hiếm khi xuất hiện trong thực tế, nhưng thực tiễn được xây dựng trên cùng các nguyên tắc.

8
David Thornley

IMHO rất nhiều chương trình khoa học máy tính khiến nhiều sinh viên lang thang dưới đó trong đám cỏ dại. Các chương trình này không bao giờ hoàn toàn truyền đạt bức tranh lớn về những gì khoa học tính toán là tất cả về. Các sinh viên tham gia vào ngành công nghiệp, vật lộn với cách áp dụng các khái niệm họ đã học, với ít hiểu biết về cách họ liên quan đến thế giới thực.

Tôi muốn nói rằng trung tâm của khoa học tính toán là khả năng suy luận về tính toán. Và bạn học các phương pháp và kỹ thuật khác nhau để làm điều này, và áp dụng chúng cho các vấn đề trừu tượng, đó là nguyên thủy nguyên mẫu được tìm thấy trong nhiều vấn đề trong thế giới thực. Bí quyết là phát hiện ra những nguyên thủy nguyên mẫu này trong thế giới thực, và sau đó lý do về những thứ như tính chính xác, độ phức tạp, thời gian, v.v., mà, bạn có thể đồng ý, là những vấn đề thực sự mà bạn cần phải lo lắng. Cái nhìn sâu sắc về cách các bộ phận cư xử, thường xuyên cung cấp cho bạn cái nhìn sâu sắc về cách toàn bộ hành xử. Và các phương pháp và kỹ thuật chung tương tự cũng có thể được áp dụng cho toàn bộ, chỉ là không có cùng sự nghiêm ngặt được dành cho các phần nhỏ hơn, trừu tượng hóa, được xác định rõ. Nhưng cuối cùng, khoa học tính toán, mang đến cho bạn khả năng đưa ra hợp lý quyết định về cách sắp xếp tính toán của bạn, với cái nhìn sâu sắc thực sự về cách nó sẽ hành xử trong các điều kiện khác nhau.

7
Ziffusion

Tự ghi nhớ!:

Tôi và nhiều người khác tự hỏi mình câu hỏi này thường xuyên.

Tôi nghĩ lý do thực sự chúng tôi yêu cầu điều này là vì chúng tôi đã trở nên lười biếng.

Kiến thức này sẽ không bao giờ hẹn hò hoặc trở nên lỗi thời. Bạn có thể không áp dụng nó trực tiếp hàng ngày nhưng bạn sẽ sử dụng nó trong tiềm thức và nó sẽ có ảnh hưởng tích cực đến các quyết định thiết kế của bạn. Một ngày nó có thể giúp bạn hoặc người khác tiết kiệm hàng giờ và ngày mã hóa.

Khi có nhiều vấn đề hơn được gói gọn bởi các thư viện và công cụ của bên thứ 3 và có sẵn cho ngày càng nhiều nhà phát triển, bạn sẽ cần biết kiến ​​thức này để phân biệt mình với những người khác và giúp giải quyết các vấn đề mới.

5
Conor

Không hẳn vậy. Về cơ bản, lần duy nhất tôi từng nghĩ về nó là khi truy cập cơ sở dữ liệu. Tôi thường nhìn vào mã và nói "Đó là thực hiện các truy vấn n + 1, bạn nên thay đổi nó thành chỉ 1 hoặc 2"

Vì tất cả dữ liệu của tôi đang được đọc từ cơ sở dữ liệu và hiển thị cho người dùng, tôi cố gắng giảm thiểu lượng dữ liệu tôi đang làm việc đến mức khác biệt giữa thuật toán tuyến tính và thuật toán O (n ^ 2) không đáng kể.

Nếu có vấn đề, chúng tôi sẽ lập hồ sơ và khắc phục sau.

5
Greg

Ba câu hỏi bạn đặt ra và tôi nghĩ rằng các câu trả lời dạng ngắn có thể hỗ trợ cho các lập luận dài hơn được đưa ra cho đến nay.

Thử nghiệm này có liên quan đến sự phát triển trong ngành như thế nào?

Phụ thuộc vào ngành.

Bất cứ nơi nào mà tốc độ mã hoặc không gian mã là một vấn đề, nó hoàn toàn phù hợp với ngành công nghiệp liên quan. Thường thì bạn cần phải biết một thói quen sẽ mất bao lâu hoặc bao nhiêu bộ nhớ (bật/ngoại tuyến).

Bạn có thường xuyên sử dụng nó không?

Phụ thuộc vào ngành.

Nếu hiệu suất và nhân rộng ít quan tâm đến công việc trong tay, thì hiếm khi, chỉ khi có sự thiếu hụt hiệu suất nghiêm trọng. Nếu bạn là một kỹ sư cho một hệ thống quan trọng được sử dụng nhiều, có lẽ mỗi ngày.

Làm thế nào cần thiết để có một tư duy được mài giũa cho vấn đề?

Hoàn toàn cần thiết.

Bạn có thể phải sử dụng nó hàng ngày, hoặc chỉ trong những trường hợp nghiêm trọng; nhưng đôi khi nó sẽ cần thiết Tốt nhất là trong quá trình thiết kế trước khi một vấn đề xảy ra, hơn là tuyệt vọng cấu hình một hệ thống nghẹt thở.

3
Orbling

Tôi muốn nói rằng nó rất thường xuyên. Chúng tôi thường không chứng minh một cái gì đó có chữ O lớn, nhưng chúng tôi đã nội tâm hóa ý tưởng và ghi nhớ/làm quen với các đảm bảo chữ O lớn cho các cấu trúc dữ liệu và thuật toán cụ thể và chúng tôi chọn những thuật toán nhanh nhất cho một mục đích sử dụng cụ thể. Nó giúp có một thư viện có đầy đủ tất cả các tùy chọn, như thư viện bộ sưu tập Java hoặc C++ STL. Bạn hoàn toàn sử dụng big-O mỗi ngày = khi bạn chọn sử dụng Java.util.HashMap (O(1) lookup) thay vì Java.util.TreeMap (O(lg n) lookup) và chắc chắn chọn không chạy tuyến tính tìm kiếm trên Java.util.LinkedList (O(n) lookup) để tìm thứ gì đó mà bạn không cần truy cập được sắp xếp.

Khi ai đó chọn triển khai dưới mức tối ưu và ai đó biết rõ hơn xuất hiện và xem mã của họ, đó là một phần từ vựng của chúng tôi để sửa lỗi cho họ "việc triển khai của bạn mất thời gian bậc hai, nhưng chúng ta có thể giảm thời gian này xuống bằng cách thực hiện nó theo cách này thay vì "một cách tự nhiên và tự động như chúng ta sẽ sử dụng ngôn ngữ tiếng Anh để đặt bánh pizza.

3
Ken Bloom

Bạn có thể không phải thực hiện các phân tích chính thức, nhưng ít nhất là một sự hiểu biết sâu sắc về thứ tự độ phức tạp của thuật toán - và cách so sánh hai thuật toán xung quanh đó - là rất quan trọng nếu bạn muốn thực hiện công việc không tầm thường và làm cho nó trở nên tốt.

Tôi đã làm việc trên hai hệ thống khác nhau có vẻ tốt trong giai đoạn đầu phát triển, nhưng đã đưa phần cứng đến đầu gối trong thử nghiệm sản xuất, vì ai đó đã sử dụng thuật toán O (n ^ 2). Và trong cả hai trường hợp, bản sửa lỗi là một thay đổi nhỏ đối với thuật toán O(n).

3
Bob Murphy

Nó có thể được sử dụng ở những nơi họ đang phát triển API để tiêu thụ. C++ STL là một trong số ít các API có các hạn chế phức tạp được áp đặt cho các thuật toán của nó. Nhưng đối với các lập trình viên làm việc hàng ngày/lập trình viên/nhà thiết kế/kiến ​​trúc sư làm việc hàng ngày thì điều đó không ảnh hưởng nhiều đến họ.

1
sashang

Tôi không thấy nó quan trọng ngoại trừ việc truyền đạt ý tưởng và tôi làm việc trong các lĩnh vực quan trọng về hiệu suất (raytracing, xử lý hình ảnh và lưới, hệ thống hạt, động cơ vật lý, v.v.) và đã phải nghĩ ra nhiều thuật toán và cấu trúc dữ liệu độc quyền khi làm việc trong R & D. Trong các lĩnh vực này, thường một số ít các cấu trúc dữ liệu và thuật toán rất hiệu quả có thể mang lại toàn bộ các sản phẩm tiên tiến mới trong khi các thuật toán của ngày hôm qua làm cho các sản phẩm hiện tại trở nên lỗi thời, vì vậy luôn có một mục tiêu là làm mọi thứ hiệu quả hơn. Như một lời cảnh báo, tôi chưa bao giờ xuất bản bất kỳ bài báo nào về các thuật toán mà tôi nghĩ ra. Họ đều là độc quyền. Nếu tôi đã làm, tôi cần sự trợ giúp của một nhà toán học để xây dựng các bằng chứng và vv.

Tuy nhiên, theo tôi, số lượng công việc tính toán trên mỗi lần lặp thường được quan tâm nhiều hơn so với khả năng mở rộng của thuật toán trừ khi thuật toán có tỷ lệ thực sự kém. Nếu ai đó nghĩ ra một kỹ thuật tiên tiến để raytracing, tôi quan tâm đến các kỹ thuật tính toán như cách họ thể hiện và truy cập dữ liệu hơn là độ phức tạp thuật toán vì khả năng mở rộng hợp lý đã được đưa ra trong kịch bản cạnh tranh và đổi mới này. Bạn không thể cạnh tranh với các thuật toán không mở rộng.

Tất nhiên nếu bạn so sánh độ phức tạp bậc hai với tuyến tính, đó là một sự khác biệt rất lớn. Nhưng hầu hết mọi người trong lĩnh vực của tôi đủ khả năng để tránh áp dụng thuật toán phức tạp bậc hai trên một đầu vào sử thi. Vì vậy, khả năng mở rộng thường được ngụ ý sâu sắc và các câu hỏi thú vị và ý nghĩa hơn sẽ trở thành như thế, "Bạn đã sử dụng GPGPU? SIMD? Nó có chạy song song không? Làm thế nào bạn biểu diễn dữ liệu? Bạn đã sắp xếp lại nó cho thân thiện với bộ nhớ cache Các mẫu truy cập? Mất bao nhiêu bộ nhớ? Nó có thể xử lý mạnh trường hợp này không? Bạn có trì hoãn việc xử lý nhất định hoặc thực hiện tất cả trong một lần không? "

Ngay cả thuật toán tuyến tính cũng có thể vượt trội hơn thuật toán thời gian tuyến tính nếu trước đây truy cập bộ nhớ theo mẫu tối ưu hơn, ví dụ, hoặc phù hợp hơn cho đa luồng và/hoặc SIMD. Đôi khi, ngay cả một thuật toán tuyến tính cũng có thể vượt trội hơn thuật toán logarit vì những lý do này và thuật toán thời gian tuyến tính tự nhiên vượt trội hơn thuật toán logarit đối với các đầu vào thiếu niên.

Vì vậy, với tôi điều quan trọng hơn là một số người có thể gọi là "tối ưu hóa vi mô", như biểu diễn dữ liệu (bố cục bộ nhớ, mẫu truy cập với phân tách trường nóng/lạnh, v.v.), đa luồng, SIMD và đôi khi là GPGPU. Trong một lĩnh vực mà tất cả mọi người đều có đủ khả năng sử dụng các thuật toán tiên tiến cho mọi thứ với các bài báo mới được xuất bản mọi lúc, Edge cạnh tranh của bạn trong việc đánh bại các thuật sĩ thuật toán không đến từ sự cải tiến về độ phức tạp thuật toán nhiều hơn trực tiếp hiệu quả tính toán.

Lĩnh vực của tôi bị chi phối bởi các nhà toán học lỗi lạc nhưng không phải lúc nào cũng là những người biết chi phí tính toán cho những gì họ đang làm hoặc rất nhiều thủ thuật cấp thấp hơn để tăng tốc mã. Đó thường là Edge của tôi vượt qua chúng trong việc đưa ra các thuật toán và cấu trúc dữ liệu nhanh hơn và chặt chẽ hơn mặc dù tôi kém tinh vi hơn rất nhiều. Tôi đang chơi những gì phần cứng thích, hướng tới bit và byte và làm cho mỗi lần lặp công việc rẻ hơn rất nhiều ngay cả khi tôi đang thực hiện một vài lần lặp công việc hơn thuật toán thực sự tinh vi - công việc trong trường hợp của tôi rẻ hơn rất nhiều. Mã tôi viết cũng có xu hướng đơn giản hơn rất nhiều. Nếu mọi người nghĩ rằng các phiên bản tối ưu hóa vi mô của các thuật toán và cấu trúc dữ liệu đơn giản là khó hiểu và duy trì, hãy thử hiểu và duy trì một bộ các thuật toán và cấu trúc dữ liệu liên quan đến lưới kỳ lạ chưa từng thấy trong ngành với các bài báo 20 trang mô tả các bước của họ về mặt toán học. .

Để làm ví dụ cơ bản, tôi đã đưa ra một cấu trúc lưới đơn giản, kết quả vượt trội so với cây KD tại công ty chúng tôi để phát hiện va chạm và loại bỏ điểm thừa. Lưới thô sơ ngu ngốc của tôi ít phức tạp hơn về mặt thuật toán và tôi ngu ngốc hơn về mặt toán học và thuật toán so với người thực hiện cây KD với cách tìm điểm trung bình mới lạ của mình, nhưng tôi chỉ điều chỉnh cách sử dụng và truy cập bộ nhớ của lưới và thế là đủ để vượt trội hơn một thứ gì đó tinh vi hơn nhiều.

Một lợi thế khác mà tôi có cho phép tôi tồn tại trong một lĩnh vực bị chi phối bởi những người thông minh hơn tôi rất nhiều là tôi thực sự hiểu cách người dùng làm việc, vì tôi sử dụng phần mềm tôi phát triển theo cách tương tự. Điều đó cho tôi ý tưởng về các thuật toán thực sự phù hợp rất ngay lập tức với sở thích của người dùng. Như một ví dụ cơ bản ở đó, hầu hết mọi người đều cố gắng tăng tốc những thứ như phát hiện va chạm bằng cách sử dụng lập chỉ mục không gian. Tôi đã thực hiện một quan sát định hình nghề nghiệp đơn giản gần một vài thập kỷ trước cho các mô hình hữu cơ, ví dụ, nếu một nhân vật đặt tay lên mặt, một cấu trúc lập chỉ mục không gian sẽ muốn phải phân chia các nút và cập nhật đắt tiền nếu nhân vật đó rồi đưa tay ra khỏi mặt. Thay vào đó, nếu bạn phân vùng dựa trên dữ liệu kết nối thay vì vị trí đỉnh, bạn có thể kết thúc với cấu trúc phân cấp ổn định, cập nhật rất nhanh và không bao giờ cần phải phân tách hoặc cân bằng lại cây (chỉ phải cập nhật các hộp giới hạn mỗi khung hình động). .. những thứ như thế này - thuật toán một đứa trẻ không có nền tảng toán học nặng nề có thể xuất hiện nếu chúng chỉ hiểu khái niệm cơ bản, nhưng những thuật toán đã lảng tránh các nhà toán học vì chúng không nghĩ về những thứ rất gần với cách người dùng đã làm việc và đã suy nghĩ quá nhiều về các tính chất của hình học chứ không phải cách hình học thường được sử dụng. Tôi hợp nhau đủ tốt bằng cách dựa nhiều hơn vào kiến ​​thức tính toán chung và kiến ​​thức cuối của người dùng hơn là thuật sĩ thuật toán. Vì vậy, dù sao, tôi thực sự thấy điều quan trọng là tập trung vào độ phức tạp thuật toán.

1
user204677

Tôi không bao giờ nghĩ về O lớn trong một quan điểm toán học, tôi không bao giờ nghĩ về O lớn, trừ khi được hỏi. Tôi chỉ nhìn thấy một thuật toán trong đầu và tôi có thể biết liệu nó có tệ không vì nó có nhiều vòng lặp thông qua bộ nhớ cho mỗi N, hoặc nếu nó phân chia và chinh phục hay đại loại như thế. Nếu cần, tôi có thể dịch nó sang ký hiệu O lớn trong vài giây, nhưng tôi dễ dàng biết được thuật toán/container hoạt động với bộ nhớ hơn là nghĩ về phối cảnh toán học.

0
Coder

Vâng, vấn đề phức tạp trong ngành công nghiệp. Nếu bạn kết thúc việc thiết kế một cái gì đó trong đó một con đường quan trọng có tỷ lệ là N bình phương (nhân đôi số thứ làm cho hệ thống được tải gấp bốn lần), bạn sẽ chạm vào nút cổ chai của mình nhanh hơn nhiều so với khi bạn có thứ gì đó có tỷ lệ tại N.

Tuy nhiên, nó thường không được thực hiện như một bằng chứng chính thức, chính thức, rằng một cái gì đó ở một độ phức tạp nhất định, do đó, có một trực giác tốt cho sự phức tạp của một mô hình hoạt động là một khởi đầu tốt.

0
Vatine