Преобразование двойного списка в сгруппированную строку

Question

Программа имеет входной список парных разрядов, а вывод должен быть строкой, содержащей значения списка, сгруппированные по их значению. Значения списка будут сгруппированы, если они равны. Что-то вроде: вход 9,77,5,5,31 => выход 9 77 2 * 5 31

Я создал алгоритм в C# (в Java я думаю, что это почти то же самое) для этого, но я не уверен, что его можно улучшить в отношении его скорости или перекоса кода, или если у него есть некоторые ошибки, которые я не мог видеть. Ниже приведен алгоритм, содержащий еще несколько примеров ввода, вывода.

  List<double> input = new List<double> { 11, 32, 32, 43}; // output 11 2*32 43 
     //List<double> input = new List<double> { 11, 11, 43, 43 }; // output 2*11 2*43 
     //List<double> input = new List<double> { 10, 11, 12, 13, 14, 15, 16 }; // output 10 11 12 13 14 15 16 
     //List<double> input = new List<double> { 11, 11, 11, 11, 11 }; // output 5 * 11 
     //List<double> input = new List<double> { 11, 11, 32, 22, 22, 22, 4, 10, 10 }; // output 2*11 32 3*22 4 2*10 

     string listAsString = string.Empty; 
     double nextElem = double.MinValue; 
     for (int i = 0; i < input.Count; i++) 
     { 
      double currentElem = input[i]; 

      if (i + 1 < input.Count) 
      { 
       nextElem = input[i + 1]; 
      } 

      int equalCount = 0; 
      while (currentElem.Equals(nextElem) && i < input.Count) 
      { 
       equalCount++; 
       i++; 
       currentElem = nextElem; 

       if (i < input.Count) 
       { 
        nextElem = input[i]; 
       } 
      } 

      if (equalCount < 2) 
      { 
       listAsString += currentElem + " "; 
      } 
      else 
      { 
       listAsString += equalCount + "*" + currentElem + " "; 
       i--; 
      } 
     } 

     Console.WriteLine(listAsString); 

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

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

Answer 1

Поскольку требование к группе только последовательных одинаковых значений, Dictionary и LINQ GroupBy подходы, упомянутые в другом ответе, не применяются, так как они будут производить неправильный результат для входной последовательности, как 1,2,1. Также нет стандартного метода LINQ для такой группировки (кроме метода Aggregate, но это не более чем неэффективно for/foreach10 эквивалент цикла).

Вскоре ваш алгоритм является лучшим для такой задачи. Но реализация не является.

Основным узким местом является конкатенация строк, как указано в Peroxy, что (также упомянутое в другом ответе) легко можно устранить, используя класс StringBuilder. Как только вы это сделаете, производительность будет прекрасной.

Другая проблема, которую я вижу в реализации, - использование специальных значений (double.MinValue), проверка дубликатов в углу, уменьшение for переменной цикла внутри тела и т. Д. Поэтому, хотя это, вероятно, работает, и я не вижу непосредственно ошибки, довольно сложно следовать логике алгоритмов и обнаруживать потенциальную ошибку, просто просматривающую реализацию. Сам алгоритм довольно прост, я бы реализовал его таким образом:

static string ListAsString(List<double> input) 
{ 
    var sb = new StringBuilder(); 
    for (int i = 0; i < input.Count;) 
    { 
     var value = input[i]; 
     int count = 1; 
     while (++i < input.Count && input[i] == value) 
      count++; 
     if (sb.Length > 0) sb.Append(' '); 
     if (count > 1) sb.Append(count).Append('*'); 
     sb.Append(value); 
    } 
    return sb.ToString(); 
} 

, с которым ИМО довольно легко следовать. Обратите внимание, что дублирующего кода нет, никаких специальных значений и переменная цикла i продвижение выполняется только в одном месте внутри тела внешнего контура. Опять же, это не имеет никакого отношения к производительности (что обеспечивается использованием StringBuilder), но просто читаемость, исключение избыточности и снижение вероятности ошибок.

Answer 2

Лично я вижу большой потенциал с Dictionary использования здесь, здесь быстрое решение, которое я сделал со словарем реализации:

var input = new List<double> { 9, 77, 5, 5, 31 }; 
var dict = new Dictionary<double, int>(); 
var listAsString = new StringBuilder(); 

foreach (var item in input) 
{ 
    if (dict.ContainsKey(item)) 
     dict[item]++; 
    else 
     dict[item] = 1; 
} 

foreach (var item in dict) 
{ 
    listAsString.Append(item.Value > 1 ? $"{item.Value}*{item.Key} " : $"{item.Key} "); 
} 

Console.WriteLine(listAsString); 

Если вы когда-нибудь хотели нон эффективное LINQ одно решение хвостовика:

string result = string.Join(" ", input.GroupBy(i => i) 
             .Select(x => 
             x.Count() > 1 ? 
             $"{x.Count()}*{x.Key} " : 
             $"{x.Key} ")); 

Однако, я считаю, что ваш метод написан красиво, хотя и немного менее читабельным, чем словарь, но основным недостатком вашего решения является то, что вы используете строку при построении окончательной строки, вы определенно должны использовать StringBuilder, я ввел StringBuilder в методе и проводил сравнение между этими тремя методами:

Dictionary | Your method | GroupBy method 
------------------------------------------------ 
2 ms   | 0 ms  | 5 ms   n=3 
0 ms   | 0 ms  | 0 ms   n=6 
0 ms   | 0 ms  | 0 ms   n=12 
0 ms   | 0 ms  | 0 ms   n=24 
0 ms   | 0 ms  | 0 ms   n=48 
0 ms   | 0 ms  | 0 ms   n=96 
0 ms   | 0 ms  | 0 ms   n=192 
0 ms   | 0 ms  | 0 ms   n=384 
0 ms   | 0 ms  | 0 ms   n=768 
0 ms   | 0 ms  | 0 ms   n=1536 
1 ms   | 0 ms  | 1 ms   n=3072 
3 ms   | 2 ms  | 3 ms   n=6144 
5 ms   | 4 ms  | 6 ms   n=12288 
8 ms   | 7 ms  | 14 ms   n=24576 
14 ms  | 13 ms | 25 ms   n=49152 
31 ms  | 32 ms | 66 ms   n=98304 
80 ms  | 59 ms | 146 ms   n=196608 
149 ms  | 123 ms | 294 ms   n=393216 
246 ms  | 218 ms | 504 ms   n=786432 
483 ms  | 428 ms | 1040 ms  n=1572864 
999 ms  | 873 ms | 2070 ms  n=3145728 
1995 ms  | 1784 ms | 3950 ms  n=6291456 

Вашим решением всегда самым быстрым, если вы хотите идти на скорость, держать свое решение, но изменить его, чтобы использовать StringBuilder , используйте listAsString.Append(currentElem + " ") вместо listAsString += currentElem + " ".

GroupBy может использоваться, если вы будете работать только с коллекциями, которые имеют n < 1000, используйте решение Dictionary, если вы предпочитаете удовлетвориться скоростью чтения.