ошибочная фиксация строк в c #

Question

У меня пять строк, как показано ниже,

ABBCCD

ABBDCD

ABBDCD

ABBECD

ABBDCD

все строки в основном одинаковы, за исключением четвертых символов.Но только персонаж, который появляется максимальное время, займет место.Например, здесь D был помещен 3 раза в четвертую позицию.Итак, последняя строка будет ABBDCD.Я написал следующий код, но он оказался менее эффективным с точки зрения времени.Потому что эту функцию можно вызывать миллион раз.Что я должен сделать, чтобы улучшить производительность?

Здесь changeString - строка, которую нужно сопоставить с другими 5 строками.Если любая позиция измененной строки не совпадает с остальными четырьмя, то найденный символ maxmum будет помещен в changeString.

len - длина строк, одинаковая для всех строк.

for (int i = 0; i < len;i++ )
{
    String findDuplicate = string.Empty + changedString[i] + overlapStr[0][i] + overlapStr[1][i] + overlapStr[2][i] +
                           overlapStr[3][i] + overlapStr[4][i];

    char c = findDuplicate.GroupBy(x => x).OrderByDescending(x => x.Count()).First().Key;
    if(c!=changedString[i])
    {
        if (i > 0)
        {
            changedString = changedString.Substring(0, i) + c +
                            changedString.Substring(i + 1, changedString.Length - i - 1);
        }
        else
        {
            changedString = c + changedString.Substring(i + 1, changedString.Length - 1);
        }
    }
    //string cleanString = new string(findDuplicate.ToCharArray().Distinct().ToArray());
}

Answer 1

Существует функция, которая может помочь с точки зрения производительности, поскольку она работает в пять раз быстрее.Идея состоит в том, чтобы подсчитать вхождения самостоятельно, используя словарь для преобразования символа в позицию в счетный массив, увеличить значение в этой позиции и проверить, не превышает ли это ранее наибольшее количество вхождений.Если это так, текущий символ является верхним и сохраняется как результат.Это повторяется для каждой строки в overlapStr и для каждой позиции в строках.Пожалуйста, прочтите комментарии внутри кода, чтобы увидеть подробности.

string HighestOccurrenceByPosition(string[] overlapStr)
{
    int len = overlapStr[0].Length;
    //  Dictionary transforms character to offset into counting array
    Dictionary<char, int> char2offset = new Dictionary<char, int>();
    //  Counting array. Each character has an entry here
    int[] counters = new int[overlapStr.Length];
    //  Highest occurrence characters found so far
    char[] topChars = new char[len];

    for (int i = 0; i < len; ++i)
    {
        char2offset.Clear();
        //  faster! char2offset = new Dictionary<char, int>();
        //  Highest number of occurrences at the moment
        int highestCount = 0;
        //  Allocation of counters - as previously unseen character arrives 
        //  it is given a slot at this offset
        int lastOffset = 0;
        //  Current offset into "counters"
        int offset = 0;
        //  Small optimization. As your data seems very similar, this helps
        //  to reduce number of expensive calls to TryGetValue
        //  You might need to remove this optimization if you don't have 
        //  unused value of char in your dataset
        char lastChar = (char)0;

        for (int j = 0; j < overlapStr.Length; ++ j)
        {
            char thisChar = overlapStr[j][i];
            //  If this is the same character as last one
            //  Offset already points to correct cell in "counters"
            if (lastChar != thisChar)
            {
                //  Get offset
                if (!char2offset.TryGetValue(thisChar, out offset))
                {
                    //  First time seen - allocate & initialize cell
                    offset = lastOffset;
                    counters[offset] = 0;
                    //  Map character to this cell
                    char2offset[thisChar] = lastOffset++;
                }
                //  This is now last character
                lastChar = thisChar;
            }
            //  increment and get count for character
            int charCount = ++counters[offset];
            //  This is now highestCount.
            //  TopChars receives current character
            if (charCount > highestCount)
            {
                highestCount = charCount;
                topChars[i] = thisChar;
            }
        }
    }
    return new string(topChars);
}

PS Это, безусловно, не лучшее решение.Но так как он значительно быстрее оригинального, я подумал, что должен помочь.

Answer 2

Я не совсем уверен, что вы собираетесь делать, но если речь идет о сортировке строк по какому-либо n-му символу, тогда лучше всего использовать Counting Sort http://en.wikipedia.org/wiki/Counting_sort Он используется для сортировки массив маленьких целых чисел и вполне подходит для символов. Он имеет линейное время O (n). Основная идея заключается в том, что если вы знаете все возможные элементы (похоже, здесь они могут быть только A-Z), вы можете создать дополнительный массив и сосчитать их. Для вашего примера это будет {0, 0, 1, 3, 1, 0, ...}, если мы будем использовать 0 для «A», 1 для «B» и т. Д.