문자열 컬렉션에서 검색하는 가장 빠른 방법

developer tip

문자열 컬렉션에서 검색하는 가장 빠른 방법

optionbox 2020. 10. 9. 11:05

문자열 컬렉션에서 검색하는 가장 빠른 방법

문제:

컬렉션에 저장하고 나중에 해당 컬렉션에 대해 검색을 수행하려는 약 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 초).

질문:

내 병목이 어디에 있다고 생각하세요? 내가 사용한 컬렉션? 검색 방법? 양자 모두?

더 나은 성능과 더 유창한 기능을 얻으려면 어떻게해야합니까?

완료되면 콜백 메서드를 호출하는 백그라운드 스레드에서 필터링 작업을 수행하거나 입력이 변경되면 필터링을 다시 시작할 수 있습니다.

일반적인 아이디어는 다음과 같이 사용할 수있는 것입니다.

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);
}

내 컴퓨터에서는 매우 빠르게 작동하므로 더 복잡한 솔루션을 찾기 전에이를 테스트하고 프로파일 링해야합니다.

즉, "더 복잡한 솔루션"은 마지막 두 개의 결과를 사전에 저장 한 다음 새 항목이 마지막 문자의 첫 번째 문자 만 다른 것으로 밝혀진 경우에만 필터링하는 것입니다.

몇 가지 테스트를 수행했으며 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.Text50 만 번 액세스하는 데 걸리는 시간을 측정 했고 OP에 언급 된 1 ~ 3 초보다 훨씬 적은 0.7 초만 걸렸습니다. 그래도 이것은 가치있는 최적화입니다.

사용 접미사 트리 인덱스로. 또는 모든 이름의 모든 접미사를 해당 이름 목록과 연결하는 정렬 된 사전을 구축하십시오.

입력 :

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"를 가정합니다.

사용자 입력에 대해 사전을 양분 하여 사용자 입력 또는 이동할 수있는 위치를 찾습니다. 이렇게하면 "barbara"- "bra"보다 낮은 마지막 키를 찾습니다. "브라"의 하한이라고합니다. 검색에는 로그 시간이 걸립니다.
사용자 입력이 더 이상 일치하지 않을 때까지 찾은 키부터 계속 반복합니다. 이것은 "bram"-> Abram 및 "braham"-> Abraham을 줄 것입니다.
반복 결과 (Abram, Abraham)를 연결하고 출력합니다.

이러한 트리는 하위 문자열을 빠르게 검색하도록 설계되었습니다. 성능은 O (log n)에 가깝습니다. 이 접근 방식은 GUI 스레드에서 직접 사용할 수있을만큼 빠르게 작동 할 것이라고 생각합니다. 또한 동기화 오버 헤드가 없기 때문에 스레드 솔루션보다 빠르게 작동합니다.

텍스트 검색 엔진 (예 : Lucene.Net ) 또는 데이터베이스 (예 : SQL CE , SQLite 등 의 임베디드 엔진을 고려할 수 있음 )가 필요합니다. 즉, 색인화 된 검색이 필요합니다. 해시 기반 검색은 하위 문자열을 검색하기 때문에 여기서 적용 할 수 없지만 해시 기반 검색은 정확한 값을 검색하는 데 적합합니다.

그렇지 않으면 컬렉션을 반복하는 반복 검색이됩니다.

"디 바운스"유형의 이벤트를 갖는 것도 유용 할 수 있습니다. 이벤트를 시작하기 전에 변경이 완료 될 때까지 일정 시간 (예 : 200ms)을 기다린다는 점에서 조절과 다릅니다.

참조 디 바운스 및 스로틀 : 시각적 설명 디 바운싱에 대한 자세한 정보를 얻을 수 있습니다. 이 기사는 C # 대신 JavaScript에 초점을 맞추고 있지만 원칙이 적용됩니다.

이것의 장점은 여전히 쿼리를 입력 할 때 검색하지 않는다는 것입니다. 그런 다음 한 번에 두 개의 검색을 수행하려는 시도를 중지해야합니다.

다른 스레드에서 검색을 실행하고 해당 스레드가 실행되는 동안 로딩 애니메이션이나 진행률 표시 줄을 표시합니다.

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);
}

업데이트 2 :

다른 두 가지 중요한 병목 현상은 이제 호출 string.Contains(실행 시간의 약 45 %)과 목록 상자 요소의 업데이트 set_Datasource(30 %)입니다.

Basilevs가 필요한 비교 횟수를 줄이고 키를 누른 후 검색에서 처리 시간을 파일에서 이름을로드 할 때까지 푸시하도록 제안했듯이 Suffix 트리를 생성하여 속도와 메모리 사용량 사이의 균형을 맞출 수 있습니다. 사용자에게 바람직 할 수 있습니다.

목록 상자에 요소를로드하는 성능을 높이려면 처음 몇 개의 요소 만로드하고 사용 가능한 추가 요소가 있음을 사용자에게 표시하는 것이 좋습니다. 이렇게하면 사용자에게 사용 가능한 결과가 있다는 피드백을 제공하여 더 많은 문자를 입력하여 검색을 구체화하거나 버튼을 눌러 전체 목록을로드 할 수 있습니다.

을 사용 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(); }~~

~~이게 도움이 되길 바란다.~~

접두사로만 일치한다고 가정하면 찾고있는 데이터 구조를 "접두사 트리"라고도 하는 trie 라고합니다 . IEnumerable.Where지금 사용하고 있는지 방법은 각 액세스에 대한 당신의 사전에있는 모든 항목을 반복하는 것입니다.

이 스레드 는 C #에서 트라이를 만드는 방법을 보여줍니다.

WinForms ListBox 컨트롤은 실제로 여기에서 적입니다. 레코드를로드하는 속도가 느리고 ScrollBar가 120,000 개의 레코드를 모두 표시하기 위해 싸울 것입니다.

데이터를 보관할 단일 열 [UserName]이있는 DataTable에 데이터 소스가있는 구식 DataGridView를 사용해보십시오.

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. 이렇게하면 입력 된 각 문자에 대한 새로운 큰 목록을 만들 수 있습니다.
대안으로 LINQ를 피하고 더 구체적이고 최적화 된 것을 작성합니다. 목록을 메모리에 보관하고 일치하는 인덱스 배열을 만들고 배열을 재사용하여 각 검색에 대해 재 할당 할 필요가 없습니다.

Second step is to do not search in the big list when small one is enough. When user started to type "ab" and he adds "c" then you do not need to research in the big list, search in the filtered list is enough (and faster). Refine search every time is possible, do not perform a full search each time.

Third step may be harder: keep data organized to be quickly searched. Now you have to change the structure you use to store your data. imagine a tree like this:

A        B         C
 Add      Better    Ceil
 Above    Bone      Contour

This may simply be implemented with an array (if you're working with ANSI names otherwise a dictionary would be better). Build the list like this (illustration purposes, it matches beginning of string):

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);
    }
}

Search will be then done using first character:

char letter = textBox_search.Text[0];
if (dictionary.Contains(letter))
{
    listBox_choices.DataSource =
        new MyListWrapper(dictionary[letter].Where(x => x.Contains(textBox_search.Text)));
}

Please note I used MyListWrapper() as suggested in first step (but I omitted by 2nd suggestion for brevity, if you choose right size for dictionary key you may keep each list short and fast to - maybe - avoid anything else). Moreover note that you may try to use first two characters for your dictionary (more lists and shorter). If you extend this you'll have a tree (but I don't think you have such big number of items).

There are many different algorithms for string searching (with related data structures), just to mention few:

Finite state automaton based search: in this approach, we avoid backtracking by constructing a deterministic finite automaton (DFA) that recognizes stored search string. These are expensive to construct—they are usually created using the powerset construction—but are very quick to use.
Stubs: Knuth–Morris–Pratt computes a DFA that recognizes inputs with the string to search for as a suffix, Boyer–Moore starts searching from the end of the needle, so it can usually jump ahead a whole needle-length at each step. Baeza–Yates keeps track of whether the previous j characters were a prefix of the search string, and is therefore adaptable to fuzzy string searching. The bitap algorithm is an application of Baeza–Yates' approach.
Index methods: faster search algorithms are based on preprocessing of the text. After building a substring index, for example a suffix tree or suffix array, the occurrences of a pattern can be found quickly.
Other variants: some search methods, for instance trigram search, are intended to find a "closeness" score between the search string and the text rather than a "match/non-match". These are sometimes called "fuzzy" searches.

Few words about parallel search. It's possible but it's seldom trivial because overhead to make it parallel can be easily much higher that search itself. I wouldn't perform search itself in parallel (partitioning and synchronization will become soon too expansive and maybe complex) but I would move search to a separate thread. If main thread isn't busy your users won't feel any delay while they're typing (they won't note if list will appear after 200 ms but they'll feel uncomfortable if they have to wait 50 ms after they typed). Of course search itself must be fast enough, in this case you don't use threads to speed up search but to keep your UI responsive. Please note that a separate thread will not make your query faster, it won't hang UI but if your query was slow it'll still be slow in a separate thread (moreover you have to handle multiple sequential requests too).

You could try using PLINQ (Parallel LINQ). Although this does not garantee a speed boost, this you need to find out by trial and error.

I doubt you'll be able to make it faster, but for sure you should:

a) Use the AsParallel LINQ extension method

a) Use some kind of timer to delay filtering

b) Put a filtering method on another thread

Keep some kind of string previousTextBoxValue somewhere. Make a timer with a delay of 1000 ms, that fires searching on tick if previousTextBoxValue is same as your textbox.Text value. If not - reassign previousTextBoxValue to the current value and reset the timer. Set the timer start to the textbox changed event, and it'll make your application smoother. Filtering 120,000 records in 1-3 seconds is OK, but your UI must remain responsive.

You can also try using BindingSource.Filter function. I have used it and it works like a charm to filter from bunch of records, every time update this property with the text being search. Another option would be to use AutoCompleteSource for TextBox control.

Hope it helps!

I would try to sort collection, search to match only start part and limit search by some number.

so on ininialization

allUsers.Sort();

and search

allUsers.Where(item => item.StartWith(textBox_search.Text))

Maybe you can add some cache.

Use Parallel LINQ. PLINQ is a parallel implementation of LINQ to Objects. PLINQ implements the full set of LINQ standard query operators as extension methods for the T:System.Linq namespace and has additional operators for parallel operations. PLINQ combines the simplicity and readability of LINQ syntax with the power of parallel programming. Just like code that targets the Task Parallel Library, PLINQ queries scale in the degree of concurrency based on the capabilities of the host computer.

Introduction to PLINQ

Understanding Speedup in PLINQ

Also you can use Lucene.Net

Lucene.Net is a port of the Lucene search engine library, written in C# and targeted at .NET runtime users. The Lucene search library is based on an inverted index. Lucene.Net has three primary goals:

According to what I have seen I agree with the fact to sort the list.

However to sort when the list is construct will be very slow, sort when building, you will have a better execution time.

Otherwise if you don't need to display the list or to keep the order, use a hashmap.

The hashmap will hash your string and search at the exact offset. It should be faster I think.

Try use BinarySearch method it should work faster then Contains method.

Contains will be an O(n) BinarySearch is an O(lg(n))

I think that sorted collection should work faster on search and slower on adding new elements, but as I understood you have only search perfomance problem.

참고URL : https://stackoverflow.com/questions/21379255/fastest-way-to-search-in-a-string-collection

'developer tip' 카테고리의 다른 글

Java.util.Timer 클래스에서 예약 된 작업을 중지하는 방법 (0)	2020.10.09
부트 스트랩 "툴팁"및 "팝 오버"는 테이블에 추가 크기를 추가합니다. (0)	2020.10.09
Ionic Framework를 사용하여 로그인 / 로그 아웃시 기록 지우기 및 페이지 다시로드 (0)	2020.10.09
Socket.IO 1.x 및 Express 4.x와 세션을 공유하는 방법은 무엇입니까? (0)	2020.10.09
주어진 git 커밋과 관련된 태그를 찾는 방법은 무엇입니까? (0)	2020.10.09

현재글문자열 컬렉션에서 검색하는 가장 빠른 방법

optionbox

문자열 컬렉션에서 검색하는 가장 빠른 방법

문자열 컬렉션에서 검색하는 가장 빠른 방법

최신 정보:

업데이트 2 :

'developer tip' 카테고리의 다른 글

'developer tip'의 다른글

티스토리툴바

문자열 컬렉션에서 검색하는 가장 빠른 방법

문자열 컬렉션에서 검색하는 가장 빠른 방법

최신 정보:

업데이트 2 :

'developer tip' 카테고리의 다른 글

'developer tip'의 다른글

관련글

티스토리툴바