Binary search on a multidimensional array 1

[jporter1]

Hello - I was wondering if anyone has experience or knows how to search an array using a binary search.

I currently have a piece of code that compares a main table (with 5000+ entries) to twenty other tables. It scans every line in each the other tables, finding its correlating value (if it exists in the main table) and updates a field in the main table array if the value is newer. However, as this search is currently done sequentially, by the time it is locating values in the second half of the table it is wasting time comparing at least 2500+ other values.

I have read plenty about binary searches on the web for other types of code including vb5 and above but cannot seem to use its functionality in vbscript.

Thanks for any help.

 

[mrmovie]

see below about instr and binary comparison, i think you change the default comparison of VB proper.

You can change the compare mode for a dictionary object!!!!
which might be more use to than an array. you could use the dictionary objects filter method to return subset of your main table. this would limit your searches. do you have a unique field that is common with all your tables,,,you could build a dictionary object of this and then filter a dictionary object of your main table!!????

InStr Function
Returns the position of the first occurrence of one string within another.

InStr([start, ]string1, string2[, compare])

Arguments
start

Optional. Numeric expression that sets the starting position for each search. If omitted, search begins at the first character position. If start contains Null, an error occurs. The start argument is required if compare is specified.

string1

Required. String expression being searched.

string2

Required. String expression searched for.

compare

Optional. Numeric value indicating the kind of comparison to use when evaluating substrings. See Settings section for values. If omitted, a binary comparison is performed.

Settings
The compare argument can have the following values:

Constant Value Description
vbBinaryCompare 0 Perform a binary comparison. NB ##########
vbTextCompare 1 Perform a textual comparison.


Return Values
The InStr function returns the following values:

If InStr returns
string1 is zero-length 0
string1 is Null Null
string2 is zero-length start
string2 is Null Null
string2 is not found 0
string2 is found within string1 Position at which match is found
start > Len(string2) 0


Remarks
The following examples use InStr to search a string:

Dim SearchString, SearchChar, MyPos
SearchString ="XXpXXpXXPXXP" ' String to search in.
SearchChar = "P" ' Search for "P".
MyPos = Instr(4, SearchString, SearchChar, 1) ' A textual comparison starting at position 4. Returns 6.
MyPos = Instr(1, SearchString, SearchChar, 0) ' A binary comparison starting at position 1. Returns 9.
MyPos = Instr(SearchString, SearchChar) ' Comparison is binary by default (last argument is omitted). Returns 9.
MyPos = Instr(1, SearchString, "W&quot ' A binary comparison starting at position 1. Returns 0 ("W" is not found).
Note The InStrB function is used with byte data contained in a string. Instead of returning the character position of the first occurrence of one string within another, InStrB returns the byte position.

Requirements

 

[jporter1]

Thanks for the extremely prompt response mrmovie! I've done some diggin on using dictionary objects and agree that if I could load the contents of my main table/array into a dictionary object I could filter for each value I'm looking for.

Now I've caught your attention I'll explain a little more of what I'm doing :-

I am auditing user accounts for our domain (5000+ of them spread across 22 domain controllers) as you may be aware a user can be authenticated by any of the BDCs that exist across the domain and only this DC will hold the true lastlogin time for that user as this information is not replicated back to the PDC. Currently, using ADSI, my script collects all the user details I require from the PDC and stores them in an array - some 12 fields in total (can dictionary objects only hold two related values?). I then contact each BDC in turn reading off all the user accounts' lastlogin times comparing them to the main table and update the lastlogin time if newer. (if the users still exist that is! - currently the script takes some 5 days to run and user accounts can be removed etc. hence my request for the sort to try to streamline the code as much as possible). The array is then output to an SQL database for analysis.

If dictionary objects can't handle more than 2 key values then I will look at your method of the binary search.

Thanks.

 

[mrmovie]

ok, forget tables and keys, you want to just deal with recordsets i would say.....have a look at this and see what you think.

this returns the users last login....based on contacting all DC's and returnin the lastest value...give it a try, will have to change domain name but i think that should be about it..


Option Explicit


Dim oRoot, sConfig, oConnection, oCommand, sQuery, acctDisabled, disname, lockedout
Dim oResults, oDC, oSite, sDNSDomain, oShell
Dim nBiasKey, nBias, k, sDCs()
Dim sAdsPath, sDate, oDate, nDate, oList, sUser,accountlock
Set oList = CreateObject("Scripting.Dictionary&quot
oList.CompareMode = vbTextCompare

Set oShell = CreateObject("Wscript.Shell&quot
nBiasKey = oShell.RegRead("HKLM\System\CurrentControlSet\Control\TimeZoneInformation\ActiveTimeBias&quot
If UCase(TypeName(nBiasKey)) = "LONG" Then
nBias = nBiasKey
ElseIf UCase(TypeName(nBiasKey)) = "VARIANT()" Then
nBias = 0
For k = 0 To UBound(nBiasKey)
nBias = nBias + (nBiasKey(k) * 256^k)
Next
End If

' Determine configuration context from RootDSE object.
Set oRoot = GetObject("LDAP://RootDSE&quot
sConfig = oRoot.Get("ConfigurationNamingContext&quot
sDNSDomain = oRoot.Get("DefaultNamingContext&quot

' Use ADO to search AD for ObjectClass nTDSDSA.
Set oCommand = CreateObject("ADODB.Command&quot
Set oConnection = CreateObject("ADODB.Connection&quot
oConnection.Provider = "ADsDSOObject"
oConnection.Open = "Active Directory Provider"
oCommand.ActiveConnection = oConnection

sQuery = &quot;<LDAP://&quot; & sConfig & &quot;>;(ObjectClass=nTDSDSA);AdsPath;subtree&quot;

oCommand.CommandText = sQuery
oCommand.Properties(&quot;Page Size&quot = 100
oCommand.Properties(&quot;Timeout&quot = 30
oCommand.Properties(&quot;Searchscope&quot = 2
oCommand.Properties(&quot;Cache Results&quot = False


Set oResults = oCommand.Execute

' Enumerate parent objects of class nTDSDSA (DCs).
k = 0
Do Until oResults.EOF
Set oDC = _
GetObject(GetObject(oResults.Fields(&quot;AdsPath&quot).Parent)
ReDim Preserve sDCs(k)
sDCs(k) = oDC.DNSHostName

k = k + 1

oResults.MoveNext
Loop

For k = 0 To Ubound(sDCs) 'loop cycles through domain controllers in array.


wscript.echo sdcs(k)

sQuery = &quot;<LDAP://&quot; & sDCs(k) & &quot;/OU=UK-Bracknell,&quot; & sDNSDomain & &quot;>;(ObjectCategory=person)&quot; & &quot;;displayname,sAMAccountName,userAccountControl,LastLogon;subtree&quot;


oCommand.CommandText = sQuery

Set oResults = oCommand.Execute


Do Until oResults.EOF 'loop throuugh users

sAdsPath = oResults.Fields(&quot;sAMAccountName&quot
sdate = oResults.Fields(&quot;LastLogon&quot
acctDisabled = oResults.fields(&quot;userAccountControl&quot
disname = oResults.fields(&quot;displayname&quot

if not isnull (disname) then
wscript.echo disname
end if

if acctdisabled = 514 then
acctdisabled = &quot;true&quot;
'else
'acctdisabled = &quot;false&quot;
end if

If not IsNull (oResults.Fields(&quot;LastLogon&quot) Then



set oDate = sDate



nDate = #1/1/1601# + (((oDate.HighPart * (2 ^ 32)) + oDate.LowPart)/600000000 - nBias)/1440 'convert count of nanoseconds to date.

If oList.Exists(sAdsPath) Then 'Check if record exists

If nDate > oList(sAdsPath) Then 'if dose exsist. Check if current domain controllers lastlogon record is greater than the one that exists.
oList(sAdsPath) = disname & &quot;;&quot; &nDate & &quot;;&quot; & acctDisabled 'update if bigger.
End If
Else


oList.Add sAdsPath, disname & &quot;;&quot; & nDate & &quot;;&quot; & acctDisabled 'add the record if not exist
End If



End If

oResults.MoveNext 'next user within domain controller

Loop 'loop around





Next 'next domain controller

For Each sUser In oList
Wscript.Echo sUser & &quot;;&quot; & oList(sUser)
Next

 

[mrmovie]

i wouldnt let the dictionary object only handling 2 keys put you off though you could use the &quot;key&quot; to hold the unique field and then the corresponding &quot;value&quot; to contain a truncated form of the rest of your fields...ie
key = saMAccountName
item = mrjones;098989090;m.jones:hmail.com;...; etc etc

then use
aArray = Split(item,&quot;;&quot
aArray(0) etc etc etc

 

[jporter1]

I'll give it a try this afternoon.

Thanks.