Блог

Моя задача состоит в том, чтобы сделать организованную перетасовку, из источника все нечетные числа пойдут влево, а четные числа пойдут вправо.

Я сделал это примерно так, и это хорошо для нормального сценария:

 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 или другое огромное число в миллионах, оно будет сильно петлять. Как я могу оптимизировать код с точки зрения скорости и потребления ресурсов?

Вы должны быть в состоянии определить по длине строки, сколько итераций потребуется, прежде чем она вернется к исходному порядку сортировки. Затем возьмите модуль количества итераций и количество входных данных и повторите только это количество раз.

Например, строка, состоящая из трех символов, будет возвращена к исходному порядку сортировки в 2 итерациях. Если счетчик входных данных должен был выполнять 11 итерации, мы это знаем 11 % 2 == 1 , поэтому нам нужно выполнить итерацию только один раз.

Как только вы определите формулу для того, сколько итераций требуется для достижения исходного порядка сортировки для любой длины строки, вы всегда можете уменьшить количество итераций до этого числа или меньше.

Однако придумать формулу будет непросто. Строка с 14 символами проходит 12 итерации до тех пор, пока не совпадет сама с собой, но строка с 15 символами проходит только 4 итерации.

Поэтому кратчайший путь может заключаться в том, чтобы просто начать итерацию, пока мы не достигнем исходного порядка сортировки (или указанного количества, в зависимости от того, что наступит раньше). Если мы доберемся до графа первыми, то вернем этот ответ. В противном случае мы можем определить ответ по идее в первом абзаце — взять модуль количества входных данных и количества итераций и вернуть этот ответ.

Для этого потребуется, чтобы мы сохраняли значения из наших итераций (например, в словаре), чтобы мы могли получить конкретное предыдущее значение.

Например:

 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;
}
 

Вместо того, чтобы создавать новые неизменяемые строки в каждом цикле, вы могли бы работать с изменяемым массивом символов ( char[] ) и обмениваться символами между местами. Это было бы наиболее эффективным с точки зрения потребления памяти, но выполнение свопов на одном массиве может оказаться довольно сложным. Использовать два массива намного проще, потому что вы можете просто копировать символы из одного массива в другой и в конце каждого цикла менять местами два массива.

Еще одна оптимизация, которую вы могли бы сделать, — это работать с индексами char массива, а не с его значениями. Я не уверен, что это будет иметь какое-либо значение на практике, поскольку в современных 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]));
}