Вопрос по list, string, performance, c# – поиск списка <string> для строки .StartsWith ()

4

у меня есть

<code>List<string>
</code>

с 1500 строк. Теперь я использую следующий код, чтобы извлечь только строку, начинающуюся со строки prefixText.

<code>foreach(string a in <MYLIST>)
{            
    if(a.StartsWith(prefixText, true, null))
    {
        newlist.Add(a);                   
    }            
}
</code>

Это довольно быстро, но я ищу Google быстро. Теперь мой вопрос: если я упорядочу Список в алфавитном порядке, то сравните символ за символом, могу ли я сделать это быстрее? Или какие-либо другие предложения по ускорению?

Вы заполняете свой список при каждой загрузке страницы? walther
Как жаль, что вы задали вопрос на 1500. Вы должны были задать его на 150000, чтобы мы получили более дружественные ответы. Shimmy
Почему у тебя в списке 1500 строк? Откуда вы берете свои ценности? DB? walther
он приходит из БД на page_Load, затем в список, затем в кэш, затем я читаю список из кэша здесь Scott Selby
для сейчас да, просто тестирование, чтобы получить его как можно быстрее, его можно легко переместить в Page_Init или любое количество нескольких решений, как только я запустил это быстро Scott Selby

Ваш Ответ

10   ответов
1

Вы можете искать его параллельно с простым разделением и преодолением проблемы. Искать каждую половину списка в двух (или разделить на три, четыре, ..., части) разных заданий / потоков.

Или вместо этого храните строки в (не двоичном) дереве. Будет O (log n).

отсортировано в алфавитном порядке, вы можете сделать бинарный поиск (вроде того же, что и предыдущий)

Согласен. 1500 мало кому. Тем не менее, есть более эффективные алгоритмы поиска префиксов, чем ваши три варианта. Смотрите мой ответ ниже. George Mamaladze
Да @ ачитака-сан и Дуглас ответят O (1) чётно. Дерево префиксов - это мой второй пункт выше, но он не так хорошо описан, как ваше решение (за которое я ранее проголосовал). Должно быть, было более ясно, возможно. На самом деле это не O (log n), хотя, как я уже говорил, зависит от строк и ключа, поэтому не связано с этим (см. Ссылку на Witipedia от Achitaka-san или ваш любимый учебник по структуре данных). В худшем случае строки длинные и отличаются только концом, например и т. Д. И т. Д. Mattias Isegran Bergander
+ 1 для разделяй и властвуй Dene B
13

1500 не является бинарным поиском в огромном количестве в отсортированном списке. Тем не менее, наиболее эффективные алгоритмы поиска префиксов основаны на структуре данных с именем Trie или Prefix Tree. Видеть:http: //en.wikipedia.org/wiki/Tri

Следующая картинка демонстрирует идею очень кратко:

Для реализации c # см. Например .NET СТРУКТУРЫ ДАННЫХ ДЛЯ ПРЕФИКСНОГО ПОИСКА СТРОК И ПОИСКА (INFIX) ПОИСКА ДЛЯ ОСУЩЕСТВЛЕНИЯ АВТОЗАПОЛНЕНИЯ И INTELLI-SENSE

Хороший! Ты избил меня на 1 минуту ... Chris Gessler
4

вы можете использовать вариант бинарный поиск чтобы сделать это намного быстрее.

В качестве отправной точки будет возвращен индекс одной из строк, соответствующих префиксу, поэтому вы можете смотреть вперед и назад в списке, чтобы найти остальные:

public static int BinarySearchStartsWith(List<string> words, string prefix, int min, int max) {
  while (max >= min) {
    int mid = (min + max) / 2;
    int comp = String.Compare(words[mid].Substring(0, prefix.Length), prefix);
    if (comp < 0) {
      min = mid + 1;
    } else if (comp > 0) {
      max = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}

int index = BinarySearchStartsWith(theList, "pre", 0, theList.Count - 1);
if (index == -1) {
  // not found
} else{
  // found
}

Примечание: если вы используете префикс, который длиннее любой из сравниваемых строк, он сломается, поэтому вам может понадобиться выяснить, как вы хотите с этим справиться.

короткий пример того, как вызвать это было бы удобно. Например, параметры min и max могут быть неочевидными? vidstige
@ vidstige: Да, вы правы. Я добавил это. Guffa
.Net уже имеет Array.BinarySearch L.B
4

кости данных и высокой производительности. Первое место: все префиксы хранятся в словаре: ключ - префикс, значения - элементы, соответствующие префиксу.

Вот простая реализация этого алгоритма:

public class Trie<TItem>
{
    #region Constructors

    public Trie(
        IEnumerable<TItem> items,
        Func<TItem, string> keySelector,
        IComparer<TItem> comparer)
    {
        this.KeySelector = keySelector;
        this.Comparer = comparer;
        this.Items = (from item in items
                      from i in Enumerable.Range(1, this.KeySelector(item).Length)
                      let key = this.KeySelector(item).Substring(0, i)
                      group item by key)
                     .ToDictionary( group => group.Key, group => group.ToList());
    }

    #endregion

    #region Properties

    protected Dictionary<string, List<TItem>> Items { get; set; }

    protected Func<TItem, string> KeySelector { get; set; }

    protected IComparer<TItem> Comparer { get; set; }

    #endregion

    #region Methods

    public List<TItem> Retrieve(string prefix)
    {
        return  this.Items.ContainsKey(prefix)
            ? this.Items[prefix]
            : new List<TItem>();
    }

    public void Add(TItem item)
    {
        var keys = (from i in Enumerable.Range(1, this.KeySelector(item).Length)
                    let key = this.KeySelector(item).Substring(0, i)
                    select key).ToList();
        keys.ForEach(key =>
        {
            if (!this.Items.ContainsKey(key))
            {
                this.Items.Add(key, new List<TItem> { item });
            }
            else if (this.Items[key].All(x => this.Comparer.Compare(x, item) != 0))
            {
                this.Items[key].Add(item);
            }
        });
    }

    public void Remove(TItem item)
    {
        this.Items.Keys.ToList().ForEach(key =>
        {
            if (this.Items[key].Any(x => this.Comparer.Compare(x, item) == 0))
            {
                this.Items[key].RemoveAll(x => this.Comparer.Compare(x, item) == 0);
                if (this.Items[key].Count == 0)
                {
                    this.Items.Remove(key);
                }
            }
        });
    }

    #endregion
}
3

Вы можете использоватьPLINQ (Parallel LINQ) чтобы ускорить выполнение:

var newList = list.AsParallel().Where(x => x.StartsWith(prefixText)).ToList()
0

если вы разместите записи в алфавитном порядке, попробуйте бинарный поиск.

Как мне разместить List в алфавитном порядке? Кроме того, это не обязательно должен быть список. Строки изначально поступают из БД в операторе Select, поэтому они могут быть в любом формате Scott Selby
+ 1 за предложение БД вернуть их отсортированные. Mattias Isegran Bergander
Есть несколько способов сделать это. Если бы они пришли из БД, вы могли бы сделать так, чтобы БД выполняла сортировку, которая была бы наиболее эффективной. Или вы можете использовать Ling следующим образом: MyList = UnsortedList.OrderBy (someField). Randy Minder
1

ith:

char first = prefixText[0];

foreach(string a in <MYLIST>) 
    {    
         if (a[0]==first)
         {        
            if(a.StartsWith(prefixText, true, null)) 
            { 
                newlist.Add(a);                    
            }
         }             
    } 
1

что самым быстрым способом было бы создать словарь со всеми возможными префиксами из ваших 1500 строк, эффективно предварительно рассчитав результаты для всех возможных поисков, которые будут возвращать непустые значения. Тогда ваш поиск будет просто поиском по словарю, который завершится за O (1) раз. Это случай торговой памяти (и времени инициализации) для скорости.

private IDictionary<string, string[]> prefixedStrings;

public void Construct(IEnumerable<string> strings)
{
    this.prefixedStrings =
        (
            from s in strings
            from i in Enumerable.Range(1, s.Length)
            let p = s.Substring(0, i)
            group s by p
        ).ToDictionary(
            g => g.Key,
            g => g.ToArray());
}

public string[] Search(string prefix)
{
    string[] result;
    if (this.prefixedStrings.TryGetValue(prefix, out result))
        return result;

    return new string[0];
}
0

нужно ли тебе делать это один или несколько раз.

Если вы находите список StartsWithPrefix только один раз, вы не можете получить быстрее, чем оставить исходный список как есть и делатьmyList.Where(s => s.StartsWith(prefix)). Это смотрит на каждую строку один раз, так что этоO(n)

Если вам нужно несколько раз найти список StartsWithPrefix или, возможно, вы захотите добавить или удалить строки в исходном списке и обновить список StartsWithPrefix, то вам следует отсортировать исходный список и использовать бинарный поиск. Но это будетsort time + search time = O(n log n) + 2 * O(log n)

Если бы вы использовали метод двоичного поиска, вы найдете индексы первого вхождения вашего префикса и последнего вхождения с помощью поиска. Тогда делайmySortedList.Skip(n).Take(m-n) где n - первый индекс, а m - последний индекс.

Редактировать

Подождите минутку, мы используем не тот инструмент для этой работы. Использовать Trie! Если вы поместите все свои строки в Trie вместо списка, все, что вам нужно сделать, это пройтись по Trie с вашим префиксом и взять все слова под этим узлом.

-2

Я хотел бы использовать Linq:

 var query = list.Where(w => w.StartsWith("prefixText")).Select(s => s).ToList();
Это короче, но не быстрее. Так же.Select(s => s) часть не нужна. Guffa

Похожие вопросы