1
\$\begingroup\$

Brief illustration:

I have 2 classes - tbCustomer and tbDHN which is stored inside a list. Both contains attribute CustomerName and NPWP. I need to display the percentage of similarity between the customer in tbCustomer and tbDHN.

The algorithm that I use is Levenshtein Distance, taken from this link (the second one, which the poster claims to take ~10s for long strings). If the result of this algorithm exceeds or equal to the specified threshold, then I store the result in another list.

The only approach that I can think of is to compare them one by one, as indicated by the nested For Each. The result will be pushed to database per batch in order to save memory i.e. using BulkCopy to push the list for every 6000 matching records and then Clear the list for storing further calculation.
The whole process is placed inside Background Worker. The function UpdateProgressBar simply calls a delegate to update the UI (progress bar).


Problem description:

listCustomer contains approximately 12000 records, while the listDHN contains 50000 records. If we use the above approach, then there will be around 600 million calls of Levenshtein procedure. Current execution time is about 6 hours (includes storing the result to database which is just around 1500 records).

Is there any suggestion on how to improve its performance?


This is the main process code:

For Each tbCustomer As tbCustomer In listCustomer
        If (BackgroundWorkerMatch.CancellationPending) Then
            Exit Sub
        End If

        For Each tbDHN As tbDHN In listDHN

            If tbDHN.npwp_trimmed.Length >= 5 AndAlso
                tbCustomer.npwp_trimmed.Length >= 5 AndAlso
                tbDHN.npwp_trimmed.Equals(tbCustomer.npwp_trimmed) Then
                listResult.Add(New tbResult With {.periodedate = tbDHN.periodedate, .basenumber = tbCustomer.basenumber,
                                                 .npwpDHN = tbDHN.npwp, .npwp = tbCustomer.npwp,
                                                 .custnameDHN = tbDHN.customername, .custname = tbCustomer.customername,
                                                 .similarityPercent = 100, .similarityBy = "NPWP"})
            Else
                ' We need to match single words with single words as well. Likewise, multiple words with multiple words as well.
                ' Previous implementation is rather flawed. Multiple words can be compared with single words.
                If (tbCustomer.isSingleWord AndAlso tbDHN.isSingleWord) OrElse
                   (Not tbCustomer.isSingleWord AndAlso Not tbDHN.isSingleWord) Then
                    Dim result = LevenshteinDistance(tbCustomer.customername_excluded, tbDHN.customername_excluded)
                    If result >= possibility Then
                        listResult.Add(New tbResult With {.periodedate = tbDHN.periodedate, .basenumber = tbCustomer.basenumber,
                                                         .npwpDHN = tbDHN.npwp, .npwp = tbCustomer.npwp,
                                                         .custnameDHN = tbDHN.customername, .custname = tbCustomer.customername,
                                                         .similarityPercent = result, .similarityBy = "CustomerName"})
                    End If
                End If
            End If
            countProgressBar += 1 : lineNo += 1
            UpdateProgressBar(ProgressBarMatch, If(countProgressBar = 0, 0, (countProgressBar / countMax) * 100))
            If lineNo Mod 10 = 0 Then Application.DoEvents()
            If listResult.Count Mod 6000 = 0 Then PushToDatabase()
        Next
    Next

This is the structure of tbDHN and tbCustomer:

Private Class tbDHN
    Public Property periodedate As String
    Public Property npwp As String
    Public Property npwp_trimmed As String
    Public Property customername As String
    Public Property customername_excluded As String
    Public Property isSingleWord As Boolean
End Class
Private Class tbCustomer
    Public Property basenumber As String
    Public Property npwp As String
    Public Property npwp_trimmed As String
    Public Property customername As String
    Public Property customername_excluded As String
    Public Property isSingleWord As Boolean
End Class
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.