Постоянное время минусы - PullRequest
       1

Постоянное время минусы

0 голосов
/ 08 августа 2011

Есть ли способ (например, изменение типов аргументов), чтобы следующая функция «cons» занимала постоянное время, а не O (n).то есть построение списка должно занять O (n) время, а не O (n ^ 2).

Можно ли сделать это при следующих условиях:

(1) Нет динамического выделения памяти
(2) x должен все еще оставаться действительным (то есть может не иметь ссылок на временные данные)
(3) Тип HEAD может иметь конструкторы, которые компилируются отдельно (не встроено)

#include <type_traits>

template <typename HEAD, typename TAIL>
struct List
{
  List(HEAD head, TAIL tail) : head(head), tail(tail) {}
  typename std::remove_reference<HEAD>::type head;
  typename std::remove_reference<TAIL>::type tail;
};

template <typename HEAD, typename TAIL>
List<HEAD, TAIL> cons(HEAD head, TAIL tail)
{
  return List<HEAD, TAIL>(head, tail);
}

struct Empty {};

int main()
{
  auto x = cons(1, cons(2, cons(3, Empty())));
  // x should still be valid here
}

Пример того, как может работать.

Компилятор знает тип x, поэтому выделяет место в стеке.

Таким образом, стек выглядит так:

| Int1 | Int2 | Int3 |
| p    | p+4  | p+8  |

Где p - произвольный адрес.

Компилятор создает вызов cons(2, cons(3, Empty())), перенаправляя возвращаемое значение на p+4.

Внутри cons(2, cons(3, Empty())), компилятор создает вызов cons(3, Empty()) направление возвращаемого значения в p+8.

Таким образом, каждый раз, когда вызывается cons, tail копировать не нужно.

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

Ответы [ 2 ]

2 голосов
/ 08 августа 2011

Вы, кажется, заново изобретаете std::tuple с худшим помощником std::make_tuple. Используйте это вместо этого. Стандарт не дает гарантий сложности ни для конструктора переадресации std::tuple, ни для std::make_tuple, но это своего рода спорный вопрос, потому что эти два используют идеальную пересылку, поэтому для вызова элемента создается ровно одна конструкция перемещения / копирования / размещения на элемент std::make_tuple; остальное перемешивает ссылки вокруг. Это линейное число конструкций по крайней мере.

Конечно, не гарантируется, что ваш компилятор будет корректно обрабатывать все перетасовки ссылок, но вы все равно оптимизируете на неправильном уровне.


В целях иллюстрации почти, но не совсем то, что происходит:

template<typename... T>
class tuple {
    T... members; // this is not correct, only here for illustration

    // The forwarding constructor
    template<typename... U>
    explicit
    tuple(U&&... u)
        : member(std::forward<U>(u)...)
    {}
};

template<typename... T>
tuple<typename std::decay<T>::type...>
make_tuple(T&&... t)
{ return tuple<typename std::decay<T>::type...>(std::forward<T>(t)...); }

Таким образом, в вызове к auto tuple = std::make_tuple(1, 2, 3) есть три временных int s от вызова к make_tuple, затем три int&& x значения от первых вызовов к std::forward<int>(t)... внутри make_tuple, которые связываются с аргументы конструкторов, которые снова передаются в виде int&& x значений для концептуальных трех членов std::tuple<int, int, int>, которые построены из них.


Просто понял, что то, что я сказал о количестве конструкций, относится только к вызову std::make_tuple, а не ко всему выражению auto tuple = std::make_tuple(...);. Поскольку кортеж возвращается из функции, он может потребовать перемещения / RVO к конечной переменной. Он по-прежнему линейный, и его по-прежнему любят оптимизировать компиляторы, и не стоит беспокоиться об оптимизации.

Однако C ++ 0x настолько совершенен, что уже может делать то, что вы описываете в своем ответе:

int i = 3;
std::tuple<int, int, int> tuple = std::forward_as_tuple(1, 2, i);

Вызов forward_as_tuple вернет std::tuple<int&&, int&&, int&>. Этот помощник никогда не возвращает кортеж со значениями, только «мелкий» кортеж ссылок. Соответствующий конструктор преобразования std::tuple<int, int, int> затем инициализирует свои «члены» двумя ходами и копией. Обратите внимание, что эта глупая (не) оптимизация ставит вас под угрозу написания auto tuple = std::forward_as_tuple(1, 2, i);, который является кортежем с двумя висячими ссылками.

0 голосов
/ 08 августа 2011

Я собираюсь дать ответ на свой вопрос после моих расследований, но мне все равно будет интересно, если кто-нибудь знает лучший способ.

(1) Переименуйте List в TempList.
(2) Сделать конструкторов (включая перемещение и копирование) TempList закрытыми.
(3) Сделать cons другом TempList.
(4) Сделать HEAD иTAIL члены в ссылках.

Теперь TempList содержит только ссылки, поэтому копий нет.Однако это могут быть ссылки на временные ссылки, но это нормально, потому что временные значения сохраняются до конца выражения, и поскольку TempList имеет только частные конструкторы, его нельзя назначить LHS выражения.Только cons может создать TempList и не может пережить выражение, в котором он создан.

Теперь создайте функцию save или что-то с таким эффектом, которая принимает TempList и возвращаетreal List, другой тип, данные которого хранятся по значению.

Итак, у нас есть

auto x = save(cons(1, cons(2, cons(3, Empty()))));

И данные будут скопированы или перемещены не более одного раза (сохранением), вся конструкция теперь составляет O(n).Структура TempList, вероятно, будет оптимизирована, так как cons и save встроены.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...