如何将字符串字符向右和向左打乱直到 int.MaxValue？

Question

我的任务是进行有组织的洗牌，从源头开始，所有奇数都将向左，偶数将向右。

我已经做了这么多了，一般情况下还是不错的：

public static string ShuffleChars(string source, int count)
{
    if (string.IsNullOrWhiteSpace(source) || source.Length == 0)
    {
        throw new ArgumentException(null);
    }

    if (count < 0)
    {
        throw new ArgumentException(null);
    }

    for (int i = 0; i < count; i++)
    {
        source = string.Concat(source.Where((item, index) => index % 2 == 0)) +
                    string.Concat(source.Where((item, index) => index % 2 != 0));
    }

    return source;
}

现在的问题是，如果 count 是 int.MaxValue 或其他以百万为单位的巨大数字，它会循环很多次。如何在速度和资源消耗方面优化代码？

Answer 1

您应该能够根据字符串的长度确定在返回到原始排序顺序之前需要迭代多少次。然后对迭代次数和输入次数取模，只迭代那么多次

例如，一个包含三个字符的字符串将在 2 次迭代后恢复到其原始排序顺序。如果输入计数要进行 11 次迭代，我们知道 11 % 2 == 1，因此我们只需要迭代一次。

一旦确定了为达到任意长度字符串的原始排序顺序所需的迭代次数的公式，您始终可以将迭代次数减少到该次数或更少。

然而，想出一个公式会很棘手。具有 14 个字符的字符串需要 12 次迭代才能匹配自身，但是具有 15 个字符的字符串只需要 4 次迭代。

因此，一个捷径可能是简单地开始迭代，直到我们达到原始排序顺序（或指定的计数，以先到者为准）。如果我们首先达到计数，那么我们 return 那个答案。否则，我们可以从第一段的思路中确定答案——取输入计数和迭代计数的模数，return那个答案。

这需要我们存储迭代中的值（例如，在字典中），以便我们可以检索特定的先前值。

例如：

public static string ShuffleChars(string source, int count)
{
    string s = source;
    var results = new Dictionary<int, string>();

    for (int i = 0; i < count; i++)
    {
        s = string.Concat(s.Where((item, index) => index % 2 == 0)) +
            string.Concat(s.Where((item, index) => index % 2 != 0));

        // If we've repeated our original string, return the saved
        // value of the input count modulus the current iteration
        if (s == source)
        {
            return results[count % (i + 1) - 1];
        }
        // Otherwise, save the value for later
        else
        {
            results[i] = s;
        }
    }

    // If we get here it means we hit the requested count before
    // ever returning to the original sort order of the input
    return s;
}

Answer 2

您可以使用可变字符数组 (char[])，并在不同位置之间交换字符，而不是在每个循环中创建新的不可变字符串。就内存消耗而言，这将是最有效的，但在单个数组上进行交换可能会非常棘手。使用两个数组要容易得多，因为您只需将字符从一个数组复制到另一个数组，并在每个循环结束时交换两个数组。

您可以做的另一个优化是使用 char 数组的 indices，而不是它的值。我不确定这在实践中是否会有任何不同，因为在现代 64 位机器中，char 和 int 类型都占用 8 个字节（AFAIK）。不过，它肯定会在 32 位机器上有所作为。这是一个实现，将所有这些想法放在一起：

public static string ShuffleChars(string source, int count)
{
    if (source == null) throw new ArgumentNullException(nameof(source));
    if (count < 0) throw new ArgumentOutOfRangeException(nameof(count));

    // Instantiate the two arrays
    int[] indices = new int[source.Length];
    int[] temp = new int[source.Length];

    // Initialize the indices array with incremented numbers
    for (int i = 0; i < indices.Length; i++)
        indices[i] = i;

    for (int k = 0; k < count; k++)
    {
        // Copy the odds to the temp array
        for (int i = 0, j = 0; j < indices.Length; i += 1, j += 2)
            temp[i] = indices[j];

        // Copy the evens to the temp array
        int lastEven = (indices.Length >> 1 << 1) - 1;
        for (int i = indices.Length - 1, j = lastEven; j >= 0; i -= 1, j -= 2)
                temp[i] = indices[j];

        // Swap the two arrays, using value tuples
        (indices, temp) = (temp, indices);
    }

    // Map the indices to characters from the source string
    return String.Concat(indices.Select(i => source[i]));
}

如何将字符串字符向右和向左打乱直到 int.MaxValue？

How to shuffle string characters to right and left until int.MaxValue?

c#

performance

loops

shuffle

max