3

いくつかの都市を検証するアプリケーションを作成しています。検証の一部は、国コードと都市名 (または代替都市名) を照合して、都市が既にリストに含まれているかどうかを確認することです。

既存の都市リストを次のように保存しています。

public struct City
{
    public int id;
    public string countrycode;
    public string name;
    public string altName;
    public int timezoneId;
}

List<City> cityCache = new List<City>();

次に、国コードや都市名などを含む場所文字列のリストを作成します。この文字列を分割して、都市が既に存在するかどうかを確認します。

string cityString = GetCity(); //get the city string
string countryCode = GetCountry(); //get the country string
city = new City();             //create a new city object
if (!string.IsNullOrEmpty(cityString)) //don't bother checking if no city was specified
{
    //check if city exists in the list in the same country 
    city = cityCache.FirstOrDefault(x => countryCode == x.countrycode && (Like(x.name, cityString ) || Like(x.altName, cityString )));
    //if no city if found, search for a single match accross any country
    if (city.id == default(int) && cityCache.Count(x => Like(x.name, cityString ) || Like(x.altName, cityString )) == 1)
        city = cityCache.FirstOrDefault(x => Like(x.name, cityString ) || Like(x.altName, cityString ));
}

if (city.id == default(int))
{
    //city not matched
}

空港や国などの他のオブジェクトも同じ方法でチェックしているため、これは多くのレコードにとって非常に遅いです。これをスピードアップする方法はありますか？List<> よりも高速なこの種の比較のコレクションはありますか? また、FirsOrDefault() という高速な比較関数はありますか?

編集

Like() 関数を投稿するのを忘れていました:

bool Like(string s1, string s2)
    {
        if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2))
            return s1 == s2;
        if (s1.ToLower().Trim() == s2.ToLower().Trim())
            return true;

        return Regex.IsMatch(Regex.Escape(s1.ToLower().Trim()), Regex.Escape(s2.ToLower().Trim()) + ".");
    }
4

2 に答える 2

1

CityString と CountryCode には HashSet を使用します。何かのようなもの

var validCountryCode = new HashSet<string>(StringComparison.OrdinalIgnoreCase);
if (validCountryCode.Contains(city.CountryCode))
{
}

等...

個人的には、有効な City オブジェクトのみが存在することを確認するために、コンストラクターですべての検証を行います。

パフォーマンスのために注意すべきその他の事項

  1. 有効なリストで検索する場合は、HashSet を使用します。
  2. 必要に応じて IEqualityComparer を使用し、オブジェクトを再利用して構築/GC コストを回避します。
  3. 検索する必要があるものには辞書を使用します (例: timeZoneId)

編集 1

あなたはcityCacheです

var cityCache = new Dictionary<string, Dictionary<string, int>>();
var countryCode = "";
var cityCode = "";
var id = x;

public static IsCityValid(City c)
{
     return
         cityCache.ContainsKey(c.CountryCode) &&
         cityCache[c.CountryCode].ContainsKey(c.CityCode) &&
         cityCache[c.CountryCode][c.CityCode] == c.Id;  
}

編集 2

これを説明する必要はないと思いましたが、コメントに基づいて、おそらく.

FirstOrDefault()O(n) 操作です。基本的に、リスト内の何かを見つけようとするたびに、幸運でリストの最初にある場合と、不運でリストの最後の平均である場合があります.Count / 2.一方、辞書O(1) ルックアップになります。IEqualtiyComparer を使用して、HashCode() を生成し、それが格納されているバケットを検索します。衝突が大量にある場合にのみ、Equals を使用して、同じバケット内のもののリストで求めているものを見つけます。品質の低い HashCode() でも (常に同じ HashCode を返さない)、Dictionary/HashSet素数バケットを使用すると、リストを分割して、完了する必要がある等式の数を減らすことができます。

したがって、10 個のオブジェクトのリストは、平均して LIKE を 5 回実行していることを意味します。以下と同じ 10 個のオブジェクトのディクショナリ (HashCode の品質によって異なります) は、わずか 1 回の呼び出しに 1 回のHashCode()呼び出しが続く可能性がありEquals()ます。

于 2012-07-24T13:13:36.213 に答える
0

これは二分木の良い候補のように思えます。

.NET でのバイナリ ツリーの実装については、ツリーを表すオブジェクトを参照してください。

編集:
コレクションをすばやく検索したい場合、そのコレクションが特に大きい場合は、コレクションを並べ替えて、その並べ替えに基づいて検索アルゴリズムを実装するのが最善の方法です。

二分木は、すばやく検索し、アイテムを比較的まれに挿入する場合に適したオプションです。ただし、検索を迅速に行うには、バランス バイナリ ツリーを使用する必要があります。

ただし、これが適切に機能するためには、都市に使用する標準のキーも必要です。数値キーが最適ですが、文字列も問題なく機能します。都市を他の情報 (州や国など) と連結すると、素敵な一意のキーが得られます。大文字と小文字を区別しないキーを取得するために、大文字と小文字をすべて大文字または小文字に変更することもできます。

キーがない場合、データを並べ替えることができません。データを並べ替えることができない場合、多くの「迅速な」オプションはありません。

編集 2:
Like 関数が文字列を頻繁に編集していることに気付きました。文字列の編集は、非常にコストのかかる操作です。できれば最初にデータをロードするときに、 ToLower()and関数を 1 回実行する方がはるかに良いでしょう。Trim()これにより、おそらく関数が大幅に高速化されます。

于 2012-07-24T13:32:48.300 に答える