再帰の使用を回避するためにこのルーチンをリファクタリングする方法は？
https://stackoverflow.com/questions/3412935
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
だから私は書いていました mergesort の C＃ として エクササイズ そして、それはうまくいきましたが、コードを振り返ると、改善の余地がありました。
基本的に、アルゴリズムの2番目の部分では、 2つのソートされたリストをマージします.
いくつかのリファクタリングを使用できる私の方法が長すぎる実装です。
private static List<int> MergeSortedLists(List<int> sLeft, List<int> sRight)
{
if (sLeft.Count == 0 || sRight.Count == 0)
{
sLeft.AddRange(sRight);
return sLeft;
}
else if (sLeft.Count == 1 && sRight.Count == 1)
{
if (sLeft[0] <= sRight[0])
sLeft.Add(sRight[0]);
else
sLeft.Insert(0, sRight[0]);
return sLeft;
}
else if (sLeft.Count == 1 && sRight.Count > 1)
{
for (int i=0; i<sRight.Count; i++)
{
if (sLeft[0] <= sRight[i])
{
sRight.Insert(i, sLeft[0]);
return sRight;
}
}
sRight.Add(sLeft[0]);
return sRight;
}
else if (sLeft.Count > 1 && sRight.Count == 1)
{
for (int i=0; i<sLeft.Count; i++)
{
if (sRight[0] <= sLeft[i])
{
sLeft.Insert(i, sRight[0]);
return sLeft;
}
}
sLeft.Add(sRight[0]);
return sLeft;
}
else
{
List<int> list = new List<int>();
if (sLeft[0] <= sRight[0])
{
list.Add(sLeft[0]);
sLeft.RemoveAt(0);
}
else
{
list.Add(sRight[0]);
sRight.RemoveAt(0);
}
list.AddRange(MergeSortedLists(sLeft, sRight));
return list;
}
}
確かにこのルーチンは、削除することで改善/短縮できます 再帰, など。2つのソートされたリストをマージする他の方法さえあります。そう どれか リファクタリングは大歓迎です。
私には答えがありますが、他のプログラマーがこのルーチンを改善する方法について興味があります。
ありがとうございました！
解決
出発点として、いずれかのリストが持っている場合のためにあなたの特別なケースを削除します Count == 1 - それらは、あなたのより一般的な（現在再発）ケースによって処理されることができます。
if (sLeft.Count > 1 && sRight.Count == 0) 意思 一度もない あなたがチェックしたので真実である sRight.Count == 0 最初は - したがって、このコードに到達することはなく、冗長です。
最後に、再帰の代わりに（この場合、あなたが作成する新しいリストの数があるため、これは非常に費用がかかります - 要素ごとに1つ！）私はあなたの中でこのようなことをします else （実際、これはあなたの方法全体を置き換えることができます）：
List<int> list = new List<int>();
while (sLeft.Count > 0 && sRight.Count > 0)
{
if (sLeft[0] <= sRight[0])
{
list.Add(sLeft[0]);
sLeft.RemoveAt(0);
}
else
{
list.Add(sRight[0]);
sRight.RemoveAt(0);
}
}
// one of these two is already empty; the other is in sorted order...
list.AddRange(sLeft);
list.AddRange(sRight);
return list;
（理想的には、これをリファクタリングして、各リストに対して整数インデックスを使用します。 .RemoveAt, 、リストを破壊するよりもリストをループする方がパフォーマンスが高いため、元のリストをそのまま残すと便利かもしれないからです。ただし、これは元のコードよりも効率的なコードです！）
他のヒント
2つのソートされたリストのマージは、O（n）で実行できます。
List<int> lList, rList, resultList;
int r,l = 0;
while(l < lList.Count && r < rList.Count)
{
if(lList[l] < rList[r]
resultList.Add(lList[l++]);
else
resultList.Add(rList[r++]);
}
//And add the missing parts.
while(l < lList.Count)
resultList.Add(lList[l++]);
while(r < rList.Count)
resultList.Add(rList[r++]);
これについての私の見解は次のとおりです。
private static List<int> MergeSortedLists(List<int> sLeft, List<int> sRight)
{
List<int> result = new List<int>();
int indexLeft = 0;
int indexRight = 0;
while (indexLeft < sLeft.Count || indexRight < sRight.Count)
{
if (indexRight == sRight.Count ||
(indexLeft < sLeft.Count && sLeft[indexLeft] < sRight[indexRight]))
{
result.Add(sLeft[indexLeft]);
indexLeft++;
}
else
{
result.Add(sRight[indexRight]);
indexRight++;
}
}
return result;
}
手作業でやらなければならなかったら、まさに私がしていること。 =）
あなたのコードがまったく機能していると確信していますか？テストせずに、次のことがわかります。
...
else if (sLeft.Count > 1 && sRight.Count == 0) //<-- sRight is empty
{
for (int i=0; i<sLeft.Count; i++)
{
if (sRight[0] <= sLeft[i]) //<-- IndexError?
{
sLeft.Insert(i, sRight[0]);
return sLeft;
}
}
sLeft.Add(sRight[0]);
return sLeft;
}
...
あなたも異なるアプローチを求めていました。使用法に応じて、以下のように行うことがあります。以下のコードは怠けているため、リスト全体を一度に並べ替えず、要素が要求された場合にのみ並べ替えます。
class MergeEnumerable<T> : IEnumerable<T>
{
public IEnumerator<T> GetEnumerator()
{
var left = _left.GetEnumerator();
var right = _right.GetEnumerator();
var leftHasSome = left.MoveNext();
var rightHasSome = right.MoveNext();
while (leftHasSome || rightHasSome)
{
if (leftHasSome && rightHasSome)
{
if(_comparer.Compare(left.Current,right.Current) < 0)
{
yield return returner(left);
} else {
yield return returner(right);
}
}
else if (rightHasSome)
{
returner(right);
}
else
{
returner(left);
}
}
}
private T returner(IEnumerator<T> enumerator)
{
var current = enumerator.Current;
enumerator.MoveNext();
return current;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return ((IEnumerable<T>)this).GetEnumerator();
}
private IEnumerable<T> _left;
private IEnumerable<T> _right;
private IComparer<T> _comparer;
MergeEnumerable(IEnumerable<T> left, IEnumerable<T> right, IComparer<T> comparer)
{
_left = left;
_right = right;
_comparer = comparer;
}
}
編集： それは基本的に、セルゲイ・オシプチュクと同じものであり、ソートが最速であることのみを見ると、最初から最後まで彼の意志がありますが、リスト全体を前もって並べ替えるという事実により、レイテンシも高くなります。そのため、使用法に応じて言ったように、私はこのアプローチで行くかもしれませんし、代替手段はセルゲイ・オシプチュクに似たものになるでしょう
多くの場合、再帰を使用する代わりにスタックを使用できます
マージリスト（理論、入力リストは事前にソートされます）のソートは、次の方法で実装できます。
List<int> MergeSorting(List<int> a, List<int> b)
{
int apos = 0;
int bpos = 0;
List<int> result = new List<int>();
while (apos < a.Count && bpos < b.Count)
{
int avalue = int.MaxValue;
int bvalue = int.MaxValue;
if (apos < a.Count)
avalue = a[apos];
if (bpos < b.Count)
bvalue = b[bpos];
if (avalue < bvalue)
{
result.Add(avalue);
apos++;
}
else
{
result.Add(bvalue);
bpos++;
}
}
return result;
}
ソートされていないリストから開始する場合に備えて、ソートされたサブシーケンスによって分割し、上記の関数を使用してそれらをマージする必要があります
マージソートに再帰を使用することはありません。ソートされたブロックサイズがマージパスごとに2倍になるという事実を利用して、入力を反復的にパスすることができます。各入力リストから処理したアイテムのブロックサイズとカウントを追跡します。それらが等しい場合、リストは使い果たされます。両方のリストが使い果たされると、次のブロックのペアに移動できます。ブロックサイズが入力サイズ以上の場合、完了です。
編集： 私が以前に残した情報のいくつかは、私の誤解のために間違っていました - C＃のリストは、リンクされたリストではなく配列に似ています。謝罪いたします。
