Поиск лучшей позиции для элемента в списке

Question

У меня есть коллекция списков, которая заполняется в определенном порядке (требуется, чтобы этот порядок не мог быть изменен). Этот список содержит объекты типа объекта.

После первоначального заполнения списка мне нужно вставить еще несколько объектов, которые поступают из другого источника данных. Эти объекты необходимо вставить в определенную позицию, чтобы сортировка была правильной.

Например, если в начальном списке есть следующие элементы

1. AAA
2. AAB
3. AAC
4. ACC
5. ADA

После начального заполнения я хочу вставить элемент "ABB", его нужно вставить между 3 и 4.

На данный момент у меня есть следующий метод нахождения правильной позиции для новых элементов.

    private static int FindPositionForArticle(string word)        
    {
        string key = word.ToLower();
        for (int i = word.Length; i >= 0; i--)
        {
            if(i < word.Length)
                key = key.Remove(i, 1);

            int pos = 0;
            int insertPos = 0;
            foreach(ArticleEntity article in list)
            {
                if(article.Text.ToLower().StartsWith(key))
                    insertPos = pos;
                else if (!article.Text.ToLower().StartsWith(key) && insertPos > 0)
                    return insertPos++;
                pos++;
            }
        }
        return 0;
    }

Цель идеи этого метода:

1. Возьмите «слово», которое нужно вставить, и попытайтесь найти положение элемента с тем же именем, что и «слово»

2. Если ничего не найдено, удалите последний символ из слова и повторите поиск.

3. Повторять удаление последних символов, пока не будет найдена лучшая позиция.

К сожалению, в моих методах есть ошибки (реализованы неправильно). В настоящее время мои методы предполагают, что наилучшая позиция будет 0, что совершенно неверно.

Если вы хотите поиграть с моим примером кода, вы можете скачать его по адресу:

http://dl.getdropbox.com/u/204110/FindPosition.cs.txt

Заранее спасибо.

Answer 1

int index = list.BinarySearch(word);

Если индекс положительный или равен нулю, элемент найден в списке. Если оно отрицательное, оно содержит побитовое дополнение индекса следующего наивысшего элемента в списке.

Итак, для этого:

List<string> list = new List<string>{"AAA","AAB","AAC","ACC","ADA"};
int index = list.BinarySearch("ABB"); // => -4
int insertIndex = ~index; // => 3
list.Insert(insertIndex, "ABB");

Answer 2

Поскольку этот список, который вы используете, доступен через его индекс, вы можете захотеть реализовать бинарный поиск, аналогичный тому, который дал Крис Доггетт. Это даст вам лучшее время выполнения, чем просмотр списка, поскольку вы в настоящее время последовательно его реализуете:

Ваша среда выполнения в настоящее время линейна по отношению к количеству элементов в списке, и если вы вставите n таких элементов, вы получите время выполнения около n ² операций.

Используя бинарный поиск (как, впрочем, SortedList делает внутренне), вы получите гораздо лучшую среду выполнения log2 (n) для каждой вставки, например, * n *** log2 (n) * общее время выполнения при вставке n элементов.

Основная идея бинарного поиска проста:

1. Элемент списка

2. Сначала вы берете полный диапазон в качестве возможного положения (слева = 0, справа = текущий счет в списке)

3. Если слева равно вправо, вы нашли подходящую позицию

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

   • Если результат сравнения <0, вы устанавливаете право на средний индекс-1, поэтому диапазон поиска для следующей итерации сбрасывается в левую половину списка </li>
   • Если результат больше 0, вы устанавливаете влево средний индекс + 1, так что следующий поиск будет в правой части
   • В противном случае сравнение равно 0, и вы получаете дубликат, обрабатываете по своему усмотрению (игнорируйте или вставляете с тем же индексом) и прерываете цикл (см. 5).
5. Петля на 3 .; диапазон поиска теперь меньше ...

Answer 3

Не лучше ли работает SortedList типа string?

Answer 4

Ваша коллекция нуждается в , чтобы быть List?

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

1. Вставьте все ваши начальные элементы в кучу
2. Позже, вставьте дополнительные элементы точно таким же образом
3. Считайте каждый элемент в отсортированном порядке из кучи в List.

Каждый из этих шагов - только O (log n) времени на объект. Я уверен, что в C # есть реализация кучи.

Примечание: я имею в виду «кучу» в смысле структуры данных, а не в смысле глобального пула памяти.

Answer 5

Я сделал то, что вы пытаетесь сделать, вот так. У вас есть список ваших объектов ArticleEntity. Вам нужно отсортировать этот список. Итак, прежде всего вам нужно добавить возможность сортировки в вашем классе. Мои примеры в VB, не должно быть слишком сложно конвертировать в C #.

Добавьте сортировку к вашему классу так:

 Public Class ArticleEntity
    Implements IComparable(Of ArticleEntity)

    Public Overloads Function CompareTo(ByVal Other As ArticleEntity) As Integer _
        Implements IComparable(Of ArticleEntity).CompareTo
        Return Me._PropertyToSort.CompareTo(Other._PropertyToSort)
    End Function

Затем, после того, как вы добавите все, что вам нужно добавить в свой список (ArticleEntity), вы можете:

MyListOfArticleEntities.Sort()

Я думаю, это то, что вы ищете. Дайте мне знать, если это не так.

Answer 6

Этот код:

    private static System.Collections.SortedList list = new System.Collections.SortedList();

    static void Main(string[] args)
    {
        list.Add("AAA" , "AAA");
        list.Add("AAB", "AAB");
        list.Add("AAC", "AAC");
        list.Add("ACC", "ACC");
        list.Add("ADA", "ADA");
        Console.WriteLine("List before");
        for (int j = 0; j < list.Count ; j++)
        {
            Console.WriteLine(list.GetByIndex(j));
        }
        list.Add("ABB","ABB");


        Console.WriteLine(list.IndexOfKey("ABB"));

        for (int j = 0; j < list.Count; j++)
        {
            Console.WriteLine(list.GetByIndex(j));
        }


        Console.ReadLine();

    }

вставляет элемент туда, где он вам нужен.

Или тебе нужно что-то еще ?? Icompare не требуется, вы сортируете общие строки.

Answer 7

Рассматривали ли вы использование структуры данных SortedList ? Если он будет содержать сложные типы данных, которые необходимо отсортировать определенным образом, вы можете создать его, указав объект IComparer .

Единственное, что должен сделать IComparer, - это определить, принадлежит ли один элемент до или после другого. Учитывая это, SortedList будет правильно хранить порядок.

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