Lỗi khi sử dụng đệ quy tìm vị trí của giá trị trong mảng được sắp xếp. (2 người xem)

dhn46 · 23/2/14

Dhn46 sử dụng hàm đệ quy sau để chỉ ra vị trí của giá trị cần tìm trong mảng đã được sắp xếp

Mã:

Public rMax As Long, rMin As Long, GT As Long, Arr(), KQ As Long
Function DeQuy(Arr, rMax, rMin) As Long
    If Arr((rMax - rMin) / 2 + rMin, 1) < GT Then
        rMin = (rMax - rMin) / 2 + rMin
        Call DeQuy(Arr, rMax, rMin)
    ElseIf Arr((rMax - rMin) / 2 + rMin, 1) > GT Then
        rMax = (rMax - rMin) / 2 + rMin
        Call DeQuy(Arr, rMax, rMin)
    Else
        KQ = (rMax - rMin) / 2 + rMin
        Exit Function
    End If
End Function

Sub Test là:

Mã:

Sub Test()
    Arr = [A1:A4000].Value
    rMax = Ubound(Arr,1)
    rMin = Lbound(Arr,1)
    GT = 10
    Call DeQuy(Arr, rMax, rMin)
    Debug.Print KQ
End Sub

Nhưng xuất hiện lỗi "Out of stack space" khi áp dụng cho dữ liệu lớn (phụ thuộc cấu hình máy)

Vậy mong các anh chị trợ giúp dhn46 2 câu hỏi:

1/ Tại sao lại xảy ra lỗi "Out of stack space" nói trên và cách khắc phục

2/ Khi dhn46 sử dụng phương pháp duyệt mảng để tìm ra kết quả tương tự thì tốc độ lại cao hơn, nhưng theo logic thì đệ quy sẽ xử lý ít lần so sánh hơn vậy tại sao tốc độ lại có chênh lệch như vậy

Cảm ơn GPE!

VetMini · 23/2/14

dhn46 đã viết:
Dhn46 sử dụng hàm đệ quy sau để chỉ ra vị trí của giá trị cần tìm trong mảng đã được sắp xếp

Mã:

Public rMax As Long, rMin As Long, GT As Long, Arr(), KQ As Long Function DeQuy(Arr, rMax, rMin) As Long If Arr((rMax - rMin) / 2 + rMin, 1) < GT Then rMin = (rMax - rMin) / 2 + rMin Call DeQuy(Arr, rMax, rMin) ElseIf Arr((rMax - rMin) / 2 + rMin, 1) > GT Then rMax = (rMax - rMin) / 2 + rMin Call DeQuy(Arr, rMax, rMin) Else KQ = (rMax - rMin) / 2 + rMin Exit Function End If End Function

Sub Test là:

Mã:

Sub Test() Arr = [A1:A4000].Value rMax = Ubound(Arr,1) rMin = Lbound(Arr,1) GT = 10 Call DeQuy(Arr, rMax, rMin) Debug.Print KQ End Sub

Nhưng xuất hiện lỗi "Out of stack space" khi áp dụng cho dữ liệu lớn (phụ thuộc cấu hình máy)

Vậy mong các anh chị trợ giúp dhn46 2 câu hỏi:

1/ Tại sao lại xảy ra lỗi "Out of stack space" nói trên và cách khắc phục

2/ Khi dhn46 sử dụng phương pháp duyệt mảng để tìm ra kết quả tương tự thì tốc độ lại cao hơn, nhưng theo logic thì đệ quy sẽ xử lý ít lần so sánh hơn vậy tại sao tốc độ lại có chênh lệch như vậy

Cảm ơn GPE!

1. Tại sao lỗi:
Tôi cũng chẳng hiểu code của bạn lắm. Hình như bạn bị lẫn lộn giữa trị và vị trí của phần tử mảng

2. theo logic thì đệ quy sẽ xử lý ít lần so sánh hơn:
Không đúng lắm.
Cách tìm nhị phân sẽ nhanh hơn cách dò dọc vì nó quy vào đích nhanh hơn. Tuy nhiên cách dò nhị phân cũng có thể làm được bằng vòng lặp. Đệ quy chỉ trông đẹp mắt hơn thôi.

Nói chung thì hàm của bạn bị vướng những điểm cấm kỵ sau đây:

(i) tránh dùng biến static và biến global. Trừ phi bắt buộc.

(ii) bên trong hàm, tránh sửa trị các tham số. Trừ phi không thể khác hơn.

(iii) nếu là hàm để tìm một trị thì cho hàm trả về trị đó, không nên dùng biến hay tham số để chứa kết quả
function DeQuyTimViTri(mang() as integer, byVal tri as integer, byVal, dau as integer, duoi as integer) as Integer
...
end function

gọi hàm:
viTri = DeQuyTimViTri(mang, 10, lbound(mang), ubound(mang))

siwtom · 23/2/14

dhn46 đã viết:
Dhn46 sử dụng hàm đệ quy sau để chỉ ra vị trí của giá trị cần tìm trong mảng đã được sắp xếp

Mã:

Public rMax As Long, rMin As Long, GT As Long, Arr(), KQ As Long Function DeQuy(Arr, rMax, rMin) As Long If Arr((rMax - rMin) / 2 + rMin, 1) < GT Then rMin = (rMax - rMin) / 2 + rMin Call DeQuy(Arr, rMax, rMin) ElseIf Arr((rMax - rMin) / 2 + rMin, 1) > GT Then rMax = (rMax - rMin) / 2 + rMin Call DeQuy(Arr, rMax, rMin) Else KQ = (rMax - rMin) / 2 + rMin Exit Function End If End Function

Sub Test là:

Mã:

Sub Test() Arr = [A1:A4000].Value rMax = Ubound(Arr,1) rMin = Lbound(Arr,1) GT = 10 Call DeQuy(Arr, rMax, rMin) Debug.Print KQ End Sub

Nhưng xuất hiện lỗi "Out of stack space" khi áp dụng cho dữ liệu lớn (phụ thuộc cấu hình máy)

Vậy mong các anh chị trợ giúp dhn46 2 câu hỏi:

1/ Tại sao lại xảy ra lỗi "Out of stack space" nói trên và cách khắc phục

2/ Khi dhn46 sử dụng phương pháp duyệt mảng để tìm ra kết quả tương tự thì tốc độ lại cao hơn, nhưng theo logic thì đệ quy sẽ xử lý ít lần so sánh hơn vậy tại sao tốc độ lại có chênh lệch như vậy

Cảm ơn GPE!

1. Đệ qui hay không đệ qui thì bạn không nên dùng biến toàn cục - Public. Mọi giá trị cần trong code của hàm/sub thì truyền vào ở dạng tham số. Mọi giá trị cần trả về thì phải trả về thông qua thông số (khai báo ByRef) hoặc nếu chỉ cần trả về 1 giá trị thì nếu là hàm thì trả dưới dạng giá trị của hàm.
Ngoài các tham số thì code có thể dùng các biến (khai báo trong hàm/sub) cục bộ, vd. để nhớ các giá trị tính toán trung gian. Cũng phải dùng biến cục bộ (local) chứ không dùng biến toàn cục (Public).

2. Dùng đệ qui có nguy hiểm là nếu "độ sâu" đệ qui quá lớn thì có thể sẩy ra "Out of stack space".

Tại sao?

code tôi đã sửa chút

Mã:

Function DeQuy(Arr, rMax, rMin) As Long
    If Arr((rMax + rMin) / 2, 1) < GT Then
        rMin = (rMax + rMin) / 2
'       ...                ' <-- 1
        Call DeQuy(Arr, rMax, rMin) ' <-- A
'       ...                ' <-- 2
    ElseIf Arr((rMax + rMin) / 2, 1) > GT Then
        rMax = (rMax + rMin) / 2
'       ...                ' <-- 3
        Call DeQuy(Arr, rMax, rMin) ' <-- B
'       ...                ' <-- 4
    Else
        KQ = (rMax + rMin) / 2
        Exit Function
    End If
End Function

Khi ở chỗ nào đó trong code của hàm/sub có gọi chính nó thì trước khi thực hiện code của chính hàm đó thì:
1. Địa chỉ trở về của hàm được nhớ trên local stack
2. Giá trị của các biến local được nhớ trên local stack

Điểm 1. Khi gọi đệ quy trở về (return) thì phải biết là sẽ trở về chỗ nào trong code. Ở hàm trên chẳng hạn thì có 2 chỗ gọi đệ qui là vị trí A hoặc B. Trong trường hợp tổng quát thì trước dòng code gọi đệ quy và sau khi gọi thì code có thể thực hiện những tính toán khác trên các biến local. Tức trước và sau A và B có thể có 1, 2, 3, 4. Vậy để biết sau khi trở về (return) thì trở về và thực hiện dòng 2 hay dòng 4 thì phải nhớ địa chỉ trở về - địa chỉ đó phụ thuộc gọi đệ quy ở điểm A hay B.

Điểm 2. Tại thời điểm A hay B thì trạng thái - giá trị của các biến local có thể khác nhau cho mỗi lần thực hiện code của hàm/sub. Vậy để tại điểm 2 hay 4 các tính toán được thực hiện với giá trị đúng của các biến local, y như chúng có trước dòng gọi đệ qui, thì giá trị của chúng được nhớ trên local stack.

Nói nôm na thì địa chỉ trở về được nhớ (PUSH) trên local stack và khi hàm trở về (return) thì giá trị đó được lấy đi (POP) từ local stack. Giá trị của các biến cục bộ cũng được nhớ trên local stack và được lấy đi từ local stack khi hàm trở về để phục hồi lại các giá trị của các biến cục bộ.
--------------
Từ các điều trên thì khi độ sâu của đệ qui rất lớn thì những giá trị phải nhớ trên local stack là rất lớn và nếu vượt quá độ lớn của local stack (thường không nhiều) thì sẽ "Out of stack space"

Ta xét code cực kỳ đơn giản

Mã:

Function hichic(ByVal n As Long) As Long
    If n = 1 Then
        hichic = 1
    Else
        hichic = hichic(n - 1)
    End If
End Function

Sub Test()
Dim n As Long
    n = hichic(6449)
    MsgBox n
End Sub

Code trên chạy không có lỗi - độ sâu đệ quy là 6449

Nếu thay dòng n = hichic(6449) bằng n = hichic(6450) thì có lỗi "Out of stack space". Tức với độ sâu đệ quy >= 6450 thì có lỗi. Tức với ví dụ n = hichic(10000) thì có lỗi.

Trong trường hợp của bạn thì độ sâu đệ quy không lớn. 10^6 < 1024^2 = 2^20. Vậy với mảng 1 triệu phần tử mà không có các lỗi khác thì độ sâu đệ quy cùng lắm là bằng 20.

Vậy code của bạn có những lỗi khác chứ không phải do "sự đe dọa" của độ sâu đệ quy.

Nói trắng ra thì code của bạn chưa chẩn.

Ta xét với ví dụ

Mã:

Function DeQuy(Arr(), ByVal find_value, ByVal rMax As Long, ByVal rMin As Long) As Long
Dim rMid As Long
    rMid = (rMax + rMin) \ 2
    If Arr(rMid, 1) < find_value Then
        Call DeQuy(Arr, find_value, rMax, rMid) ' <-- A
    ElseIf Arr(rMid, 1) > find_value Then
        Call DeQuy(Arr, find_value, rMid, rMin) ' <-- B
    Else
        DeQuy = rMid
    End If
End Function

Sub Test()
Dim Arr(1 To 3, 1 To 1), KQ As Long
    Arr(1, 1) = 1
    Arr(2, 1) = 5
    Arr(3, 1) = 10
    KQ = DeQuy(Arr, 6, 3, 1)    ' <-- C
    Debug.Print KQ
End Sub

Tại <-- C bạn gọi hàm DeQuy => rMid = 2, và Arr(rMid, 1) = Arr(2, 1) = 5 < 6 = find_value => Gọi DeQuy tai <-- A, tức Call DeQuy(Arr, 6, 3, 2) => rMid = 2, và Arr(rMid, 1) = Arr(2, 1) = 5 < 6 = find_value => Gọi DeQuy tai <-- A, tức Call DeQuy(Arr, 6, 3, 2) => ....

Cứ như thế cho tới ngày tận thế - Call DeQuy(Arr, 6, 3, 2) muôn đời. Nhưng thực ra chưa tới ngày tận thế thì đã có lỗi "Out of stack space" vì với một độ sâu đệ quy đủ lớn thì ta có lỗi "Out of stack space".

Ngoài ra nếu ở lần gọi nào đấy mà ta có rMin = rMax = xyz mà Arr(rMid, 1) <> find_value thì

Mã:

Call DeQuy(Arr, find_value, xyz, xyz)

sẽ thực hiện cho tới ngày tận thế, tức cho tới khi có lỗi "Out of stack space"

Tóm lại có 2 trường hợp gọi DeQuy muôn đời: cả khi có rMin < rMax và cả khi rMin = rMax.

---------------

À, còn điểm 2 nữa, tức "...phương pháp duyệt mảng để tìm ra kết quả tương tự ..."

Tùy vào việc các giá trị đang được bố trí thế nào. Tôi cho vd. Mảng có 10^6 phần tử mà trong đó "ngẫu nhiên" có Arr(1, 1) = GT. Vd. Arr(n, 1) = n, với n = 1, 2, ..., 1000000. Và GT = 1

Nếu bạn duyệt mảng thì ngay ở vòng lặp đầu tiên bạn đã tìm thấy.

Còn nếu dùng đệ quy

Mã:

Function DeQuy(Arr(), ByVal find_value, ByVal rMax As Long, ByVal rMin As Long, index As Long) As Long
Dim rMid As Long
    rMid = (rMax + rMin) \ 2
    If Arr(rMid, 1) < find_value Then
        index = index + 1
        Call DeQuy(Arr, find_value, rMax, rMid, index) ' <-- A
    ElseIf Arr(rMid, 1) > find_value Then
        index = index + 1
        Call DeQuy(Arr, find_value, rMid, rMin, index) ' <-- B
    Else
        DeQuy = rMid
    End If
End Function

Sub Test()
Dim Arr(1 To 1000000, 1 To 1), KQ As Long, index As Long
    For index = 1 To 1000000
        Arr(index, 1) = index
    Next
    index = 1
    KQ = DeQuy(Arr, 1, 1000000, 1, index)
    Debug.Print KQ
    MsgBox index
End Sub

Thì hàm DeQuy được gọi 20 lần - độ sâu (level) đệ quy là 20

dhn46 · 23/2/14

Dhn46 cảm ơn anh VetMini và bác Siwtom đã quan tâm tới vướng mắc của dhn46

Qua quá trình tìm hiểu đệ quy dhn46 đưa ra trường hợp "mỹ mãn" nhất cho điều kiện sử dụng đệ quy này đó là các số trong mảng đuợc sắp xếp và giá trị tìm nằm trong mảng. Và nhờ bài viết #2 và #3 dhn46 đã hiểu hơn phần nào về cách sử dụng đệ quy nhưng dhn46 vẫn còn vướng mắc mong bác và các anh chị giúp đỡ

1/ Khi sử dụng code test độ sâu đệ quy của bác Siwtom

Mã:

................
    KQ = DeQuy(Arr, 1, 1000000, 1, index)
    Debug.Print KQ
...............

Thì KQ trả về 0, điều này dhn6 đã gặp phải ngay từ đầu nên dùng giải phải "thủ công" là khai báo Public cho KQ. Không biết dhn46 đã làm sai thao tác nào?

2/ Khi test tốc độ tại giá trị cần tìm là như nhau (50000) thì độ sâu đệ quy là 19 tức là tiến hành so sánh 19 lần trong khi dùng phương pháp duyệt mảng phải so sánh 50000 lần nhưng tốc độ dhn46 thấy chênh lệch không nhiều chỉ khoảng 0.01 giây. Tại sao số lần so sánh chênh lệch như vậy mà tốc độ lại không tỷ lệ?

siwtom · 24/2/14

dhn46 đã viết:
Dhn46 cảm ơn anh VetMini và bác Siwtom đã quan tâm tới vướng mắc của dhn46

Qua quá trình tìm hiểu đệ quy dhn46 đưa ra trường hợp "mỹ mãn" nhất cho điều kiện sử dụng đệ quy này đó là các số trong mảng đuợc sắp xếp và giá trị tìm nằm trong mảng. Và nhờ bài viết #2 và #3 dhn46 đã hiểu hơn phần nào về cách sử dụng đệ quy nhưng dhn46 vẫn còn vướng mắc mong bác và các anh chị giúp đỡ

1/ Khi sử dụng code test độ sâu đệ quy của bác Siwtom

Mã:

................ KQ = DeQuy(Arr, 1, 1000000, 1, index) Debug.Print KQ ...............

Thì KQ trả về 0, điều này dhn6 đã gặp phải ngay từ đầu nên dùng giải phải "thủ công" là khai báo Public cho KQ. Không biết dhn46 đã làm sai thao tác nào?

Xin lỗi. Tôi cứ chơi trò "copy/paste" nhưng chỗ cần sửa thì lại quên.

Nguyên tắc là: giá trị trả về bởi level (k + 1) sẽ là giá trị trả về bởi level k

Nói hình tượng thì: KQ <-- DeQuy1 <-- DeQuy2 ... <-- DeQuy19 <-- DeQuy20

Mã:

Function DeQuy(Arr(), ByVal find_value, ByVal rMax As Long, ByVal rMin As Long, index As Long) As Long
Dim rMid As Long
    rMid = (rMax + rMin) \ 2
    If Arr(rMid, 1) < find_value Then
        index = index + 1
        [B][COLOR=#ff0000]DeQuy =[/COLOR][/B] DeQuy(Arr, find_value, rMax, rMid, index) ' <-- A
    ElseIf Arr(rMid, 1) > find_value Then
        index = index + 1
        [B][COLOR=#ff0000]DeQuy =[/COLOR][/B] DeQuy(Arr, find_value, rMid, rMin, index) ' <-- B
    Else
        DeQuy = rMid
    End If
End Function

Chỗ đỏ đỏ là chỗ cần sửa.

Tương tự như những chỗ khác, tức không phải là

Mã:

Call DeQuy(...)

Mà là

Mã:

DeQuy = DeQuy(...)

Đấy là hàm trả về giá trị. Còn nếu là Sub thì dĩ nhiên là

Mã:

Call DeQuy(...)

Lúc đó nếu cần trả về giá trị thì trả về qua thông số ByRef (như ở vd. là index). Chẳng hạn thay cho index (độ sâu của đệ quy chẳng qua là để xem chơi) thì truyền tham số KQ bằng ByRef (mọi chỗ có index thay bằng KQ)

2/ Khi test tốc độ tại giá trị cần tìm là như nhau (50000) thì độ sâu đệ quy là 19 tức là tiến hành so sánh 19 lần trong khi dùng phương pháp duyệt mảng phải so sánh 50000 lần nhưng tốc độ dhn46 thấy chênh lệch không nhiều chỉ khoảng 0.01 giây. Tại sao số lần so sánh chênh lệch như vậy mà tốc độ lại không tỷ lệ?

Bạn không thể so sánh như thế được.
Phải tính tỉ lệ phần trăm.
Tuy 2 cách chỉ khác nhau rất ít vd. 0,01 giây nhưng do tốc độ 2 cách cực lớn nên sự khác biệt đó lại là "một trời một vực".

Bạn so sánh 2 con vật và chúng khác nhau 0,01 g (gam) thì bạn nghĩ là chúng không khác nhau mấy?
Thế nếu con A = 0,0001 g, con B = 0,0101 g thì sao? Hiệu = 0,01 g = 100 con A. Và con B = 101 con A đấy bạn ạ.

Nếu dq = 0,00001 s còn For = 0,01001 s thì chúng chỉ chênh nhau có 0,01 giây thôi. Nhưng rõ ràng là dq nhanh hơn for gấp 1000 lần.

Có thể bạn sẽ hỏi: Tai sao độ sâu dq là 19 trong khi for duyệt 50000 vòng tức 50000 / 19 ≈ 2632 mà dq lại chỉ nhanh hơn for có 1000 lần thay vì 2632 lần?

Bạn nên nhớ là for rất đơn giản:

Mã:

For index = 1 To 1000000
            If Arr(index, 1) = 50000 Then Exit For
Next

Trong khi mỗi lần trong 19 lần phải đi sâu xuống level mới là: ngoài việc kiểm tra đk (IF ... THEN) còn có tính toán rMid, tính toán index, đặt giữ liệu vào local stack và lấy về.
------------
Nhắc lại lần nữa: hàm của bạn chưa chuẩn đâu.

Cũng có cả trường hợp không tìm thấy. Lúc đó thì trả về vd. kết quả = -1. Chẳng hạn tìm giá trị 2,5 (2 rưỡi) trong mảng 1 triệu phần tử của tôi thì chắc chắn sẽ không tìm thấy. Không có rMid nào thỏa cả. Nếu nhận được giá trị trả về là -1 thì biết ngay là không tìm thấy. Vì làm gì có chỉ số -1 nếu mảng của ta có LBound(...) >= 0 hoặc >= 1.

Lỗi khi sử dụng đệ quy tìm vị trí của giá trị trong mảng được sắp xếp. (2 người xem)

Người dùng đang xem chủ đề này

dhn46

Hướng tới tương lai

VetMini

Ăn cùng góc phố

siwtom

Thành viên gắn bó

dhn46

Hướng tới tương lai

siwtom

Thành viên gắn bó

Bài viết mới nhất

Thành viên có số lượng bài viết cao nhất tháng

Thành viên có điểm tương tác cao nhất tháng

Đếm ngược thời gian