最快的方法来比较c中的对象＃

我正在编写一个验证一些城市的应用程序。验证的一部分是通过匹配国家代码和城市名称（或alt cityname）来检查城市是否已经在列表中。最快的方法来比较c中的对象＃

我储存我现有的城市名单为：

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（）吗？

编辑

我忘了我的后赞（）函数：

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()) + "."); 
    }

来源

2012-07-24 Random Developer

我相信你最大的性能问题是'Like'运营商，这是昂贵的。你不能简单地使用一个相等比较器吗？ – 2012-07-24 13:06:06

你能告诉我们你是怎么称呼这个比较方法 – 2012-07-24 13:09:36

我建议不要在内存中这样做，原因有两个。首先是因为你已经看到这个机制存在明显的性能问题，其次是因为你在内存中保存了大量的信息，严格来说是为了搜索它。这适用于数据库服务器，并且往返开销非常微不足道。 – 2012-07-24 13:15:26

我会用一个HashSet的CityString和COUNTRYCODE。喜欢的东西

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

等等

个人而言，我会做所有的验证在构造函数中，以确保只有合法市物体存在。

其他的事情需要提防的性能

使用HashSet的，如果你在一个有效的清单中找到它。
在适当情况下使用IEqualityComparer，重用该对象以避免构建/ GC成本。
使用字典任何你需要查找（如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-24 13:13:36

请注意，代码使用Like运算符 - 此代码将不起作用，除非发生更改。 – 2012-07-24 13:25:19

通过将正确的IEqualityComparer传递到Dictionary中，可以很容易地进行修复。然后，ContainsKey会匹配您正在执行的操作。 – 2012-07-24 13:27:33

因此，如果您重新实施Like操作，那么您并未解决性能问题 - 是的？这显然是一个非常大的数据集，所以做一个Like需要扫描，因为如果它是直接相等的话，还有其他选项 - 比如二分查找等等。如果Like是必需的 - 让数据库引擎执行它，因为它适合它。 – 2012-07-24 13:32:20

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

对于.NET二叉树的实现，请参阅：Objects that represent trees

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

当您想快速搜索并插入相对较少的项目时，二叉树是一个不错的选择。然而，为了保持你的搜索速度，你需要使用一个平衡二叉树。

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

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

编辑2：
我注意到你的函数编辑你的字符串很多。编辑字符串是一项非常昂贵的操作。您最好在执行ToLower()和Trim()函数一次时，最好是在您首次加载数据时。这可能会大大加快你的功能。

来源

2012-07-24 13:32:48 JDB

为什么你会使用二叉树来搜索当前的无序列表？ – 2012-07-24 13:40:24

@DanPuzey - 海报说他正在建立自己的名单。如果他使用二叉树，它不会无序。（或者，用户可以轻松地从无序列表中构建二叉树。） – JDB 2012-07-24 13:41:39

@DanPuzey - 还想补充一点，您不能用二叉树“搜索”。你的问题没有意义。（您可以搜索二叉树，但这意味着您需要先构建树。） – JDB 2012-07-24 14:09:47

最快的方法来比较c中的对象＃

回答

相关问题