Оптимизация алгоритма по скорости

[xenomorph]

Привет всем!

Задача: пишу алгоритм, который из текста:

"Я, очень, люблю !!! сладкие спелые бананы на завтрак."

Сформирует такой массив:

data[0] "я очень люблю"
data[1] "очень люблю сладкие"
data[2] "люблю сладкие бананы"
data[3] "сладкие бананы на"
data[4] "бананы на завтрак"

Условия:
1. Шаг смещения (в примере = 1) может быть любым.
2. Длинна элемента в выходном массиве (в примере = 3) может быть любая.

Проблема:

Алгоритм написан. Быстродействее крайне плохое!!!
Пните меня где можно ускориться??? Где кривые места?

Основная функция: DefineFPs

Заранее огромное спасибо!

[MIT]

Не сильно вдавался в систему реализации алгоритма, но я бы сделал по-другому: разбил бы String.Split`ом строку по пробелам, создал бы массив соответствия и на его основе по очереди забивал новый (необходимый) массив. Если хочешь - могу написать пример.

[xenomorph]

2 MIT: Может я тебя не правильно понял, но мне кажеться я делаю сплит правильно:

Код: Выделить всё

    Private Sub DoSplit(ByRef sa_Text() As String, ByRef s_Text As String)
        Try
            Dim chara_separators(4) As Char
            chara_separators(0) = vbCrLf
            chara_separators(1) = " "
            chara_separators(2) = vbCr
            chara_separators(3) = vbLf
            chara_separators(4) = vbTab
            sa_Text = s_Text.Split(chara_separators, StringSplitOptions.None)
        Catch ex As Exception
            lex(ex)
        End Try
    End Sub


[MIT]

Да, что-то я больно поспешно "вынес приговор". Действительно, сплит у тебя правильный, но.
Собствеено, думаю, что начать следует с переработки функций обработки строк.

На коленке (в общем-то, как и всегда ) написал один тестосравнивалку, зацени:

Код: Выделить всё

Public Class Form1

    Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
        Dim s As String = IO.File.ReadAllText("O:\dl\SpeedTest\SpeedTest\bin\Debug\test_text.txt")
        Dim ts1, ts2, ts3 As New DateTime

        ts1 = Now


        Dim chara_separators(4) As Char
        chara_separators(0) = " "c : chara_separators(1) = vbCr : chara_separators(2) = vbLf : chara_separators(3) = vbTab
        Dim myarr1(), out1 As String, sb As System.Text.StringBuilder
        'For i As Integer = 0 To 99
        myarr1 = s.Split(chara_separators, StringSplitOptions.RemoveEmptyEntries)
        sb = New System.Text.StringBuilder
        For j As Integer = 0 To myarr1.Length - 1
            sb.Append(NormalizeString(myarr1(j)))
            sb.Append(" "c)
        Next
        out1 = sb.ToString
        'Next



        ts2 = Now


        Dim myarr2(), out2 As String
        'For i As Integer = 0 To 99
        'out2 = ""
        DoSplit(myarr2, s)
        For j As Integer = 0 To myarr2.Length - 1
            out2 &= CleanFP(myarr2(j)) & " "
        Next
        'Next




        ts3 = Now

        MsgBox(String.Format("{1}{0}{2}", vbCrLf, ts2.Ticks - ts1.Ticks, ts3.Ticks - ts2.Ticks))
        End
    End Sub

    Private Function NormalizeString(ByVal str As String) As String
        If String.IsNullOrEmpty(str) Then Return str
        Dim chs As Char() = str.ToCharArray
        Dim shift, i As Integer

        Do While i < chs.Length - shift
            If Char.IsLetterOrDigit(chs(i)) Then
                i += 1
            Else
                shift += 1
                Array.ConstrainedCopy(chs, i + 1, chs, i, chs.Length - shift - i)
            End If
        Loop
        ReDim Preserve chs(chs.Length - shift - 1)

        Return New String(chs)
    End Function


    Private Sub DoSplit(ByRef sa_Text() As String, ByRef s_Text As String)
        Try
            Dim chara_separators(4) As Char
            chara_separators(0) = vbCrLf
            chara_separators(1) = " "
            chara_separators(2) = vbCr
            chara_separators(3) = vbLf
            chara_separators(4) = vbTab
            sa_Text = s_Text.Split(chara_separators, StringSplitOptions.None)
        Catch ex As Exception
            'lex(ex)
        End Try
    End Sub
    Dim sa_SpecialChar() As Char = {"."c, ","c, "<"c, ">"c, "'"c, ":"c, ";"c, Chr(9), "?"c, """"c, "/"c, "{"c, "["c, "}"c, "]"c, "`"c, "~"c, "!"c, "@"c, "#"c, "$"c, "%"c, "^"c, "&"c, "*"c, "("c, ")"c, "_"c, "-"c, "+"c, "="c, "|"c, "\"c}
    Public Function CleanFP(ByVal buf As String) As String
        If String.IsNullOrEmpty(buf) Then Return buf
        'If String.IsNullOrEmpty(buf) Then Return Nothing


        For i As Integer = 0 To sa_SpecialChar.Length - 1
            buf = buf.Replace(sa_SpecialChar(i), "")

        Next
        Return buf.Replace("  ", " ").Trim
    End Function
End Class


Суть - альтернатива связке твоих функций CleanFP (которую я несколько оптимизировал) и DoSplit. Результат - неплохой: при обработке 2кб текста превосходство раз в 10, а при обработке твоего файла (2,2мб)... Не знаю во сколько раз, но моя версия отработала быстрее чем за секунду, а завершения твоей связки я не дождался (ждал 10 минут).

Дальше - больше, ждите продолжения

[MIT]

Заменив код, расположенный между ts1 = Now и ts2 = Now на этот:

Код: Выделить всё

        Dim chara_separators(4) As Char
        chara_separators(0) = " "c : chara_separators(1) = vbCr : chara_separators(2) = vbLf : chara_separators(3) = vbTab
        Dim myarr1(), out1 As String, sb As System.Text.StringBuilder
        Dim outArr() As String
        myarr1 = s.Split(chara_separators, StringSplitOptions.RemoveEmptyEntries)
        ReDim outArr(myarr1.Length - 1 - words)
        sb = New System.Text.StringBuilder
        For j As Integer = 0 To myarr1.Length - 1
            myarr1(j) = NormalizeString(myarr1(j))
        Next
        For j As Integer = 0 To myarr1.Length - 1 - words
            For k = 0 To words - 1
                sb.Append(myarr1(j + k))
                sb.Append(" "c)
            Next
            outArr(j) = sb.ToString
            sb = New System.Text.StringBuilder
        Next

и добавив новую переменную Dim words As Integer = 5 можно получить реализацию первоначальной задачи (ведь там вроде это надо?).
Код еще не оптимизирован до конца, но уже сейчас обрабатывает исходный файл за 2 секунды (против 22 в оригинале)

[xenomorph]

2 MIT Спасибо, ЧЕЛОВЕЧИЩЕ!!! Код рулит!!!

1. Я заменил CleanFP на твой вариант протестил код - дало 1.4 секунды (у меня Intell Core 2 Quad 9550, DDR4).
2. Я не могу использовать RemoveEmptyEntries по некоторой причине в DoSplit.
3. Я попробовал вставить StringBuilder в места аккумуляции строк - не покатило. Время увеличилось.
ИМХО операции с этим объектом больше съедают чем эффект от него даёт. Он должен и будет давать эффект
при больших стрингах, а здесь - фразы до 10 слов, поэтому не окупилось, а жаль.

Поделюсь статистикой -

Этот кусок кода - в программе к. я делаю отрабатывает 400.000.000 (именно миллионов!) раз.
Так что производительность просто фантастически улучшилась!!!

Ещё раз спасибо!
Если выиграю конкурс - с меня НЕ виртуальные пряники!