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

Question

Некоторое время я задавался вопросом, как может выглядеть хорошее, чистое решение для объединения массива строк. Пример: у меня есть ["Alpha", "Beta", "Gamma"] и я хочу объединить строки в одну, разделенную запятыми - "Alpha, Beta, Gamma".

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

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

Answer 1

Я написал рекурсивную версию решения на 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"))

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

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

Answer 2

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

Answer 3

Perl 6

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

Следующее больше не зависит от языка (но это не имеет значения для обсуждения, поскольку реализация легко переносима на другие языки). Я попытался реализовать решение Луки (по тем временам лучшее) на императивном языке программирования. Сделайте ваш выбор; мой 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();
}