Searching Between Two Large Arrays

[buymeapc]

Hi all,

I'm trying to find the fastest method to search a huge array which can be 30,000 items deep or more against another smaller, but still large array, which is around 120. The way I have posted below takes a bit of time - approximately 22 seconds or more.

Can someone please help me speed this up? Thanks!

#include <array.au3>

Dim $aRestore[120][2]
Dim $aNewFile[30000]
Dim $aFinal[30000]
Dim $x = True

For $i = 0 To 119
     $x = Not $x
     $aRestore[$i][0] = "variable"&$i
     $aRestore[$i][1] = $x
Next

For $i = 0 To 29999
     Switch $i
         Case 10, 26, 39, 45
             $aNewFile[$i] = "variable1"
         Case 1000, 1567, 1687, 2001
             $aNewFile[$i] = "variable20"
         Case Else
             $aNewFile[$i] = $i
     EndSwitch
Next

If IsArray($aRestore) Then
     $time = TimerInit()
     For $s = 0 To UBound($aRestore) - 1
         If $aRestore[$s][1] = 1 Then $fCase = True
         If $aRestore[$s][1] = 0 Then $fCase = False
         For $t = 0 To UBound($aNewFile)-1
             If $aFinal[$t] = "" Then $aFinal[$t] = "No Match"
             If StringInStr($aNewFile[$t], $aRestore[$s][0], $fCase) <> 0 Then $aFinal[$t] = "---------->Match!"
         Next
     Next
     _ArrayDisplay($aFinal, TimerDiff($time))
EndIf

[bogQ]

Change your writing methonds will save you half the time

Dim $aFinal[1] instead Dim $aFinal[30000]

and change to

If IsArray($aRestore) Then
$time = TimerInit()
For $s = 0 To UBound($aRestore) - 1
     If $aRestore[$s][1] = 1 Then $fCase = True
     If $aRestore[$s][1] = 0 Then $fCase = False
     For $t = 0 To UBound($aNewFile) - 1
         If StringInStr($aNewFile[$t], $aRestore[$s][0], $fCase) Then _ArrayAdd($aFinal,$t)
     Next
Next
_ArrayDisplay($aFinal, TimerDiff($time))
EndIf

[BrewManNH]

Using _ArrayAdd will increase the time a lot, not decrease it.

[guinness]

Look at _ReDim in my signature and you'll see the increase in time.

[bogQ]

Using _ArrayAdd will increase the time a lot, not decrease it.

when i told writing method i ment writing unneeded data, my point was not on _ArrayAdd

as for _ArrayAdd if you don't write that unneeded data, time diffrance instead populating large pre-dimed array with = or adding on small pre-dimed array with _ArrayAdd is irrelevant when your not gonna have a lot of correct results that do need to be writen.

Edited September 14, 2012 by bogQ

[Spiff59]

I'm trying to find the fastest method

This takes >22 seconds to <.2 seconds.

expandcollapse popup

#include <array.au3>

Dim $aRestore[120][2]
Dim $aNewFile[30000]
Dim $aFinal[30000]
Dim $aFinal2[30000]
Dim $x = True

For $i = 0 To 119
     $x = Not $x
     $aRestore[$i][0] = "variable"&$i
     $aRestore[$i][1] = $x
Next

For $i = 0 To 29999
    Switch $i
        Case 10, 26, 39, 45
            $aNewFile[$i] = "variable1"
     Case 1000, 1567, 1687, 2001
         $aNewFile[$i] = "variable20"
     Case Else
         $aNewFile[$i] = $i
EndSwitch
Next

;===================================================================================================================================
$time = TimerInit()
For $s = 0 To UBound($aRestore) - 1
    If $aRestore[$s][1] = 1 Then $fCase = True
    If $aRestore[$s][1] = 0 Then $fCase = False
    For $t = 0 To UBound($aNewFile)-1
        If $aFinal[$t] = "" Then $aFinal[$t] = "No Match"
        If StringInStr($aNewFile[$t], $aRestore[$s][0], $fCase) <> 0 Then $aFinal[$t] = "---------->Match!"
    Next
Next
_ArrayDisplay($aFinal, TimerDiff($time))

;===================================================================================================================================
$time = TimerInit()
For $i = 0 To UBound($aRestore) - 1 ; assign $aRestore to variables
     Assign("__" & $aRestore[$i][0], 0, 1)
Next

For $t = 0 To UBound($aNewFile)-1
    If IsDeclared("__" & $aNewFile[$t]) Then
        $aFinal2[$t] = "---------->Match!"
    Else
        $aFinal2[$t] = "No Match"
    EndIf
Next
_ArrayDisplay($aFinal2, TimerDiff($time))

I'm confused what the alternating case-sensitivity test is about, but bet it could be worked in if necessary.

I added logic to handle your case flag, and changed the data so that just over 50% of it would be subject to the case test (half of those passing the test, and the other half failing). It only pushed the total time to the vicinity of 275ms.

expandcollapse popup

#include <array.au3>

Dim $aRestore[120][2]
Dim $aNewFile[30000]
Dim $aFinal[30000]
Dim $aFinal2[30000]
Dim $x = True

For $i = 0 To 119
     $x = Not $x
     $aRestore[$i][0] = "variable" & $i
     $aRestore[$i][1] = $x
Next

For $i = 0 To 29999
     Switch $i
         Case 10
             $aNewFile[$i] = "VaRiAbLe1" ; 1 = case-sensitive
         Case 26, 39, 45
             $aNewFile[$i] = "variable1"
         Case 1000
             $aNewFile[$i] = "VaRiAbLe20" ; 20 = case-insensitive
         Case 1567, 1687, 2001
             $aNewFile[$i] = "variable20"
         Case 15000 to 29999
             $aNewFile[$i] = "VaRiAbLe" & Mod($i, 100)
         Case Else
             $aNewFile[$i] = $i
     EndSwitch
Next

;===================================================================================================================================
$time = TimerInit()
For $s = 0 To UBound($aRestore) - 1
    If $aRestore[$s][1] = 1 Then $fCase = True
    If $aRestore[$s][1] = 0 Then $fCase = False
    For $t = 0 To UBound($aNewFile) - 1
        If $aFinal[$t] = "" Then $aFinal[$t] = "No Match"
     If StringInStr($aNewFile[$t], $aRestore[$s][0], $fCase) <> 0 Then $aFinal[$t] = "---------->Match!"
    Next
Next
_ArrayDisplay($aFinal, TimerDiff($time))

;===================================================================================================================================
$time = TimerInit()
For $i = 0 To UBound($aRestore) - 1 ; assign $aRestore to variables
    Assign("__" & $aRestore[$i][0], $i, 1)
Next

For $t = 0 To UBound($aNewFile)-1
    If IsDeclared("__" & $aNewFile[$t]) Then
        $z = Eval("__" & $aNewFile[$t])
     If (Not $aRestore[$z][1]) Or ($aNewFile[$t] == $aRestore[$z][0]) Then ;case-sensitive is false, or strings are exact match
            $aFinal2[$t] = "---------->Match!"
        Else
            $aFinal2[$t] = "No Match"
        EndIf
    Else
        $aFinal2[$t] = "No Match"
    EndIf
Next
_ArrayDisplay($aFinal2, TimerDiff($time))

Oddly, the second half of the output arrays no longer match between the versions. I'd guess from the match/no-match pattern that the faster version is showing the correct results.

Edited September 14, 2012 by Spiff59

[buymeapc]

Spiff, that's amazingly fast!

What I'm ultimately trying to do is read a text file into an array, which is $aNewFile. This file is just a text file, but can be upwards of 500MB. I'm doing this by using _FileReadToArray() which also takes some time. Then, I have my search criteria array in $aRestore. I am trying to search throughout the $aNewFile array for anything in the $aRestore array and that's where the case sensitivity comes into play. So, I've been comparing each item of $aNewFile to every item of $aRestore.

I hope this makes sense.

EDIT: I just noticed the StringInStr() is missing. I'll have to figure out how to add that back in for partial matches.

Edited September 14, 2012 by buymeapc

[James]

In my experience, I wouldn't move 500MB of file lines into an array...

[buymeapc]

It's not exactly ideal (or quick), but it's the only way I can read the lines of the file into a virtual listview, though

[buymeapc]

Using Spiff's code, I've been trying to figure out how to find partial matches, but I can't quite see where I can fit in a StringInStr() function to accomplish this. The thing is, I need to see if any part of each $aNewFile[$i] contains any one of the $aRestore variables. As it is, it's looking to see if "IsDeclared("__" & $aNewFile[$t])", but this will never be true since "Assign("__" & $aRestore[$i][0], $i, 1)" will almost always be shorter.

Bottom line, I'm trying to figure out how I can find "variable1" within the huge array of sentences where "variable1" is contained in several sentences - like an advanced find function, where the search criteria is pre-defined in an array.

For $t = 0 To UBound($aNewFile)-1
    If IsDeclared("__" & $aNewFile[$t]) Then
        $z = Eval("__" & $aNewFile[$t])
  If (Not $aRestore[$z][1]) Or ($aNewFile[$t] == $aRestore[$z][0]) Then ;case-sensitive is false, or strings are exact match
            $aFinal2[$t] = "---------->Match!"
        Else
            $aFinal2[$t] = "No Match"
        EndIf
    Else
        $aFinal2[$t] = "No Match"
    EndIf
Next
_ArrayDisplay($aFinal2, TimerDiff($time))

[Spiff59]

Partial matches does present a problem.

You could make it work if you're matching on entire words?

But if your search strings are way short, like "er" , and need to picked out of the middle of a word like "operator" then I think this method may be a no-go. I don't think scripting.dictionary does partial searches either.

[buymeapc]

I'll give you an example of what I'm trying to accomplish. Here's a small snippet of the text that I'm populating $aNewFile with:

struct pPob1 "0000000000h 000000029142000000848300000000000000030000000003762500000000000000000000000003762500000000 01780010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
struct pPob2 01 "V 000000079160013033010000000000601400000019020000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
struct pPob2 02 "V 000000297090048917010000000002312800000065810000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
struct pAeb1 "00 104                     0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
struct pAeb_Dx "0000000000000000000000000000000000000000"
struct pAeb_Op 01 "00613000000000000000000000000000000000000V 910000002000000100000000000"
struct pAeb_Op 02 "00616000000000000000000000000000000000000V 910000002000000100000000000"
ACE Edit V10, R4, EdtRC=00
struct pPws1 "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
struct pOob2 "0000000000000000000000000000000000000000000000000000000000000000000000000"
struct pPaths->system "C:\Inetpub\wwwroot\HSS\Data"
struct irec "010001      09      2010100100600000838700010000050000000000000050000178001100000000005000175000000000000000000000000100981000010981000000001FS2010     0800002000      0800002000AL        10000000001010200   0800002000NATIONAL 08000020001010200    0000000000      000000000000000000000000000000000000000000000000000000000000000000000000000020106 0000000000ALLEDITSOFF         000000000000000000002175000178000000        0000L999            09      20101001 apc010h NA000"
13:07:53 opcode=16, OptRC=00, APC, Group=55/55 V10/10, GrpRC=00, Price=h /h , PrcRC=00

The array $aRestore would contain criteria like this (String to search for|Case):

struct pAeb1|0
ACE|1
opcode=16|0

Lastly, what I'm going for is the output in $aFinal of each line whether they match one of the criteria above from $aRestore or not.

Your code is fantastic and fast, but I agree, I don't think it suits my need. Do you know of another way I can accomplish this?

[bogQ]

do you think that youl have more

---------->Match!

or

No Match

results?

and do you need "No Match" string or can it be replaced with '' or 0 (null char)?

Edited September 14, 2012 by bogQ

[jdelaney]

could always try through regular expressions: stringregexp

[buymeapc]

do you think that youl have more

---------->Match!

or

No Match

results?

and do you need "No Match" string or can it be replaced with '' or 0 (null char)?

I would definitely have many more "No Match" than matches in the results. Are you thinking pre-populating the results array with "No Match" then finding the matches after? The "No Match" was just for the example I posted. It could be "0" or anything, to be quite honest.

could always try through regular expressions: stringregexp

I've always been in awe of those who use StringRegExp() as I've never mastered it. How would I use that to find the (partial) search criteria from the array in the data from the much larger array?

[bogQ]

Are you thinking pre-populating the results array with "No Match" then finding the matches after?

yes

so i tought something like this then (if i did not messupo code along the way)

#include <array.au3>
$time = TimerInit()
Local $aRestore[121][2], $aNewFile[30001], $aFinal[30001], $x = True
$aRestore[0][0] = 120
$aNewFile[0] = 30000
$aFinal[0] = $aNewFile[0]
For $i = 1 To 120
    $x = Not $x
    $aRestore[$i][0] = "variable" & $i
    $aRestore[$i][1] = $x
Next
For $i = 1 To 30000
    Switch $i
        Case 10, 26, 39, 45
            $aNewFile[$i] = "variable1"
        Case 1000, 1567, 1687, 2001
            $aNewFile[$i] = "variable20"
        Case Else
            $aNewFile[$i] = $i
    EndSwitch
Next
For $x = 1 To $aFinal[0];disinclude this 3 lines if you dont need "No Match" textual statement
    $aFinal[$x] = "No Match"
Next
If IsArray($aRestore) Then
    For $s = 1 To $aRestore[0][0]
        $fCase = $aRestore[$s][1]
        $aRest = $aRestore[$s][0]
        For $t = 1 To $aNewFile[0]
            If StringInStr($aNewFile[$t], $aRest, $fCase) Then $aFinal[$t] = "---------->Match!"
        Next
    Next
EndIf
_ArrayDisplay($aFinal, TimerDiff($time))

it shud be in some way faster than your first original script regardless of including "No Match" to result or not

Edited September 14, 2012 by bogQ

[Reg2Post]

Does _ArraySearch not help any here?

[jdelaney]

Not sure of exactly what you are looking for, but it seems that you are looking for some text at the begin of some line (correct me if wrong)...what is the point of finding these restore points...are you going to replace them with some text?

You can add regexp conditions to the array, and they will return to $aFinal...that is the line will return, not the line number

#include <Array.au3>
$sText = 'struct pPob1 "0000000000h 000000029142000000848300000000000000030000000003762500000000000000000000000003762500000000 01780010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"' & @CRLF & _
'struct pPob2 01 "V 000000079160013033010000000000601400000019020000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"' & @CRLF & _
'struct pPob2 02 "V 000000297090048917010000000002312800000065810000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"' & @CRLF & _
'struct pAeb1 "00 104                    0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"' & @CRLF & _
'struct pAeb_Dx "0000000000000000000000000000000000000000"' & @CRLF & _
'struct pAeb_Op 01 "00613000000000000000000000000000000000000V 910000002000000100000000000"' & @CRLF & _
'struct pAeb_Op 02 "00616000000000000000000000000000000000000V 910000002000000100000000000"' & @CRLF & _
'ACE Edit V10, R4, EdtRC=00' & @CRLF & _
'struct pPws1 "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"' & @CRLF & _
'struct pOob2 "0000000000000000000000000000000000000000000000000000000000000000000000000"' & @CRLF & _
'struct pPaths->system "C:InetpubwwwrootHSSData"' & @CRLF & _
'struct irec "010001      09      2010100100600000838700010000050000000000000050000178001100000000005000175000000000000000000000000100981000010981000000001FS2010    0800002000   0800002000AL      10000000001010200   0800002000NATIONAL 08000020001010200    0000000000    000000000000000000000000000000000000000000000000000000000000000000000000000020106 0000000000ALLEDITSOFF        000000000000000000002175000178000000       0000L999            09    20101001 apc010h NA000"' & @CRLF & _
'13:07:53 opcode=16, OptRC=00, APC, Group=55/55 V10/10, GrpRC=00, Price=h /h , PrcRC=00'
Dim $aRestore[3] = ["[rn](struct pAeb1.*)","[rn](ACE.*)","[rn]([d:]+sopcode=16.*)"]
Dim $aFinal[1]
$iCounter = 0
For $i = 0 To UBound ( $aRestore ) - 1
 $aData = StringRegExp ( $sText, $aRestore[$i], 3 )
 If IsArray ( $aData ) Then
  For $j = 0 To UBound ( $aData ) - 1
    ReDim $aFinal[$iCounter+1]
    $aFinal[UBound($aFinal)-1] = $aData[$j]
 $iCounter += 1
  Next
 EndIf
Next

Edited September 14, 2012 by jdelaney

[buymeapc]

Not sure of exactly what you are looking for, but it seems that you are looking for some text at the begin of some line (correct me if wrong)...what is the point of finding these restore points...are you going to replace them with some text?

You can add regexp conditions to the array, and they will return to $aFinal...that is the line will return, not the line number

My ultimate goal is to find the text that a user defines within the logs that are available. I want the user to be able to define multiple search criteria and have all of them be found in the log. Kind of like doing a "find" on a document, but finding an array of items instead of just one at a time.

What I've been doing is reading the log into an array and reading each line of that array to see if any part of that line matches what the search array contains in every line. So, if I have 4 things in the search criteria array, I'd check each line of the log array against all 4 items of the search array and flag it in another array if one of them match.

[jdelaney]

unlikly they would be able to write the regexp then...i'm still curious how much quicker the regexp is, rather than looping through the array (if at all).

I guess you could have a simple regexp, where the user puts in the input, and you just wrap it in "(.*" & $TheirInput & ".*)". My script does dynamically add all results to an array.