Компактный список номеров с разделителями-запятыми в диапазонах

Я ищу умный способ выполнить следующую операцию:

Возьмите список чисел:

1, 2, 3, 4, 5, 12, 13, 14, 19

и скомпоновать его в строку следующим образом:

1-5, 12-14, 19

Следующее правило: только сжимать в диапазон (т. е. использовать тире), когда количество чисел в диапазоне равно 3 или более.

Ie: 1, 2, 4, 5 приведет к: 1, 2, 4, 5 и NOT : 1-2, 4-5

Это моя реализация, но я чувствую, что она может быть значительно улучшена:

 public string CompactNumberRanges(IEnumerable<int> numbers, 
                                   int requiredRangeCount)
 {
     if (requiredRangeCount <= 1)
         throw new ArgumentOutOfRangeException("requiredRangeCount");

     int[] sorted = numbers.OrderBy(e => e).ToArray();

     StringBuilder b = new StringBuilder();

     for (int i = 0; i < sorted.Length; i++)
     {
         int cv = sorted[i];
         int count = 0;

         for (int j = cv; ; j++)
         {
             if (Array.IndexOf(sorted, j) == -1)
                 break;
             else
                 count++;
         }

         if (count == 0)
             throw new InvalidOperationException();
         else if (count < requiredRangeCount)
             b.Append(", ").Append(cv);
         else if (count >= requiredRangeCount)
         {
             b.Append(", ").AppendFormat("{0}-{1}", cv, sorted[i + count - 1]);

             i += count - 1;
         }
     }

     return b.ToString().Trim(',', ' '); ;
 }

В качестве примера:

List<int> numbers = new List<int>
    (
        new int[] { 1, 2, 3, 4, 5, 12, 13, 14, 19 }
    );

Console.WriteLine(CompactNumberRanges(numbers, 3));
//  output: 1-5, 12-14, 19

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

11 голосов | спросил test 7 Maypm15 2015, 21:14:21

3 ответа


17

Вы можете вычислить значение для группировки, т. е. number - index. Все последовательные номера имеют одинаковое значение:

index  number  number - index
-----  ------  --------------
  0       1          1
  1       2          1
  2       3          1
  3       4          1
  4       5          1
  5      12          7
  6      13          7
  7      14          7
  8      19         11

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

Пример:

List<int> numbers = new List<int> { 1, 2, 3, 4, 5, 12, 13, 14, 19 };

List<string> items = numbers
  .Select((n,i) => new { number = n, group = n - i })
  .GroupBy(n => n.group)
  .Select(g =>
    g.Count() >= 3 ?
      g.First().number + "-" + g.Last().number
    :
      String.Join(", ", g.Select(x => x.number))
  )
  .ToList();

Console.WriteLine(String.Join(", ", items));

Вывод:

1-5, 12-14, 19
ответил Guffa 7 Maypm15 2015, 21:28:10
5

Обзор

Хорошие вещи:

  1. IEnumerable вместо List - IEnumerable более чем достаточно для получения желаемых данных.
  2. Проверка аргументов - никогда не доверяйте вводам.
  3. Использование StringBuilder - часто забытый (неизвестный) изначально, но очень эффективный подход.
  4. У кода, похоже, не было проблем в начале или в конце последовательности (забывая возвращать некоторые диапазоны для элементов в начале или в конце в некоторых случаях)

Возможные проблемы:

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

Проблемы с правильностью

  1. Наиболее заметным является то, что, проверяя requiredRangeCount, вы не проверяете numbers для значения null. Это не критично, но сделает ваш метод более пуленепробиваемым и намного более последовательным.
  2. Этот код, вероятно, будет иметь некоторые проблемы с дубликатами, поскольку внутренний цикл не учитывает их - он ищет следующее добавленное значение для каждой новой итерации.

Проблемы с производительностью:

  1. Array.IndexOf use - он реализован с помощью линейного поиска, поэтому он не использует тот факт, что массив уже заказано .
  2. И Array.IndexOf вызывается несколько раз, выполняется линейный поиск объекта, наличие которого можно проверить из массива [текущий индекс + 1].

Проблемы с стилями

  1. Это уже упоминалось в другом ответе , но для полноты использования имен неиндексных переменных должен быть указан: i не проблема, потому что это просто индекс, но использование j, что на самом деле означает, что следующий элемент для поиска и cv, возможно, станет более понятным с еще несколько букв.

Другие (дизайн) проблемы

  1. Этот метод фактически выполняет сразу две вещи - обрабатывает исходную последовательность для определения диапазонов последовательных элементов и объединяет эти диапазоны в одну строку. Хотя это одновременно может показаться более простым, он действительно объединяет две конкретные операции и операции многократного использования в одно. Это сочетание логики (получение диапазонов), основанной на домене, и логики представления (создание их строковых представлений).

Альтернативное общее решение

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

Класс диапазона

Создайте класс для представления диапазона (как первого, так и последнего элемента или только первого элемента). Для простоты мы создадим метод ToString для вывода нужного формата:

public class Range<T>
{
    public Range(T start, T end)
    {
        this.Start = start;
        this.End = end;
    }

    public Range(T startOnly)
    {
        this.Start = startOnly;
    }

    public T Start
    {
        get;
        private set;
    }

    private T m_end;

    public T End
    {
        get
        {
            if (!this.HasEnd)
                throw new InvalidOperationException("Range is a single element");

            return this.m_end;
        }                
        private set
        {
            this.HasEnd = true;
            this.m_end = value;
        }
    }

    public Boolean HasEnd
    {
        get;
        private set;
    }

    public override string ToString()
    {
        if (this.HasEnd)
            return String.Format("{0}-{1}", this.Start, this.End);

        return this.Start.ToString();
    }
}

Общий метод

Создайте общий метод, который требует дополнительного делегата Func, чтобы определить, находятся ли элементы в последовательном диапазоне. ПРЕДУПРЕЖДЕНИЕ: Этот метод предполагает, что коллекция является либо неубывающей, либо невозрастающей последовательностью, поэтому неупорядоченные последовательности должны быть упорядочены до вызова:

public static IEnumerable<Range<T>> CompactOrderedRanges<T>(this IEnumerable<T> collection, Int32 minForRange, Func<T, T, Boolean> areNeighbours)
{
    if (collection == null)
        throw new ArgumentNullException("collection");
    if (minForRange < 1)
        throw new ArgumentException("minForRange");
    if (areNeighbours == null)
        throw new ArgumentNullException("areNeighbours");

    List<T> range = new List<T>()
        {
            collection.First()
        };

    foreach (var item in collection.Skip(1))
    {
        if (areNeighbours(range.Last(), item))
        {
            range.Add(item);
            continue;
        }

        if (range.Count >= minForRange)
        {
            // Yield range
            yield return new Range<T>(range.First(), range.Last());
        }
        else
        {
            // Yield items in range one by one
            foreach (var rangeItem in range)
            {
                yield return new Range<T>(rangeItem);
            }
        }

        range.Clear();
        range.Add(item);
    }

    // Deal with leftovers. Code duplication, but I am not sure that it can  
    // be avoided due to yields other than with another helper function 
    // that returns IEnumerable<Range<T>>, so for now leave it as it is.
    if (range.Count >= minForRange)
    {
        // Yield range
        yield return new Range<T>(range.First(), range.Last());
    }
    else
    {
        // Yield items in range one by one
        foreach (var rangeItem in range)
        {
            yield return new Range<T>(rangeItem);
        }
    }
}

Специализация Int32

Для простоты также создайтеспециализированный метод, который обрабатывает коллекции IEnumerable<Int32>:

public static IEnumerable<Range<Int32>> CompactOrderedRanges(this IEnumerable<Int32> collection, Int32 minForRange)
{
    return collection.CompactOrderedRanges(minForRange,
        (a, b) =>
        {
            checked { return Math.Abs(a - b) <= 1; }
        });
}

Использование

List<List<Int32>> numberSequences = new List<List<Int32>>
{
    new List<Int32> { 1 },
    new List<Int32> { 1, 2 },
    new List<Int32> { 1, 3 },
    new List<Int32> { 1, 2, 3 },
    new List<Int32> { 1, 5, 3 },
    new List<Int32> { 1, 2, 4, 5 },
    new List<Int32> { 1, 2, 3, 4, 10 }, 
    new List<Int32> { -5, 1, 2, 3, 4}, 
    new List<Int32> { 1, 2, 3, 4, 7, 11, 12, 13}, 
    new List<Int32> { 1, 2, 1 }, // fails because it is unoredered
    new List<Int32> { 1, 1, 2 } // works
};

foreach (var sequence in numberSequences)
{
    Console.WriteLine("{0} : {1}",
        String.Join(",", sequence),
        String.Join(",",
            sequence
                .CompactOrderedRanges(3)));
}

ПРОФИ

  1. Это довольно общий.
  2. У этого есть интерфейс, совместимый с LINQ, поэтому его можно легко переплетать в другие сценарии.
  3. Он не использует никаких дополнительных методов Find (IndexOf) и, в основном, затрагивает все элементы последовательно и в худшем случае два раза.

CONS

  1. Для этого требуется упорядочивание последовательности (этого можно избежать, добавив дополнительный параметр делегата-компаратора и проверив «направление» близости объектов друг к другу).
ответил Eugene Podskal 7 Maypm15 2015, 22:37:52
2

Несколько замечаний о вашем коде;

Нейминг:

Имена, подобные b или cv не означает много, не вам и не другим. Используйте значащие имена для ваших переменных.

Ключевое слово var:

В руководстве по программированию на C #

  

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

Итак, строки вроде:

int count = 0;

станет:

var count = 0;

Реализация:

Ваша реализация не плоха, и это не те из других решений. Хотя мне не нравится слишком много методов LinQ, создавая отдельные классы или несколько циклов для чего-то довольно простого, как эта «проблема».

Я реализовал решение, отличное от LinQ, которое требует только один цикл над коллекцией, используя Метод IENumerable.GetEnumerator () .

Логика выглядит следующим образом:

  1. Получить счетчик
  2. Петля над коллекцией
  3. Рассчитать разницу между предыдущим и текущим
    • если он равен 1, он последователен
    • если нет, добавьте правильный формат в строку
  4. В конце, если count больше 1, добавьте последний номер к выходу

Объяснение немного простое, но код достаточно ясный нормально :) Во всяком случае, здесь идет:

public static string CompactNumberRange(IEnumerable<int> range)
{
    var sorted = range.OrderBy(x => x);
    var output = new StringBuilder();

    using (var enumerator = sorted.GetEnumerator())
    {
        if (!enumerator.MoveNext())
            return "";

        var current = enumerator.Current;
        var count = 1;

        output.Append(current);

        while (enumerator.MoveNext())
        {
            var previous = current;
            current = enumerator.Current;

            if (current - previous == 1)
            {
                count++;
            }
            else
            {
                var format = count >= 3 ? "-{0}, {1}" : ", {0}, {1}, ";
                output.AppendFormat(format, previous, current);
                count = 1;
            }
        }

        if (count > 1)
            output.Append(current);
    }

    return output.ToString();
}
ответил Abbas 7 Maypm15 2015, 23:18:45

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132