Eric Lippert的挑战：“逗号争论”，最佳答案是什么？

Question

我希望引起stackoverflow社区对这个挑战的关注。原始问题和答案在此处。顺便说一句，如果你以前没有关注过它，应该尝试阅读Eric的博客，那是纯粹的智慧。

总结：

编写一个函数，它接受一个非空的IEnumerable并返回一个具有以下特征的字符串：

1. 如果序列为空，则生成的字符串为“{}”。
2. 如果序列是单个项“ABC”，则生成的字符串为“{ABC}”。
3. 如果序列是两个项序列“ABC”，“DEF”，则生成的字符串为“{ABC and DEF}”。
4. 如果序列有多于两个项，比如“ABC”，“DEF”，“G”，“H”，则生成的字符串为“{ABC，DEF，G和H}”（注意：没有牛津逗号！）

正如你所看到的，即使我们自己的Jon Skeet（是的，众所周知他可以同时出现在两个地方）也发表了一个解决方案，但是他的（在我看来）不是最优雅的，尽管也许你无法击败它的性能。

你认为呢？有相当好的选择。我真的很喜欢其中一个涉及选择和聚合方法（来自Fernando Nicolet）的解决方案。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) + "}";
}

- MMind

---

请注意，使用Count而不是Reverse并不一定会提高性能：如果字符串集合没有实现ICollection接口，则Count将需要完全迭代它。 - LukeH

让我理解正确，这个问题不应该是要找出最佳的“LINQ”解决问题的方式，而不是使用枚举器的琐碎过程式方法吗？ - Akash Kava

原挑战的作者说：“我特别关注那些让代码维护者能够清晰理解代码语义的解决方案。” 在我看来，一些得票较高的解决方案违反了这一点。是的，它们很聪明，而且表现出色，但我觉得它们难以阅读。 - Thomas Eyde

看起来Jon Skeet的回答已经被删除了。找不到它。 - Luminous

Answer 1

虽然效率低，但我认为很清晰易懂。

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] + "}";
}

如果我在维护这段代码，我会更倾向于使用这个而不是更聪明的版本。

- dbkk

---

这个回答比上面的所有回答都好得多。我猜很少有 Stack Overflow 用户读 Eric 的博客——他强调一种易读的解决方案。这就是为什么这个回答是最好的原因。 - Paul Batum

在 .Net 4 中，你可以在倒数第二行中省略 .ToArray()，这样会使得程序更加高效。 - configurator

Answer 2

这种方法怎么样？完全是累加的方式 - 没有回溯，只迭代一次。就原始性能而言，我不确定使用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" }));
    }
}

- Marc Gravell

---

当你写下 "new StringBuilder().Append('{')" 这段代码时，你有什么特别的想法吗？这段代码已经被 Peter Wone 修改了。 - VVS

@Peter：是的……它不必解析格式字符串“，{0}”——这只是两个虚拟调用。在内部，解析将会做更多的工作，并且可能仍然调用完全相同的2个方法。 - Marc Gravell

这个问题不是关于性能，而是要理解 LINQ 的威力，以简单的方式编写复杂的算法。高性能的代码等价于更多的代码行数，更多的代码行数意味着编写和管理逻辑所需的时间更长。 - Akash Kava

请告诉我在哪里提到了LINQ作为必要条件？ - Marc Gravell

看起来很粗糙，像C语言一样，但我非常同意:) 但我仍然不喜欢嵌入的moveNexts..它看起来有一些依赖关系。如果我需要实际的原始速度，我仍会编写linq代码，但这是情况:) - luckyluke

Answer 3

如果我需要处理很多需要首/尾信息的流，我会使用这个扩展：

[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)) + "}" ;
}

- Anton Tykhyy

---

好主意。使解决方案变得非常简单。我想知道性能会如何。 - Daniel Fortunov

+1 优雅、简洁、清晰。这不是关于“漂亮”或“聪明”，而是关于目的的清晰和影响的广泛程度。 - Peter Wone

由于JIT在较新版本的.NET之前不会优化返回值类型的方法，因此上述更改应该具有更好的性能。 - Anton Tykhyy

Answer 4

这里是一个 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}'

- John La Rooy

Answer 5

迟到的输入：

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();
}

- Foole

Answer 6

另一种变体-为了代码清晰性而分离标点和迭代逻辑。同时考虑其性能。

与纯IEnumerable/string/和列表中的字符串不能为null的要求一样运作正常。

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 )  + "}"

- darkiri

Answer 7

这里有一个简单的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的非常相似。)

测试代码：

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"]        

- Brian

Answer 8

免责声明：我利用这个机会玩弄新技术，所以我的解决方案并没有真正达到Eric对于清晰和可维护性的要求。

天真枚举器解决方案（我承认，使用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();
}

为了简洁起见，单元测试被省略了。

- Daniel Fortunov

Answer 9

我是一个串联逗号的粉丝：我吃饭，射击，然后离开。

我不断需要解决这个问题，并已在三种语言中解决了它（但不包括C#）。我将通过编写适用于任何IEnumerable的concat方法来使以下解决方案（在Lua中，不要用花括号包装答案）得到改进。

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

- Norman Ramsey

Answer 10

虽然这段内容难以阅读，但是在涉及大量字符串的情况下，它具有良好的可扩展性。我正在一台旧的 Pentium 4 工作站上开发，处理平均长度为 8 的 1,000,000 个字符串需要约 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);
}

- Aaron Eshbach