6

我正在开发一个在 Windows Mobile 6 上运行的应用程序，该应用程序需要能够从项目表中检索所有项目，这些项目表中包含项目描述字段中的给定字符串（由最终用户提供）。问题是表中有大约 170,000 个项目。由于我需要在描述中的任何位置返回包含字符串的所有项目，因此我不得不使用 LIKE %string%，这消除了使用索引的任何机会。数据和表结构最初基于 Progress 数据库，该数据库在任何单词索引字段上都有一个精彩的 contains 运算符。我们的移动应用程序并非如此，因为它使用 SQL Server Compact 3.5。

基本上，我的 DAL 运行查询并检索 SqlCeDataReader，然后使用 ItemFactory 创建仅包含匹配项的 List 对象。这显然让我们将域/业务对象与数据访问层分开。

很好，花花公子，除了当我搜索描述中包含“高尔夫”之类的所有项目时检索项目所需的 8m 和 42s。显然，这不是最终用户可接受的时间范围。

我的第一次尝试是使用 SELECT * FROM Item" （在一个主要索引字段上使用 order by 子句）从数据库中检索所有项目。此时，我在运行 SqlCeDataReader 时运行了 IndexOf 检查并有ItemFactory 仅在项目包含请求的描述文本时才将项目添加到 List 对象。这将速度提高到 1m 46s。不是太破旧，但仍然太慢。

然后我尝试了另一种显示承诺的方法......几乎......当应用程序启动时，我尝试创建一个包含数据库中所有项目对象的列表（运行查询并填充整个列表大约需要 2 分钟，但是至少在应用程序初始化时只有一次......仍然......呃）。列表完成后，我可以轻松地在该列表上运行查询，执行以下操作（我希望我的语法是正确的......我现在不在工作，我的电脑上没有 Visual Studio 我我坐在）：

List<Item> specificItems = 
    AllItems.FindAll(i => i.Description.IndexOf(searchString, StringComparison.OrdinalIgnoreCase) >= 0);

这种方法将其降低到 21 秒。非常好（尽管在宏伟的计划中仍然很慢）。但是，问题是如果我从数据库中加载所有项目，内存使用量太大了。在初始加载期间，我实际上不得不切断最后 20,000 个项目（因此 21 秒的时间范围可能更像是 25 秒），因为抛出了 OutOfMemoryException。根据模拟器上的内存管理器，我仍然有大约 20 MB 的可用 RAM，但我听说一个进程只能有 32 MB 或与之关联的 RAM（不确定 WM 6 是否如此，但它似乎所以）。

为了确保这不是因为我使用 List 对象来保存所有项目（我在其构造函数中使用所需的容量对其进行实例化以避免动态调整大小），我还读过它可能会导致额外的内存使用隐式调用 EnsureCapacity，我尝试使用 Item[] 数组（提前调整大小）。这仍然存在内存问题，并且大小差异可以忽略不计。

好吧，足够的漫无边际。我知道我可能不得不限制数据读取器从数据库返回的记录（通过对不同类型字段的一些索引搜索），然后可能会在较小的项目子集上使用 indexOf 以获得最大性能（因此一起跳过 Like 运算符）。这将导致最终用户必须输入的不仅仅是描述搜索（也许是项目层次结构信息来限制要搜索的项目类型）。

有任何想法吗？我会以错误的方式解决这个问题吗？

感谢收听（抱歉这篇文章很长，我有点想大声）。

哦，我应该添加（只是总结）我正在使用的内容：

  • 视窗手机 6
  • Sql Server 精简版 3.5
  • C# 3.5

更新：虽然下面提到的布隆过滤器方法看起来很有趣，但我无法满足一个要求（我没有在上面真正指定）。我无法真正匹配包含在其他单词中的单词（例如“club”不会返回“clubs”）。因此，我被迫完全使用不同的方法（Kent Fredric ......感谢您指出这一点）。我已将 Kent 的答案标记为正确的答案，因为他的方法是满足最多要求的方法（Mitch，你的问题与 Jaunder 建议的 Bloom 过滤器类似）。但是，我也采取了与他不同的方法（目前......）。

我所做的是将所有项目对象拉入内存，只有项目编号和描述（这使其保持在内存限制之下，但是它仍然会导致比我喜欢的更长的初始化......多线程并在幕后加载该信息我猜在应用程序运行时可以解决这个问题）。为了执行我自己编写的包含例程的搜索。该例程是用非托管 c# 代码编写的，该代码使用两个指针和几个循环来运行描述和所需的匹配文本。如果它在描述的任何地方找到匹配项，它会将项目编号添加到数组中。搜索完所有项目后，新的查询将返回数据库并仅获取匹配的项目编号（由于整数字段上的索引，这非常快）。然后这些项目将在包含所有信息的列表中创建（不仅仅是项目编号和描述）。整个操作大约需要 5 - 10 秒（取决于描述），这对于现在来说已经足够了。

我仍然会考虑进一步优化这个（可能能够跟踪搜索词有多少个字符......如果项目描述中剩余的字符少于所需的文本，则循环可以直接继续到下一个项目） .

仍然欢迎任何建议。现在，我已将肯特的回答标记为我的问题的“最正确”。

感谢 Dolch 帮助我编写 contains 例程。

4

3 回答 3

5

如何预处理（一次）项目表（并且需要处理添加到其中的每个新条目），以创建一个单词出现表

CREATE TABLE WordItemOccurance
(
    [Word] varchar(50) not null,

    ItemId int not null
        constraint FK_Items references ItemTable(ID)
)

遍历所有项目，分解成单独的单词，并在找到条目时将条目添加到出现表中。

在 [Word] 上创建聚集索引并在 ItemId 上加入 Item 表应该很快。

于 2008-12-31T01:27:07.377 回答
4

我投票支持Mitch Wheat 的答案，但我也将测试一些技巧以验证其有效性。

我对有一个充满 [char],[int] 的表的最大担心是你可能仍然会发现自己执行大量毫无意义的字符串比较，特别是如果你在这个新表上使用 %word% 。（重复但不匹配我们的搜索条目）。

我可能会选择体验

Words
-----
chars  | word_id 

WordsToEntry
------------
word_id | entry_id

看看数据库开销是否值得缓解这个可能的问题（我无法测试，抱歉）

于 2008-12-31T01:44:39.650 回答
1

您可以尝试使用布隆过滤器。

  1. 维基百科
  2. 使用布隆过滤器
于 2008-12-31T02:23:12.163 回答