Algorithm for joining e.g. an array of strings
我想知道一段时间了，连接字符串数组的好方法是什么样子呢？
示例：我有[" Alpha"，" Beta"，" Gamma"]，并希望将字符串连接成一个，并用逗号分隔–" Alpha，Beta，Gamma"。
现在我知道大多数编程语言都为此提供了某种联接方法。 我只是想知道如何实现这些目标。
当我参加入门课程时，我经常尝试单独学习，但从未找到令人满意的算法。 一切似乎都很混乱，问题在于您不能只遍历数组，将字符串连接起来，因为您会添加太多逗号(在最后一个字符串之前或之后)。
我不想检查循环中的条件。 我真的不想在循环之前/之后添加第一个或最后一个字符串(我想这可能是最好的方法？)。
有人可以给我一个优雅的解决方案吗？ 还是确切地告诉我为什么没有什么更优雅？
我为此类问题找到的最优雅的解决方案是这样的(用伪代码)
1
2
3
4
5
6
| separator =""
foreach(item in stringCollection)
{
concatenatedString += separator + item
separator =","
} |
您只需运行循环，并且仅在第二次设置分隔符之后才运行循环。因此，第一次不会被添加。它不像我希望的那样干净，因此我仍然要添加注释，但是它比if语句或在循环外添加第一个或最后一个项目要好。
所有这些解决方案都是不错的解决方案，但是对于底层库而言，分隔符的独立性和不错的速度都非常重要。假设该语言具有某种形式的字符串生成器，则此功能可满足要求。
1
2
3
4
5
6
7
8
9
10
11
| 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();。通过重用相同的字符串生成器对象，我们可以减少分配的数量和产生的垃圾。
在有人以优化为罪恶之前，我们正在谈论实现通用库函数。可接受的，可扩展的性能是它们的要求之一。需要很长时间的联接将是不经常使用的联接。
当今大多数语言-例如perl(由Jon Ericson提及)，php，javascript-具有join()函数或方法，这是迄今为止最优雅的解决方案。更少的代码就是更好的代码。
作为对Mendelt Siebenga的回应，如果您确实需要手动解决方案，我将与三元运算符一起执行以下操作：
1
2
3
4
5
| separator =","
foreach (item in stringCollection)
{
concatenatedString += concatenatedString ? separator + item : item
} |
我通常会喜欢...
1
2
3
4
5
6
7
8
| 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
@孟德尔·西本加
字符串是编程语言中的基石对象。不同的语言实现字符串的方式有所不同。 join()的实现很大程度上取决于字符串的基础实现。伪代码不能反映基础实现。
考虑Python中的join()。它可以很容易地使用：
1
2
| print",".join(["Alpha","Beta","Gamma"])
# Alpha, Beta, Gamma |
它可以很容易地实现如下：
1
2
3
4
5
6
7
| 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()方法的方法(取自主干)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| PyDoc_STRVAR(join__doc__,
"S.join(sequence) -> string
\
\
Return a string which is the concatenation of the strings in the
\
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.代码只是整个函数的一小部分。
用伪代码：
1
2
3
4
5
| /* Catenate everything. */
for each item in sequence
copy-assign item
if not last item
copy-assign separator |
伪代码假定从零开始
1
2
3
4
5
6
7
| ResultString = InputArray[0]
n = 1
while n (is less than) Number_Of_Strings
ResultString (concatenate)","
ResultString (concatenate) InputArray[n]
n = n + 1
loop |
收集不同的语言实现？
为了您的娱乐，以下是Smalltalk版本：
1
2
3
4
5
6
7
8
9
| join:collectionOfStrings separatedBy:sep
|buffer|
buffer := WriteStream on:''.
collectionOfStrings
do:[:each | buffer nextPutAll:each ]
separatedBy:[ buffer nextPutAll:sep ].
^ buffer contents. |
当然，以上代码已经在标准库中找到：
集合>> asStringWith：
因此，使用该代码，您将编写：
1
| #('A' 'B' 'C') asStringWith:',' |
但这是我的主要观点：
我想更加强调以下事实：强烈建议使用StringBuilder(或在Smalltalk中称为" WriteStream")。不要在循环中使用" +"连接字符串-结果将是许多中间的一次性字符串。如果您有一个好的垃圾收集器，那就很好。但是，有些不是，因此需要回收大量内存。 StringBuilder(和WriteStream，它的曾祖父)使用缓冲区加倍甚至自适应增长算法，该算法需要更少的暂存内存。
但是，如果只连接几个小字符串，则不在乎，并用" +"表示；使用StringBuilder进行的额外工作实际上可能适得其反，最多取决于实现和语言的字符串数量。
在Perl中，我只使用join命令：
1
2
3
4
| $ echo"Alpha
Beta
Gamma" | perl -e 'print(join(",", map {chomp; $_} <> ))'
Alpha, Beta, Gamma |
(地图资料大部分用于创建列表。)
在没有内置语言的语言(如C)中，我使用简单的迭代(未经测试)：
1
2
3
4
5
| for (i = 0; i < N-1; i++){
strcat(s, a[i]);
strcat(s,",");
}
strcat(s, a[N]); |
当然，您需要先检查s的大小，然后再添加更多字节。
您需要特殊情况下的第一个条目或最后一个条目。
Ruby中的join()函数：
1
2
3
4
5
6
| def join(seq, sep)
seq.inject { |total, item| total << sep << item } or""
end
join(["a","b","c"],",")
# =>"a, b, c" |
在C＃中使用String.join方法
http://msdn.microsoft.com/en-us/library/57a79xd0.aspx
在Perl中join()：
1
2
3
4
5
6
| use List::Util qw(reduce);
sub mjoin($@) {$sep = shift; reduce {$a.$sep.$b} @_ or ''}
say mjoin(', ', qw(Alpha Beta Gamma));
# Alpha, Beta, Gamma |
或不带reduce：
1
2
3
4
5
6
| sub mjoin($@)
{
my ($sep, $sum) = (shift, shift);
$sum .= $sep.$_ for (@_);
$sum or ''
} |
Perl 6
1
2
3
4
5
6
7
| sub join( $separator, @strings ){
my $return = shift @strings;
for @strings -> ( $string ){
$return ~= $separator ~ $string;
}
return $return;
} |
是的，我知道这毫无意义，因为Perl 6已经具有联接功能。
以下内容不再与语言无关(但是对于讨论而言，这无关紧要，因为该实现很容易移植到其他语言中)。我试图用命令式编程语言实现Luke(在理论上最好的)解决方案。随便你吧我的C＃。一点也不优雅。但是，(不进行任何测试)我可以想象它的性能相当不错，因为递归实际上是尾递归。
我的挑战：提供更好的递归实现(使用命令式语言)。您说"更好"的意思是：更少的代码，更快的速度，我愿意征求建议。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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();
} |
在Java 5中，使用单元测试：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| 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，则会将列表尽可能地分成两半，然后尝试合并子列表
1
2
3
4
5
6
7
8
9
10
11
12
| (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")) |
我曾尝试对问题采用分而治之的策略，但我想这并没有比单纯的迭代更好的结果。请让我知道是否可以做得更好。
我还对通过算法获得的递归进行了分析，可在此处获得。
|
