3

ここでの説明の用語と複雑さに多少苦労しています。自由に編集してください。

1.000 ～ 20.000 個のオブジェクトがあります。それぞれに、いくつかの名前の単語 (ファースト、セカンド、ミドル、ラスト、タイトルなど) と正規化された数字 (ホーム、ビジネスなど)、電子メール アドレス、または住所や配偶者の名前を含めることができます。

単語部分と数字部分を自由に組み合わせて検索できるようにしたい。
「LL 676」を検索すると、「LL」と「676」を含む文字列を含むすべてのオブジェクトが検索されます。
現在、私はすべてのオブジェクトとすべてのオブジェクトのプロパティを反復処理しており、" " で searchString を分割し、stringInstance.Contains(searchword) を実行しています。

これは遅すぎるので、より良い解決策を探しています。

これに適した言語にとらわれないデータ構造は何ですか?
私の場合、C#に必要です。

次のデータ構造は適切なソリューションですか?

これは HashMap/Dictionary に基づいています。
最初に、調べたいすべての名前の部分と電話番号を含む文字列を作成します。1 つの例は次のようになります。「William Bill Henry Gates III 3. +436760000 billgatesstreet 12
」 x.contains(y) を満たすすべての可能な部分文字列 y を作成します。これらの部分文字列をすべてハッシュマップ/辞書に入れました。
ルックアップ/検索では、すべての検索ワードの検索を呼び出し、結果を結合するだけです。当然、検索速度は非常に高速です (ネイティブのハッシュマップ/辞書の速度)。

編集:部分文字列を取得するためによりスマートなアルゴリズムを使用するようになったため、挿入も非常に高速になりました (わずかな時間)。

4

2 に答える 2

1

あなたのアルゴリズムや要件を誤解している可能性がありますが、これは潜在的なパフォーマンスの向上のようです:

foreach (string arg in searchWords)
{
    if (String.IsNullOrEmpty(arg))
        continue;
    tempList = new List<T>();

    if (dictionary.ContainsKey(arg))
        foreach (T obj in dictionary[arg])
        if (list.Contains(obj))
                tempList.Add(obj);
    list = new List<T>(tempList);
}

アイデアは、この前に最初の検索単語を個別に実行し、後続のすべての単語のみを searchWords リストに入れることです。

これにより、最後の foreach ループを完全に削除できるはずです。結果は、最初に単一の単語に一致するすべてのものを積み上げ、最後にそれらをフィルタリングするのではなく、すべての検索単語に一致し続ける限りリストに残ります。

于 2014-03-15T17:32:52.820 に答える
0

誰かが私の解決策を気にかけている場合:
免責事項:
これはラフ ドラフトにすぎません。
私はいくつかの模擬テストを行っただけで、再テストせずに多くのことを書きました.
コードを修正しました。挿入は、無限に高速な 2^n-1 ではなく ((n^2)/2)+(n/2) になりました。単語の長さは関係ありません。

namespace MegaHash
{
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Threading.Tasks;

public class GenericConcurrentMegaHash<T>
{
    // After doing a bulk add, call AwaitAll() to ensure all data was added!
    private ConcurrentBag<Task> bag = new ConcurrentBag<Task>();

    private ConcurrentDictionary<string, List<T>> dictionary = new ConcurrentDictionary<string, List<T>>();

    // consider changing this to include for example '-'
    public char[] splitChars;

    public GenericConcurrentMegaHash()
        : this(new char[] { ' ' })
    {
    }

    public GenericConcurrentMegaHash(char[] splitChars)
    {
        this.splitChars = splitChars;
    }

    public void Add(string keyWords, T o)
    {
        keyWords = keyWords.ToUpper();

        foreach (string keyWord in keyWords.Split(splitChars))
        {
            if (keyWord == null || keyWord.Length < 1)
                return;

            this.bag.Add(Task.Factory.StartNew(() => { AddInternal(keyWord, o); }));
        }
    }

    public void AwaitAll()
    {
        lock (this.bag)
        {
            foreach (Task t in bag)
                t.Wait();

            this.bag = new ConcurrentBag<Task>();
        }
    }

    private void AddInternal(string key, T y)
    {
        for (int i = 0; i < key.Length; i++)
        {
            for (int i2 = 0; i2 < i + 1; i2++)
            {
                string desire = key.Substring(i2, key.Length - i);

                if (dictionary.ContainsKey(desire))
                {
                    List<T> l = dictionary[desire];
                    lock (l)
                    {
                        try
                        {
                            if (!l.Contains(y))
                                l.Add(y);
                        }
                        catch (Exception ex)
                        {
                            ex.ToString();
                        }
                    }
                }
                else
                {
                    List<T> l = new List<T>();
                    l.Add(y);
                    dictionary[desire] = l;
                }
            }
        }
    }

    public IList<T> FulltextSearch(string searchString)
    {
        searchString = searchString.ToUpper();

        List<T> list = new List<T>();

        string[] searchWords = searchString.Split(splitChars);

        foreach (string arg in searchWords)
        {
            if (arg == null || arg.Length < 1)
                continue;

            if (dictionary.ContainsKey(arg))
                foreach (T obj in dictionary[arg])
                    if (!list.Contains(obj))
                        list.Add(obj);
        }

        List<T> returnList = new List<T>();

        foreach (T o in list)
        {
            foreach (string arg in searchWords)
                if (dictionary[arg] == null || !dictionary[arg].Contains(o))
                    goto BREAK;
            returnList.Add(o);
        BREAK:
            continue;
        }

        return returnList;
    }
}

}

于 2014-03-14T23:19:19.437 に答える