私はしばらくの間、文字列の配列を結合するためのすてきでクリーンなソリューションがどのように見えるか疑問に思っていました。例: ["Alpha", "Beta", "Gamma"] があり、コンマで区切られた文字列を 1 つに結合したい – "Alpha, Beta, Gamma".
これで、ほとんどのプログラミング言語が何らかの結合メソッドを提供することがわかりました。これらがどのように実装されるのか疑問に思っています。入門コースを受講したとき、私はしばしば一人で行こうとしましたが、満足のいくアルゴリズムを見つけることができませんでした. 問題は、配列をループして文字列を連結することはできず、(最後の文字列の前または後に) コンマを 1 つ追加しすぎるためです。ループ内の条件をチェックしたくありません。ループの前後に最初または最後の文字列を追加したくありません (これが最善の方法だと思いますか?)。
誰かが私にエレガントなソリューションを見せてもらえますか? それとも、もっとエレガントなものがない理由を正確に教えてください。
このような問題に対して私が見つけた最もエレガントな解決策は、このようなものです（疑似コードで）
separator = ""
foreach(item in stringCollection)
{
concatenatedString += separator + item
separator = ","
}
ループを実行するだけで、2回目のセパレーターが設定された後にのみ実行されます。そのため、初めて追加されません。思ったほどきれいではないので、コメントを追加しますが、if ステートメントやループ外の最初または最後の項目を追加するよりはましです。
これらのソリューションはすべて適切なものですが、基盤となるライブラリでは、セパレーターの独立性と適切な速度の両方が重要です。言語に何らかの形式の文字列ビルダーがあると仮定すると、要件に適合する関数を次に示します。
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(); です。同じ文字列ビルダー オブジェクトを再利用することで、生成する割り当てとガベージの量を減らすことができます。
そして、誰かが最適化は悪だと言う前に、共通のライブラリ関数を実装することについて話しています。許容できるスケーラブルなパフォーマンスは、要件の 1 つです。時間がかかる結合は、あまり使用されないものです。
最近のほとんどの言語 (perl (Jon Ericson による言及)、php、javascript など) には join() 関数またはメソッドがあり、これは最も洗練されたソリューションです。より少ないコードはより良いコードです。
Mendelt Siebenga への回答として、手巻きのソリューションが必要な場合は、次のような三項演算子を使用します。
separator = ","
foreach (item in stringCollection)
{
concatenatedString += concatenatedString ? separator + item : item
}
私は通常、次のようなもので行きます...
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(rest)
実際には、これをより一般的な方法で記述し、同じアルゴリズムを再利用しますが、データ型 (文字列である必要はありません) と操作 (途中でコンマを使用して連結する必要はありません) を抽象化します。 . 次に、通常は「reduce」と呼ばれ、多くの関数型言語にはこれが組み込まれています。たとえば、リスト内のすべての数値を Lisp で乗算します。
( #'* '(1 2 3 4 5) を減らす) => 120
@メンデルト・シーベンガ
文字列は、プログラミング言語の基礎となるオブジェクトです。言語が異なれば、文字列の実装も異なります。の実装は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
' 疑似コード ゼロベースと仮定
結果文字列 = 入力配列[0]
n = 1
while n (より小さい) Number_Of_Strings
ResultString (連結) ", "
ResultString (連結) InputArray[n]
n = n + 1
ループ
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のサイズを確認する必要があります。
最初のエントリまたは最後のエントリを特別なケースにする必要があります。
異なる言語の実装を収集していますか?
ここに、あなたの娯楽のために、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 を使用する余分な作業は、実装および言語に依存する数の文字列まで、実際には逆効果になる可能性があります。
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"));
}
}
以下は言語に依存しなくなりました (ただし、実装は他の言語に簡単に移植できるため、議論には関係ありません)。私は命令型プログラミング言語で 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();
}
join()Ruby での関数:
def join(seq, sep)
seq.inject { |total, item| total << sep << item } or ""
end
join(["a", "b", "c"], ", ")
# => "a, b, c"
C# で String.join メソッドを使用する
sub join( $separator, @strings ){
my $return = shift @strings;
for @strings -> ( $string ){
$return ~= $separator ~ $string;
}
return $return;
}
はい、Perl 6 には既に結合機能があるため、無意味であることはわかっています。
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"))
問題に分割統治戦略を適用してみましたが、単純な反復よりも良い結果は得られないと思います。これがもっとうまくできるかどうか教えてください。
アルゴリズムによって得られた再帰の分析も実行しました。ここで入手できます。
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 ''
}