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))
{
}

ETC...

就我个人而言，我会在构造函数中进行所有验证，以确保仅存在有效的 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) 操作。基本上每次您试图在列表中查找内容时，您可能是幸运的，它是列表中的第一个，或者是不幸的，它是 list.Count / 2 的平均值。另一方面是字典将是 O(1) 查找。使用 IEqualtiyComparer 它将生成一个 HashCode() 并查找它所在的存储桶。如果只有大量冲突，它将使用 Equals 在同一个存储桶中的事物列表中查找您所追求的内容。即使使用质量差的 HashCode() （总是返回相同的 HashCode），因为Dictionary/HashSet使用素数存储桶，您会将列表拆分，从而减少您需要完成的 Equalities 的数量。

因此，包含 10 个对象的列表意味着您平均运行 LIKE 5 次。与下面相同的 10 个对象的字典（取决于 HashCode 的质量），可能只有一个HashCode()调用，然后是一个Equals()调用。

于 2012-07-24T13:13:36.213 回答
0

这听起来像是二叉树的一个很好的候选者。

有关 .NET 中的二叉树实现，请参阅：表示树的对象

编辑：
如果您想快速搜索一个集合，并且该集合特别大，那么您最好的选择是对其进行排序并实现基于该排序的搜索算法。

当您想要快速搜索并相对不频繁地插入项目时，二叉树是一个不错的选择。但是，为了保持快速搜索，您需要使用平衡二叉树。

但是，要使其正常工作，您还需要一个用于您的城市的标准密钥。数字键是最好的，但字符串也可以正常工作。如果您将您的城市与其他信息（例如州和国家/地区）连接起来，您将获得一个很好的唯一键。您还可以将大小写更改为全部大写或小写，以获得不区分大小写的密钥。

如果您没有密钥，则无法对数据进行排序。如果您无法对数据进行排序，那么就不会有很多“快速”选项。

编辑 2：
我注意到您的 Like 函数会大量编辑您的字符串。编辑字符串是一项极其昂贵的操作。最好执行一次ToLower()andTrim()函数，最好是在第一次加载数据时执行。这可能会大大加快您的功能。

于 2012-07-24T13:32:48.300 回答