Giúp đỡ về bài toán nghĩ dễ mà hoàn toàn không dễ

aaa

Senior Member
Chào các thím, mình nhận được 1 bài toán, nghĩ nó đơn giản mà hoàn toàn không đơn giản, mong nhận được cao kiến từ các thím
Bối cảnh: Giả sử hệ thống các thím có lượng user rất lớn, số lượng phần tử lên đến hàng trăm triệu records, mỗi user có rất nhiều thuộc tính như tên, tuổi, địa chỉ.... vì số lượng thuộc tính trên mỗi user rất nhiều nên không thể đánh index hết được, và số lượng user records sẽ tiếp tục tăng nhiều nữa.
Vấn đề đặt ra là các thím muốn biết được ngay số lượng có bao nhiêu user (n) thỏa mãn 1 điều kiện filter nhất định (ví dụ tuổi >20,địa chỉ là việt nam...) và điều kiện filter này sẽ linh động thay đổi theo nhu cầu các thím muốn tìm và xem xét theo những gì nên việc đánh index cho tất cả là không tối ưu.

Input: Mảng user arr = [1..N] với số phần tử N rất lớn, mỗi phần tử có rất nhiều thuộc tính(tên, tuổi, địa chỉ...)
Output:
- Hiện thực hàm và thuật toán tối ưu để sắp xếp và trả về số lượng có bao nhiêu user thỏa mãn filter trên mảng đó.
- Cách tối ưu nhất để lưu dữ liệu users
À mà ngôn ngữ hệ thống là Python nhé các thím, mình k biết python có hổ trợ nhiều về phần xữ lý này không.

Một phần nữa là nếu số lượng mảng phần tử user chỉ tương đối, hoàn toàn có thể cache trên RAM thì có cách nào giải quyết bài toán trên tối ưu nhất trên python không các thím, mình mới chuyển qua nghiên cứu thằng này. Khoai quá mấy thím, cũng muốn thử sức mong các thím khai sáng :)
 
Last edited:
dùng database thôi , chứ ai đời dùng hàm thường
Ay7pENF.png

Database sinh ra để làm thứ chú nói mà
Ay7pENF.png
 

sunary

Member
Tôi cũng ạ ông nào hỏi câu này, người ta làm hết rồi ko dùng cứ thích đánh đố, còn để giải quyết cái này thì cứ implement 1 dạng db mới đi cậu, ko chứa hết trên RAM đâu:
+ dùng log merge tree để lưu data theo index
+ tạo các secondary index dựa theo các tiêu chứ filter
 

TTN_vOz

Senior Member
Không biết bài toán này có tương tự phương pháp sort một file 4gb mà ngày xưa hay bị hỏi ko :v
Ý tưởng là tách dữ liệu ra nhiều đoạn, sort song song
rồi merge vào nhau sort tiếp
 

drwpls

Member
Không biết bài toán này có tương tự phương pháp sort một file 4gb mà ngày xưa hay bị hỏi ko :v
Ý tưởng là tách dữ liệu ra nhiều đoạn, sort song song
rồi merge vào nhau sort tiếp
Kỹ thuật sort này là Merge Sort luôn đó thím
 

aaa

Senior Member
Tôi cũng ạ ông nào hỏi câu này, người ta làm hết rồi ko dùng cứ thích đánh đố, còn để giải quyết cái này thì cứ implement 1 dạng db mới đi cậu, ko chứa hết trên RAM đâu:
+ dùng log merge tree để lưu data theo index
+ tạo các secondary index dựa theo các tiêu chứ filter
Filter này động thím ạ, và số lượng trường rất nhiều nên mình nghĩ khó mà đánh hết index dc
Tống vào database đánh index
Còn tự implement giải thuật thì hóng
:D
Nó nói là chưa cần dùng db và đánh index đó thím, implement trên mảng trước
 
Last edited:

Jaffar-T1FE.As

Senior Member
Chào các thím, mình nhận được 1 bài toán, nghĩ nó đơn giản mà hoàn toàn không đơn giản, mong nhận được cao kiến từ các thím
Bối cảnh: Giả sử hệ thống các thím có lượng user rất lớn, số lượng phần tử lên đến hàng trăm triệu records, mỗi user có rất nhiều thuộc tính như tên, tuổi, địa chỉ.... vì số lượng thuộc tính trên mỗi user rất nhiều nên không thể đánh index hết được, và số lượng user records sẽ tiếp tục tăng nhiều nữa.
Vấn đề đặt ra là các thím muốn biết được ngay số lượng có bao nhiêu user (n) thỏa mãn 1 điều kiện filter nhất định (ví dụ tuổi >20,địa chỉ là việt nam...) và điều kiện filter này sẽ linh động thay đổi theo nhu cầu các thím muốn tìm và xem xét theo những gì...
Input: Mảng user arr = [1..N] với số phần tử N lên đến hàng trăm triệu, mỗi phần tử có rất nhiều thuộc tính(tên, tuổi, địa chỉ...)
Output:
- Hiện thực hàm và thuật toán tối ưu để sắp xếp và trả về số lượng user cần filter trên mảng đó.
- Cách tối ưu nhất để lưu dữ liệu users
À mà ngôn ngữ hệ thống là Python nhé các thím, mình k biết python có hổ trợ nhiều về phần xữ lý này không.
Thanks các thím
Làm nhiều array là ổn.
Mình VD cho 1 bài
VD: có 100 phần tử được nhập của N = 100
gồm 5 thuộc tính của user U name - Tên, ns - tuổi, qq - quê quán, đc - Địa chỉ, nn - nghề nghiệp, qq - Quê quán.
==>lọc ra tên những người trên 20 tuổi, địa chỉ tại HCM, làm Công nhân, sinh ra tại Lào, Việt, TQ trong mảng user được nhập.
CÁCH LÀM:
GĐ1: lập mảng
1. XĐ THUỘC TÍNH ĐẶC BIỆT KHÔNG THỂ THAY THẾ CỦA PHẦN TỬ CHO CHUNG 1 MẢNG
. thường là các thuộc tính không đồng bộ được
special -> only 1 user has 1 special.
1.1. array user U thì phần tử u có 3 thuộc tính u.name(tên) + u.ns(tuổi) + u.qq(quên quán).
1.2. array chính là account user U = [u(i), i = 1...N + 1] gồm N phần tử
1.3. tuổi = năm trên máy tính đến hiện tại - ns.
2. các mảng array còn lại là các thuộc tính user mà có thể đồng bộ về tên gọi.
Popular -
the same thing every user can have
gọi là S. Mỗi mảng là 1 thuộc tính user:"Địa chỉ: ĐC, nghề nghiệp: NN,..." S có thể là ĐC, NN,..
trong mỗi mảng s(i) ánh xạ user của u(i),
GĐ2 Search.
GĐ 2.1. Search đặc tính chung chung không cố định.
1. search Địa chỉ nơi ở
chẳng hạn. giá trị Search VD HCM cho ra -> đc = 1, 8, 9, 10, 11 ,15, 30. thì ĐC[đc] -> User[đc].
2. search nghề nghiệp chẳng ra giá trị Công nhân -> cn = 1, 3, 9 ,10, 30 thì NN[nn] -> User[nn].
3. search Quê quán ra Lào, Việt, TQ trong mảng U với thuộc tính u.qq -> Lao: 1, Việt : 3, 10, 20, TQ ra 9,30, 60
U = [u(u.qq)].
1 + 2 + 3 => lọc filter giữa các thuộc tính đc + nn + qq -> kq =1, 9, 10, 30 -> u(kq1) ra trang hiện nhá.
GĐ 2.2 SEARCH THUỘC TÍNH ĐẶC BIỆT SAU CÙNG. kq2
4. Search
;LỌC từ 20 tuổi trở lên thì lấy filter: 2020-u.ns > 19. u.ns = 9, 10, 30. -> u(kq2)
GĐ3. Lọc giữa kq1 và kq2 -> ra kq cần tìm
5. GÁN kq
= 9, 10, 30 từ U ta có Mảng cần search cho ra KQ = [u(kq), kq = 9, 10, 30]
Hiện giá trị mảng cần tìm kq ra màn hình -> hết
 

aaa

Senior Member
Làm nhiều array là ổn.
Mình VD cho 1 bài
VD: có 100 phần tử được nhập của N = 100
gồm 5 thuộc tính của user U name - Tên, ns - tuổi, qq - quê quán, đc - Địa chỉ, nn - nghề nghiệp, qq - Quê quán.
==>lọc ra tên những người trên 20 tuổi, địa chỉ tại HCM, làm Công nhân, sinh ra tại Lào, Việt, TQ trong mảng user được nhập.
CÁCH LÀM:
GĐ1: lập mảng
1. XĐ THUỘC TÍNH ĐẶC BIỆT KHÔNG THỂ THAY THẾ CỦA PHẦN TỬ CHO CHUNG 1 MẢNG
. thường là các thuộc tính không đồng bộ được
special -> only 1 user has 1 special.
1.1. array user U thì phần tử u có 3 thuộc tính u.name(tên) + u.ns(tuổi) + u.qq(quên quán).
1.2. array chính là account user U = [u(i), i = 1...N + 1] gồm N phần tử
1.3. tuổi = năm trên máy tính đến hiện tại - ns.
2. các mảng array còn lại là các thuộc tính user mà có thể đồng bộ về tên gọi.
Popular -
the same thing every user can have
gọi là S. Mỗi mảng là 1 thuộc tính user:"Địa chỉ: ĐC, nghề nghiệp: NN,..." S có thể là ĐC, NN,..
trong mỗi mảng s(i) ánh xạ user của u(i),
GĐ2 Search.
GĐ 2.1. Search đặc tính chung chung không cố định.
1. search Địa chỉ nơi ở
chẳng hạn. giá trị Search VD HCM cho ra -> đc = 1, 8, 9, 10, 11 ,15, 30. thì ĐC[đc] -> User[đc].
2. search nghề nghiệp chẳng ra giá trị Công nhân -> cn = 1, 3, 9 ,10, 30 thì NN[nn] -> User[nn].
3. search Quê quán ra Lào, Việt, TQ trong mảng U với thuộc tính u.qq -> Lao: 1, Việt : 3, 10, 20, TQ ra 9,30, 60
U = [u(u.qq)].
1 + 2 + 3 => lọc filter giữa các thuộc tính đc + nn + qq -> kq =1, 9, 10, 30 -> u(kq1) ra trang hiện nhá.
GĐ 2.2 SEARCH THUỘC TÍNH ĐẶC BIỆT SAU CÙNG. kq2
4. Search
;LỌC từ 20 tuổi trở lên thì lấy filter: 2020-u.ns > 19. u.ns = 9, 10, 30. -> u(kq2)
GĐ3. Lọc giữa kq1 và kq2 -> ra kq cần tìm
5. GÁN kq
= 9, 10, 30 từ U ta có Mảng cần search cho ra KQ = [u(kq), kq = 9, 10, 30]
Hiện giá trị mảng cần tìm kq ra màn hình -> hết
Cảm ơn thím, mình còn 1 điểm thắc mắc trong góp ý của thím là đoạn này
S có thể là ĐC, NN,..
trong mỗi mảng s(i) ánh xạ user của u(i)
>>Như vậy mỗi trường sẽ được tổ chức thành 1 mảng, tuy nhiên mình chưa rõ chỗ thím nói ánh xạ qua u(i), thím sẽ ánh xạ qua 3 thuộc tính u.name(tên) + u.ns(tuổi) + u.qq(quên quán) đúng không, nếu ánh xạ qua key đó mình nghĩ dữ liệu trong mảng sẽ bị trùng lặp kiểu như vậy

Mảng DC
u1 Sài Gòn
u2 Hà Nội
u3 Sài Gòn
u4 Đà Nẵng
không biết mình đã hiểu đúng ý thím chưa, mong nhận được thêm sự chỉ giáo. Cảm ơn thím
 

TrungNgaoNgo

Senior Member
Hàng trăm m mà lưu hết trên ram á , mẹ tưởng lưu trên file load từng phần vào xử lý thôi chứ
 

Jaffar-T1FE.As

Senior Member
Cảm ơn thím, mình còn 1 điểm thắc mắc trong góp ý của thím là đoạn này
S có thể là ĐC, NN,..
trong mỗi mảng s(i) ánh xạ user của u(i)
>>Như vậy mỗi trường sẽ được tổ chức thành 1 mảng, tuy nhiên mình chưa rõ chỗ thím nói ánh xạ qua u(i), thím sẽ ánh xạ qua 3 thuộc tính u.name(tên) + u.ns(tuổi) + u.qq(quên quán) đúng không, nếu ánh xạ qua key đó mình nghĩ dữ liệu trong mảng sẽ bị trùng lặp kiểu như vậy

Mảng DC
u1 Sài Gòn
u2 Hà Nội
u3 Sài Gòn
u4 Đà Nẵng
không biết mình đã hiểu đúng ý thím chưa, mong nhận được thêm sự chỉ giáo. Cảm ơn thím

phải phân biệt dữ liệu thì special -> thuộc tính. popular -> array.
riêng mảng array thì đừng dùng string để ánh xạ mà dùng i là số tự nhiên cho trên mảng U = u(i) ánh xạ trên các mảng khác cho dễ. Coi như STT trên Database cho dễ hiểu.
 

aaa

Senior Member
phải phân biệt dữ liệu thì special -> thuộc tính. popular -> array.
riêng mảng array thì đừng dùng string để ánh xạ mà dùng i là số tự nhiên cho trên mảng U = u(i) ánh xạ trên các mảng khác cho dễ. Coi như STT trên Database cho dễ hiểu.
Cảm ơn thím, nó giống như cách mình đang hiểu, mình vẫn nghĩ tổ chức kiểu này sẽ gây lặp dữ liệu
 

Jaffar-T1FE.As

Senior Member
Cảm ơn thím, nó giống như cách mình đang hiểu, mình vẫn nghĩ tổ chức kiểu này sẽ gây lặp dữ liệu
Mảng DC
u1 Sài Gòn
u2 Hà Nội
u3 Sài Gòn
u4 Đà Nẵng

KHÔNG NÊN ĐỂ MẢNG KIỂU NÀY.
NÊN ĐỂ MẢNG THEO i nhá. Gán giá trị địa chỉ theo i của u(i) trong mảng U.coi i như số thứ tự (ID) cần nhập từ 1 đến N thôi. i là giá trị phần từ thứ i trong 1 mảng bất kì đó.
mấy cái địa danh nên gán như dưới nhá
User Popular special
U(1)= 1 ĐC(1) Sài Gòn => Name(1) = Tùng A
U(2)=2 ĐC(2) Hà Nội => Name(2) = Xuân
U(3)=3 ĐC(3) Sài Gòn => Name(3) = Trang
U(4)=4 ĐC(4) Đà Nẵng => Name(4) = Minh
U(5)=5 ĐC(5) Sài Gòn => Name(5) = Linh
U(6)=6 ĐC(6) Hà Nội => Name(6) = Tùng B
U(7)=7 ĐC(7) Đà Nẵng => Name(7) = Nam A
U(8)=8 ĐC(8) Sài Gòn => Name(8) = Nam B
mấy cái search lọc ra giá trị của i rồi dựa theo i để hiện trường cần tìm ra bảng Filter.
phải search các trường dạng popular -> các giá trị i trước, rồi mới lọc special theo các giá trị i đã tìm được sau để ra kết quả.
 
Last edited:

hissteria

Senior Member
Em thấy các bác đang làm lại cái bánh xe. Với dữ liệu bảng cột. Python có các thư viện rất tốt là pandas.

Ưu điểm của pandas là hỗ trợ transform dữ liệu, hoặc cũng có thể query như sql.
Pandas có nhược điểm là nó chỉ hoạt động tốt với tầm 1GB dữ liệu csv.

Nếu data của bác quá lớn, thì cần sử dụng distributed computed, có bọn spark chạy trên nền java, có python api. Hoặc nếu dùng python thuần thì có dask hỗ trợ khá tốt.
Đang định trả lời Pandas nếu xử lý in-memory, Pýpark nếu dữ liệu trên external storage, thì bác này trả lời chuẩn rồi.
Nếu ý người hỏi muốn hỏi thuật toán thì merge sort có thể giải quyết
 
Top