Sign in to follow this  
Followers 0
mattw112

Best way to compare strings for duplicates?

6 posts in this topic

If one has 1000 strings and wants to find out if any are duplicates what is the best way to do that?

I can think of a couple ways to do it like writing out everything to compare if they are equal, or even doing a loop or maybe using an array. But just wondering what the easiest way would be? Is there some simple command I'm missing or UDF?

Thanks,

Terry

Share this post


Link to post
Share on other sites



Use either a scripting dictionary or an array. The dictionary will run much faster and with less code.


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

Use either a scripting dictionary or an array. The dictionary will run much faster and with less code.

Thanks, I'm not familiar with scripting dictionary? I did some searching on Autoit after I saw your post and really only saw a couple things to look at. I'm not sure how this would be less code? Do you think you can explain how it works to me?

Thanks,

Terry

Share this post


Link to post
Share on other sites

Using the search feature will help you locate example use. There are even at least two UDF mentionned around, but none is necessary in fact.

A scripting dictionary is a Windows COM component (all Windows versions) which allows you to efficiently store/lookup pairs of keys-values. Only one copy of each key can reside in a dictionary.

It's a good fit to your problem in that it uses an internal hash table for fastest possible access, which makes you don't have to compare yourself each new string to every string already processed: just lookup the dictionary and store the new string if it isn't already there. Being a COM object, the core functions are fast compiled code, probably C[++], faster than any AutoIt loop comparing values stored in an array.

Local $oDict = ObjCreate("Scripting.Dictionary") ; to create a dictionary object

$oDict.Add($string, $value) ; to store a string (you may set $value = '' if you have no use of it)

$already_there = $oDict.Exists ($string) ; to test if a string already exists


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

First method uses StringInStr() on a string to check if a new entry is a duplicate or not.

The second method uses a Scripting.Dictionary to check for duplicate entries.

Results

String time to complete = 0.93 - 0.98 secs

Scripting.Dictionary time = 0.11 - 0.17 secs

Local $sStr, $begin, $dif, $sNoDuplicates = "", $sMatches

; Create random test data
For $i = 1 To 1000
    $sStr &= Chr(Random(Asc("a"), Asc("z"), 1)) & Chr(Random(Asc("a"), Asc("z"), 1)) & _
            Chr(Random(Asc("a"), Asc("z"), 1)) & Chr(Random(Asc("a"), Asc("z"), 1)) & @CRLF
Next
;ConsoleWrite($sStr & @CRLF)

$begin = TimerInit()

; Check for duplicates
Local $aArray = StringSplit(StringStripWS($sStr, 2), @CRLF, 3)
For $i = 0 To UBound($aArray) - 1
    If StringInStr($sNoDuplicates, $aArray[$i]) Then
        $sMatches &= $i & " " & $aArray[$i] & @CRLF ; Record duplicates
    Else
        $sNoDuplicates &= $aArray[$i] & " " ; Add to non-duplicate string
    EndIf
Next
$dif = Round(TimerDiff($begin) / 1000, 3) & " secs"


;Display results
If $sMatches <> "" Then
    MsgBox(0, "Results", StringTrimRight($sMatches, 2) & @CRLF & "Time taken = " & $dif)
Else
    MsgBox(0, "Results", "No duplicates found" & @CRLF & "Time taken = " & $dif)
EndIf

Local $sStr, $begin, $dif, $sMatches

; Create random test data
For $i = 1 To 1000
    $sStr &= Chr(Random(Asc("a"), Asc("z"), 1)) & Chr(Random(Asc("a"), Asc("z"), 1)) & _
            Chr(Random(Asc("a"), Asc("z"), 1)) & Chr(Random(Asc("a"), Asc("z"), 1)) & @CRLF ;
Next
;ConsoleWrite($sStr & @CRLF)

$begin = TimerInit()

Local $oDict = ObjCreate("Scripting.Dictionary") ; to create a dictionary object
Local $aArray = StringSplit(StringStripWS($sStr, 2), @CRLF, 3)
For $i = 0 To UBound($aArray) - 1
    If $oDict.Exists($aArray[$i]) Then
        $sMatches &= $i & " " & $aArray[$i] & @CRLF ; Record duplicates
    Else
        $oDict.add($aArray[$i], '') ; to store a string (you may set $value = '' if you have no use of it)
    EndIf
Next
$dif = Round(TimerDiff($begin) / 1000, 3) & " secs"

;Display results
If $sMatches <> "" Then
    MsgBox(0, "Results", StringTrimRight($sMatches, 2) & @CRLF & "Time taken = " & $dif)
Else
    MsgBox(0, "Results", "No duplicates found" & @CRLF & "Time taken = " & $dif)
EndIf

Share this post


Link to post
Share on other sites

Thanks Malkey,

I used your dictionary example and it works great!

Terry

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0