Matching Values
-
This line just initialize the Array to have 1 elem inside at index 0
Kindest Regards,Vasc
-
Thanks Vasc. It works now. Let me see whether I can reproduce it in SQL.
Recursive is way too fast than non recursive. Check 1200. Not found is the answer.
Regards,
gova -
My test results match govinn's. Test results for both programs set to not start timer until after value is loaded into the array. (in both cases it requires about 0.0156 seconds to load the array: a great place to save a lot of time)
For values that can be found I have not been able to locate one that requires measurable amounts of time using either method. Both methods are fast when the value can be found
Sample data for cases where value is not found.
value 1200 recursive method = 0.0000 non-recursive method =11.328 seconds
value 789 recursive method =1.234 seconds non-recursive = 15.81 seconds
value 889 recursive method = 0.59375 seconds non_recursive method =19.0488 seconds
a wide variance in the time for both methods but the recursive method seems to be beating the pants off the non-recursive method.
Mike
-
Noticed the large number of posts on this, and got curious.
Here's an iterative (non-recursive) search. It does it breadth-first, so it finds the solution that uses the smallest number of values.
I'm doing a nasty cursor at the end just to print the the results.
Of course, you can use a table variable instead of my table.
It's not particularly optimised... because a breadth-first search isn't typically the best way of doing this type of thing. But I'm sure someone could work out ways of optimising it, and working out what values give a better result this way than the depth-first search that the recursive method uses. For instance... it works fast for 103, but not so fast on 512.
RobF
/*
create table vals
(valueid int identity(1,1), value numeric(10,2))
go
INSERT INTO vals (Value) VALUES (15)
INSERT INTO vals (Value) VALUES (10)
INSERT INTO vals (Value) VALUES (21)
INSERT INTO vals (Value) VALUES (25)
INSERT INTO vals (Value) VALUES (26)
INSERT INTO vals (Value) VALUES (30)
INSERT INTO vals (Value) VALUES (30)
INSERT INTO vals (Value) VALUES (40)
INSERT INTO vals (Value) VALUES (41)
INSERT INTO vals (Value) VALUES (45)
INSERT INTO vals (Value) VALUES (50)
INSERT INTO vals (Value) VALUES (55)
INSERT INTO vals (Value) VALUES (60)
INSERT INTO vals (Value) VALUES (60)
INSERT INTO vals (Value) VALUES (65)
INSERT INTO vals (Value) VALUES (70)
INSERT INTO vals (Value) VALUES (75)
INSERT INTO vals (Value) VALUES (80)
INSERT INTO vals (Value) VALUES (85)
INSERT INTO vals (Value) VALUES (90)
INSERT INTO vals (Value) VALUES (95)
INSERT INTO vals (Value) VALUES (100)
INSERT INTO vals (Value) VALUES (105)
go
create table match
( id int identity(1,1),
value numeric(10,2),
valueid int,
parent int,
remainder numeric(10,2),
checked int
)
*/
declare @goal numeric(10,2)
set @goal = 627
truncate table match
insert into match
(value, valueid, parent, remainder, checked)
select value, valueid, 0, @goal-value, -1 from vals where value < @goal
declare @stillgoing int
set @stillgoing = 1
while (@stillgoing = 1)
begin
update match set checked = checked + 1
where checked < 1
insert into match
(value, valueid, parent, remainder, checked)
select v.value, v.valueid, m.id, m.remainder - v.value, -1
from match m
join
vals v
on v.valueid <= m.valueid -- Or '<' if you want distinct values
and v.value 0)
begin
select @res = parent, @val = value
from match
where id = @res
print convert(varchar,@val)
end
fetch csrResult into @val, @res
end
close csrResult
deallocate csrResult
Rob Farley
LobsterPot Solutions & Adelaide SQL Server User Group
Company: http://www.lobsterpot.com.au
Blog: http://blogs.lobsterpot.com.au -
There is a RULE: an iterative version is ALWAYS faster than the RECURSIVE version. (off course if it is well written : )
So based on your Observation (good one : ) ) and govvin's too I looked on the nonrecursive code and I found that the recursive function is faster because is "hidding" an extra optimization that reduce the number of unwanted cicles by starting with the biggest value, decrease value and stop when it doesn't make sense to go on that path anymore ... because SUM is smaller than MyNumber this part was missing from the nonrecursive code : when I was generating the Stack I was putting on the stack ALL values that are smaller than my values EVEN if by treating them you won't reach a solution (because their SUM is smaller that MyNumber so they won't have any change to produce a solution)
I added this to the VB code:
==========================================================
Private Sub Command1_Click()
Dim val As Double
Dim cn As New ADODB.Connection
Dim rs As New ADODB.Recordset
Dim High As Double
Dim Low As Double
Dim Found As Boolean
Dim count As Integer
Dim AllSum As Double
Dim TempSum As Double
AllSum = 0
count = 0
Found = False
cn.CursorLocation = adUseClient
cn.Provider = "SQLOLEDB.1;Integrated Security=SSPI;Persist Security Info=False;Initial Catalog=test1;Data Source=ITWSVK01"
cn.Open
val = CDbl(Text1.Text)
rs.Open "select value From MyTable WHERE Value<=" + Str(val) + " order by Value", cn
While Not rs.EOF
count = count + 1
ReDim Preserve ArrayValues(count)
ArrayValues(count) = rs!Value
AllSum = AllSum + ArrayValues(count)
rs.MoveNext
Wend
Set rs = Nothing
cn.Close
Set cn = Nothing
If count = 0 Then
MsgBox "The value is smaller than the lowest value in the table" _
, vbOKOnly, "Error"
Exit Sub
End If
Dim MyElem As Double
Dim MySol As String
Dim cntSOl As Integer
Dim cntStack As Integer
cntStack = 0
mm = UBound(ArrayValues)
TempSum = 0
For ii = 1 To mm
TempSum = TempSum + ArrayValues(ii)
If TempSum >= val Then
cntStack = cntStack + 1
ReDim Preserve MyStack(cntStack)
MyStack(cntStack) = ii
End If
Next ii
If cntStack = 0 Then
MsgBox "NotFound"
Exit Sub
End If
ReDim Preserve Sol(0)
While UBound(MyStack) > 0
MyElem = MyStack(UBound(MyStack))
If MyElem = Sol(UBound(Sol)) Then
ReDim Preserve MyStack(UBound(MyStack) - 1)
ReDim Preserve Sol(UBound(Sol) - 1)
val = val + ArrayValues(MyElem)
AllSum = AllSum + ArrayValues(MyElem)
If UBound(Sol) = 1 Then AllSum = AllSum - ArrayValues(MyElem)
Else
cntSOl = UBound(Sol)
cntSOl = cntSOl + 1
ReDim Preserve Sol(cntSOl)
Sol(cntSOl) = MyElem
val = val - ArrayValues(MyElem)
AllSum = AllSum - ArrayValues(MyElem)
If val = 0 Then
For jj = 1 To UBound(Sol)
MySol = MySol + Str(ArrayValues(Sol(jj)))
Next jj
MsgBox MySol
Exit Sub
Else
If AllSum >= val Then
'check to see if the value is in the remaining values
For rr = MyElem - 1 To 1 Step -1
If val = ArrayValues(rr) Then
For jj1 = 1 To UBound(Sol)
MySol = MySol + Str(ArrayValues(Sol(jj1)))
Next jj1
MsgBox MySol + " " + Str(val)
Exit Sub
End If
Next rr
TempSum = AllSum
While ArrayValues(MyElem) > val
MyElem = MyElem - 1
TempSum = TempSum - ArrayValues(MyElem)
Wend
If MyElem > 1 And TempSum >= val Then
TempSum = ArrayValues(1)
jj1 = 1
While TempSum < val
jj1 = jj1 + 1
TempSum = TempSum + ArrayValues(jj1)
Wend
For kk = jj1 To MyElem - 1
ReDim Preserve MyStack(UBound(MyStack) + 1)
MyStack(UBound(MyStack)) = kk
Next kk
End If
End If
End If
End If
Wend
MsgBox "notfound"
End Sub
=========================================================
If there are still cases in which the Recursive version is FASTER than the NonRecursive than this version is NOT DONE YET : )
Kindest Regards,Vasc
-
Do you guys think this thread will hit 100 messages?? I think it would be a first
. -
breadth-first or deph-first they have the same cost. They produce different result times based on the distribution of the Initial Set of Numbers which you can't control
Kindest Regards,Vasc
-
breadth-first or deph-first they have the same cost. They produce different result times based on the distribution of the Initial Set of Numbers which you can't control
I tend to differ on that. In databases you must know your data and usually you can find skews on it
so if you know where it will most probaly go, just use the most probable way.
I had to research a problem that one client had once and they were assuming any number of order detail items could happen in an Order. After we analized the DATA we arrived to the conclusion that with 60 line Items 97% of the cases could be covered accross their customer base. Speed improvement based on that finding was outstanding!
Just my $0.02
* Noel -
Can you elaborate on that one??
-
Actually it seems that you agree with me (or my english was poor )
They produce different result times based on the distribution of the Initial Set of Numbers which you can't control
They have the same cost regarding the processing time as a metod to travers searching tree.
If you have knoledge like in your case you can optimize your solution based on the metod choosed I really agree with that : )
Kindest Regards,Vasc
-
Yes I agree with this part:
They produce different result times based on the distribution of the Initial Set of Numbers
The part I was differing with was:
which you can't control
Which in my opinion in Databases you can tell if there is a skew in the data and I was proposing not to stop at one or the other just Like you said use the most appropriate for your data
* Noel -
As an exercise, it's fun to write the code to make a database do this kind of work. In reality though, you wouldn't use a database for it, because a database is just that, a BASE for the data - not really designed for the kind of computations that are required here. Pulling the data into something that is better at playing with numbers and different data structures is definitely the way to go.
Rob Farley
LobsterPot Solutions & Adelaide SQL Server User Group
Company: http://www.lobsterpot.com.au
Blog: http://blogs.lobsterpot.com.au
Viewing 12 posts - 91 through 101 (of 101 total)
You must be logged in to reply to this topic. Login to reply