如何将String与字符序列交错

Question

将java String与给定字符序列交错的最佳方法是什么？交错间隔应该是可变的.

例:

String s = " .... 0000000000000 ..."; // length random
String b = interleave(s, 3, "-");

结果:

... 000-000-000-000-000 ...

另一个例子:

String s = " .... we all we all we all ...";
String b = interleave(s, 7, "rock ");

结果:

... we all rock we all rock we all rock ...

如果字符串长度不是交错距离的倍数,则该函数也应该起作用.有什么建议？是否(再次)采用"公地"的方式来做到这一点？

Answer 1

这是非常简单和相当可读的实现(我在下面的基准测试中将其称为StringBuilder):

public static String interleave(String s, int interval, String separator)
{
    StringBuilder sb = new StringBuilder(s);
    for (int pos = (s.length()-1) / interval; pos > 0; pos--)
    {
        sb.insert(pos * interval, separator);
    }
    return sb.toString();
}

如果你关心简单的StringBuilder实现的效率,那么这个实现可能会更好地满足你的需求(我在下面的基准测试中称之为Arrays):

public static String interleave(String string, int interval, String separator)
{
    char[] src = string.toCharArray();
    char[] sep = separator.toCharArray();
    int count = (src.length-1)/interval;
    char[] dst = new char[src.length + count * sep.length];
    int srcpos = 0, dstpos = 0;
    for (int i = 0; i < count; i++)
    {
        System.arraycopy(src, srcpos, dst, dstpos, interval);
        srcpos += interval;
        dstpos += interval;
        System.arraycopy(sep, 0, dst, dstpos, sep.length);
        dstpos += sep.length;
    }
    if (dstpos < dst.length)
    {
        System.arraycopy(src, srcpos, dst, dstpos, dst.length - dstpos);
    }
    return String.valueOf(dst);
}

注意:我可能只在J2ME环境下使用这种实现,但它应该在巨大的字符串上更快.虽然可读性很差......

当然,RegExp做事的方式总是非常快,在你爬过编译RegExp本身不再成为问题的长度之后(你不能预编译一个RegExp,因为它是在运行时产生的,取决于间隔,感谢Rubens Farias指出这一点,不知怎的错过了我自己).所以这里(我在下面的基准测试中称之为RegExp):

public static String interleave(String string, int interval, String separator)
{
    return string.replaceAll("(.{"+interval+"})", "$1"+Matcher.quoteReplacement(separator));
}

注意:如果字符串的长度是间隔的倍数,则此实现在末尾插入分隔符(而其他实现则不是).我不喜欢RegExps,因为它们不可读也不太快.哦,你可以很容易地忘记"quoteReplacement"部分,如果分隔符包含"$ 1"甚至更糟 - 如果它来自用户,则会让自己陷入困境.

基准

在这一点上我做了一些基准测试,所以在字符串长度100000第一个实现需要0.002643秒,第二个 - 0.000010,第三个 - 0.000071,但一切都取决于字符串的长度.

Length    StringBuilder   Arrays       RegExp
  10000     0.000012     0.000001     0.000054
 100000     0.002643     0.000010     0.000071
1000000     0.315413     0.000026     0.000199

它绝不是一个严肃的基准测试,但它仍然显示了所涉及的算法的趋势和复杂性.

注意:尽管使用这些想法很有趣,但在处理大小小于1M的字符串时,我们仍然在讨论亚秒级的改进.因此,如果你只处理大小达1K的字符串(它将是0ms对0ms),那么你走哪条路并不重要.最重要的是它应该是可读的,直截了当的,并且不需要花太多时间来编写,因为我确信你有更多重要的问题需要解决,除非你正在编写一个通用库供所有人在最奇怪的情况下使用.记住 - 你的时间比CPU时间更有价值.

左对齐和右对齐交错

我将采用Arrays实现,因为它似乎最容易改变:

public static String interleave(String string, int interval, String separator, boolean fromRight)
{
    char[] src = string.toCharArray();
    char[] sep = separator.toCharArray();
    int count = (src.length-1)/interval;
    char[] dst = new char[src.length + count * sep.length];
    int srcpos = 0, dstpos = 0;
    if (fromRight)
    {
        srcpos = dstpos = src.length - count * interval;
        if (srcpos > 0) System.arraycopy(src, 0, dst, 0, srcpos);
        if (count > 0)
        {
            System.arraycopy(sep, 0, dst, dstpos, sep.length);
            dstpos += sep.length;
            count--;
        }
    }
    for (int i = 0; i < count; i++)
    {
        System.arraycopy(src, srcpos, dst, dstpos, interval);
        srcpos += interval;
        dstpos += interval;
        System.arraycopy(sep, 0, dst, dstpos, sep.length);
        dstpos += sep.length;
    }
    if (dstpos < dst.length)
    {
        System.arraycopy(src, srcpos, dst, dstpos, dst.length - dstpos);
    }
    return String.valueOf(dst);
}