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

Question

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

ABBCCD

ABBDCD

ABBDCD

ABBECD

ABBDCD

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

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

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

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

Answer 2

Существует функция, которая может помочь в производительности, поскольку она работает в пять раз быстрее. Идея состоит в том, чтобы самостоятельно подсчитывать вхождения с помощью словаря для преобразования символа в позицию в счетный массив, увеличивать значение в этой позиции и проверять, больше ли это по сравнению с предыдущим самым большим числом вхождений. Если это так, текущий символ является верхним и сохраняется как результат. Это повторяется для каждой строки в 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); 
} 

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