Алгоритм присоединения, например, массив строк

Самое элегантное решение, которое я нашел для подобных проблем, - это что-то вроде этого (в псевдокоде)

separator = ""
foreach(item in stringCollection)
{
    concatenatedString += separator + item
    separator = ","
}

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

Я обычно использую что-то вроде ...

list = ["Alpha", "Beta", "Gamma"];
output = "";
separator = "";
for (int i = 0; i < list.length ; i++) {
  output = output + separator;
  output = output + list[i];
  separator = ", ";
}

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

Конечно, вы могли бы немного развернуть это, чтобы сделать его немного быстрее (назначение разделителю снова и снова не идеально), хотя я подозреваю, что компилятор мог бы сделать это за вас автоматически.

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

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

присоединиться ([]) = ""

присоединиться ([x]) = "x"

join ([x, rest]) = "x," + join (отдых)

На самом деле вы бы написали это более общим способом, чтобы повторно использовать тот же алгоритм, но абстрагироваться от типа данных (не обязательно строк) и операции (не обязательно конкатенации с запятой посередине) . Затем его обычно называют `` уменьшить '', и многие функциональные языки имеют это встроенное, например умножение всех чисел в списке в Лиспе:

(уменьшить # '*' (1 2 3 4 5)) => 120

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

public static string join(String[] strings, String sep) {
  if (strings.length == 0) return "";
  if (strings.length == 1) return strings[0];
  StringBuilder sb = new StringBuilder();
  sb.append(strings[0]);
  for(int i = 1; i < strings.length; i++) {
    sb.append(sep);
    sb.append(strings[i]);
  }
  return sb.toString();
}

Обновлено: Я полагаю, я должен упомянуть, почему это будет быстрее. Основная причина в том, что каждый раз, когда вы вызываете c = a + b; базовая конструкция обычно c = (new StringBuilder ()). append (a) .append (b) .toString () ;. Повторно используя один и тот же объект построителя строк, мы можем уменьшить количество выделяемых ресурсов и мусора, который мы производим.

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

'Псевдокод Предположим, что на основе нуля

ResultString = InputArray[0]
n = 1
while n (is less than)  Number_Of_Strings
    ResultString (concatenate) ", "
    ResultString (concatenate) InputArray[n]
    n = n + 1
loop

Следующее больше не зависит от языка (но это не имеет значения для обсуждения, потому что реализация легко переносится на другие языки). Я попытался реализовать решение Люка (теоретически лучшее) на императивном языке программирования. Сделайте ваш выбор; мой C#. Совсем не очень элегантно. Однако (без какого-либо тестирования) я мог представить, что его производительность вполне приличная, потому что рекурсия на самом деле является хвостовой рекурсией.

Моя задача: дать лучшую рекурсивную реализацию (на императивном языке). Вы говорите, что «лучше» означает: меньше кода, быстрее, я открыт для предложений.

private static StringBuilder RecJoin(IEnumerator<string> xs, string sep, StringBuilder result) {
    result.Append(xs.Current);
    if (xs.MoveNext()) {
        result.Append(sep);
        return RecJoin(xs, sep, result);
    } else
        return result;
}

public static string Join(this IEnumerable<string> xs, string separator) {
    var i = xs.GetEnumerator();
    if (!i.MoveNext())
        return string.Empty;
    else
        return RecJoin(i, separator, new StringBuilder()).ToString();
}

В Perl я просто использую команду присоединиться:

$ echo "Alpha
Beta
Gamma" | perl -e 'print(join(", ", map {chomp; $_} <> ))'
Alpha, Beta, Gamma

(Материал карта в основном используется для создания списка.)

В языках, у которых нет встроенного, например C, я использую простую итерацию (непроверенную):

for (i = 0; i < N-1; i++){
    strcat(s, a[i]);
    strcat(s, ", ");
}
strcat(s, a[N]);

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

Вы должны либо особый случай первая запись, либо последний.

Большинство языков в настоящее время - например, perl (упоминается Джоном Эриксоном), php, javascript - имеют функцию или метод join (), и это, безусловно, самое элегантное решение. Чем меньше кода, тем лучше.

В ответ Мендельту Зибенге, если вам действительно требуется ручное решение, я бы выбрал тернарный оператор для чего-то вроде:

separator = ","
foreach (item in stringCollection)
{
    concatenatedString += concatenatedString ? separator + item : item
}

@Mendelt Siebenga

Строки - это краеугольный камень языков программирования. В разных языках строки реализуются по-разному. Реализация join() сильно зависит от базовой реализации строк. Псевдокод не отражает базовую реализацию.

Рассмотрим join() в Python. Его легко использовать:

print ", ".join(["Alpha", "Beta", "Gamma"])
# Alpha, Beta, Gamma

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

def join(seq, sep = " "):
    if not seq:         return ""
    elif len(seq) == 1: return seq[0]
    return reduce(lambda x, y: x + sep + y, seq)

print join(["Alpha", "Beta", "Gamma"], ", ")
# Alpha, Beta, Gamma

А вот как реализован метод join() на C (взято из хобот):

PyDoc_STRVAR(join__doc__,
"S.join(sequence) -> string\n\
\n\
Return a string which is the concatenation of the strings in the\n\
sequence.  The separator between elements is S.");

static PyObject *
string_join(PyStringObject *self, PyObject *orig)
{
    char *sep = PyString_AS_STRING(self);
    const Py_ssize_t seplen = PyString_GET_SIZE(self);
    PyObject *res = NULL;
    char *p;
    Py_ssize_t seqlen = 0;
    size_t sz = 0;
    Py_ssize_t i;
    PyObject *seq, *item;

    seq = PySequence_Fast(orig, "");
    if (seq == NULL) {
        return NULL;
    }

    seqlen = PySequence_Size(seq);
    if (seqlen == 0) {
        Py_DECREF(seq);
        return PyString_FromString("");
    }
    if (seqlen == 1) {
        item = PySequence_Fast_GET_ITEM(seq, 0);
        if (PyString_CheckExact(item) || PyUnicode_CheckExact(item)) {
            Py_INCREF(item);
            Py_DECREF(seq);
            return item;
        }
    }

    /* There are at least two things to join, or else we have a subclass
     * of the builtin types in the sequence.
     * Do a pre-pass to figure out the total amount of space we'll
     * need (sz), see whether any argument is absurd, and defer to
     * the Unicode join if appropriate.
     */
    for (i = 0; i < seqlen; i++) {
        const size_t old_sz = sz;
        item = PySequence_Fast_GET_ITEM(seq, i);
        if (!PyString_Check(item)){
#ifdef Py_USING_UNICODE
            if (PyUnicode_Check(item)) {
                /* Defer to Unicode join.
                 * CAUTION:  There's no gurantee that the
                 * original sequence can be iterated over
                 * again, so we must pass seq here.
                 */
                PyObject *result;
                result = PyUnicode_Join((PyObject *)self, seq);
                Py_DECREF(seq);
                return result;
            }
#endif
            PyErr_Format(PyExc_TypeError,
                     "sequence item %zd: expected string,"
                     " %.80s found",
                     i, Py_TYPE(item)->tp_name);
            Py_DECREF(seq);
            return NULL;
        }
        sz += PyString_GET_SIZE(item);
        if (i != 0)
            sz += seplen;
        if (sz < old_sz || sz > PY_SSIZE_T_MAX) {
            PyErr_SetString(PyExc_OverflowError,
                "join() result is too long for a Python string");
            Py_DECREF(seq);
            return NULL;
        }
    }

    /* Allocate result space. */
    res = PyString_FromStringAndSize((char*)NULL, sz);
    if (res == NULL) {
        Py_DECREF(seq);
        return NULL;
    }

    /* Catenate everything. */
    p = PyString_AS_STRING(res);
    for (i = 0; i < seqlen; ++i) {
        size_t n;
        item = PySequence_Fast_GET_ITEM(seq, i);
        n = PyString_GET_SIZE(item);
        Py_MEMCPY(p, PyString_AS_STRING(item), n);
        p += n;
        if (i < seqlen - 1) {
            Py_MEMCPY(p, sep, seplen);
            p += seplen;
        }
    }

    Py_DECREF(seq);
    return res;
}

Обратите внимание, что приведенный выше код Catenate everything. является небольшой частью всей функции.

В псевдокоде:

/* Catenate everything. */
for each item in sequence
    copy-assign item
    if not last item
        copy-assign separator

Функция join() в Ruby:

def join(seq, sep) 
  seq.inject { |total, item| total << sep << item } or "" 
end

join(["a", "b", "c"], ", ")
# => "a, b, c"

join() на Perl:

use List::Util qw(reduce);

sub mjoin($@) {$sep = shift; reduce {$a.$sep.$b} @_ or ''}

say mjoin(', ', qw(Alpha Beta Gamma));
# Alpha, Beta, Gamma

Или без reduce:

 sub mjoin($@) 
 {
   my ($sep, $sum) = (shift, shift); 
   $sum .= $sep.$_ for (@_); 
   $sum or ''
 }

Perl 6

sub join( $separator, @strings ){
  my $return = shift @strings;
  for @strings -> ( $string ){
    $return ~= $separator ~ $string;
  }
  return $return;
}

Да, я знаю, что это бессмысленно, потому что в Perl 6 уже есть функция соединения.

В Java 5 с модульным тестом:

import junit.framework.Assert;
import org.junit.Test;

public class StringUtil
{
    public static String join(String delim, String... strings)
    {
        StringBuilder builder = new StringBuilder();

        if (strings != null)
        {
            for (String str : strings)
            {
                if (builder.length() > 0)
                {
                    builder.append(delim);
                }

                builder.append(str);
            }
        }           

        return builder.toString();
    }

    @Test
    public void joinTest()
    {
        Assert.assertEquals("", StringUtil.join(", ", null));
        Assert.assertEquals("", StringUtil.join(", ", ""));
        Assert.assertEquals("", StringUtil.join(", ", new String[0]));
        Assert.assertEquals("test", StringUtil.join(", ", "test"));
        Assert.assertEquals("foo, bar", StringUtil.join(", ", "foo", "bar"));
        Assert.assertEquals("foo, bar, baz", StringUtil.join(", ", "foo", "bar", "baz"));
    }
}

Я написал рекурсивную версию решения на лиспе. Если длина списка больше 2, он как можно лучше разбивает список пополам, а затем пытается объединить подсписки.

    (defun concatenate-string(list)
       (cond ((= (length list) 1) (car list))
             ((= (length list) 2) (concatenate 'string (first list) "," (second list)))
             (t (let ((mid-point (floor (/ (- (length list) 1) 2))))
                   (concatenate 'string 
                                (concatenate-string (subseq list 0 mid-point))
                                ","
                                (concatenate-string (subseq list mid-point (length list))))))))



    (concatenate-string '("a" "b"))

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

Я также провел анализ рекурсии, полученной алгоритмом, он доступен здесь.

собираете разные языковые реализации?
Вот, для вашего развлечения, версия Smalltalk:

join:collectionOfStrings separatedBy:sep

  |buffer|

  buffer := WriteStream on:''.
  collectionOfStrings 
      do:[:each | buffer nextPutAll:each ]
      separatedBy:[ buffer nextPutAll:sep ].
  ^ buffer contents.

Конечно, приведенный выше код уже есть в стандартной библиотеке:

Коллекция >> asStringWith:

поэтому, используя это, вы должны написать:

#('A' 'B' 'C') asStringWith:','

Но вот моя главная мысль:

Я хотел бы сделать больший акцент на том факте, что настоятельно рекомендуется использовать StringBuilder (или то, что в Smalltalk называется «WriteStream»). Не объединяйте строки с помощью «+» в цикле - в результате получится много промежуточных отбрасываемых строк. Если у вас есть хороший сборщик мусора, ничего страшного. Но некоторые из них - нет, и необходимо восстановить много памяти. StringBuilder (и WriteStream, который является его прадедом) используют алгоритм удвоения буфера или даже алгоритм адаптивного увеличения, для которого требуется МНОГО меньше оперативной памяти.

Однако, если вы объединяете всего несколько маленьких строк, не обращайте внимания и «+» их; дополнительная работа с использованием StringBuilder может оказаться контрпродуктивной, вплоть до количества строк, зависящего от реализации и языка.

Используйте метод String.join в C#

http://msdn.microsoft.com/en-us/library/57a79xd0.aspx