2

プログラミング スキルを向上させるための計画の一環として、文字列の大きな配列を辞書順にソートすることにしました (後でスレッドを使用してソートする予定です)。私はさまざまなソートアルゴリズムを調査し、理解したものからマージソートを実装しようとしました。今のところ、いくつかの単純な文字列を並べ替える予定です。

以下のメソッドでソートする次の文字列を入力しています。

 string[] stringsArray = new string[] { "cixymn", "adfxij", "adxhxy", "abcdef", "iejfyq", "uqbzxo", "aaaaaa" };
 string[] stringSorted = MergeSort(stringsArray);

 // For display purposes
 foreach (string s in stringSorted)
        {
            Console.WriteLine("Item at index " + Array.IndexOf(stringSorted, s) + " is " + s);
        }

私が得ている結果は次のとおりです。

Item at index 0 is aaaaaa
Item at index 1 is abcdef
Item at index 2 is adfxij
Item at index 3 is uqbzxo
Item at index 4 is 
Item at index 4 is 
Item at index 4 is

マージソートを実装するには、まず配列を 2 つに分割する必要があるため、この場合、左の部分は正常にソートされ、右の部分は無視されていることが容易に理解できます。すべての再帰で配列の左側から各文字列の文字を比較しているため、これが起こっているという印象を受けています（したがって、右側を無視する可能性があります）。それで、問題がどこにあるのかを実際に理解したと思います。しかし、私はこれについてどうすればよいのかよくわかりません。どんな助けでも大歓迎です。

以下は、MergeSort メソッドのコードです。

  private static string[] MergeSort(string[] stringsArray)
    {
        if (stringsArray.Length == 1)
        {
            return stringsArray;
        }

        int middle = stringsArray.Length / 2;

        string[] left = new string[middle];
        string[] right = new string[stringsArray.Length - middle];

        for (int i = 0; i < middle; i++)
        {
            left[i] = stringsArray[i];
        }

        for (int i = 0; i < stringsArray.Length - middle; i++)
        {
            right[i] = stringsArray[i + middle];
        }

        left = MergeSort(left);
        right = MergeSort(right);

        int leftPointer = 0;
        int rightPointer = 0;

        string[] sorted = new string[stringsArray.Length];

        for (int k = 0; k < stringsArray.Length; k++)
        {
            if (k == left.Length)
            {
                break;
            }

            for (int i = 0; i < left[leftPointer].Count(); i++)
            {
                var leftChar = left[leftPointer][i];

                if (i == right[rightPointer].Count())
                {
                    continue;
                }

                var rightChar = right[rightPointer][i];

                if ((rightPointer == right.Length || leftPointer < left.Length) && leftChar < rightChar)
                {
                    sorted[k] = left[leftPointer];
                    sorted[k + 1] = right[rightPointer];
                    leftPointer++;

                    break;
                }

                if ((leftPointer == left.Length || rightPointer < right.Length) && (rightChar < leftChar))
                {
                    sorted[k] = right[rightPointer];
                    sorted[k + 1] = left[leftPointer];
                    rightPointer++;
                    break;
                }
            }
        }

質問 #2 : スレッド化を使用できるようにするために、コードをどのように最適化することをお勧めしますか?

4

2 に答える 2

1

これが実用的な解決策です。MergeSortは最も基本的なバージョンであり、ThreadedMergeSortはタスクを使用し、些細なケースを最適化します。単純なバージョンは、私のマシンの.Sort（）メソッド（クイックソートだと思います）よりも約30％遅くなりますが、スレッド化されたバージョンは約2倍速くなります。

    static List<T> MergeSort<T>(List<T> input) where T: IComparable
    {
        var length = input.Count;

        if (length < 2)
            return input;

        var left = MergeSort(input.GetRange(0, length / 2));
        var right = MergeSort(input.GetRange(length / 2, length - length / 2));
        var result = new List<T>();
        for (int leftIndex = 0, leftLength = left.Count, rightLength = right.Count, rightIndex = 0; leftIndex + rightIndex < length;)
        {
            if (rightIndex >= rightLength || leftIndex < leftLength && left[leftIndex].CompareTo(right[rightIndex]) <= 0)
                result.Add(left[leftIndex++]);
            else
                result.Add(right[rightIndex++]);
        }

        return result;
    }

    static List<T> ThreadedMergeSort<T>(List<T> input) where T : IComparable
    {
        var length = input.Count;

        if (length < 2)
            return input;

        // this next part can be commented out if you want a "pure" mergesort, but it
        // doesn't make sense to merge sort very short sublists.
        if (length < 10)
        {
            for (int i = 0; i < length - 1; i++)
                for (int j = i + 1; j < length; j++)
                    if (input[i].CompareTo(input[j]) > 0)
                    {
                        var tmp = input[i];
                        input[i] = input[j];
                        input[j] = tmp;
                    }
            return input;
        }

        List<T> left, right;
        if (length > 10000)
        {
            var taskLeft = Task<List<T>>.Factory.StartNew(() => { return ThreadedMergeSort(input.GetRange(0, length / 2)); });
            var taskRight = Task<List<T>>.Factory.StartNew(() => { return ThreadedMergeSort(input.GetRange(length / 2, length - length / 2)); });
            taskLeft.Wait();
            taskRight.Wait();
            left = taskLeft.Result;
            right = taskRight.Result;
        }
        else
        {
            left = ThreadedMergeSort(input.GetRange(0, length / 2));
            right = ThreadedMergeSort(input.GetRange(length / 2, length - length / 2));
        }
        var result = new List<T>();
        for (int leftIndex = 0, leftLength = left.Count, rightLength = right.Count, rightIndex = 0; leftIndex + rightIndex < length; )
        {
            if (rightIndex >= rightLength || leftIndex < leftLength && left[leftIndex].CompareTo(right[rightIndex]) <= 0)
                result.Add(left[leftIndex++]);
            else
                result.Add(right[rightIndex++]);
        }

        return result;
    }
于 2012-08-10T09:42:25.617 に答える
1

ここから私が盗み、一般化し、最新のものにした答えをここに示します

public static IList<T> MergeSort<T>(
    this IList<T> unsorted,
    IComparer<T> comparer = null)
{
    if (unsorted == null ||  unsorted.Count < 2)
    {
        return unsorted;
    }

    if (comparer == null)
    {
        comparer = Comparer<T>.Default;
    }

    IList<T> sorted = new List<T>();
    int middle = (int)unsorted.Count/2;
    Ilist<T> left = unsorted.GetRange(0, middle);
    IList<T> right = unsorted.GetRange(middle, unsorted.Count - middle);

    var sortLeft = Task<IList<T>>.Factory.StartNew(
        () => left.MergeSort(comparer));

    var sortRight = Task<IList<T>>.Factory.StartNew(
        () => right.MergeSort(comparer));

    left = sortLeft.Result;
    right = sortRight.Result;

    int leftPtr = 0;
    int rightPtr = 0;
    for (int i = 0; i < left.Count + right.Count; i++)
    {
        if (leftPtr == left.Count)
        {
            sorted.Add(right[rightPtr]);
            rightPtr++;
        }
        else if (rightPtr == right.Count)
        {
            sorted.Add(left[leftPtr]);
            leftPtr++;
        }
        else if (comparer.Compare(left[leftPtr], right[rightPtr]) < 0)
        {
            sorted.Add(left[leftPtr]);
            leftPtr++;
        }
        else
        {
            sorted.Add(right[rightPtr]);
            rightPtr++;
        }
    }

    return sorted;
}

このコードは、IComparer<T>独自のものを渡さない限り、デフォルトを使用します。

このコードは、並べ替えられていない配列の半分ごとに自己反復することがわかるので、TaskTPL クラスを使用してこれらの呼び出しを個別のスレッドで非同期に実行するコードを追加しました。

次のようなコードを使用できます。

var strings = new List<string>
    {
        "cixymn", 
        "adfxij",
        "adxhxy",
        "abcdef",
        "iejfyq",
        "uqbzxo",
        "aaaaaa" 
    };

var sortedStrings = strings.MergeSort();

デフォルトの文字列比較子が十分に辞書編集的でない場合はStringComparer、おそらく次のように、選択したをインスタンス化して渡すことができます。

var sortedStrings = strings.MergeSort(StringComparer.OrdinalIgnoreCase);

いずれの もStringComparer要件を満たさない場合は、代わりに の独自の実装を記述して、それを関数にIComparer<string>渡すことができます。MergeSort

いずれにせよ、すべての型に対してマージソートを汎用的かつ再利用可能に保ち、特殊化を関数に渡すことは理にかなっています。

于 2012-08-10T09:00:28.943 に答える