#computerScience #algorithm #complexity #j2team_share

Q: Đã đến lúc này rồi, liệu rằng máy tính có cần phải nhanh hơn nữa không?

A: Emanuel Falkenauer, Tiến sĩ Khoa học Máy tính & Phát Minh ra Thuật toán Di truyền theo Nhóm

L: 1500 word[
[LINK]](https://l.facebook.com/l.php?u=https%3A%2F%2Fwww.quora.com%2FDo-computers-really-need-to-be-any-faster-at-this-point%2Fanswer%2FEmanuel-Falkenauer%3Ffbclid%3DIwAR0Em9gp0raIbKq-ZJytfxiYy4dkNe5imWOM--tJ6iX-74q6NSiYmVTjEYQ&h=AT2-ysY3OVhEbtZNggrLaxhhqQBOj4pF3TMC_vdh579pe46pbp18djCmUQIAij-SV1xdrsBtXqLXgULSOIcCQNM2HrIrvmhNWoe6PCU0V54Is9F6a5MSOUru0l_tklFnS3litQSIux7ZhC1B7FBSioiMuw)

===========

Không chỉ *đang* nhanh hơn đâu, chúng sẽ **luôn luôn nhanh hơn!**

Ấy là vì có những bài toán ***tối ưu tổ hợp*** cần được giải quyết, những bài toán có ứng dụng *thực tế *quan trọng— cùng với *nhu cầu sức mạnh tính toán vô tận* để giải những bài toán đó **với ** **tốc độ nhanh nhất **có thể (theo nghĩa chất lượng của giải pháp).

Dưới đây là một ví dụ thô thiển mà tôi đang nghiên cứu. Tại một cảng container, những chiếc container được chồng lên nóc nhau, như thế này: [ẢNH]

trong lúc chờ được vận chuyển. Đối với mỗi chiếc container, khi một xe tải đến nơi, cần cẩu sẽ nhấc nó lên khỏi sân và đặt lên xe tải rồi khởi hành.

Ô khoan, chờ chút đã… có *thực thế không?* Điều gì sẽ xảy ra nếu xe tải tới lấy container màu trắng được chỉ bằng mũi tên đỏ trong hình?

[Ảnh 2]

Có bốn *container khác nằm trên nó đang chờ được chuyển đi cơ*… vì thế trước khi đưa được nó lên xe tải, cần cẩu phải di chuyển những container trước đó ra chỗ nào đó chỉ để lôi được một chiếc ra — tốn một lượng thời gian rất lớn *chẳng để làm gì*: **Chỉ cần** chiếc màu trắng đó nằm trên cùng khi chiếc xe tải đến nơi thôi mà! Trong thực tế, cần *nhiều* container được chuyển đi để có thể dọn chỗ cho những chiếc cần lấy, hơn là số container được chuyển lên — và những lần vận chuyển *lãng phí* này tốn tới *hàng triệu đô* về mặt hiệu quả.

Giờ thì, hóa ra việc đặt chỗ cho các container có thể được **tối ưu** (khi đã biết được thời gian đến và đi), từ đấy trong phần lớn thời gian, container sắp đi *đều ở (gần) trên cùng* cột đó. Bạn có thể nghĩ rằng “Tuyệt cú mèo! Cứ viết một chương trình cho nó đi — *ngày nay máy tính mạnh lắm*, dễ như bê lễ ấy mà!”

Chậc, vấn đề là thế này này, những chiếc tàu chở container lớn chứa hàng ngàn container, vì thế khi một chiếc đến cảng, *hàng ngàn chiếc container sẽ cần được hạ xuống* bến. Mặt khác (như hình đầu tiên đã chỉ ra), thông thường sẽ có khoảng *vài trăm cột* trên bến — và với mỗi container trong số đó, cần chọn ra được cột *tốt nhất*.

Điều này tạo ra một bài toán *tối ưu cực kỳ phức tạp*. Để minh họa thì, tôi đang “chơi” dữ liệu một chút, 6000 container cần được *xếp chỗ một cách tối ưu* trong bến có 600 cột, từ đó giảm thiểu tối đa số lần di chuyển kém hiệu quả. Tức là về cơ bản, thuật toán của tôi cần chọn một trong 600 cột để đặt container đầu tiên, một trong 600 cột để đặt container thứ hai, và cứ như vậy, 6000 lần tất cả. Từ đó, số lượng khả năng chọn ra *cột tốt nhất* có thể có (tức là kích thước của *không gian tìm kiếm* của bài toán) là 600^6000=10^16668, một con số có **16.668 chữ số**. Để mô tả cho bạn biết được đôi chút về độ lớn của con số đó, hãy nghĩ về số lượng*tất cả các hạt cơ bản có trong **cả Vũ trụ*** là một số có “khoảng” **100 chữ số** hoặc tương tự thế (ước lượng tạm thời, không bao gồm vật chất đen (dark matter): WIKI ).

Vì thế, đó là… một *bài toán khó* giải— nói nhẹ một chút là vậy. Với những thuật toán cực kỳ thông minh *việc này có thể được giải quyết* (thực sự thì với chỗ dữ liệu này, tôi đang làm rất tốt đó), nhưng độ khó của nó là do bạn muốn có được lời giải có chất lượng tốt hơn (rất, rất ít những lần di chuyển container không hiệu quả) **một cách nhanh chóng**, để phản ứng trong thời gian thực với những thông tin mới liên tục được cảng cập nhật về container đến và đi.

Và đó là lúc **tốc độ máy tính trở thành thứ *cốt lõi***: thật tuyệt vời nếu như bài toán có thể được giải một cách tối ưu chỉ trong vòng một giây! Tuy nhiên, từ độ hại não của vấn đề, người ta còn nghi ngờ rằng không biết *liệu* có giải quyết được hay không nữa. Có được một chiếc máy tính *nhanh hơn một triệu lần* chiếc tiền nhiệm ư? May mắn nhỏ nhoi nè: bạn đã loại ra được *sáu chữ số của con số 16668* ở trên rồi đó — bạn chỉ còn lại 16662 thôi nhé.

Và nếu như chuyện này khả thi thì sao? Chậc… thì sau đó họ sẽ yêu cầu bạn xếp chỗ không chỉ 6000 mà là 20000 container (đã có những con tàu mang theo từng ấy rồi đó!), và bạn sẽ có một con số **55561 chữ số**! Về cơ bản thì, bạn lại *bắt đầu từ đầu thôi*.

Và đó là bản chất của tối ưu tổ hợp: bài toán đang — và *sẽ luôn là* như vậy — **luôn luôn lớn hơn** những gì mà máy tính có thể giải quyết theo thời gian đủ ngắn.

Update: Trời, 1.8k upvote… tôi choáng mất rồi, và *rất vui nữa* — **xin cảm ơn** vì sự trân trọng và chia sẻ của các bạn với câu trả lời mang tính kỹ thuật của tôi!

Nhưng ngoài việc kiếm được “Fame Quora” (tôi chẳng bao giờ cần làm vậy), tôi rất vui khi thấy rằng thành công này có được ít nhiều nhờ vào thông điệp chính của mình, tức là tối ưu tổ hợp là **một việc thực sự khó nhằn đó** — cũng như sự khác biệt của nó khi so sánh với việc “lập trình”, hệt như liệu pháp gen rất khác so với việc dán băng vào vết thương ấy: cả hai cái sau đều là “thuốc”… và hai cái trước đều là “lập trình” — quá nhiều luôn đó.

Hi vọng là, bài post này của tôi sẽ giúp bạn hiểu rõ sai lầm lớn về mặt nhận thức mà nhiều người vẫn nghĩ *bấy lâu nay* trong nghề nghiệp của tôi, tức là ***được*** sử dụng thông tin ***không *** đồng nghĩa với việc bạn có thể ngay lập tức***tận dụng*** được chỗ thông tin đó. Vâng, bạn cần có dữ liệu… nhưng đó chỉ là một phần rất nhỏ, thậm chí là không đáng kể (và trong nhiều trường hợp, là tầm thường) trong việc *thực sự giải quyết được * vấn đề. Vậy mà vẫn rất nhiều lần, mọi người (khách hàng đó) yêu cầu có được bất kỳ giao diện nào có thể mà còn *không thèm hỏi xem* liệu chúng tôi có thể thực sự ***giải quyết được vấn đề *** hay không — bởi lẽ đối với họ, có được thông tin (dữ liệu) *đồng nghĩa* với việc giải quyết được vấn đề! từ đó, họ phải đi “giải” *bằng tay* đó, dùng những giao diện cực kỳ đẹp mắt do những bên thầu rẻ nhất cung cấp… và chẳng có khả năng *tối ưu thực sự* nào— chỉ vì nhà cung cấp đó có được chứng nhận SAP hoặc thứ gì đó tương tự. Chẳng cần phải nói, liệu họ có cơ hội giải bài toán với chất lượng *ra sao * khi làm *bằng tay* cơ chứ? Tuyệt đối là *không * nhé— nhưng họ vẫn tin rằng mình có thể xử lý bằng cách dùng bảng trắng (hoặc cái giao diện đẹp đẽ tương ứng), bởi lẽ họ không nhận ra rằng vấn đề này có thể bùng nổ tới mức độ khủng khiếp ra sao.

Tôi hi vọng rằng bài viết của tôi đã chỉ ra rằng câu nói “**dùng được dữ liệu = giải quyết được bài toán**” là mệnh đề *sai* hoàn toàn khi xem xét đến những bài toán *thực sự khó khăn* (như việc đặt container vừa rồi đó). Cũng như ai đó chia sẻ câu trả lời này đã nói, “bài này sẽ làm bạn thay đổi quan điểm…”. Nếu thực vậy thì tôi xúc động lắm. Một lần nữa, xin cảm ơn!

#j2team_share #computerscience #vmc
No 17.
Hỏi: Thời gian dài nhất mà bạn từng dành ra để sửa lỗi code là bao lâu?
Trả lời: Andrew McGregor, Kỹ sư Xác thực Website tại Google (2013-hiện tại)
-------
Sáu năm, cùng với tám kỹ sư. Hơn thế nữa, chúng tôi đã tìm ra lỗi tương tự trong Windows, MacOS, FreeBSD và Linux, với khoảng sáu hoặc bảy thiết bị. Trong trường hợp ví dụ của Linux và FreeBSD mà chúng tôi có thể sửa, những thay đổi cần thiết chỉ là thay đổi hai ký tự trong mã nguồn.

Lỗi đó là như thế này:

Wi-Fi có một thứ gì đó gọi là chế độ ad-hoc (ad-hoc: ám chỉ giải pháp này được sử dụng cho một vấn đề cụ thể, rất khó để tổng quát hóa - ND), một thứ rất hiếm khi được sử dụng những ngày này (có lẽ vì lỗi này vẫn còn). Nó cho phép một nhóm các thiết bị Wi-Fi tạo thành một mạng với nhau, mà không cần có điểm truy cập, và điều này thực sự khá thích thú.

Chúng tôi đang xây dựng các mạng ngoài trời lớn sử dụng chế độ ad-hoc, và chúng tôi nhận thấy rằng sau khoảng sáu tuần hoạt động liên tục, một thiết bị ngẫu nhiên sẽ bắt đầu trở nên rất chậm. Sự chậm trễ này lại có thể bị lây nhiễm: sau thiết bị đầu tiên đó, mỗi lần khởi động lại sẽ có nguy cơ bị chậm khi nó hoạt động trở lại, cho đến khi toàn bộ mạng bị chậm và chúng tôi phải tắt tất cả các thiết bị, và tất cả các máy tính xách tay và thiết bị thử nghiệm từng tham gia vào mạng đó, và khởi động nguội mọi thứ (cold-start- khởi động khi mọi engine đang mát, khác với khởi động nóng - ND). Điều này thật bất tiện vì một số thiết bị nằm ở nóc cột chiếu sáng 45 mét trên sân đường sắt, tại đó chúng tôi phải có sự sắp xếp đặc biệt mới có thể tiếp cận với các công tắc bật tắt...

Chúng tôi đã tìm kiếm lỗi này trong nhiều năm. Chúng tôi tìm thấy hàng tá lỗi khác, và sửa được chúng; một vài bản sửa lỗi đã trở thành các phần tiêu chuẩn của Linux WiFi stack. Chúng tôi đã đổi sang phần cứng mới hai lần, một lần trong số đó có các chip của các nhà thiết kế mà chúng tôi cộng tác trong quá trình phát triển phần cứng.

Chúng tôi đã phát hiện ra nhiều điều:

• Đã có một khoảng thời gian trước khi điều này có thể đã không xảy ra.

• Wi-Fi theo dõi thời gian kể từ khi mạng khởi động; ngay cả trước khi có vấn đề về hiệu suất hoạt động, hệ thống của chúng tôi sẽ được tuyên bố là đã sáu mươi nghìn năm tuổi, và già đi khoảng hai ngàn năm một ngày.

• Điều này được thực hiện với một biến thời gian được gọi là TSF (Timing synchronization function - hàm đồng bộ hẹn giờ - ND) nằm trong các đơn vị của 802.11 TU, mỗi 1.024 micro-giây, kể từ khi mạng được thiết lập.

• Các nút bị chậm sẽ không thể nhận thông tin trong khoảng 90% số thời gian, nhưng có thể truyền tải tốt và luôn nhận được thông tin đúng bởi ngay cả một nút bị chậm khác.

• Thiết bị Wi-Fi vào thời điểm đó rất tệ khi phải chọn những cài đặt máy phát tốt và chúng tôi có thể làm việc đó tốt hơn; chúng tôi sửa chữa vấn đề đó, và khi nó không bị mắc kẹt thì mạng bị chậm đó lại có tốc độ nhanh hơn gấp 10 lần, nhưng sự cố này thực ra lại làm cho vấn đề nút chậm trở nên tồi tệ hơn; các nút bị chậm lại chậm hơn nhiều, và từ đó lây lan nhanh hơn.

Một ngày chúng tôi đã quá mệt mỏi với vấn đề này, chúng tôi quyết định rằng chúng tôi sẽ ngồi trong một phòng họp với tất cả các nhà phát triển những hạt nhân phần mềm của chúng tôi cùng nhau, chiếu mã nguồn trên màn hình máy chiếu và đọc những dòng lệnh cùng nhau.

TSF chính thức là một số 64 bit, nhưng được xử lý ở những vị trí khác nhau tại hậu tố 24, 32 và 48 bit, và mã lệnh phải xác định các bit bị thiếu.

Chúng tôi bắt đầu với tệp định nghĩa cấu trúc dữ liệu cơ bản của stack Wi-Fi. Chúng tôi đưa thêm vài chục dòng lệnh vào tệp tin đó và đã phát hiện ra một dòng mã mà bây giờ tôi không thể tìm thấy, nhưng nó đã định nghĩa kiểu biến sẽ được sử dụng để xử lý các giá trị thời gian. Và nó nói rằng TSF sẽ là một số nguyên 32 bit. Và tất cả chúng ta nhìn vào dòng mã đó, và cuối cùng tôi nói "u32 TSF? Tôi tự hỏi điều đó về mặt toán học đã đúng hẳn chưa... ". Chúng tôi đã đi tìm và nhìn vào mọi chỗ mà nó được sử dụng, và không thể thấy được rằng nó có được sử dụng hay không.

Vì vậy, chúng tôi quyết định làm điều hiển nhiên, và thay đổi nó thành một số nguyên 64 bit. Sau đó chúng tôi xây dựng lại code của chúng mình và khởi động lại mạng, mất một tuần để làm.

Ba tháng sau, mạng vẫn còn tốt và chúng tôi tuyên bố chúng tôi đã sửa được nó.

Chúng tôi đã thử nghiệm tất cả thiết bị Wi-Fi mà chúng tôi có thể chạm tay vào, và khoảng 3/4 trong số đó có cùng một lỗi. Những thiết bị có thể chạy những hệ điều hành khác nhau, chủ yếu là máy tính xách tay của Apple, đôi khi có lỗi trong hai hoặc ba hệ điều hành. Chúng tôi đã báo cáo sự cố này cho tất cả công ty mà chúng tôi có thể tìm thấy: Apple, Microsoft, bốn nhà sản xuất chip, và nhiều cty khác.

Hóa ra có khá nhiều bản thực thi tồi tệ hơn thế: thay vì sử dụng một số 32 bit, họ đã sử dụng 24 bit, và sau đó mạng chạy chế độ ad-hoc của họ sẽ sập sau 4 giờ và 46 phút ... (Tiết kiệm thế làm cái *beep gì k biết).

Nhưng nếu bạn thắc mắc tại sao chúng ta có Bluetooth cho nhiều thứ như vậy trong khi Wi-Fi có thể làm tương tự hoặc tốt hơn ... Lý do nằm ở lỗi này, tôi tin là vậy. Wi-Fi chỉ không đáng tin cậy trong chế độ ad-hoc trong những khoảng thời gian quan trọng, và Bluetooth đã trở thành cách để làm những việc này.

Bài mình dịch từ câu trả lời gốc tại:
https://www.quora.com/What-is-the-longest-amount-of-time-you-have-spent-fighting-a-code-bug/answer/Andrew-McGregor-12

Các bạn hay phải debug kêu in ít thôi nhé ~~