Задача Эрика Липперта "запятая", лучший ответ? - PullRequest
23 голосов
/ 25 апреля 2009

Я хотел довести эту проблему до сведения сообщества stackoverflow. Исходная проблема и ответы: здесь . Кстати, если вы не следили за этим раньше, вы должны попытаться прочитать блог Эрика, это чистая мудрость.

Резюме:

Напишите функцию, которая принимает ненулевое значение IEnumerable и возвращает строку со следующими характеристиками:

  1. Если последовательность пуста, в результате получается строка "{}".
  2. Если последовательность представляет собой один элемент «ABC», тогда полученная строка будет «{ABC}».
  3. Если последовательность представляет собой последовательность из двух элементов «ABC», «DEF», то полученная строка будет «{ABC and DEF}».
  4. Если последовательность содержит более двух элементов, скажем, «ABC», «DEF», «G», «H», то полученная строка будет «{ABC, DEF, G и H}». (Примечание: запятая не оксфордская!)

Как вы можете видеть, даже наш собственный Джон Скит (да, хорошо известно, что он может быть в двух местах одновременно ) опубликовал решение, но его (ИМХО) нет самый элегантный, хотя, вероятно, вы не можете побить его производительность.

Что ты думаешь? Там есть довольно хорошие варианты. Мне действительно нравится одно из решений, которое включает методы выбора и агрегирования (от Фернандо Николе). Linq очень силен и посвящает некоторое время таким вызовам, чтобы вы многому научились. Я немного изменил его, чтобы он был более производительным и понятным (используя Count и избегая Reverse):

public static string CommaQuibbling(IEnumerable<string> items)
{
    int last = items.Count() - 1;
    Func<int, string> getSeparator = (i) => i == 0 ? string.Empty : (i == last ? " and " : ", ");
    string answer = string.Empty;

    return "{" + items.Select((s, i) => new { Index = i, Value = s })
                      .Aggregate(answer, (s, a) => s + getSeparator(a.Index) + a.Value) + "}";
}

Ответы [ 25 ]

33 голосов
/ 25 апреля 2009

Неэффективно, но я думаю, ясно.

public static string CommaQuibbling(IEnumerable<string> items)
{
    List<String> list = new List<String>(items);
    if (list.Count == 0) { return "{}"; }
    if (list.Count == 1) { return "{" + list[0] + "}"; }

    String[] initial = list.GetRange(0, list.Count - 1).ToArray();
    return "{" + String.Join(", ", initial) + " and " + list[list.Count - 1] + "}";
}

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

28 голосов
/ 25 апреля 2009

Как насчет этого подхода? Чисто кумулятивно - без отслеживания и повторяется только один раз. Что касается производительности, я не уверен, что вы будете лучше работать с LINQ и т. Д., Независимо от того, насколько «симпатичным» может быть ответ LINQ.

using System;
using System.Collections.Generic;
using System.Text;

static class Program
{
    public static string CommaQuibbling(IEnumerable<string> items)
    {
        StringBuilder sb = new StringBuilder('{');
        using (var iter = items.GetEnumerator())
        {
            if (iter.MoveNext())
            { // first item can be appended directly
                sb.Append(iter.Current);
                if (iter.MoveNext())
                { // more than one; only add each
                  // term when we know there is another
                    string lastItem = iter.Current;
                    while (iter.MoveNext())
                    { // middle term; use ", "
                        sb.Append(", ").Append(lastItem);
                        lastItem = iter.Current;
                    }
                    // add the final term; since we are on at least the
                    // second term, always use " and "
                    sb.Append(" and ").Append(lastItem);
                }
            }
        }
        return sb.Append('}').ToString();
    }
    static void Main()
    {
        Console.WriteLine(CommaQuibbling(new string[] { }));
        Console.WriteLine(CommaQuibbling(new string[] { "ABC" }));
        Console.WriteLine(CommaQuibbling(new string[] { "ABC", "DEF" }));
        Console.WriteLine(CommaQuibbling(new string[] {
             "ABC", "DEF", "G", "H" }));
    }
}
5 голосов
/ 25 апреля 2009

Если бы я много делал с потоками, которым требовалась первая / последняя информация, у меня было бы расширение thid:

[Flags]
public enum StreamPosition
{
   First = 1, Last = 2
}

public static IEnumerable<R> MapWithPositions<T, R> (this IEnumerable<T> stream, 
    Func<StreamPosition, T, R> map)
{
    using (var enumerator = stream.GetEnumerator ())
    {
        if (!enumerator.MoveNext ()) yield break ;

        var cur   = enumerator.Current   ;
        var flags = StreamPosition.First ;
        while (true)
        {
            if (!enumerator.MoveNext ()) flags |= StreamPosition.Last ;
            yield return map (flags, cur) ;
            if ((flags & StreamPosition.Last) != 0) yield break ;
            cur   = enumerator.Current ;
            flags = 0 ;
        }
    }
}

Тогда самое простое (не самое быстрое, которое потребует еще несколько удобных методов расширения) будет:

public static string Quibble (IEnumerable<string> strings)
{
    return "{" + String.Join ("", strings.MapWithPositions ((pos, item) => (
       (pos &  StreamPosition.First) != 0      ? "" : 
        pos == StreamPosition.Last   ? " and " : ", ") + item)) + "}" ;
}
3 голосов
/ 12 октября 2009

Здесь как Python один вкладыш


>>> f=lambda s:"{%s}"%", ".join(s)[::-1].replace(',','dna ',1)[::-1]
>>> f([])
'{}'
>>> f(["ABC"])
'{ABC}'
>>> f(["ABC","DEF"])
'{ABC and DEF}'
>>> f(["ABC","DEF","G","H"])
'{ABC, DEF, G and H}'

Эта версия может быть проще для понимания


>>> f=lambda s:"{%s}"%" and ".join(s).replace(' and',',',len(s)-2)
>>> f([])
'{}'
>>> f(["ABC"])
'{ABC}'
>>> f(["ABC","DEF"])
'{ABC and DEF}'
>>> f(["ABC","DEF","G","H"])
'{ABC, DEF, G and H}'
2 голосов
/ 09 октября 2009

Другой вариант - разделение знаков препинания и итераций для ясности кода. И все еще думаю о производительности.

Работает в соответствии с запросом чистого IEnumerable / string /, и строки в списке не могут быть нулевыми.

public static string Concat(IEnumerable<string> strings)
{
    return "{" + strings.reduce("", (acc, prev, cur, next) => 
               acc.Append(punctuation(prev, cur, next)).Append(cur)) + "}";
}
private static string punctuation(string prev, string cur, string next)
{
    if (null == prev || null == cur)
        return "";
    if (null == next)
        return " and ";
    return ", ";
}

private static string reduce(this IEnumerable<string> strings, 
    string acc, Func<StringBuilder, string, string, string, StringBuilder> func)
{
    if (null == strings) return "";

    var accumulatorBuilder = new StringBuilder(acc);
    string cur = null;
    string prev = null;
    foreach (var next in strings)
    {
        func(accumulatorBuilder, prev, cur, next);
        prev = cur;
        cur = next;
    }
    func(accumulatorBuilder, prev, cur, null);

    return accumulatorBuilder.ToString();
}

F # наверняка выглядит намного лучше:

let rec reduce list =
    match list with
    | []          -> ""
    | head::curr::[]  -> head + " and " + curr
    | head::curr::tail  -> head + ", " + curr :: tail |> reduce
    | head::[] -> head

let concat list = "{" + (list |> reduce )  + "}"
2 голосов
/ 23 мая 2009

Это не очень хорошо читается, но хорошо масштабируется до десятков миллионов строк. Я работаю на старой рабочей станции Pentium 4, и она выполняет 1 000 000 строк средней длины 8 примерно за 350 мс.

public static string CreateLippertString(IEnumerable<string> strings)
{
    char[] combinedString;
    char[] commaSeparator = new char[] { ',', ' ' };
    char[] andSeparator = new char[] { ' ', 'A', 'N', 'D', ' ' };

    int totalLength = 2;  //'{' and '}'
    int numEntries = 0;
    int currentEntry = 0;
    int currentPosition = 0;
    int secondToLast;
    int last;
    int commaLength= commaSeparator.Length;
    int andLength = andSeparator.Length;
    int cbComma = commaLength * sizeof(char);
    int cbAnd = andLength * sizeof(char);

    //calculate the sum of the lengths of the strings
    foreach (string s in strings)
    {
        totalLength += s.Length;
        ++numEntries;
    }

    //add to the total length the length of the constant characters
    if (numEntries >= 2)
        totalLength += 5;  // " AND "

    if (numEntries > 2)
        totalLength += (2 * (numEntries - 2)); // ", " between items

    //setup some meta-variables to help later
    secondToLast = numEntries - 2;
    last = numEntries - 1;

    //allocate the memory for the combined string
    combinedString = new char[totalLength];
    //set the first character to {
    combinedString[0] = '{';
    currentPosition = 1;

    if (numEntries > 0)
    {
        //now copy each string into its place
        foreach (string s in strings)
        {
            Buffer.BlockCopy(s.ToCharArray(), 0, combinedString, currentPosition * sizeof(char), s.Length * sizeof(char));
            currentPosition += s.Length;

            if (currentEntry == secondToLast)
            {
                Buffer.BlockCopy(andSeparator, 0, combinedString, currentPosition * sizeof(char), cbAnd);
                currentPosition += andLength;
            }
            else if (currentEntry == last)
            {
                combinedString[currentPosition] = '}'; //set the last character to '}'
                break;  //don't bother making that last call to the enumerator
            }
            else if (currentEntry < secondToLast)
            {
                Buffer.BlockCopy(commaSeparator, 0, combinedString, currentPosition * sizeof(char), cbComma);
                currentPosition += commaLength;
            }

            ++currentEntry;
        }
    }
    else
    {
        //set the last character to '}'
        combinedString[1] = '}';
    }

    return new string(combinedString);
}
2 голосов
/ 02 мая 2009

Я фанат серийной запятой: я ем, стреляю и ухожу.

Мне постоянно нужно решение этой проблемы, и я решил его на 3 языках (но не на C #). Я бы адаптировал следующее решение (в Lua , не заключает ответ в фигурные скобки), написав метод concat, который работает на любом IEnumerable:

function commafy(t, andword)
  andword = andword or 'and'
  local n = #t -- number of elements in the numeration
  if n == 1 then
    return t[1]
  elseif n == 2 then
    return concat { t[1], ' ', andword, ' ', t[2] }
  else
    local last = t[n]
    t[n] = andword .. ' ' .. t[n]
    local answer = concat(t, ', ')
    t[n] = last
    return answer
  end
end
2 голосов
/ 25 апреля 2009

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

Наивное решение для перечисления (Я признаю, что вариант foreach лучше, так как он не требует ручного перебора с перечислителем.)

public static string NaiveConcatenate(IEnumerable<string> sequence)
{
    StringBuilder sb = new StringBuilder();
    sb.Append('{');

    IEnumerator<string> enumerator = sequence.GetEnumerator();

    if (enumerator.MoveNext())
    {
        string a = enumerator.Current;
        if (!enumerator.MoveNext())
        {
            sb.Append(a);
        }
        else
        {
            string b = enumerator.Current;
            while (enumerator.MoveNext())
            {
                sb.Append(a);
                sb.Append(", ");
                a = b;
                b = enumerator.Current;
            }
            sb.AppendFormat("{0} and {1}", a, b);
        }
    }

    sb.Append('}');
    return sb.ToString();
}

Решение с использованием LINQ

public static string ConcatenateWithLinq(IEnumerable<string> sequence)
{
    return (from item in sequence select item)
        .Aggregate(
        new {sb = new StringBuilder("{"), a = (string) null, b = (string) null},
        (s, x) =>
            {
                if (s.a != null)
                {
                    s.sb.Append(s.a);
                    s.sb.Append(", ");
                }
                return new {s.sb, a = s.b, b = x};
            },
        (s) =>
            {
                if (s.b != null)
                    if (s.a != null)
                        s.sb.AppendFormat("{0} and {1}", s.a, s.b);
                    else
                        s.sb.Append(s.b);
                s.sb.Append("}");
                return s.sb.ToString();
            });
}

Решение с TPL

Это решение использует очередь производителя-потребителя для передачи входной последовательности процессору, сохраняя в очереди по крайней мере два элемента в буфере. Как только производитель достиг конца входной последовательности, последние два элемента могут быть обработаны с особой обработкой.

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

public static string ConcatenateWithTpl(IEnumerable<string> sequence)
{
    var queue = new ConcurrentQueue<string>();
    bool stop = false;

    var consumer = Future.Create(
        () =>
            {
                var sb = new StringBuilder("{");
                while (!stop || queue.Count > 2)
                {
                    string s;
                    if (queue.Count > 2 && queue.TryDequeue(out s))
                        sb.AppendFormat("{0}, ", s);
                }
                return sb;
            });

    // Producer
    foreach (var item in sequence)
        queue.Enqueue(item);

    stop = true;
    StringBuilder result = consumer.Value;

    string a;
    string b;

    if (queue.TryDequeue(out a))
        if (queue.TryDequeue(out b))
            result.AppendFormat("{0} and {1}", a, b);
        else
            result.Append(a);

    result.Append("}");
    return result.ToString();
}

Юнит тесты для краткости.

2 голосов
/ 23 марта 2010

Поздняя запись:

public static string CommaQuibbling(IEnumerable<string> items)
{
    string[] parts = items.ToArray();
    StringBuilder result = new StringBuilder('{');
    for (int i = 0; i < parts.Length; i++)
    {
        if (i > 0)
            result.Append(i == parts.Length - 1 ? " and " : ", ");
        result.Append(parts[i]);
    }
    return result.Append('}').ToString();
}
2 голосов
/ 25 апреля 2009

Вот простое решение F #, которое выполняет только одну прямую итерацию:

let CommaQuibble items =
    let sb = System.Text.StringBuilder("{")
    // pp is 2 previous, p is previous
    let pp,p = items |> Seq.fold (fun (pp:string option,p) s -> 
        if pp <> None then
            sb.Append(pp.Value).Append(", ") |> ignore
        (p, Some(s))) (None,None)
    if pp <> None then
        sb.Append(pp.Value).Append(" and ") |> ignore
    if p <> None then
        sb.Append(p.Value) |> ignore
    sb.Append("}").ToString()

(РЕДАКТИРОВАТЬ: Оказывается, это очень похоже на Skeet's.)

Тестовый код:

let Test l =
    printfn "%s" (CommaQuibble l)

Test []
Test ["ABC"]        
Test ["ABC";"DEF"]        
Test ["ABC";"DEF";"G"]        
Test ["ABC";"DEF";"G";"H"]        
Test ["ABC";null;"G";"H"]        
...