eta*_*iso 79 c# linq collections string-search winforms
问题:
我有一个大约120,000个用户(字符串)的文本文件,我想将其存储在一个集合中,然后再对该集合执行搜索.
每次用户更改a的文本时都会发生搜索方法TextBox,结果应该是包含文本的字符串TextBox.
我不必更改列表,只需将结果拉出来并将其放入ListBox.
到目前为止我尝试过的:
我尝试了两个不同的集合/容器,我正在从外部文本文件中转储字符串条目(当然是一次):
List<string> allUsers;HashSet<string> allUsers;使用以下LINQ查询:
allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();
我的搜索事件(用户更改搜索文本时触发):
private void textBox_search_TextChanged(object sender, EventArgs e)
{
if (textBox_search.Text.Length > 2)
{
listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();
}
else
{
listBox_choices.DataSource = null;
}
}
结果:
两者都给了我一个很差的响应时间(每次按键之间大约1-3秒).
题:
你认为我的瓶颈在哪里？我用过的系列？搜索方法？都？
如何获得更好的性能和更流畅的功能？
Gro*_*roo 48
您可以考虑在后台线程上执行过滤任务,该线程将在完成时调用回调方法,或者只是在输入更改时重新启动过滤.
一般的想法是能够像这样使用它:
public partial class YourForm : Form
{
private readonly BackgroundWordFilter _filter;
public YourForm()
{
InitializeComponent();
// setup the background worker to return no more than 10 items,
// and to set ListBox.DataSource when results are ready
_filter = new BackgroundWordFilter
(
items: GetDictionaryItems(),
maxItemsToMatch: 10,
callback: results =>
this.Invoke(new Action(() => listBox_choices.DataSource = results))
);
}
private void textBox_search_TextChanged(object sender, EventArgs e)
{
// this will update the background worker's "current entry"
_filter.SetCurrentEntry(textBox_search.Text);
}
}
粗略的草图将是这样的:
public class BackgroundWordFilter : IDisposable
{
private readonly List<string> _items;
private readonly AutoResetEvent _signal = new AutoResetEvent(false);
private readonly Thread _workerThread;
private readonly int _maxItemsToMatch;
private readonly Action<List<string>> _callback;
private volatile bool _shouldRun = true;
private volatile string _currentEntry = null;
public BackgroundWordFilter(
List<string> items,
int maxItemsToMatch,
Action<List<string>> callback)
{
_items = items;
_callback = callback;
_maxItemsToMatch = maxItemsToMatch;
// start the long-lived backgroud thread
_workerThread = new Thread(WorkerLoop)
{
IsBackground = true,
Priority = ThreadPriority.BelowNormal
};
_workerThread.Start();
}
public void SetCurrentEntry(string currentEntry)
{
// set the current entry and signal the worker thread
_currentEntry = currentEntry;
_signal.Set();
}
void WorkerLoop()
{
while (_shouldRun)
{
// wait here until there is a new entry
_signal.WaitOne();
if (!_shouldRun)
return;
var entry = _currentEntry;
var results = new List<string>();
// if there is nothing to process,
// return an empty list
if (string.IsNullOrEmpty(entry))
{
_callback(results);
continue;
}
// do the search in a for-loop to
// allow early termination when current entry
// is changed on a different thread
foreach (var i in _items)
{
// if matched, add to the list of results
if (i.Contains(entry))
results.Add(i);
// check if the current entry was updated in the meantime,
// or we found enough items
if (entry != _currentEntry || results.Count >= _maxItemsToMatch)
break;
}
if (entry == _currentEntry)
_callback(results);
}
}
public void Dispose()
{
// we are using AutoResetEvent and a background thread
// and therefore must dispose it explicitly
Dispose(true);
}
private void Dispose(bool disposing)
{
if (!disposing)
return;
// shutdown the thread
if (_workerThread.IsAlive)
{
_shouldRun = false;
_currentEntry = null;
_signal.Set();
_workerThread.Join();
}
// if targetting .NET 3.5 or older, we have to
// use the explicit IDisposable implementation
(_signal as IDisposable).Dispose();
}
}
此外,您应该在处置_filter父级时实际处置实例Form.这意味着您应该打开并编辑您Form的Dispose方法(在YourForm.Designer.cs文件中),如下所示:
// inside "xxxxxx.Designer.cs"
protected override void Dispose(bool disposing)
{
if (disposing)
{
if (_filter != null)
_filter.Dispose();
// this part is added by Visual Studio designer
if (components != null)
components.Dispose();
}
base.Dispose(disposing);
}
在我的机器上,它的工作速度非常快,因此在进行更复杂的解决方案之前,您应该对其进行测试和分析.
话虽这么说,一个"更复杂的解决方案"可能是将最后几个结果存储在一个字典中,然后只有当新条目仅仅是最后一个字符的第一个不同时才过滤它们.
Mat*_*son 36
我已经完成了一些测试,并且搜索了120,000个项目的列表并使用条目填充新列表花费的时间可以忽略不计(即使所有字符串都匹配,也只需要1/50秒).
因此,您所看到的问题必须来自数据源的填充,此处:
listBox_choices.DataSource = ...
我怀疑你只是在列表框中放了太多项目.
也许您应该尝试将其限制为前20个条目,如下所示:
listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text))
.Take(20).ToList();
另请注意(正如其他人所指出的那样)您正在访问TextBox.Text每个项目的属性allUsers.这可以很容易地修复如下:
string target = textBox_search.Text;
listBox_choices.DataSource = allUsers.Where(item => item.Contains(target))
.Take(20).ToList();
但是,我计算了访问TextBox.Text500,000次需要多长时间,它只花了0.7秒,远远低于OP中提到的1-3秒.不过,这是值得的优化.
Bas*_*evs 28
使用后缀树作为索引.或者更确切地说,只需构建一个排序字典,将每个名称的每个后缀与相应名称列表相关联.
输入:
Abraham
Barbara
Abram
结构看起来像:
a -> Barbara
ab -> Abram
abraham -> Abraham
abram -> Abram
am -> Abraham, Abram
aham -> Abraham
ara -> Barbara
arbara -> Barbara
bara -> Barbara
barbara -> Barbara
bram -> Abram
braham -> Abraham
ham -> Abraham
m -> Abraham, Abram
raham -> Abraham
ram -> Abram
rbara -> Barbara
搜索算法
假设用户输入"bra".
这些树设计用于快速搜索子串.它的性能接近于O(log n).我相信这种方法的工作速度足以让GUI线程直接使用.此外,由于没有同步开销,它将比线程解决方案更快地工作.
Den*_*nis 15
您需要文本搜索引擎(如Lucene.Net)或数据库(您可能需要考虑嵌入式搜索引擎,如SQL CE,SQLite等).换句话说,您需要一个索引搜索.基于散列的搜索在这里不适用,因为您搜索子字符串,而基于散列的搜索很适合搜索精确值.
否则,它将是循环遍历集合的迭代搜索.
ani*_*ine 11
在另一个线程上运行搜索,并在该线程运行时显示一些加载动画或进度条.
您也可以尝试并行化LINQ查询.
var queryResults = strings.AsParallel().Where(item => item.Contains("1")).ToList();
这是一个演示AsParallel()的性能优势的基准:
{
IEnumerable<string> queryResults;
bool useParallel = true;
var strings = new List<string>();
for (int i = 0; i < 2500000; i++)
strings.Add(i.ToString());
var stp = new Stopwatch();
stp.Start();
if (useParallel)
queryResults = strings.AsParallel().Where(item => item.Contains("1")).ToList();
else
queryResults = strings.Where(item => item.Contains("1")).ToList();
stp.Stop();
Console.WriteLine("useParallel: {0}\r\nTime Elapsed: {1}", useParallel, stp.ElapsedMilliseconds);
}
And*_*ris 11
我做了一些分析.
(更新3)
2.500.000记录的初始测试运行时间为20.000毫秒.
头号罪魁祸首是对textBox_search.Text内线的呼唤Contains.这使得每个元素的调用get_WindowText成为文本框的昂贵方法.只需将代码更改为:
var text = textBox_search.Text;
listBox_choices.DataSource = allUsers.Where(item => item.Contains(text)).ToList();
将执行时间缩短为1.858ms.
另外两个重要的瓶颈现在是调用string.Contains(大约45%的执行时间)和列表框元素的更新set_Datasource(30%).
我们可以通过创建一个后缀树来在速度和内存使用之间进行权衡,因为Basilevs建议减少必要的比较数量,并在按键后从搜索推送一些处理时间到从文件中加载名称.可能对用户来说更可取.
为了提高将元素加载到列表框中的性能,我建议只加载前几个元素,并向用户表明还有其他元素可用.这样,您可以向用户提供有关结果的反馈,以便他们可以通过输入更多字母或按一下按钮加载完整列表来优化搜索.
使用BeginUpdate并EndUpdate没有改变执行时间set_Datasource.
正如其他人在这里指出的那样,LINQ查询本身运行得非常快.我相信你的瓶颈是列表框本身的更新.你可以尝试类似的东西:
if (textBox_search.Text.Length > 2)
{
listBox_choices.BeginUpdate();
listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();
listBox_choices.EndUpdate();
}
我希望这有帮助.
WinForms ListBox控件确实是你的敌人.加载记录的速度很慢,ScrollBar会跟你一起显示所有120,000条记录.
尝试使用一个老式的DataGridView数据源,使用单个列[UserName]来保存数据:DataTable:
private DataTable dt;
public Form1() {
InitializeComponent();
dt = new DataTable();
dt.Columns.Add("UserName");
for (int i = 0; i < 120000; ++i){
DataRow dr = dt.NewRow();
dr[0] = "user" + i.ToString();
dt.Rows.Add(dr);
}
dgv.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.Fill;
dgv.AllowUserToAddRows = false;
dgv.AllowUserToDeleteRows = false;
dgv.RowHeadersVisible = false;
dgv.DataSource = dt;
}
然后在TextBox的TextChanged事件中使用DataView来过滤数据:
private void textBox1_TextChanged(object sender, EventArgs e) {
DataView dv = new DataView(dt);
dv.RowFilter = string.Format("[UserName] LIKE '%{0}%'", textBox1.Text);
dgv.DataSource = dv;
}
首先,我会改变ListControl您查看数据源的方式,将结果转换IEnumerable<string>为List<string>.特别是当你输入几个字符时,这可能是低效的(并且不需要).不要制作数据的大量副本.
.Where()结果包装到一个只实现IList(搜索)所需内容的集合中.这将节省您为每个键入的字符创建一个新的大列表.第二步是当小的足够时不要在大列表中搜索.当用户开始键入"ab"并添加"c"时,您不需要在大列表中进行研究,在过滤列表中搜索就足够了(并且更快).每次都可以进行精确搜索,每次都不要进行全面搜索.
第三步可能更难:保持数据组织快速搜索.现在,您必须更改用于存储数据的结构.想象一下这样的树:
A B C Add Better Ceil Above Bone Contour
这可以简单地用数组实现(如果你使用ANSI名称,否则字典会更好).像这样构建列表(插图目的,它匹配字符串的开头):
var dictionary = new Dictionary<char, List<string>>();
foreach (var user in users)
{
char letter = user[0];
if (dictionary.Contains(letter))
dictionary[letter].Add(user);
else
{
var newList = new List<string>();
newList.Add(user);
dictionary.Add(letter, newList);
}
}
然后使用第一个字符完成搜索:
char letter = textBox_search.Text[0];
if (dictionary.Contains(letter))
{
listBox_choices.DataSource =
new MyListWrapper(dictionary[letter].Where(x => x.Contains(textBox_search.Text)));
}
请注意我MyListWrapper()在第一步中使用了建议(但为了简洁,我省略了第二个建议,如果您为字典键选择正确的大小,您可以保持每个列表简短且快速 - 可能 - 避免其他任何事情).此外请注意,您可以尝试使用前两个字符作为字典(更多列表和更短).如果你扩展这个你将有一棵树(但我不认为你有这么大的项目).
字符串搜索有许多不同的算法(具有相关的数据结构),仅举几例:
关于并行搜索的几句话.这是可能的,但它很少是微不足道的,因为使其并行的开销可以比搜索本身高得多.我不会并行执行搜索(分区和同步将很快变得过于庞大并且可能很复杂)但我会将搜索移动到单独的线程中.如果主线程不忙,用户在打字时不会感到任何延迟(他们不会注意列表是否会在200毫秒后出现但如果他们输入后需要等待50毫秒,他们会感到不舒服) .当然搜索本身必须足够快,在这种情况下,你不使用线程来加速搜索,但保持你的UI响应.请注意,单独的线程不会使您的查询更快,它不会挂起UI但如果您的查询很慢,它在单独的线程中仍然会很慢(此外,您还必须处理多个顺序请求).
| 归档时间： |
|
| 查看次数： |
18655 次 |
| 最近记录： |