加入算法字符串数组
我想知道有一段时间了，连接字符串数组的一种不错的，干净的解决方案会是什么样子。
示例：我有[" Alpha"，" Beta"，" Gamma"]，并希望将字符串连接成一个，并用逗号" Alpha，Beta，Gamma"分隔。
现在我知道大多数编程语言都为此提供了某种联接方法。我只是想知道如何实现这些目标。
当我参加入门课程时，我经常尝试单独学习，但从未找到令人满意的算法。一切似乎都很混乱，问题在于我们不能只遍历数组，将字符串连接起来，因为我们会添加太多逗号(在最后一个字符串之前或者之后)。
我不想检查循环中的条件。我真的不想在循环之前/之后添加第一个或者最后一个字符串(我想这可能是最好的方法？)。
有人可以向我展示一个优雅的解决方案吗？还是确切地告诉我为什么没有什么更优雅？
解决方案
回答
我为此类问题找到的最优雅的解决方案是这样的(用伪代码)
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 = ", ";
}
之所以有效，是因为在第一遍中，分隔符为空(因此一开始不会出现逗号，但是在随后的每一遍中，都需要在添加下一个元素之前添加一个逗号。
我们当然可以稍微展开一下以使其更快一些(一次又一次地分配给分隔符是不理想的)，尽管我怀疑编译器会自动为我们执行此操作。
最后，我很怀疑这是大多数语言级别的连接函数所要遵循的。只不过是语法糖，但它肯定是甜蜜的。
回答
为了获得纯正的优雅，典型的递归功能语言解决方案非常不错。这不是实际的语言语法，但我们可以理解(使用硬分隔符也已对其进行硬编码)：
join([])=""
join([x])=" x"
join([x，rest])=" x，" + join(休息)
实际上，我们将以更通用的方式编写此代码，以重用相同的算法，但抽象出数据类型(不必是字符串)和操作(不必在中间用逗号串联) 。然后通常将其称为``减少''，并且许多功能语言都内置了这种功能，例如在Lisp中将列表中的所有数字相乘：
(减少＃'*'(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
回答
以下内容不再与语言无关(但是对于讨论而言，这无关紧要，因为该实现很容易移植到其他语言中)。我试图用命令式编程语言实现Luke的(在理论上最好的)解决方案。随便你吧；我的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中，我只使用join命令：
$ 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(由Jon Ericson提及)，php，javascript具有join()函数或者方法，这是迄今为止最优雅的解决方案。更少的代码就是更好的代码。
作为对Mendelt Siebenga的回应，如果我们确实需要手动解决方案，那么我将与三元运算符一起执行以下操作：
separator = ","
foreach (item in stringCollection)
{
concatenatedString += concatenatedString ? separator + item : item
}
回答
@孟德尔·西本加(Mendelt Siebenga)
字符串是编程语言中的基石对象。不同的语言实现字符串的方式有所不同。 join()的实现很大程度上取决于字符串的基础实现。伪代码不能反映基础实现。
考虑Python中的join()。它可以很容易地使用：
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
这里是如何在C中实现" join()"方法的方法(取自主干)：
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. */
for each item in sequence
copy-assign item
if not last item
copy-assign separator
回答
Ruby中的join()函数：
def join(seq, sep)
seq.inject { |total, item| total << sep << item } or ""
end
join(["a", "b", "c"], ", ")
# => "a, b, c"
回答
Perl中的join()：
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"));
}
}
回答
我用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"))
我曾尝试对问题采用分而治之的策略，但我想这不会带来比普通迭代更好的结果。请让我知道是否可以做得更好。
我还对通过算法获得的递归进行了分析，可在此处获得。
回答
收集不同的语言实现？
为了娱乐，以下是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进行的额外工作实际上可能适得其反，具体取决于实现和与语言相关的字符串数量。
回答
在C＃中使用String.join方法
http://msdn.microsoft.com/zh-CN/library/57a79xd0.aspx
