1

さて、これが取引の人々です。私は持っていtwo text filesます。それぞれに500行(文)が含まれています。

memoryそれらを独自の配列にロードしました(データ型:文字列)。に名前を付けましょうarray A & B

次に in を取得しfirst sentence、単語を取得するために区切り文字として使用しarray Aて別のファイルに分割します。array CSPACE

次に、 の各文を区切り文字として使用しarray Bて分割し、単語を取得して、 の各単語と各単語を比較し、2 つの文の一致率を計算します。array DSPACEarray Carray D

array Aのすべての文に対するの最初の文の平均一致率を計算しarray Bます。

Array E次に、すべての文array Aとその平均一致率を含むに保存します。

first sentence配列 A のすべてのタイトルに対して上記と同じことを行います。

問題は、配列 A のすべてのタイトルを処理するのに約 15 秒かかることです。とにかく、この時間を最適化して高速化することはできますか?

ハードウェア: AMD Phenom I 32 ビット クアッド コア

コード:

Imports System.IO
Imports System.Object
Imports System.Xml
Imports System.Text.RegularExpressions

Module Module1

    Sub Main()
        'Important File Paths
        Dim titlesFilePath As String = Environment.CurrentDirectory & "\titles.txt"
        Dim xmlTitlesFilePath As String = Environment.CurrentDirectory & "\extractedTitles.txt"
        Dim stopWordsFilePath As String = Environment.CurrentDirectory & "\stopWords.txt"

        'Import Important Data From Files -> Memory
        Dim titles As Array = FileToArray(titlesFilePath)
        Dim stopWords As Array = FileToArray(stopWordsFilePath)
        Dim xmlDataUnprocessed As Array = FileToArray(xmlTitlesFilePath)

        'Delimters To Filter Titles For
        Dim userDefinedDelimeters(4, 1)

        userDefinedDelimeters(0, 0) = "-"
        userDefinedDelimeters(0, 1) = " "

        userDefinedDelimeters(1, 0) = ","
        userDefinedDelimeters(1, 1) = " "

        userDefinedDelimeters(2, 0) = "—"
        userDefinedDelimeters(2, 1) = " "

        userDefinedDelimeters(3, 0) = "'s"
        userDefinedDelimeters(3, 1) = ""

        userDefinedDelimeters(4, 0) = "'"
        userDefinedDelimeters(4, 1) = " "

        'Declare Important Variables
        Dim xmlData(xmlDataUnprocessed.Length / 2, 1)
        Dim xmlTurn = 0
        Dim xmlDataCount = 0

        'Create Feed Title/URL Array
        For i = 0 To (xmlDataUnprocessed.Length - 1)
            If xmlTurn = 0 Then
                xmlData(xmlDataCount, 0) = xmlDataUnprocessed(i)
                xmlTurn = 1
            Else
                xmlData(xmlDataCount, 1) = xmlDataUnprocessed(i)
                xmlTurn = 0

                xmlDataCount += 1
            End If
        Next


        'CPU-Intensive Stuff Occurs
        Dim xmlTitle As String
        Dim xmlTitleWords As Array
        Dim savedTitleWords As Array
        Dim titleResults(xmlData.GetUpperBound(0) - 1, 1)
        Dim titlePercentageMatch As Integer
        Dim numberOfTitlesMatched As Integer


        For i = 0 To xmlData.GetUpperBound(0) - 1
            Console.WriteLine("Working On Title No. " & i & " Out Of " & xmlData.GetUpperBound(0) - 1)
            titlePercentageMatch = 0
            numberOfTitlesMatched = 0

            xmlTitle = xmlData(i, 0)
            xmlTitle = processTitle(stopWords, userDefinedDelimeters, xmlTitle)
            xmlTitleWords = xmlTitle.Split(" ")

            For Each title In titles
                title = processTitle(stopWords, userDefinedDelimeters, title)
                savedTitleWords = title.split(" ")
                Dim compareResult = compareTitle(xmlTitleWords, savedTitleWords)
                If compareResult > 0 Then
                    titlePercentageMatch += compareResult
                    numberOfTitlesMatched += 1
                End If
            Next

            titleResults(i, 0) = xmlData(i, 0)
            titleResults(i, 1) = (titlePercentageMatch / numberOfTitlesMatched)
        Next

        For i = 0 To titleResults.GetUpperBound(0) - 1
            Console.WriteLine(titleResults(i, 0) & " ---> " & titleResults(i, 1) & vbCrLf)
        Next

        Console.Read()
    End Sub

    Function compareTitle(ByRef xmlTitleWords As Array, ByRef savedTitleWords As Array)
        Dim NumberOfMatches = 0

        For Each xmlWord In xmlTitleWords
            For Each savedWord In savedTitleWords
                If (xmlWord.ToString.ToLower = savedWord.ToString.ToLower) Then
                    NumberOfMatches += 1
                End If
            Next
        Next

        Return ((NumberOfMatches / xmlTitleWords.Length) * 100)
    End Function

    Function processTitle(ByRef stopWordArray As Array, ByRef delimArray As Array, ByVal title As String)
        title = removeStopWords(stopWordArray, title)
        title = removeDelims(delimArray, title)

        Return title
    End Function

    Function removeStopWords(ByRef stopWordsArray As Array, ByVal sentence As String)
        For i = 0 To stopWordsArray.Length - 1
            If sentence.ToLower.Contains(" " & stopWordsArray(i).ToString.ToLower & " ") = True Then
                sentence = Microsoft.VisualBasic.Strings.Replace(sentence, " " & stopWordsArray(i) & " ", " ", 1, -1, Constants.vbTextCompare)
                'ElseIf sentence.ToLower.Contains(stopWordsArray(i).ToString.ToLower & " ") = True Then
                'sentence = Microsoft.VisualBasic.Strings.Replace(sentence, stopWordsArray(i) & " ", "", 1, -1, Constants.vbTextCompare)
            End If

            sentence = Regex.Replace(sentence, "\s+", " ")

            Dim Words = sentence.ToLower.Split(" ")

            If Words(0).ToString.ToLower & " " = stopWordsArray(i).ToString.ToLower & " " Then
                sentence = sentence.Remove(0, stopWordsArray(i).ToString.ToLower.Length + 1)
            End If

            Words = sentence.ToLower.Split(" ")
            Dim LastWord = Words(Words.Length - 1)
            'Console.WriteLine(LastWord & "++")

            If " " & LastWord.ToString.ToLower = " " & stopWordsArray(i).ToString.ToLower Then
                sentence = sentence.Remove(sentence.Length - 1 - LastWord.Length, stopWordsArray(i).ToString.ToLower.Length + 1)
            End If

        Next

        sentence = Regex.Replace(sentence, "\s+", " ")

        Return sentence
    End Function

    Function removeDelims(ByRef delimArray As Array, ByVal sentence As String)
        For i = 0 To delimArray.GetUpperBound(0) - 1
            sentence = sentence.Replace(delimArray(i, 0), delimArray(i, 1))
        Next
        sentence = Regex.Replace(sentence, "\s+", " ")
        Return sentence
    End Function

    Function FileToArray(ByVal filePath As String) As String()
        Dim content As String
        Dim lines As New ArrayList
        Dim sr As System.IO.StreamReader

        ' read the file's lines into an ArrayList
        Try
            sr = New System.IO.StreamReader(filePath)
            Do While sr.Peek() >= 0
                lines.Add(sr.ReadLine())
            Loop
        Finally
            If Not sr Is Nothing Then sr.Close()
        End Try

        ' convert from ArrayList to a String array
        Return CType(lines.ToArray(GetType(String)), String())
    End Function

End Module

編集:あまり混乱しないことを願っています。ごめんなさい! 編集2:提供されたソース:P

4

3 に答える 3

2

基本的なアルゴリズムはN*M*A 2です。

  • N = 最初のファイルのタイトル数
  • M = 2 番目のファイルのタイトル数
  • A = タイトルあたりの平均単語数

500*500*5 2の場合、6,250,000 の大文字と小文字を区別しない文字列比較をプッシュしています。しかし、それはあなたがしていたすべての場合です。内側のループは、外側のループの長さごとにprocessTitlefor everyを呼び出します。titleそうする必要はありません。

シングルスレッド

できることは、各単語をその単語を表す整数 (記号) に置き換える前処理ステップを用意することです。このために、辞書を使用してシンボルを検索し、存在しない場合は、新しい一意のシンボルを割り当てます (たとえば、整数カウンターを保持し、次の値を使用します)。

その後、以前と同様のメイン処理ループを使用できますが、代わりに整数比較を行っています (はるかに高速です)。実際、この処理ステップでは、統計の比較と収集のみを行う必要があります。他のすべてを移動する必要があります。

マルチスレッド

前処理ステップを維持します。

処理ステップを並列化します。これを行う 1 つの方法は、最も外側のループにParallel.For()Parallel.For(0, xmlData.GetUpperBound(0) - 1, Sub(i) ... End Sub)を使用することです。ここで、アクションは上から見たループ本体です。TPL はおそらく負荷を適切に分散します (4 つのコアを均等に使用します)。

もう 1 つの方法は、タスク並列ライブラリを使用して、データの 1/4 で動作するタスクをスピンアップすることです。次に、結果を使用する継続を開始します。

于 2012-11-14T19:56:31.290 に答える
1

一度にメモリにのみ読み取りarray B、次に行ごとに読み取りますarray A

該当する場合は、文字列の代わりに StringBuilder を使用します。

また、並列処理、つまりタスクを使用できるかどうかも確認してください。

距離、マッチングアルゴリズムについては、それが何であり、どのように機能するかについて言及していません。それについて何かを言うのはとても難しいです。

于 2012-11-14T18:59:58.463 に答える
1

いくつかのことで少し速度を落としています...

  1. If (xmlWord.ToString.ToLower = savedWord.ToString.ToLower) Then

    配列に入れる前に、すべてを小文字に変更しないのはなぜですか?

  2. title = processTitle(stopWords, userDefinedDelimeters, title)

    配列にロードする前にそれをしないのはなぜですか??

事前にすべての処理を行ってから、比較を個別に行うだけです。

于 2012-11-14T19:18:29.113 に答える