混合した数字と文字列の並べ替え
https://stackoverflow.com/questions/1032775
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
文字またはintの文字列表現（最大2桁）を含むことができる文字列のリストがあります。 それらは、アルファベット順または（実際にはintの場合）数値でソートする必要があります。
例：
IList<string> input = new List<string>()
{"a", 1.ToString(), 2.ToString(), "b", 10.ToString()};
input.OrderBy(s=>s)
// 1
// 10
// 2
// a
// b
欲しいのは
// 1
// 2
// 10
// a
// b
私はそれを解析しようとしてフォーマットすることを含むいくつかのアイデアを持っています、そしてそれが成功するなら、私の独自のカスタム文字列フォーマッターでフォーマットを試みて、それが先行ゼロを持つようにします。もっとシンプルでパフォーマンスの良いものを期待しています。
編集
後で使用するためにUtilsライブラリにダンプしたIComparerを作成しました。
その間、私もミックスでダブルを投げました。
public class MixedNumbersAndStringsComparer : IComparer<string> {
public int Compare(string x, string y) {
double xVal, yVal;
if(double.TryParse(x, out xVal) && double.TryParse(y, out yVal))
return xVal.CompareTo(yVal);
else
return string.Compare(x, y);
}
}
//Tested on int vs int, double vs double, int vs double, string vs int, string vs doubl, string vs string.
//Not gonna put those here
[TestMethod]
public void RealWorldTest()
{
List<string> input = new List<string>() { "a", "1", "2,0", "b", "10" };
List<string> expected = new List<string>() { "1", "2,0", "10", "a", "b" };
input.Sort(new MixedNumbersAndStringsComparer());
CollectionAssert.AreEquivalent(expected, input);
}
解決
より一般的なアプローチで、自然なC＃実装などのソートアルゴリズム こちら。
他のヒント
2つの方法が思い浮かびますが、どちらがパフォーマンスが良いかはわかりません。カスタムIComparerを実装します：
class MyComparer : IComparer<string>
{
public int Compare(string x, string y)
{
int xVal, yVal;
var xIsVal = int.TryParse( x, out xVal );
var yIsVal = int.TryParse( y, out yVal );
if (xIsVal && yIsVal) // both are numbers...
return xVal.CompareTo(yVal);
if (!xIsVal && !yIsVal) // both are strings...
return x.CompareTo(y);
if (xIsVal) // x is a number, sort first
return -1;
return 1; // x is a string, sort last
}
}
var input = new[] {"a", "1", "10", "b", "2", "c"};
var e = input.OrderBy( s => s, new MyComparer() );
または、シーケンスを数字と数字以外に分割してから、各サブグループを並べ替え、最後に並べ替えた結果を結合します。次のようなもの：
var input = new[] {"a", "1", "10", "b", "2", "c"};
var result = input.Where( s => s.All( x => char.IsDigit( x ) ) )
.OrderBy( r => { int z; int.TryParse( r, out z ); return z; } )
.Union( input.Where( m => m.Any( x => !char.IsDigit( x ) ) )
.OrderBy( q => q ) );
IComparer パラメータを取る OrderBy の他のオーバーロードを使用します。
その後、 int.TryParse を使用して数値かどうかを判断する独自の IComparer を実装できます。
RegularExpressionを使用して値を分割し（すべてがintであると仮定）、それらを再結合できると思います。
//create two lists to start
string[] data = //whatever...
List<int> numbers = new List<int>();
List<string> words = new List<string>();
//check each value
foreach (string item in data) {
if (Regex.IsMatch("^\d+<*>quot;, item)) {
numbers.Add(int.Parse(item));
}
else {
words.Add(item);
}
}
次に、2つのリストを使用して、それぞれを並べ替えてから、必要な形式でそれらを結合します。
Win32 APIで提供される関数を使用できます。
[DllImport ("shlwapi.dll", CharSet=CharSet.Unicode, ExactSpelling=true)]
static extern int StrCmpLogicalW (String x, String y);
他の人が示したように IComparer から呼び出します。
public static int? TryParse(string s)
{
int i;
return int.TryParse(s, out i) ? (int?)i : null;
}
// in your method
IEnumerable<string> input = new string[] {"a", "1","2", "b", "10"};
var list = input.Select(s => new { IntVal = TryParse(s), String =s}).ToList();
list.Sort((s1, s2) => {
if(s1.IntVal == null && s2.IntVal == null)
{
return s1.String.CompareTo(s2.String);
}
if(s1.IntVal == null)
{
return 1;
}
if(s2.IntVal == null)
{
return -1;
}
return s1.IntVal.Value.CompareTo(s2.IntVal.Value);
});
input = list.Select(s => s.String);
foreach(var x in input)
{
Console.WriteLine(x);
}
まだ変換を行いますが、1回/アイテムのみです。
カスタム比較演算子を使用できます-順序ステートメントは次のようになります。
var result = input.OrderBy(s => s, new MyComparer());
MyComparerは次のように定義されています：
public class MyComparer : Comparer<string>
{
public override int Compare(string x, string y)
{
int xNumber;
int yNumber;
var xIsNumber = int.TryParse(x, out xNumber);
var yIsNumber = int.TryParse(y, out yNumber);
if (xIsNumber && yIsNumber)
{
return xNumber.CompareTo(yNumber);
}
if (xIsNumber)
{
return -1;
}
if (yIsNumber)
{
return 1;
}
return x.CompareTo(y);
}
}
これは少し冗長に見えるかもしれませんが、ソートロジックを適切な型にカプセル化します。その後、必要に応じて、Comparerを簡単に自動テスト（ユニットテスト）にかけることができます。また、再利用可能です。
（アルゴリズムを少し明確にすることも可能かもしれませんが、これは私がすぐに一緒に投げることができる最高のものでした。）
「チート」することもできます。ある意味で。問題の説明に基づいて、長さ2の文字列は数字になることがわかっています。したがって、長さ1のすべての文字列を並べ替えてから、長さ2のすべての文字列を並べ替えてから、一連のスワッピングを実行して、正しい順序で文字列を並べ替えます。基本的に、プロセスは次のように機能します：（データが配列にあると仮定します。）
手順1：長さ2のすべての文字列を配列の最後にプッシュします。所有者数を追跡します。
ステップ2：長さ1の文字列と長さ2の文字列をインプレースソートします。
ステップ3：2つの半分の境界にある「a」のバイナリ検索。
ステップ4：必要に応じて、2桁の文字列を文字と交換します。
とはいえ、このアプローチは機能しますが、正規表現を使用せず、int以外の値をintとして解析しようとはしません-お勧めしません。既に提案されている他のアプローチよりも大幅に多くのコードを記述します。あなたがやろうとしていることの要点を分かりにくくします。突然2文字の文字列または3桁の文字列を取得した場合は機能しません。等。私はそれを含めて、あなたがどのように問題を異なって見ることができるかを示し、代替ソリューションを考え出す。
シュワルツ変換を使用して、O（n）変換を実行します。
private class Normalized : IComparable<Normalized> {
private readonly string str;
private readonly int val;
public Normalized(string s) {
str = s;
val = 0;
foreach (char c in s) {
val *= 10;
if (c >= '0' && c <= '9')
val += c - '0';
else
val += 100 + c;
}
}
public String Value { get { return str; } }
public int CompareTo(Normalized n) { return val.CompareTo(n.val); }
};
private static Normalized In(string s) { return new Normalized(s); }
private static String Out(Normalized n) { return n.Value; }
public static IList<String> MixedSort(List<String> l) {
var tmp = l.ConvertAll(new Converter<String,Normalized>(In));
tmp.Sort();
return tmp.ConvertAll(new Converter<Normalized,String>(Out));
}
同様の問題があり、ここに着陸しました。次の例のように、数値の接尾辞を持つ文字列をソートします。
オリジナル：
"Test2", "Test1", "Test10", "Test3", "Test20"
デフォルトのソート結果：
"Test1", "Test10", "Test2", "Test20", "Test3"
望ましいソート結果：
"Test1", "Test2", "Test3, "Test10", "Test20"
最終的にカスタムComparerを使用しました：
public class NaturalComparer : IComparer
{
public NaturalComparer()
{
_regex = new Regex("\\d+<*>quot;, RegexOptions.IgnoreCase);
}
private Regex _regex;
private string matchEvaluator(System.Text.RegularExpressions.Match m)
{
return Convert.ToInt32(m.Value).ToString("D10");
}
public int Compare(object x, object y)
{
x = _regex.Replace(x.ToString, matchEvaluator);
y = _regex.Replace(y.ToString, matchEvaluator);
return x.CompareTo(y);
}
}
HTH; o）
