3

我在这里解释的术语和复杂性有些挣扎，请随时编辑它。

我有 1.000 - 20.000 个对象。每一个都可以包含几个名字词（第一，第二，中间，最后，头衔......）和标准化数字（家庭，企业......），电子邮件地址甚至物理地址和配偶姓名。

我想实现一个搜索，使用户可以自由组合单词部分和数字部分。
当我搜索“LL 676”时，我想找到所有包含“LL”和“676”字符串的对象。
目前我正在遍历每个对象和每个对象属性，将 searchString 拆分为“”并执行 stringInstance.Contains(searchword)。

这太慢了，所以我正在寻找更好的解决方案。

什么是合适的与语言无关的数据结构？
就我而言，我需要它用于 C#。

以下数据结构是一个好的解决方案吗？

它基于 HashMap/Dictionary。
首先，我创建了一个字符串，其中包含我想要查看的所有姓名部分和电话号码，一个示例是：“William Bill Henry Gates III 3. +436760000 billgatesstreet 12”：
然后我拆分为“”，每个单词 x我创建了所有可能的子字符串 y 来填充 x.contains(y)。我把这些子字符串中的每一个都放在了 hashmap/dictionary 中。
在查找/搜索时，我只需要调用每个搜索词的搜索并加入结果。自然，查找速度非常快（原生 Hashmap/Dictionary 速度）。

编辑：现在我使用更智能的算法来获取子字符串，插入也非常快（时间很短）。

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 循环。只要结果与每个 searchWord 保持匹配，结果就会保留在您的列表中，而不是最初必须将与单个单词匹配的所有内容堆积起来，然后在最后将它们过滤掉。

于 2014-03-15T17:32:52.820 回答
0

如果有人关心我的解决方案：
免责声明：
这只是一个粗略的草案。
我只做了一些综合测试，我已经写了很多没有再次测试它。
我已经修改了我的代码：插入现在是 ((n^2)/2)+(n/2) 而不是 2^n-1 ，它的速度无限快。字长现在无关紧要。

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 回答