Структура данных в C #, которая позволяет Reverse в O (1) - PullRequest
Новая
       34

Структура данных в C #, которая позволяет Reverse в O (1)

2 голосов
/ 25 октября 2019

У меня есть список, который я хочу перебрать, иногда от начала до конца, иногда от конца до начала. Этот список никогда не изменяется, и я буду повторять его несколько раз. Я хотел бы избежать операции обращения к списку в O (n), когда я хочу выполнить итерацию от конца к началу.

Есть ли какая-то структура данных, которая позволяет это?

Я думалчто было бы просто для (вдвойне) реализации LinkedList в C # разрешить такое поведение (сохраняя внутреннюю ссылку на то, что является началом списка), но я не думаю, что это реализовано таким образом. Можете ли вы предоставить ссылку, если я ошибаюсь.

1 Ответ

6 голосов
/ 25 октября 2019

Любая структура данных с прямым индексированным доступом и длиной (массивы, списки, строки, файловые потоки) позволяют представить завершение «обратного» за O (1) времени (обратите внимание, что оно само обратное, очевидно, итерирование всех элементов все равно будет O(n).

Есть несколько примеров в Возможна ли итерация в обратном направлении через foreach? с "возвращением дохода" , предложенным Джоном Скитом - самый гибкий способ (вероятно, чуть менее производительный, чем просто назад for): 

public static IEnumerable<T> FastReverse<T>(this IList<T> items)
{
    for (int i = items.Count-1; i >= 0; i--)
    {
        yield return items[i];
    }
}

Как прокомментировал Патрик Робертс , вы также можете использовать другую структуру данных, которая выглядит как массив - то есть словарь с последовательным int ключи и известные верхние / нижние границы будут работать (примерно так работают массивы JavaScript).

Действительно, двойной связанный список (LinkedList в C #) является предпочтительной структурой данных, когда только вперед и назадитерации необходимы ... но преобразование массива / списка (которое уже дает O (1) способ представления обратной итерации) не стоит. В зависимости от другихпереключение требований на связанный список может быть вполне возможным.

Обратите внимание, что с теоретической точки зрения, если вам все равно нужно перебирать все элементы, то затраты O (n) на реверс не изменяют общую сложность.

...