поиск списка <string> для строки .StartsWith ()

у меня есть

<code>List<string>
</code>

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

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

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

 Shimmy25 июл. 2017 г., 02:07
Как жаль, что вы задали вопрос на 1500. Вы должны были задать его на 150000, чтобы мы получили более дружественные ответы.
 Scott Selby06 мая 2012 г., 20:32
для сейчас да, просто тестирование, чтобы получить его как можно быстрее, его можно легко переместить в Page_Init или любое количество нескольких решений, как только я запустил это быстро
 Scott Selby06 мая 2012 г., 20:13
он приходит из БД на page_Load, затем в список, затем в кэш, затем я читаю список из кэша здесь
 walther06 мая 2012 г., 20:17
Вы заполняете свой список при каждой загрузке страницы?
 walther06 мая 2012 г., 20:06
Почему у тебя в списке 1500 строк? Откуда вы берете свои ценности? DB?

Ответы на вопрос(10)

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

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

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

 Chris Gessler06 мая 2012 г., 20:39
Хороший! Ты избил меня на 1 минуту ...

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

 var query = list.Where(w => w.StartsWith("prefixText")).Select(s => s).ToList();
 Guffa06 мая 2012 г., 20:26
Это короче, но не быстрее. Так же.Select(s => s) часть не нужна.

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

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

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

Если вы находите список 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 с вашим префиксом и взять все слова под этим узлом.

Решение Вопроса

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

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

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

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

ith:

char first = prefixText[0];

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

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

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

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

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

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
}

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

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

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
}

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

 vidstige06 мая 2012 г., 20:29
короткий пример того, как вызвать это было бы удобно. Например, параметры min и max могут быть неочевидными?
 Guffa06 мая 2012 г., 20:32
@ vidstige: Да, вы правы. Я добавил это.
 L.B06 мая 2012 г., 20:32
.Net уже имеет Array.BinarySearch

что самым быстрым способом было бы создать словарь со всеми возможными префиксами из ваших 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];
}

Ваш ответ на вопрос