View Full Version : Vấn đề này có phải liên quan đến đệ qui k? Xin giúp đỡ...
php_code
08-10-2011, 02:13
http://www.uphinh.vn/image/stream/430536.gif
Mình có bảng user gồm id và parent_id, username,... mỗi id sẽ có parent_id là id khác. Trong trường hợp hình trên, mình đang chạy funtion có id = 1, id 1 này có 2 con là cty1 và cty2 (cty1 và cyt2 có parent_id là 1), cty1 lại có con là cty3 (cty3 có parent_id là id của cty1), cty3 có con là cty4 (cty4 có parent_id là id của cty3)....
Giờ vấn đề là mình dùng cách gì để đếm trong hệ thống của id = 1 có bao nhiêu người, như trong hình thì mình đang chạy funtion có id = 1, vậy trong hệ thống của tôi có 7 người, xin nhờ cao thủ giúp mình cách tính ra con số 7 (số 7 chỉ là ví dụ)
Xin nhờ cao thủ trợ giúp.
Tuyển người design skin cho
Đúng là cần đệ quy đó bạn , hoặc có thể làm thủ công theo mysql_fetch_array
php_code
08-10-2011, 13:34
Post nguyên cái hàm viết = codeigniter, đôi khi nó tính đúng, đôi khi lại sai. Anh em xem dùm mình với.
@stano1: bạn có thể hướng dẫn chi tiết dùm mình k?
public function so_nguoi_co_trong_cay($user_id, $total_users = 0) {
$query_members = $this->db->select('*')
->from('vd_members')
->where('parent_id', $user_id)
->order_by('username', 'ASC')
->get();
$members = $query_members->result();
$total_users += $query_members->num_rows();
if(!empty($members)) {
foreach($members as $member)
{
$is_parent = $this->db->select('*')
->from('vd_members')
->where('parent_id', $member->id)
->order_by('username', 'ASC')
->get()->num_rows();
$total_users += $is_parent;
if($is_parent > 0) {
$this->so_nguoi_co_trong_caycay($member->id, $total_users);
}
}
}
return $total_users;
}
ebookfinder
08-10-2011, 13:50
Bạn dùng phép "tự kết" của 1 bảng, bổ sung thêm trường selfref đánh dấu con đã tìm đc cha, thì bằng câu lệnh SQL cũng cho ra kết quả. Việc viết 1 thủ tục đệ qui để dò mẫu tin trong table, cho dù là dùng stored proc cũng kém hiệu quả lắm.
php_code
08-10-2011, 14:04
Bạn dùng phép "tự kết" của 1 bảng, bổ sung thêm trường selfref đánh dấu con đã tìm đc cha, thì bằng câu lệnh SQL cũng cho ra kết quả. Việc viết 1 thủ tục đệ qui để dò mẫu tin trong table, cho dù là dùng stored proc cũng kém hiệu quả lắm.
Kĩ thuật này mình chưa nghe qua, bạn có thể demo dùm mình k? Chân thành cảm ơn bạn.
Kĩ thuật này mình chưa nghe qua, bạn có thể demo dùm mình k? Chân thành cảm ơn bạn.
"Tự Kết", mình đoán chính là "Tự Liên Kết" hay tiếng Anh là Self Join, đây là kỹ thuật thông thường thôi.
php_code
08-10-2011, 22:17
Thank a Tuấn, e sẽ xem xét vấn đề self join này.
"Tự Kết", mình đoán chính là "Tự Liên Kết" hay tiếng Anh là Self Join, đây là kỹ thuật thông thường thôi.
Thank a Tuấn, e sẽ xem xét vấn đề self join này.
uhm, đây là kỹ thuật tổ chức dữ liệu căn bản trong db, mà thank thì bấm nút thank (like) là được rồi :D, ko cần nói ra đâu :D
php_code
09-10-2011, 19:06
Thật sự là mình làm hết khả năng rồi, nhưng vẫn chưa giải quyết dc vấn đề. Xin nhờ sự giúp đỡ.
ebookfinder
09-10-2011, 20:28
Bạn có thể chỉnh lại cấu trúc bảng đc ko? với các trường: t(id, pid, level, info)
trong đó level(id) = level(pid)+1, level giúp
1) hiển trị cây các id
2) khi sql thì thực hiện theo từng level
bạn cho t tự liên kết:
Giả sử level của id xuất phát là k, đặt cur_level = k-1
set cur_level = cur_level+1; SELECT ... FROM t AS t1 INNER JOIN t AS t2 ON t1.id=t2.pid WHERE t1.level = cur_level
lặp cái sql này đến khi ko còn lấy được thêm mẩu tin.
php_code
10-10-2011, 00:35
t(id, pid, level)
level(id), level(pid) là sao bạn? mình chưa hiểu chỗ này...
Bạn có thể chỉnh lại cấu trúc bảng đc ko? với các trường: t(id, pid, level, info)
trong đó level(id) = level(pid)+1, level giúp
1) hiển trị cây các id
2) khi sql thì thực hiện theo từng level
e
ebookfinder
10-10-2011, 01:06
bạn thêm field 'level', trong đó level con = level cha + 1. Root có level = 0.
php_code
10-10-2011, 01:35
Như vậy thì sao dc bạn? Vì 1 người vừa là con của người này, nhưng có thể là cha của người khác, mô hình tháp mà. và cấp thấp nhất là vô hạn, k có điểm dừng. Ví dụ tôi có con, con tôi có con, con của con tôi có con, con của con của con tôi có con....
ebookfinder
10-10-2011, 02:28
đúng là đặc trưng cho dân tin học VN,
Vậy tháp có đỉnh ko, đó là root, bạn đừng bảo 1 tháp có nhiều hơn 1 đỉnh nhé.
Các level cha, con chỉ là khái niệm tương đối và cấu trúc này có nhiều thể hiện cho mỗi cái như vậy.
Ko ai cấm bạn có nhiều con, nhưng mỗi người chỉ có 1 cha duy nhất. Mệt...
Vấn đề này nếu bạn tham khảo các trang web lớn thì sẽ tìm ra được giải pháp họ đã dùng. Ví dụ trong forum VBB. Nó cũng cho bạn tạo không giới hạn các sub forum. 1->2->3->4... rất nhiều level.
Vậy họ đã giải quyết thế nào? Họ có 2 cột cho mỗi forum: parentlist và childlist, 2 bảng này sẽ lưu trữ các id của các level cha hoặc level con của mỗi forum.
Trong trường hợp của bạn:
cty1: parentlist(1) childlist (3,4)
cty2: parentlist (1) childlist (5,7,6)
... tương tự.
Như vậy thì khi bạn select ra là đã có thể giải quyết được vấn đề rồi.
php_code
10-10-2011, 21:31
đúng là đặc trưng cho dân tin học VN,
Vậy tháp có đỉnh ko, đó là root, bạn đừng bảo 1 tháp có nhiều hơn 1 đỉnh nhé.
Các level cha, con chỉ là khái niệm tương đối và cấu trúc này có nhiều thể hiện cho mỗi cái như vậy.
Ko ai cấm bạn có nhiều con, nhưng mỗi người chỉ có 1 cha duy nhất. Mệt...
Cảm ơn bạn đã nhiệt tình giúp đỡ, dù thế nào cũng cảm ơn bạn rất nhiều.
Vấn đề này nếu bạn tham khảo các trang web lớn thì sẽ tìm ra được giải pháp họ đã dùng. Ví dụ trong forum VBB. Nó cũng cho bạn tạo không giới hạn các sub forum. 1->2->3->4... rất nhiều level.
Vậy họ đã giải quyết thế nào? Họ có 2 cột cho mỗi forum: parentlist và childlist, 2 bảng này sẽ lưu trữ các id của các level cha hoặc level con của mỗi forum.
Trong trường hợp của bạn:
cty1: parentlist(1) childlist (3,4)
cty2: parentlist (1) childlist (5,7,6)
... tương tự.
Như vậy thì khi bạn select ra là đã có thể giải quyết được vấn đề rồi.
Uhm, mình cũng đi theo cách đó, mình có 2 cột là parent_id và follow_id. Parent_id là cột chứ id người ở tầng trên của mình, follow_id chứ id của cha mình(mình là con trực tiếp của người đó).
khi mình thêm 1 member vào hệ thống thì sẽ update follow_id là id sẽ là cha của member đó, và parent_id sẽ là id mình chọn để làm tầng trên của member đó.
và cách mình đệ qui (ví dụ mìh đang chạy function có tham số id là 1)
function total_user($user_id, $total=0)
$query = select * from table where parent_id = $user_id
update biến total;
$total += mysql_num_rows($queyr); // lúc này biến total sẽ là 2
tiếp tục đi vào cấp con
$row = mysql_fetch_assoc($query);
if(!empty($row))
{
while($row = mysql_fetch_assoc($query))
{
// tiếp tục tìm parent_id = $row[id]
$query2 = mysql_query(select * from table where parent_id = $row[id]);
$num = mysql_num_rows($query2);
$total += $num;
lúc này mình kiểm tra nếu biến $num > 0 sẽ gọi lại hàm total_user
if($num>0)
{
$this->total_user($row[id], $total);
}
}
}
Code trên chỉ tính đúng nếu mình chỉ có 1 nhánh và chỉ có 1 con, 1 con lại chỉ có 1 con, 1 con lại chỉ có 1 con,.... thì đúng, nhưng nếu có 2 nhánh thì sẽ sai.
Xin vui lòng xem qua giúp mình với.
Nếu làm theo cách của bạn sonnb thì khi add 1 member vào hệ thống phải tìm ngược lên trên để update cột childlist thì có phiền k? Nếu member dc đang ở tầng 100 thì phải tìm ngược lên 100 member để update, và lúc đó update lại cột childlist của 100 member ở trên?
nnquangit
10-10-2011, 22:47
thường thì trên hệ thống phân cấp nhỏ người ta sẽ dùng dệ quy
id,name,pid
1,Mr A,0
2,Mr B,1
3,Mr B,2
nếu trên 1 hệ thống lớn người ta sẽ làm
id,name,listpid
1,Mr A,0
2,Mr B,1
3,Mr C,1-2
Khi thêm / cập nhật dữ liệu / xóa ... bạn phải tính ra được listpid và cập nhật những row có liên quan. Điều này là bắt buộc rồi vì trên 1 hệ thống lớn vậy không thể thêm / xóa / .... khơi khơi. Nhưng sau này bạn sẽ dễ dàng query nó
Select * ... like "1%" or like "%-1-%" or .....
ebookfinder
11-10-2011, 00:33
Hơn 99.9% dân IT ở VN biết rằng: chuongtrinh = cautrucdulieu + giathuat, nhưng số đông dùng nó để "dội bom" những người ko bít IT chứ ít khi nghĩ đến triết lý sâu sắc của nó trong công việc lập trình của mình. Khi làm 1 CT, trước hết bạn phải xác định cấu trúc DL của CT để từ đó lựa chọn hoặc phát triển giải thuật phù hợp.
Trở lại vấn đề của bạn, tại sao tôi đã đề xuất giải pháp như trong các bài post trước? Nếu bạn lưu dữ liệu trong 1 cấu trúc cây thực sự và địa chỉ của từng node có thể truy cập nhanh chóng bằng con trỏ thì giải thuật đệ qui sẽ là lựa chọn tốt nhất. Nhưng ở đây, cấu trúc DL được triển khai trên CSDL quan hệ, vì vậy cần phải "KHử Đệ Quy" bằng vòng lặp, và để "vòng lặp" đừng lặp lại việc trích 1 dữ liệu nào đó thì thuộc tính "level" (mức) trong CSDL là 1 giải pháp. Việc cài đặt cấu trúc DL trên CSDL cũng có cái hay của nó là khai thác thế mạnh của phép kết (ngôn ngữ đại số quan hệ) và cơ chế chỉ mục (CSDL quan hệ).
Biểu diễn dữ liệu của bạn theo cấu trúc cây với thuộc tính 'level':
root (id=0) level 0, mức trong cây != bậc (degree)
/ \
ct1 ct2 level 1
/ / \
ct3 ct5 ct7 level 2
/ /
ct4 ct6 level 3
Khi đưa vào CSDL quan hệ:
table(id, pid, level)
(1, 0, 1)
(2, 0, 1)
(3, 1, 2)
(5, 2, 2)
(7, 2, 2)
(4, 3, 3)
(6, 5, 3)
*) Muốn tìm toàn bộ cây, đặt cur_level = 0-1 = -1, "bảng" các id là {0}
**) Muốn tìm toàn bộ cây từ 'ct2', đặt cur_level = 1-1 = 0, bảng các id là {2}
Khi thực hiện câu lệnh SQL đầu tiên (xem tôi đã post phần trước),
1) cur_level = cur_level + 1, như trong (**) thì cur_level = 1
2) Chỉ lọc các node có level bằng cur_level, tức là bằng 1 như (**) có quan hệ với id trong "bảng"
3) Nếu 1) và 2) bổ sung thêm mẩu tin cho "bảng" thì lặp lại 1) và 2)
4) Còn nếu không thì "Kết thúc".
Lưu ý:
a) Mỗi khi lặp lại các bước 1) và 2), giá trị cur_level tăng thêm 1, điều đó giúp câu lệnh SQL tiếp tục tìm node mới chứ không lặp lại trên node cũ. Cái này chính xác là "breadth first search" trên cấu trúc cây.
b) Nếu bảng 'table' có chỉ mục theo id, pid và level thì câu lệnh sẽ chạy rất nhanh.
Thực sự tôi ko muốn đi vào chi chiết mỗi khi giúp đỡ 1 vấn đề vì thiết nghĩ sẽ thú vị hơn cho người được giúp đỡ tự phát hiện thêm. Tuy nhiên trong diễn đàn có nhiều người dị ứng với cách này, tôi thì ko có ý kiến nhưng cũng hiểu được như vậy họ chằng có đẳng cấp gì. Hàng ngày tôi cũng phải đối đầu với hàng đống vấn đề mà thuật giải cho nó còn kinh hoàng hơn nhiều. Những lúc như thế, giá mà ai đó cho tôi 1 "tinyray of idea" thôi thì tôi cũng biết ơn lắm. Haiz, vì lương lâm nghề nghiệp và trách nhiệm với đồng nghiệp nên tôi đã cố gắng viết nhiều thế này.
1. Bạn nên query 1 lần ra array và tránh query nhiều lần. Mọi thao tác chọn, lọc là đều làm trên array.
2. Khi add ở tầng 100 ví dụ cty100. Bạn chỉ cần quan tâm cha nó là ai -> cty99. Sau đó thì update tất cả những đứa nào có cty99 ở trong childid thôi. Việc này sẽ dễ dàng khi bạn làm việc trên array khi dùng in_array và không phải query nhiều lần.
3. Khi lưu các bảng parentid và childid bạn dùng serialize array để khi bạn đọc dùng unserialize thì nó trả lại bạn array -> làm việc sẽ dễ dàng và gọn gàng hơn. Khi update ngược lại cũng nhanh.
4. Do query của bạn là dùng theo cách bình thường, cách này người ta chỉ dùng tới level 2, 3 cùng lắm là 4 nên không thể dùng cho trường hợp này được. Rất tốt query và công sức.
php_code
12-10-2011, 04:04
Thank ebookfinder và sonnb, mình tổng hợp cách của 2 pro và đã giải quyết dc vấn đề.
Một lần nữa xin cảm ơn rất nhiều vì sự nhiệt tình của 2 pro.
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.