String.comparison производительность (с отделкой)

Question

Мне нужно сделать много высокопроизводительных сравнений строк без учета регистра, и я понял, что мой способ сделать это .ToLower (). Trim () был действительно глупым из-за того, что все новые строки были выделены

Итак, я немного покопался, и этот способ кажется предпочтительным:

String.Compare(txt1,txt2, StringComparison.OrdinalIgnoreCase)

Единственная проблема здесь в том, что я хочу игнорировать начальные или конечные пробелы, то есть Trim (), но если я использую Trim, у меня та же проблема с распределением строк. Я думаю, что я мог бы проверить каждую строку и посмотреть, если она StartsWith ("") или EndsWith (""), и только тогда Trim. Либо так, либо вычислите индекс, длину для каждой строки и передайте строку. Сравнение переопределения

public static int Compare
(
    string strA,
    int indexA,
    string strB,
    int indexB,
    int length,
    StringComparison comparisonType
) 

но это кажется довольно запутанным, и мне, вероятно, придется использовать некоторые целые числа, если я не сделаю действительно большого оператора if-else для каждой комбинации конечных и ведущих пробелов в обеих строках ... так есть ли идеи элегантного решения?

Вот мое текущее предложение:

public bool IsEqual(string a, string b)
    {
        return (string.Compare(a, b, StringComparison.OrdinalIgnoreCase) == 0);
    }

    public bool IsTrimEqual(string a, string b)
    {
        if (Math.Abs(a.Length- b.Length) > 2 ) // if length differs by more than 2, cant be equal
        {
            return  false;
        }
        else if (IsEqual(a,b))
        {
            return true;
        }
        else 
        {
            return (string.Compare(a.Trim(), b.Trim(), StringComparison.OrdinalIgnoreCase) == 0);
        }
    }

Answer 1

Что-то вроде этого должно сделать это:

public static int TrimCompareIgnoreCase(string a, string b) {
   int indexA = 0;
   int indexB = 0;
   while (indexA < a.Length && Char.IsWhiteSpace(a[indexA])) indexA++;
   while (indexB < b.Length && Char.IsWhiteSpace(b[indexB])) indexB++;
   int lenA = a.Length - indexA;
   int lenB = b.Length - indexB;
   while (lenA > 0 && Char.IsWhiteSpace(a[indexA + lenA - 1])) lenA--;
   while (lenB > 0 && Char.IsWhiteSpace(b[indexB + lenB - 1])) lenB--;
   if (lenA == 0 && lenB == 0) return 0;
   if (lenA == 0) return 1;
   if (lenB == 0) return -1;
   int result = String.Compare(a, indexA, b, indexB, Math.Min(lenA, lenB), true);
   if (result == 0) {
      if (lenA < lenB) result--;
      if (lenA > lenB) result++;
   }
   return result;
}

Пример:

string a = "  asdf ";
string b = " ASDF \t   ";

Console.WriteLine(TrimCompareIgnoreCase(a, b));

Выход:

0

Вы должны профилировать его по сравнению с простой Обрезкой и сравнивать с некоторыми реальными данными, чтобы увидеть, есть ли какая-либо разница в том, для чего вы собираетесь его использовать.

Answer 2

Я бы использовал ваш код

String.Compare(txt1,txt2, StringComparison.OrdinalIgnoreCase)

и добавляйте любые .Trim() звонки по мере необходимости. Это сохранит исходную опцию 4 строки большую часть времени (.ToLower().Trim() и две строки все время (.ToLower()).

Если после этого у вас возникли проблемы с производительностью, то ваш «грязный» вариант, вероятно, лучший выбор.

Answer 3

Разве вы не можете просто обрезать (и, возможно, сделать это строчными буквами) каждую строку ровно один раз (при ее получении)? Делать больше звуков, как преждевременная оптимизация ....

Answer 4

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

Если вам действительно нужно оптимизировать, вы можете попытаться обработать строки при первом их сохранении, а не при сравнении (при условии, что это происходит на разных этапах программы). Например, храните обрезанные и строчные версии строк, чтобы при сравнении их можно было просто использовать проверку на эквивалентность.

Answer 5

Я заметил, что ваше первое предложение сравнивает только на равенство, а не сортировку, что позволяет еще больше сэкономить на эффективности.

public static bool TrimmedOrdinalIgnoreCaseEquals(string x, string y)
{
    //Always check for identity (same reference) first for
    //any comparison (equality or otherwise) that could take some time.
    //Identity always entails equality, and equality always entails
    //equivalence.
    if(ReferenceEquals(x, y))
        return true;
    //We already know they aren't both null as ReferenceEquals(null, null)
    //returns true.
    if(x == null || y == null)
        return false;
    int startX = 0;
    //note we keep this one further than the last char we care about.
    int endX = x.Length;
    int startY = 0;
    //likewise, one further than we care about.
    int endY = y.Length;
    while(startX != endX && char.IsWhiteSpace(x[startX]))
        ++startX;
    while(startY != endY && char.IsWhiteSpace(y[startY]))
        ++startY;
    if(startX == endX)      //Empty when trimmed.
        return startY == endY;
    if(startY == endY)
        return false;
    //lack of bounds checking is safe as we would have returned
    //already in cases where endX and endY can fall below zero.
    while(char.IsWhiteSpace(x[endX - 1]))
        --endX;
    while(char.IsWhiteSpace(y[endY - 1]))
        --endY;
    //From this point on I am assuming you do not care about
    //the complications of case-folding, based on your example
    //referencing the ordinal version of string comparison
    if(endX - startX != endY - startY)
        return false;
    while(startX != endX)
    {
        //trade-off: with some data a case-sensitive
        //comparison first
        //could be more efficient.
        if(
            char.ToLowerInvariant(x[startX++])
            != char.ToLowerInvariant(y[startY++])
        )
            return false;
    }
    return true;
}

Конечно, что такое проверка на равенство без соответствующего производителя хеш-кода:

public static int TrimmedOrdinalIgnoreCaseHashCode(string str)
{
    //Higher CMP_NUM (or get rid of it altogether) gives
    //better hash, at cost of taking longer to compute.
    const int CMP_NUM = 12;
    if(str == null)
        return 0;
    int start = 0;
    int end = str.Length;
    while(start != end && char.IsWhiteSpace(str[start]))
        ++start;
    if(start != end)
        while(char.IsWhiteSpace(str[end - 1]))
            --end;

    int skipOn = (end - start) / CMP_NUM + 1;
    int ret = 757602046; // no harm matching native .NET with empty string.
    while(start < end)
    {
            //prime numbers are our friends.
        ret = unchecked(ret * 251 + (int)(char.ToLowerInvariant(str[start])));
        start += skipOn;
    }
    return ret;
}

Answer 6

Вы можете реализовать свой собственный StringComparer. Вот базовая реализация:

public class TrimmingStringComparer : StringComparer
{
    private StringComparison _comparisonType;

    public TrimmingStringComparer()
        : this(StringComparison.CurrentCulture)
    {
    }

    public TrimmingStringComparer(StringComparison comparisonType)
    {
        _comparisonType = comparisonType;
    }

    public override int Compare(string x, string y)
    {
        int indexX;
        int indexY;
        int lengthX = TrimString(x, out indexX);
        int lengthY = TrimString(y, out indexY);

        if (lengthX <= 0 && lengthY <= 0)
            return 0; // both strings contain only white space

        if (lengthX <= 0)
            return -1; // x contains only white space, y doesn't

        if (lengthY <= 0)
            return 1; // y contains only white space, x doesn't

        if (lengthX < lengthY)
            return -1; // x is shorter than y

        if (lengthY < lengthX)
            return 1; // y is shorter than x

        return String.Compare(x, indexX, y, indexY, lengthX, _comparisonType);
    }

    public override bool Equals(string x, string y)
    {
        return Compare(x, y) == 0;
    }

    public override int GetHashCode(string obj)
    {
        throw new NotImplementedException();
    }

    private int TrimString(string s, out int index)
    {
        index = 0;
        while (index < s.Length && Char.IsWhiteSpace(s, index)) index++;
        int last = s.Length - 1;
        while (last >= 0 && Char.IsWhiteSpace(s, last)) last--;
        return last - index + 1;
    }
}

Примечания:

• это не всесторонне проверено и может содержать ошибки
• производительность еще предстоит оценить (но, вероятно, лучше, чем звонить Trim и ToLower в любом случае)
• метод GetHashCode не реализован, поэтому не используйте его в качестве ключа в словаре

Answer 7

Предупреждения о преждевременной оптимизации верны, но я предполагаю, что вы проверили это и обнаружили, что копирование строк тратит много времени. В этом случае я бы попробовал следующее:

int startIndex1, length1, startIndex2, length2;
FindStartAndLength(txt1, out startIndex1, out length1);
FindStartAndLength(txt2, out startIndex2, out length2);

int compareLength = Math.Max(length1, length2);
int result = string.Compare(txt1, startIndex1, txt2, startIndex2, compareLength);

FindStartAndLength - это функция, которая находит начальный индекс и длину «обрезанной» строки (это не проверено, но должно дать общее представление):

static void FindStartAndLength(string text, out int startIndex, out int length)
{
    startIndex = 0;
    while(char.IsWhiteSpace(text[startIndex]) && startIndex < text.Length)
        startIndex++;

    length = text.Length - startIndex;
    while(char.IsWhiteSpace(text[startIndex + length - 1]) && length > 0)
        length--;
}

Answer 8

1. Дело в том, что если это нужно сделать, это нужно сделать. Я не думаю, что любое из ваших разных решений будет иметь значение. В каждом случае должен быть ряд сравнений, чтобы найти пробел или удалить его.

   Очевидно, что удаление пробелов является частью проблемы, поэтому вам не стоит об этом беспокоиться.

2. И нижний регистр строки перед сравнением является ошибкой, если вы работаете с символами Юникода и возможно медленнее, чем копирование строки.