Почему std :: list :: reverse имеет сложность O (n)?

192

Почему обратная функция для std::listкласса в стандартной библиотеке C ++ имеет линейное время выполнения? Я думаю, что для двусвязных списков обратная функция должна была быть O (1).

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

любознательный
источник
18
Я не понимаю, почему люди понижают этот вопрос. Это вполне разумный вопрос. Обращение двусвязного списка должно занять O (1) времени.
Любопытно
46
к сожалению, некоторые люди путают понятия «вопрос хорош» с «вопрос имеет хорошую идею». Мне нравятся такие вопросы, когда, по сути, «мое понимание отличается от общепринятой практики, пожалуйста, помогите разрешить этот конфликт», потому что расширение ваших представлений поможет вам решить гораздо больше проблем в будущем! Казалось бы, другие придерживаются подхода «это пустая трата обработки в 99,9999% случаев, даже не думай об этом». Если это утешит меня, я был понижен за намного, намного меньше!
CorsiKa
4
Да, этот вопрос получил чрезмерное количество голосов за его качество. Вероятно, это то же самое, что кто проголосовал против ответа Блинди. Справедливости ради, «изменение двусвязного списка должно включать в себя только переключение указателей головы и хвоста», как правило, неверно для стандартного связанного списка, подразумевающего, что все учатся в старшей школе, или для многих реализаций, которые используют люди. Много раз в SO немедленная интуитивная реакция людей на вопрос или ответ приводит к повышению или понижению голосов. Если бы вы были более ясны в этом предложении или пропустили его, я думаю, вы получили бы меньше отрицательных голосов.
Крис Бек
3
Или позвольте мне взять на себя бремя доказывания, @Curious: здесь я описал реализацию двусвязного списка: ideone.com/c1HebO . Можете ли вы указать, как вы ожидаете, что Reverseфункция будет реализована в O (1)?
CompuChip
2
@CompuChip: На самом деле, в зависимости от реализации, это не так. Вам не нужно дополнительное логическое значение, чтобы знать, какой указатель использовать: просто используйте тот, который не указывает на вас ... который, кстати, вполне может быть автоматическим со связанным списком XOR. Так что да, это зависит от того, как реализован список, и можно ли уточнить утверждение OP.
Матье М.

Ответы:

187

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

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

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

Ами Тавори
источник
29
@MooseBoys: я не согласен с вашей аналогией. Разница заключается в том, что, в случае списка, реализация может обеспечить reverseс O(1)сложностью , не затрагивая большой-о какой - либо другой операции , с помощью этого булева трюк флага. Но на практике дополнительная ветвь в каждой операции обходится дорого, даже если технически это O (1). Напротив, вы не можете создать структуру списка, в которой sortO (1) и все другие операции имеют одинаковую стоимость. Суть вопроса в том, что, похоже, вы можете получить O(1)реверс бесплатно, если вы заботитесь только о большом О, так почему же они этого не сделали.
Крис Бек
9
Если бы вы использовали XOR-связанный список, реверсирование стало бы постоянным временем. Хотя итератор был бы больше, а увеличение / уменьшение его было бы немного дороже в вычислительном отношении. Это может быть карликовым из-за неизбежных обращений к памяти, хотя для любого вида связанного списка.
Дедупликатор
3
@IlyaPopov: это нужно каждому узлу? Пользователь никогда не задает никаких вопросов самому узлу списка, только основному телу списка. Таким образом, доступ к логическому значению прост для любого метода, который вызывает пользователь. Вы могли бы сделать правило, что итераторы аннулируются, если список перевернут, и / или сохранить копию логического значения, например, с помощью итератора. Так что я думаю, что это не повлияет на большой O, обязательно. Я признаю, я не проходил построчно через спецификацию. :)
Крис Бек
4
@ Кевин: Хм, что? Вы не можете напрямую xor два указателя в любом случае, вам нужно сначала преобразовать их в целые числа (очевидно, типа std::uintptr_t. Затем вы можете xor их.
Дедупликатор
3
@Kevin, вы определенно могли бы создать XOR-связанный список в C ++, это практически дочерний язык для такого рода вещей. Ничто не говорит, что вы должны использовать std::uintptr_t, вы можете привести к charмассиву, а затем XOR компонентов. Это будет медленнее, но на 100% портативно. Вероятно, вы могли бы сделать выбор между этими двумя реализациями и использовать в качестве запасного только второе, если uintptr_tоно отсутствует. Некоторые, если это описано в этом ответе: stackoverflow.com/questions/14243971/…
Крис Бек
61

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

current = current->next;

в operator++итераторе списка вы получите

if (reversed)
  current = current->prev;
else
  current = current->next;

это не то, что вы решили бы добавить легко. Учитывая , что списки обычно проходится гораздо чаще , чем они поменялись местами, было бы очень неразумно стандарт для санкционировать эту технику. Следовательно, обратная операция может иметь линейную сложность. Заметим, однако, что tO (1) ⇒ tO ( n ), поэтому, как упоминалось ранее, техническая реализация вашей «оптимизации» будет разрешена.

Если вы пришли из Java или из аналогичного фона, вы можете спросить, почему итератор должен каждый раз проверять флаг. Не могли бы мы вместо этого иметь два разных типа итераторов, оба производных от общего базового типа, а также иметь std::list::beginи std::list::rbeginполиморфно возвращать соответствующий итератор? Хотя это и возможно, это еще больше ухудшит ситуацию, поскольку продвижение итератора теперь будет косвенным (трудно встроенным) вызовом функции. В Java вы все равно платите эту цену регулярно, но опять же, это одна из причин, по которой многие люди обращаются к C ++, когда производительность критична.

Как отметил Бенджамин Линдли в комментариях, поскольку reverseнедопустимо делать недействительными итераторы, единственным подходом, допускаемым стандартом, кажется, является сохранение указателя на список внутри итератора, который вызывает двойной косвенный доступ к памяти.

5gon12eder
источник
7
@galinette: std::list::reverseне делает недействительными итераторы.
Бенджамин Линдли
1
@galinette Извините, я неправильно прочитал ваш предыдущий комментарий как «флаг на итератор », а не «флаг на узел », как вы его написали. Конечно, флаг на узел будет контрпродуктивным, так как вам, опять же, придется делать линейный обход, чтобы перевернуть их все.
5gon12eder
2
@ 5gon12eder: Вы могли бы устранить ветвления при очень потерянной стоимости: хранить nextи prevуказатели в массиве, и сохраняет направление как 0или 1. Чтобы выполнить итерацию вперед, вы должны следовать pointers[direction]и выполнять итерацию в обратном направлении pointers[1-direction](или наоборот). Это все равно добавит немного накладных расходов, но, вероятно, меньше, чем ветвь.
Джерри Коффин
4
Вы, вероятно, не можете хранить указатель на список внутри итераторов. swap()указано постоянное время и не делает недействительными никакие итераторы.
Тавиан Барнс
1
@TavianBarnes Черт возьми! Ну, тогда тройная косвенность… (я имею в виду, на самом деле не тройная. Вы должны хранить флаг в динамически размещаемом объекте, но указатель в итераторе может, конечно, указывать непосредственно на этот объект, а не косвенно по списку.)
5gon12eder
37

Конечно, поскольку все контейнеры, поддерживающие двунаправленные итераторы, имеют концепцию rbegin () и rend (), этот вопрос является спорным?

Тривиально создать прокси, который переворачивает итераторы и получает доступ к контейнеру через него.

Эта неоперация действительно O (1).

Такие как:

#include <iostream>
#include <list>
#include <string>
#include <iterator>

template<class Container>
struct reverse_proxy
{
    reverse_proxy(Container& c)
    : _c(c)
    {}

    auto begin() { return std::make_reverse_iterator(std::end(_c)); }
    auto end() { return std::make_reverse_iterator(std::begin(_c)); }

    auto begin() const { return std::make_reverse_iterator(std::end(_c)); }
    auto end() const { return std::make_reverse_iterator(std::begin(_c)); }

    Container& _c;
};

template<class Container>
auto reversed(Container& c)
{
    return reverse_proxy<Container>(c);
}

int main()
{
    using namespace std;
    list<string> l { "the", "cat", "sat", "on", "the", "mat" };

    auto r = reversed(l);
    copy(begin(r), end(r), ostream_iterator<string>(cout, "\n"));

    return 0;
}

ожидаемый результат:

mat
the
on
sat
cat
the

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

Просто мой 2с.

Ричард Ходжес
источник
18

Потому что он должен пройти через каждый узел ( nвсего) и обновить их данные (шаг обновления действительно O(1)). Это делает всю операцию O(n*1) = O(n).

Blindy
источник
27
Потому что вам нужно обновить ссылки между каждым элементом тоже. Выньте лист бумаги и вытяните его вместо голосования.
Blindy
11
Зачем спрашивать, уверены ли вы тогда? Ты тратишь как наше время.
Blindy
28
@Curious Узлы двусвязного списка имеют чувство направления. Причина оттуда.
Чистка
11
@ Blindy Хороший ответ должен быть полным. «Возьмите лист бумаги и вытяните его», таким образом, не должно быть обязательным компонентом хорошего ответа. Ответы, которые не являются хорошими ответами, подлежат отрицательным ответам.
RM
7
@Shoe: они должны? Пожалуйста, изучите XOR-связанный список и тому подобное.
Дедупликатор
2

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

techcomp
источник
1

Только объяснение алгоритма. Представьте, что у вас есть массив с элементами, тогда вам нужно инвертировать его. Основная идея состоит в том, чтобы выполнить итерацию для каждого элемента, меняя элемент в первой позиции на последнюю позицию, элемент во второй позиции на предпоследнюю позицию и так далее. Когда вы достигнете середины массива, все элементы будут изменены, таким образом, за (n / 2) итераций, что считается O (n).

danilobraga
источник
1

Это O (n) просто потому, что нужно скопировать список в обратном порядке. Каждой отдельной операции элемента является O (1), но во всем списке их n.

Конечно, существуют некоторые операции с постоянным временем, связанные с установкой пространства для нового списка, последующим изменением указателей и т. Д. Нотация O не учитывает отдельные константы, если вы включите n-фактор первого порядка.

SDsolar
источник