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

Я некоторое время задавался вопросом, какое красивое, чистое решение для объединения массива строк могло бы выглядеть. Пример: у меня есть [ "Альфа", "Бета", "Гамма" ] и хочу присоединить строки к одному, разделенные запятыми - "Альфа, Бета, Гамма".

Теперь я знаю, что большинство языков программирования предлагают для этого какой-то метод соединения. Мне просто интересно, как они могут быть реализованы. Когда я проходил вводные курсы, я часто старался идти в одиночку, но так и не нашел удовлетворительного алгоритма. Все казалось довольно запутанным, проблема в том, что вы не можете просто перебирать массив, объединяя строки, так как вы добавляете слишком много запятых (до или после последней строки). Я не хочу проверять условия в цикле. Я действительно не хочу добавлять первую или последнюю строку до/после цикла (думаю, это лучший способ?).

Может ли кто-нибудь показать мне элегантное решение? Или скажите мне, почему не может быть что-то более элегантное?

Ответы

Ответ 1

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

Ответ 4

Я обычно хожу с чем-то вроде...

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

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

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

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

Ответ 5

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

join ([]) = ""

join ([x]) = "x"

join ([x, rest]) = "x," + join (rest)

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

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

Ответ 6

@Mendelt Siebenga

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

Рассмотрим 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 (взято из trunk):

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

Ответ 7

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

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

Ответ 8

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

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

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

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

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

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

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

Ответ 9

сбор различных языковых реализаций?
Вот, для вашего развлечения, версия 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 (или то, что называется "WriteStream" в Smalltalk) настоятельно рекомендуется. Не объединяйте строки, используя "+" в цикле - результат будет много много промежуточных строк выброса. Если у вас есть хороший сборщик мусора, все в порядке. Но некоторые из них не нужны, и требуется большая память. StringBuilder (и WriteStream, который является его grand-grand-father) использует алгоритм удвоения буфера или даже адаптивного роста, для которого требуется МНОЖЕ меньше нуля памяти.

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

Ответ 10

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

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

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

Ответ 11

join() в Ruby:

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

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

Ответ 12

join() в Perl:

use List::Util qw(reduce);

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

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

Или без reduce:

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

Ответ 13

Perl 6

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

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

Ответ 14

В Java 5 с unit test:

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

Ответ 15

Я написал рекурсивную версию решения в lisp. Если длина списка больше, чем 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"))

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

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