So sánh python 2 và 3 cũng như các ngôn ngữ khác c, js, php

#21

vì nó là C++… Nếu bạn muốn xài mảng kiểu C thì sao ko viết code C luôn đi, C++ làm gì?

  • kích cỡ mảng C cố định, ko thay đổi được. Muốn thay đổi phải cấp phát động => y hệt vector
  • kích cỡ mảng C ko quá 2MB (dung lượng tối đa thông thường của stack), muốn nhiều hơn phải xài mảng động => vector
  • truyền mảng vào hàm trong C phải truyền 2 tham số: con trỏ tới phần tử đầu tiên và kích cỡ của mảng. vector chỉ cần truyền 1 tham số.
  • mảng C 2 chiều tĩnh truyền vào hàm cần 3 tham số, vector<vector<>> chỉ cần 1 tham số…
  • cấp phát động cho mảng 2 chiều?
  • một khi đã cấp phát xong thì vector chả khác gì mảng C về mặt tốc độ.
#22

mô tả đơn giản thì nó có 3 biến: 1 con trỏ tới mảng trên heap, 1 số nguyên cho biết số lượng phần tử,tạm gọi là sz, 1 số nguyên cho biết kích cỡ thực của mảng trên heap, tạm gọi là cap.

khi bạn push_back(x), vector sẽ ktra xem nếu sz < cap thì chỉ cần tăng kích cỡ sz lên 1 rồi bỏ x vào. Ngược lại thì nó sẽ tạo mảng mới, có kích cỡ thực gấp đôi kích cỡ cũ, hay new_cap = 2*cap, rồi copy mảng cũ sang mảng mới, rồi mới thêm x vào và tăng sz lên 1 đơn vị.

ko phải lúc nào nó cũng xóa mảng cũ tạo mảng mới, chỉ trong vài trường hợp đặc biệt. Nhưng nó vẫn có xóa mảng cũ tạo mảng mới, vì vậy bạn chỉ nên lưu con trỏ tới phần tử trong vector khi mà vector đó ko bị push back nữa. Hoặc tốt hơn là lưu index, đừng lưu con trỏ…

còn pop_back() thì phức tạp hơn 1 tí. Phần đơn giản nhất là chỉ cần giảm sz đi 1 đơn vị là xong, coi như xóa phần tử cuối rồi. Nhưng ko dừng lại ở đó, mà ta còn phải giải phóng phần tử cuối cùng nữa. Phải gọi dtor cho phần tử đó. Cái này ko đơn giản…

1 Like
#23

tại sao mảng mới lại cần tới kích cỡ gấp đôi mảng cũ, mình vẫn tưởng rằng mảng mới chỉ cần kích cỡ lớn hơn kích cỡ mảng cũ một chút thôi chứ.

#24

gấp đôi để khi bạn push_back n lần, bạn chỉ phải xóa mảng cũ tạo mảng mới khoảng log(n) lần thôi, và gán/copy các phần tử khoảng 3n lần. (nếu mảng có dung lượng vô hạn thì n lần push_back() tốn n lần copy/gán phần tử)

ví dụ mảng ban đầu có 0 phần tử. Bạn push_back() 9 lần
lần 1: tạo mảng mới 1 phần tử, copy 1 lần
lần 2: xóa mảng cũ tạo mảng mới, copy mảng cũ sang mảng mới mất 1 lần copy, thêm phần tử mới vào mất 1 lần copy nữa là 2 lần. Dung lượng mảng hiện tại là 2.
lần 3: xóa mảng cũ tạo mảng mới. Tốn 3 lần copy. Dung lượng mảng hiện tại là 4.
lần 4: vì dung lượng mảng hiện tại là 4 đủ chỗ, nên chỉ cần thêm phần tử mới vào. 1 lần copy
lần 5: xóa mảng cũ tạo mảng mới. Tốn 4+1 = 5 lần copy. Dung lượng mảng hiện tại là 8.
lần 6, 7, 8: chỉ cần 1 lần copy vì đủ chỗ chứa.
lần 9: xóa mảng cũ tạo mảng mới. Tốn 8+1 = 9 lần copy. Dung lượng mảng hiện tại là 16.

tổng cộng 9 lần push_back() bạn phải copy 1 + 2 + 3 + 1 + 5 + 1 + 1 + 1 + 9 = 24 lần copy ~ 3n-3 lần copy.

bạn làm thử với 16 lần, 17 lần push_back nữa sẽ thấy nó ko bao giờ vượt quá 3n lần copy, như vậy “trung bình” mỗi lần push_back() chỉ tốn 3 lần copy, hay là O(1) lần copy. Nếu bạn chỉ tăng dung lượng lên vd 1 đơn vị cho đủ chỗ chứa, thì mỗi lần push_back() phải copy cả mảng cũ rồi tạo mảng mới, như vậy là O(n) lần copy…

cái này gọi là amortized analysis gì đó, có cái dễ có cái khó…

ngồi tính công thức tổng quát cho n lần push_back luôn cũng được:
1 + 2 + 3 + 1 + 5 + 1 + 1 + 1 + 9 + …
1 + (1+1) + (1+2) + 1 + (1+4) + 1 + 1 + 1 + (1+8) + …
= 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + … + 1 + (1 + 2 + 4 + 8 + … + 2k)
= n + [2k+1 - 1]
= n + [2(2k) - 1]
= n + [2(n-1) - 1]
= 3n - 3
với n = 2k + 1 cho lần push_back() cuối cùng là hao nhất.

bạn ngồi tính nếu tăng 3 lần thay vì 2 lần nó có giảm nhỏ hơn 3n-3 ko. Đáp án là có, nhưng tăng 3 lần thì quá tốn bộ nhớ nên người ta tăng 2 thôi. Nếu tăng 1.5 lần thì hằng số c trong cn sẽ lớn hơn 3, tức là “trung bình” 1 lần push_back() sẽ lâu hơn, nhưng tiết kiệm bộ nhớ hơn. Người ta để 2 cho “cân bằng”.

4 Likes
#25

cảm ơn bạn, mặc dù vẫn chưa hiểu cái 3n lắm nhưng nên dừng lại ở đây thôi. Mình nên học tốt kiến thức nền đã.
Cảm ơn bạn

#26

Không khó đối với người học bạn :grinning:. Hơi vất vả đối với những ai đang phát triển những dự án cũ trên python 2 thôi. 3 năm nữa python 2 sẽ chính thức kết thúc và không được cập nhật nữa https://pythonclock.org.

Đa số thư viện lớn đều được chuyển sang python 3 hết rồi nên bạn không phải lo lắng gì nhiều nếu học nó http://py3readiness.org.

1 Like
#27

Mình đang học Python trên https://www.codecademy.com/learn/python , đơn giản và dễ học.

1 Like
#28

Học C++ tinh thần nên dùng vector nhưng mảng vẫn phải được coi là một feature quan trọng của C++ và nó vẫn có chỗ của riêng nó. Ví dụ tôi viết cho hệ thống nhúng và Environment của tôi không cho phép cấp phát động, không phụ thuộc STL. Với những Enviroment cho phép vector thì đôi khi tôi lại cần dùng những chuỗi dự liệu nhỏ và tốc độ nhanh, lúc đó tôi sẽ chọn dùng mảng.

4 Likes
#29

Các hàm của PHP mà bạn thấy nhiều thực ra đến từ các gói thư viện, extensions của nó. Do cách quản lý thư viện của PHP khá là kì cục nên bạn tưởng những hàm như mysql_query là hàm có sẵn, chứ thực ra nó là của extension php-mysql. Cách quản lý thư viện của PHP cũng khá yếu ở chỗ bạn không thể nạp thư viện viết bằng C 1 cách linh động, mà thư viện này phải được build kèm theo PHP (lúc biên dịch trình thông dịch PHP từ mã nguồn C của nó). Chỉ có những thư viện viết bằng PHP thuần mới nạp linh động được. Điều này thì Python làm hay hơn.

Nếu so PHP, Python, NodeJS về sự phong phú của thư viện thì mình nghĩ Python mạnh hơn, vì Python “general purpose” trong khi PHP, NodeJS chủ yếu tập trung cho viết web. Ví dụ Python có rất nhiều thư viện về mảng tính toán khoa học, là cái mà PHP & NodeJS thiếu.

NodeJS thì mình thấy nó rất củ chuối ở chỗ thư viện chuẩn (là bộ thư viện kèm sẵn) rất nghèo nàn, đến nỗi công việc thông thường như format string (tương tự hàm printf của C) nó cũng không có, muốn dùng phải cài thêm thư viện ngoài.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?