Где я нахожу сравнение другой сложности контейнеров STL (производительность)? [дубликат]

Question

Где я нахожу сравнение другой сложности контейнеров STL (производительность)? [дубликат]

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

#!/usr/bin/env bash

main() {
  for (( i = 0; i <= 100; i=$i + 1)); do
    progress_bar "$i"
    sleep 0.1;
  done
  progress_bar "done"
  exit 0
}

progress_bar() {
  if [ "$1" == "done" ]; then
    spinner="X"
    percent_done="100"
    progress_message="Done!"
    new_line="\n"
  else
    spinner='/-\|'
    percent_done="${1:-0}"
    progress_message="$percent_done %"
  fi

  percent_none="$(( 100 - $percent_done ))"
  [ "$percent_done" -gt 0 ] && local done_bar="$(printf '#%.0s' $(seq -s ' ' 1 $percent_done))"
  [ "$percent_none" -gt 0 ] && local none_bar="$(printf '~%.0s' $(seq -s ' ' 1 $percent_none))"

  # print the progress bar to the screen
  printf "\r Progress: [%s%s] %s %s${new_line}" \
    "$done_bar" \
    "$none_bar" \
    "${spinner:x++%${#spinner}:1}" \
    "$progress_message"
}

main "$@"

5

c++ performance stl complexity-theory

задан sharptooth 26 June 2009 в 13:20

2 ответа

Другие вопросы по тегам:

c++ performance stl complexity-theory

Похожие вопросы:

score 2 · Answer 1

Попробуйте с

http://www.sgi.com/tech/stl/complexity.html

http://www.sgi.com/tech/stl/table_of_contents .html

Из complex.html:

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

Чтобы алгоритм A имел время работы O (f (n)), должен быть соответствующий алгоритм A ', то есть исправить на машинах с произвольно типы long pointer и size_t, например что A и A 'по существу выполняют та же последовательность операций на фактическое оборудование. (В простых случаях A и A 'будет таким же. В других случаи A могли быть упрощены с знание, что адреса ограничено.) Для входов достаточно большой размер n, A 'должен занимать не более время Cf (n), где C - постоянная, независимо от n и адреса размер. (Указатель, size_t и ptrdiff_t предполагается проведение операций постоянное время независимо от их size.)

Все спецификации сложности контейнера или итератора относятся к амортизированная сложность. Индивидуальный операция может занять больше чем указано. Но любой достаточно длинный последовательность операций на одном контейнер или итератор займет до тех пор, пока соответствующая сумма указанных операционных затрат.

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

Спецификация сложности для операции f предполагает, что операции вызывается f требует не более указанное время выполнения. Но алгоритмы обычно остаются уместными, если вызываемые операции не более чем логарифмический множитель медленнее, чем в ожидаемом случае.

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

Чтобы сделать это точным, предположим, что F задано использовать время f (m) для ввод размером м. F использует операции Gk, с указанным временем работы gk (n) на входной размер n. Если F используется в контекст, в котором каждый Gk медленнее чем ожидалось не более чем на фактор h (n), то F замедляется не более чем на a коэффициент h (м). Это верно, потому что никто текущих алгоритмов когда-либо применяемых операции Gk с входами значительно больше, чем m.

score 1 · Answer 2

ISO C++ Standard defines the complexity of algorithms and container access methods, where required. Anywhere else (if not explicitly stated) all bets are off and a library implementor is free to do their own implementation.

For example you can assume that maps and sets are implemented using red-black trees, but there is no requirement to do so. Many algorithms are overloaded or specialized for particular iterator categories (like Random Access Iterator) and sometimes might be even optimized to perform from special hardware (like XMM register and execute some some operations in parallel).

Sometimes you really have to logically assume how much an operation might cost, due to other requirements, like splice in std::list must have O(1) complexity => length has O(n).

I have the book from N. Josuttis Стандартная библиотека C ++ - Учебное пособие и справочник и все эти аспекты хорошо освещены там.

С уважением,
Ованес