Двусвязный список — это фундаментальная структура данных, о которой все знают и повсеместно используют. Все знают почему и в каких случаях он эффективнее вектора, какие операции имеют линейную сложность, а какие — константную…
Хотя постойте, знаете ли вы какова сложность функции size ()?
«Конечно же я знаю — О(1)!», ответят многие из вас, «Что может быть проще?»
Тривиально, эффективно и безопасно, не так ли?
Я бы реализовал эту функцию именно так, большинство из вас сделали бы тоже самое.
Однако, те, кто писал реализацию GNU STL, другого мнения на этот счет.
Вот так выглядит реализация этой функции в gcc 4.x:
Если не верите — пойдите проверьте в своем дистрибутиве.
Что мы здесь видим? Чтобы выполнисть такую тривиальную операцию, как получение размера, наш список будет выполнять полный проход с подсчетом!
Это значит, что если вы дергаете эту функцию в цикле, проходя по списку, то сложность вашего алгоритма автоматически умножается на N.
Вместо, казалось бы очевидного, O(N), мы получим здесь O(N^2). Хорошо если в списке 100 элементов. А что если 1 000 000?
Это так же значит, что вызов size () — небезопасен в многопоточной среде.
Имеем серьезный риск получить крэш в первом потоке.
Оказывается, отсутствие необходимости поддерживать внутреннюю переменную _size позволяет реализовать splice за O(1), иначе было бы O(N) для худшего случая.
splice — это операция переноса последовательных элементов из одного списка в другой. Не имея необходимости подсчитывать новые размеры списков, нам достаточно «переключить» указатели с одних узлов на другие, т.е. за константное время.
Имея же внутреннюю переменную _size, нам бы пришлось посчитать сколько элементов мы переносим и соответсвенно обновить ее в обоих списках.
Вот такая вот причина. Кстати, как часто вы пользуетесь это операцией? А всеми вышеперечисленными?
Вобщем будте осторожнее. И еще имейте в виду, что в других реализациях STL переменная _size есть и size() соответственно работает за O(1). Так что будьте дважды осторожны, если вы собираете свой проект с разными реализациями STL на разных платформах.
На сем раскланиваюсь. Простите за ботанический пост в пятницу.
UPD
В новом стандерте С++11 содержится требование, чтобы size для всех STL контейнеров работала за O(1), и это очень хорошо.
Впрочем, попытка внести изменение в реализацию GNU STL пока-что провалилась из-за проблем бинарной совместимости. Подробнее здесь gcc.gnu.org/bugzilla/show_bug.cgi?id=49561
Хотя постойте, знаете ли вы какова сложность функции size ()?
«Конечно же я знаю — О(1)!», ответят многие из вас, «Что может быть проще?»
size_type size() const
{
return _size;
}
Тривиально, эффективно и безопасно, не так ли?
Я бы реализовал эту функцию именно так, большинство из вас сделали бы тоже самое.
Однако, те, кто писал реализацию GNU STL, другого мнения на этот счет.
Вот так выглядит реализация этой функции в gcc 4.x:
/** Returns the number of elements in the %list. */
size_type
size() const
{ return std::distance(begin(), end()); }
Если не верите — пойдите проверьте в своем дистрибутиве.
Что мы здесь видим? Чтобы выполнисть такую тривиальную операцию, как получение размера, наш список будет выполнять полный проход с подсчетом!
Это значит, что если вы дергаете эту функцию в цикле, проходя по списку, то сложность вашего алгоритма автоматически умножается на N.
for (std::list <int>::const_iterator I = my_list.begin (); I != my_list.end (); ++I)
{
if (*I > my_list.size ())
{
std::cout << "Haha! "<< *I << std::endl;
}
}
Вместо, казалось бы очевидного, O(N), мы получим здесь O(N^2). Хорошо если в списке 100 элементов. А что если 1 000 000?
Это так же значит, что вызов size () — небезопасен в многопоточной среде.
std::list <int> my_list;
// Thread 1
void thread1_proc ()
{
while (!stop)
{
std::cout << "List size: " << my_list.size () << std::endl;
}
}
// Thread 2
void thread2_proc ()
{
while (!stop)
{
int n = rand ()
my_list.push_back (n);
if (n % 2)
my_list.pop_front ();
}
}
Имеем серьезный риск получить крэш в первом потоке.
Это так же значит, что
- Для сравнения двух списков, нам всегда придется выполнять полный проход, вместо того, чтобы тривиальным сравнением размеров отсечь 90% случаев.
- Менее эффективный resize. Здесь мы имеем два случая
1. Уменьшение размера. Если размер списка нам известен (читай доступен за O(1)), мы можем решить, начинать нам проход с начала или с конца в зависимости от того, удаляем мы несколько элементов в конце или наоборот оставляем несколько в начале. В реализации GNU это сделать невозможно.
2. Увеличение размера. Если размер списка нам известен, нам достаточно просто добавить недостающие елементы. В реализации GNU нам придется всегда делать полный проход по списку.
- Наверное еще что-то, кто знает, подскажите.
Так что же заставило программистов GNU реализовать список таким образом?
Оказывается, отсутствие необходимости поддерживать внутреннюю переменную _size позволяет реализовать splice за O(1), иначе было бы O(N) для худшего случая.
splice — это операция переноса последовательных элементов из одного списка в другой. Не имея необходимости подсчитывать новые размеры списков, нам достаточно «переключить» указатели с одних узлов на другие, т.е. за константное время.
Имея же внутреннюю переменную _size, нам бы пришлось посчитать сколько элементов мы переносим и соответсвенно обновить ее в обоих списках.
Вот такая вот причина. Кстати, как часто вы пользуетесь это операцией? А всеми вышеперечисленными?
Вобщем будте осторожнее. И еще имейте в виду, что в других реализациях STL переменная _size есть и size() соответственно работает за O(1). Так что будьте дважды осторожны, если вы собираете свой проект с разными реализациями STL на разных платформах.
На сем раскланиваюсь. Простите за ботанический пост в пятницу.
UPD
В новом стандерте С++11 содержится требование, чтобы size для всех STL контейнеров работала за O(1), и это очень хорошо.
Впрочем, попытка внести изменение в реализацию GNU STL пока-что провалилась из-за проблем бинарной совместимости. Подробнее здесь gcc.gnu.org/bugzilla/show_bug.cgi?id=49561