在C#中比较对象的最快方法

Question

我将要编写一个验证城市的应用程序。其中一部分验证是通过匹配国家代码和城市名称（或备选城市名称）来检查城市是否已经在列表中。

我将我的现有城市列表存储为：

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<>更快的集合用于此类比较，并且是否有更快的比较函数可以替换FirstOrDefault()？

编辑

我忘记发布我的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()) + ".");
    }

- Random Developer

---

我认为你最大的性能问题在于“Like”运算符，它是很耗费资源的。难道你不能使用等值比较器吗？ - Andre Calil

你能展示一下你是如何调用这个比较方法的吗？ - HELP_ME

我建议不要在内存中执行此操作，原因有几个。首先，因为您已经看到了这种机制的明显性能问题，但第二，因为您仅出于搜索目的而在内存中保存了大量信息。这应该适用于数据库服务器，并且往返开销非常微不足道。 - Mike Perrenoud

@RandomDeveloper 你想在数据库层面上完成这个任务 - 这是最适合你所需的，也是它最擅长的。 - Mike Perrenoud

@Cyborgx37 我认为通过讨论可以很清楚地看出，有大量数据需要搜索，更糟糕的是需要使用 Like 语句（我理解），因此数据库查询将是最优模式。最后，数据已经从表中提取，因此查询该表对于技术来说非常自然，并且可以正确索引该字段以提供更好的性能。 - Mike Perrenoud

Answer 1

我会使用 HashSet 来存储 CityString 和 CountryCode。就像这样：

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

个人而言，我会在构造函数中执行所有验证，以确保只存在有效的城市对象。

其他需要注意的是性能问题：

1. 如果您要在有效列表中查找，请使用 HashSet。
2. 在适当的情况下使用 IEqualityComparer，并重复使用对象以避免构建/垃圾回收成本。
3. 对于任何需要查找的内容（例如 timeZoneId），请使用 Dictionary。

编辑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使用素数桶，您也会分割列表，从而减少您需要完成的等式数量。

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

- M Afifi

---

请注意，该代码使用了Like运算符 - 除非更改，否则此代码将无法工作。 - Mike Perrenoud

通过将正确的IEqualityComparer传递到Dictionary中，可以轻松解决此问题。如果正确实现，则ContainsKey将匹配您想要的内容。 - M Afifi

所以，如果你在这里重新实现 Like 操作，你并没有解决性能问题 - 对吧？显然，这是一个非常大的数据集，因此进行 Like 操作需要扫描，而如果是直接相等，则有其他选项 - 比如二分查找等更好的方法。如果需要 Like 操作，请让数据库引擎来执行，因为它适合处理这种情况。 - Mike Perrenoud

错误，你错了。他正在以许多方式承担代价，值得作为编辑添加进去。 - M Afifi

我决定采用您的方法，使用字典。我最终选择了使用Dictionary<string，Dictionary<string，City>>，以便可以轻松搜索外部字符串键（国家代码）和内部字符串键（城市名称）的精确匹配。如果这些检查失败，我可以退回到我的linq搜索，但这可以通过仅搜索正确国家的字典来优化。我决定不使用数据库查询，因为随着我通过检查进行的进展，如果它们是新的，我会将城市添加到缓存中。然后，我使用事务查询将它们添加到表中，我需要能够回滚。 - Random Developer

@RandomDeveloper 确保你为字符串使用正确的 IEqualityComparer。例如，如果你关心大小写敏感性或不敏感性的文化差异。 - M Afifi

Answer 2

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

有关.NET中的二叉树实现，请参阅：表示树的对象 编辑： 如果您想要快速搜索一个特别大的集合，并且该集合特别大，那么您最好的选择是对其进行排序，并基于该排序实现一个搜索算法。

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

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

如果您没有键，则无法对数据进行排序。如果无法对数据进行排序，则不会有太多“快速”选项。

编辑2：
我注意到你的“Like”函数经常编辑字符串。编辑字符串是一项非常昂贵的操作。最好在首次加载数据时执行ToLower()和Trim()函数，这样可以大大加快函数的速度。

- JDB

---

为什么要使用二叉树来搜索当前无序列表？ - Dan Puzey

@DanPuzey - 发帖者说他正在构建自己的列表。如果他使用二叉树，它将不是无序的。（或者，用户可以轻松地从无序列表构建二叉树。） - JDB

@DanPuzey - 我还想补充一点，你不能使用二叉树进行“搜索”。你的问题没有意义。（你可以搜索二叉树，但这意味着你需要先构建树。） - JDB

换句话说，二叉树本身不是一种搜索算法，而是一种组织数据的方式，以便进行搜索。 - JDB

是的，我非常清楚二叉树是什么。但是如果你有一堆值，并且想知道某个“测试”值是否在其中（正如问题所示），为什么不使用预先存在的.NET数据结构，例如HashSet，它在性能上可与之相媲美（在查找成员时），并且不需要任何自定义实现？ - Dan Puzey

我不确定HashSet在底层使用的是哪种实现方式。可能是二叉树或类似的结构。我怀疑它没有使用哈希 - 对于长字符串来说，内存要求太大了。无论如何，我不建议自定义实现 - 上面的链接提供了完整、功能齐全的二叉树实现。快速、简单、完成...而且快。仍然是一个合法的答案 - 不同意负评。 - JDB