Оптимизация работы со строками

@eltrien · Регистрация: 24.07.2011

Author24 — интернет-сервис помощи студентам

Снова здравствуйте! В этот раз хотелось бы выслушать предложения по оптимизации алгоритма для определения похожести строк. Данный метод в программе вызывается периодически и примерно 200 млн. раз за каждый обход, время выполнения составляет около 2 минут.

C#

public static bool AreSimilar(string S1, string S2)
{
    if (String.IsNullOrEmpty(S1) || String.IsNullOrEmpty(S2))
        return false;
 
    string S1temp = S1.ToLower(), S2temp = S2.ToLower();
 
    foreach (string s in signore)
    {
        if (((S1temp.Contains(s)) && (!S2temp.Contains(s))) ||
            ((!S1temp.Contains(s)) && (S2temp.Contains(s))))
            return false;
    }
    foreach (string s in repeat)
    {
        if ((S1temp.Contains(s)) && (S2temp.Contains(s)))
            return false;
    }
 
    foreach (string s in sreplace)
    {
        S1temp = S1temp.Replace(s, "");
        S2temp = S2temp.Replace(s, "");
    }
 
    int length1 = S1temp.Length, length2 = S2temp.Length;
    string LastSub = strLongestCommonSubstring(S1temp, S2temp);
    int length = 0;
    do
    {
        length += LastSub.Length;
        S1temp = S1temp.Remove(S1temp.IndexOf(LastSub), LastSub.Length);
        S2temp = S2temp.Remove(S2temp.IndexOf(LastSub), LastSub.Length);
        LastSub = strLongestCommonSubstring(S1temp, S2temp);
        if (LastSub == "")
            LastSub = " ";
    }
    while ((LastSub.Length > 2 + Settings.Strong2) || (char.IsDigit(LastSub[0])));
    int min1 = 4, min2= 4;
    if (length1 < 4)
        min1 = 0;
    else if (length1 < 7)
        min1 = 1;
    else if (length1 < 11)
        min1 = 2;
    else if (length1 < 15)
        min1 = 3;
    if (length2 < 4)
        min2 = 0;
    else if (length2 < 7)
        min2 = 1;
    else if (length2 < 11)
        min2 = 2;
    else if (length2 < 15)
        min2 = 3;
 
    return ((length1 - min1 + Settings.Strong <= length) || (length2 - min2 + Settings.Strong <= length));
}
 
//наибольшая общая подстрока
public static string strLongestCommonSubstring(string str1, string str2)
{
    if (String.IsNullOrEmpty(str1) || String.IsNullOrEmpty(str2))
        return "";
 
    string result = "";
    List<int[]> num = new List<int[]>();
    int maxlen = 0;
    for (int i = 0; i < str1.Length; i++)
    {
        num.Add(new int[str2.Length]);
        for (int j = 0; j < str2.Length; j++)
        {
            if (str1[i] != str2[j])
                num[i][j] = 0;
            else
            {
                if ((i == 0) || (j == 0))
                    num[i][j] = 1;
                else
                    num[i][j] = 1 + num[i - 1][j - 1];
                if (num[i][j] > maxlen)
                {
                    maxlen = num[i][j];
                    result = str1.Substring(i - maxlen + 1, maxlen);
                }
            }
            if (i >= 2)
                num[i - 2] = null;
        }
    }
    return result;
}

signore, sreplase, srepeat - массивы строк, их предназначение должно быть понятно. Уже не помню, откуда был позаимствован метод нахождения наибольшей общей подстроки (вроде бы с Википедии), я его немного модифицировал (изначально метод находил лишь длину наибольшей общей подстроки, мне же надо было саму подстроку).

@m0nax · 31.07.2011, 04:57

если алгоритм взят с википедии то тут уже нечего оптимизировать
Тем более, ты хочешь ворочать сотни милллионов строк и чтоб все быстро было? Такое только в сказках бывает..
даже простое сравнение в таких количествах займет те же минуты

единственный вариант это переписать все с использованием StringBuilder, в принципе дописывать придется только свой IndexOf для него (еще не факт что он будет быстрей)

Добавлено через 20 минут
еще попробуй вот такой вариант, в теории должно стать быстрей, проверить не на чем..

C#

             
     public static string strLongestCommonSubstring(string str1, string str2)
        {
            if (String.IsNullOrEmpty(str1) || String.IsNullOrEmpty(str2))
                return "";
 
            //string result = "";
           // var num = new List<int[]>(str1.Length);
            int[,] num = new int[str1.Length, str2.Length];
 
            int maxlen = 0;
            int saveIndex = 0;
            for (int i = 0; i < str1.Length; i++)
            {
//                 num.Add(new int[str2.Length]);
 
                for (int j = 0; j < str2.Length; j++)
                {
                    if (str1[i] != str2[j])
                        num[i,j] = 0;
                    else
                    {
                        if ((i == 0) || (j == 0))
                            num[i,j] = 1;
                        else
                            num[i,j] = 1 + num[i - 1,j - 1];
                        if (num[i,j] > maxlen)
                        {
                            maxlen = num[i,j];
                            saveIndex = i;
                            //result = str1.Substring(i - maxlen + 1, maxlen);
                        }
                    }
//                     if (i >= 2)
//                         num[i - 2] = null;
                }
            }
 
            return str1.Substring(saveIndex - maxlen + 1, maxlen);
        }

@eltrien · 31.07.2011, 12:25 **[ТС]**

Сообщение от m0nax

даже простое сравнение в таких количествах займет те же минуты

Извините, перепутал, там количество сравнений гораздо меньше

Примерно в 1000 раз. Так что скорость работы не устраивает. Те же операции сравнения похожести дат на таких количествах у меня занимают теперь 0,2 секунды. А за код спасибо, попробую его.

Добавлено через 13 минут
Вообще, я хотел выслушать предложения по оптимизации моего метода AreSimilar - именно в нём могут быть костыли. Пока что в голову пришла идея в данном методе перед всеми вызовами strLongestCommonSubstring просто добавить следующее:

C#

1 2	if (S1temp == S2temp) return true;

Должно будет уменьшить количество операций при почти одинаковых строках.

	31.07.2011, 12:25

Опции темы