Eric Lipperts Herausforderung "Kommaspielerei", beste Antwort?

Question

Ich wollte die Aufmerksamkeit der Stackoverflow-Community auf diese Herausforderung lenken. Das ursprüngliche Problem und die Antworten sind aquí . Übrigens, wenn Sie ihn bisher nicht verfolgt haben, sollten Sie versuchen, Erics Blog zu lesen, er ist pure Weisheit.

Zusammenfassung:

Schreiben Sie eine Funktion, die eine nicht-null IEnumerable annimmt und einen String mit den folgenden Eigenschaften zurückgibt:

1. Wenn die Sequenz leer ist, lautet die resultierende Zeichenfolge "{}".
2. Handelt es sich bei der Sequenz um ein einzelnes Element "ABC", lautet die resultierende Zeichenfolge "{ABC}".
3. Handelt es sich bei der Sequenz um die Zweierfolge "ABC", "DEF", so lautet die resultierende Zeichenfolge "{ABC und DEF}".
4. Wenn die Sequenz mehr als zwei Elemente enthält, z. B. "ABC", "DEF", "G", "H", dann ist die resultierende Zeichenfolge "{ABC, DEF, G und H}". (Hinweis: kein Oxford-Komma!)

Wie Sie sehen können, hat sogar unser eigener Jon Skeet (ja, es ist bekannt, dass er kann an zwei Orten gleichzeitig sein ) hat eine Lösung gepostet, aber seine (IMHO) ist nicht die eleganteste, obwohl ihre Leistung wahrscheinlich nicht zu schlagen ist.

Was meinen Sie dazu? Es gibt da ziemlich gute Möglichkeiten. Eine der Lösungen, die Select- und Aggregate-Methoden (von Fernando Nicolet) beinhaltet, gefällt mir sehr gut. Linq ist sehr leistungsfähig, und wenn man sich solchen Herausforderungen widmet, lernt man eine Menge. Ich habe es ein bisschen verdreht, damit es etwas leistungsfähiger und übersichtlicher ist (indem ich Count verwende und Reverse vermeide):

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

Answer 1

Hier ist eine einfache F#-Lösung, die nur eine Vorwärtsiteration durchführt:

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

(EDIT: Es hat sich herausgestellt, dass dies dem von Skeet sehr ähnlich ist.)

Der Testcode:

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

Answer 2

Verspäteter Eintritt:

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

Answer 3

Haftungsausschluss : Ich habe dies als Vorwand benutzt, um mit neuen Technologien herumzuspielen, so dass meine Lösungen den ursprünglichen Anforderungen von Eric an Klarheit und Wartbarkeit nicht wirklich gerecht werden.

Naive Enumerator-Lösung (Ich räume ein, dass die foreach Variante dieser Methode ist besser, da sie keine manuellen Eingriffe in den Enumerator erfordert).

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

Lösung mit 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();
            });
}

Lösung mit TPL

Bei dieser Lösung wird eine Producer-Consumer-Warteschlange verwendet, um die Eingabesequenz an den Prozessor weiterzuleiten, wobei mindestens zwei Elemente in der Warteschlange zwischengespeichert werden. Sobald der Producer das Ende der Eingabesequenz erreicht hat, können die letzten beiden Elemente mit einer Sonderbehandlung verarbeitet werden.

Im Nachhinein betrachtet gibt es keinen Grund, den Verbraucher asynchron arbeiten zu lassen, was die Notwendigkeit einer gleichzeitigen Warteschlange überflüssig machen würde, aber wie ich bereits sagte, habe ich dies nur als Vorwand benutzt, um mit neuen Technologien herumzuspielen :-)

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

Einheitstests wurden der Kürze halber weggelassen.

Answer 4

Das ist nicht besonders gut lesbar, aber es skaliert gut bis zu zig Millionen von Zeichenfolgen. Ich entwickle auf einer alten Pentium 4-Workstation und es schafft 1.000.000 Strings der durchschnittlichen Länge 8 in etwa 350 ms.

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

Answer 5

Eine andere Variante - die Trennung von Interpunktion und Iterationslogik im Interesse der Klarheit des Codes. Und ich denke immer noch über Perfomrance nach.

Funktioniert wie gewünscht mit reinen IEnumerable/string/ und Strings in der Liste können nicht null sein.

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# sieht sicherlich viel besser aus:

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