C # Collection - упорядочение по элементу (поворот)

Question

У меня есть коллекция IEnumerable<Point>.Допустим, он содержит 5 точек (на самом деле это больше похоже на 2000)

Я хочу упорядочить эту коллекцию так, чтобы конкретная точка в коллекции стала первым элементом, поэтому она в основном отбирает коллекцию в определенной точке.и воссоединение их вместе.

Таким образом, мой список из 5 пунктов:

{0,0}, {10,0}, {10,10}, {5,5}, {0,10}

Переупорядоченный относительно элемента по индексу 3 станет:

{5,5}, {0,10}, {0,0}, {10,0}, {10,10}

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

Answer 1

var list = new[] { 1, 2, 3, 4, 5 };

var rotated = list.Skip(3).Concat(list.Take(3));

// rotated is now {4, 5, 1, 2, 3}

Answer 2

В этом случае простой копией массива является O (n), что должно быть достаточно для почти всех реальных целей.Тем не менее, я признаю, что в некоторых случаях - если это часть глубоко внутри многоуровневого алгоритма - это может быть актуально.Кроме того, вам просто нужно перебрать эту коллекцию упорядоченным образом или создать копию?

Связанные списки очень легко реорганизовать подобным образом, хотя доступ к случайным элементам будет более дорогостоящим.В целом, вычислительная эффективность также будет зависеть от того, как точно вы получите доступ к этой коллекции элементов (а также от того, какие они элементы - типы значений или ссылочные типы?).

СтандартСвязанный список .NET, по-видимому, не поддерживает такие ручные манипуляции, но в целом, если у вас есть связанный список, вы можете легко перемещаться по разделам списка так, как вы описываете, просто назначая новые «следующий» и «предыдущий» указателидо конечных точек.

Библиотека коллекций, доступная здесь, поддерживает эту функцию: http://www.itu.dk/research/c5/. В частности, вы ищете LinkedList<T>.Slide() метод, который вы можете использовать для объекта, возвращаемого LinkedList<T>.View().

Answer 3

Версия без перечисления list в два раза, но более высокое потребление памяти из-за T[]:

public static IEnumerable<T> Rotate<T>(IEnumerable<T> source, int count)
{
    int i = 0;

    T[] temp = new T[count];

    foreach (var item in source)
    {
        if (i < count)
        {
            temp[i] = item;
        }
        else
        {
            yield return item;
        }

        i++;
    }

    foreach (var item in temp)
    {
        yield return item;
    }
}

[Test]
public void TestRotate()
{
    var list = new[] { 1, 2, 3, 4, 5 };

    var rotated = Rotate(list, 3);

    Assert.That(rotated, Is.EqualTo(new[] { 4, 5, 1, 2, 3 }));
}

Примечание: Добавить проверку аргументов.

Answer 4

Наивной реализацией, использующей linq, было бы:

IEnumerable x = new[] { 1, 2, 3, 4 };
var tail = x.TakeWhile(i => i != 3);
var head = x.SkipWhile(i => i != 3);
var combined = head.Concat(tail); // is now 3, 4, 1, 2

Здесь происходит то, что вы выполняете двойные сравнения, необходимые для получения вашего первого элемента в комбинированной последовательности.Решение читаемо и компактно, но не очень эффективно.Решения, описанные другими участниками, могут быть более эффективными, поскольку они используют специальные структуры данных в виде массивов или списков.

Answer 5

Другой альтернативой методу Linq, показанному ulrichb, будет использование очереди Queue Class (коллекция fifo) для индекса и добавление в очередь тех, которые вы убрали.