c# - 列表的 Find(s) 方法在 C# 中的工作原理

Question

循环列表的最佳方式是什么？ for循环比众多List类的find方法好吗？另外，如果我像下面提到的那样使用它的查找方法，它是匿名委托(delegate)谓词委托(delegate)的实例，它比使用 lambda 表达式更好吗？哪个执行速度更快？

var result = Books.FindLast(
        delegate(Book bk)
        {
            DateTime year2001 = new DateTime(2001,01,01);
            return bk.Publish_date < year2001;
        });

Answer 1

这是一个复杂的问题，因为它涉及很多不同的主题。

一般来说，委托(delegate)比简单的函数调用慢很多倍，但枚举列表(通过 foreach)也慢得可怕。

如果你真的关心性能(但不要先验地做，个人资料!)你应该避免委托(delegate)和枚举。第一步(只要可能)可以是使用哈希表而不是简单列表。

例子

现在是一些示例，我将以不同的方式编写相同的函数，从更易读(但更慢)到更难读(但更快)。我省略了所有错误检查，但真实世界的函数不应该(至少需要一些断言)。

这个函数使用了LINQ，比较容易理解但是最慢。注意 books可以是通用枚举(不需要是 List<T> )

public static Book FindLastBookPublishedBefore(IEnumerable<Book> books, 
                                               DateTime date)
{
 return books.FindLast(x => x.Publish_date < date);
}

与以前相同，但没有 LINQ。注意这个函数处理一种特殊情况:该列表不包含任何符合条件的图书。

public static Book FindLastBookPublishedBefore(IEnumerable<Book> books,
                                               DateTime date)
{
 Book candidate = null;
 foreach (Book book in books)
 {
  if (candidate == null || candidate.Publish_date > book.Publish_date)
   candidate = book;
 }

 return candidate;
}

和之前一样但是没有枚举，注意这个函数处理一种特殊情况:该列表不包含任何符合条件的图书。

public static Book FindLastBookPublishedBefore(List<Book> books,
                                               DateTime date)
{
 Book candidate = null;
 for (int i=0; i < books.Count; ++i)
 {
  if (candidate == null || candidate.Publish_date > books[i].Publish_date)
   candidate = books[i];
 }

 return candidate;
}

与以前相同，但带有 SortedList<T>正如@MaratKhasanov 所建议的那样。请注意，使用此容器，您将在搜索过程中获得良好的性能，但插入新元素可能比普通未排序列表慢(因为列表本身必须保持排序)。如果列表中的元素数量非常多，您可能会考虑使用 Hashtable 编写自己的排序列表。 (例如，使用年份作为第一级的关键字)。

public static Book FindLastBookPublishedBefore(SortedList<Book> books,
                                               DateTime date)
{
 Book candidate = null;
 for (int i=0; i < books.Count; ++i)
 {
  DateTime publishDate = books[i].Publish_date;

  if (publishDate > date)
   return candidate;

  if (candidate == null || candidate.Publish_date > publishDate)
   candidate = books[i];

 }

 return candidate;
}

现在是一个稍微复杂一点但具有最佳搜索性能的示例。算法来源于一个普通的binary search (注意，如果你想匹配第一个匹配谓词的元素，你可以直接使用List.BinarySearch方法)。
请注意，代码未经测试，也可以优化，请将其视为示例。

public static Book FindLastBookPublishedBefore(List<Book> books,
                                               DateTime date)
{
 int min = 0, max = books.Count;
 Book candidate = null;

 while (min < max)
 {
  int mid = (min + max) / 2;
  Book book = books[mid];

  if (book.Publish_date > date)
   max = mid - 1;
  else
  {
   candidate = book;
   ++min;
  }

  if (min >= max)
   break;
 }

  return candidate;
}

在移动到更复杂的容器之前，您可能会考虑保留您的 SortedList<T>未排序，直到第一次搜索。它会非常慢(因为它也会对列表进行排序)但插入将与普通列表一样快(但你必须尝试使用​​真实世界的数据)。总之最后一个算法可以优化很多。

也许如果您的收藏中有太多项目以至于您无法使用普通 收藏来管理它们，您可能会考虑将所有内容移动到数据库中...大声笑