Флейм
GameDev.ru / Флейм / Форум / Крестосвапы

Крестосвапы

Поделиться
Страницы: 1 2 3 Следующая »
=A=L=X=Постоялецwww8 окт. 201717:19#0
То ли совсем я от крестов отвык, то ли под вечер уже затупил не под детски, но не понимаю - что вот тут: https://ideone.com/EKEZAZ вообще происходит?
Зачем std::sort свапает хоть что-то в уже отсортированном массиве где нет равных элементов?
quicksort же вроде такой ересью не должен заниматься... чёто как то погруснел я, опять что ли велосипеды писать из двунаправленных списков?
ZegalurПостоялецwww8 окт. 201717:55#1
=A=L=X=Постоялецwww8 окт. 201717:56#2
https://ideone.com/qv0ML8
Короче не знаю что там за хипсорт или квиксорт, но оно явно в узловых точках занимается какой то совершенно не нужной мне хренью.
Ладно, пизурок так пизурок...
ZegalurПостоялецwww8 окт. 201718:15#3
вот и ответ?
https://ideone.com/KetCPW
=A=L=X=Постоялецwww8 окт. 201718:29#4
Zegalur

Бредня в том, что согласно http://en.cppreference.com/w/cpp/algorithm/stable_sort

order of equal elements is guaranteed to be preserved

Да, то что sort может произвольно себя вести для равных элементов - это я знал и в первопосте про это написал.
И stable_sort гарантирует по идее только это!
Какого пип-пип???

Правка: 8 окт. 2017 18:29

return [](){};Участникwww8 окт. 201718:30#5
Запустил в первой попавшейся консоли
(gdb) b main.cpp:17
Breakpoint 1 at 0x401e66: file main.cpp, line 17.
(gdb) r
Starting program: /home/vano/test/sort/a.out 
swapCount=0

Breakpoint 1, swap (a=..., b=...) at main.cpp:17
17          swap( a.x, b.x );
(gdb) bt
#0  swap (a=..., b=...) at main.cpp:17
#1  0x0000000000402bb7 in std::iter_swap<__gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, __gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > > > (__a=..., __b=...) at /usr/include/c++/5/bits/stl_algobase.h:148
#2  0x00000000004014e3 in std::__move_median_to_first<__gnu_cxx::__normal_iterator<X*, std::vector<X> >, __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(const X&, const X&)> > >(__gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, __gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, __gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, __gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(const X&, const X&)> >) (__result=..., __a=..., __b=..., __c=..., __comp=...) at /usr/include/c++/5/bits/stl_algo.h:84
#3  0x0000000000401147 in std::__unguarded_partition_pivot<__gnu_cxx::__normal_iterator<X*, std::vector<X> >, __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(const X&, const X&)> > >(__gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, __gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(const X&, const X&)> >) (__first=..., __last=..., __comp=...) at /usr/include/c++/5/bits/stl_algo.h:1916
#4  0x0000000000400f50 in std::__introsort_loop<__gnu_cxx::__normal_iterator<X*, std::vector<X> >, long int, __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(const X&, const X&)> > >(__gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, __gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, long, __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(const X&, const X&)> >) (__first=..., __last=..., __depth_limit=11, __comp=...) at /usr/include/c++/5/bits/stl_algo.h:1948
#5  0x0000000000400e8a in std::__sort<__gnu_cxx::__normal_iterator<X*, std::vector<X> >, __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(const X&, const X&)> > >(__gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, __gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(const X&, const X&)> >) (__first=..., __last=..., __comp=...) at /usr/include/c++/5/bits/stl_algo.h:1963
#6  0x0000000000400dd1 in std::sort<__gnu_cxx::__normal_iterator<X*, std::vector<X> >, main()::<lambda(const X&, const X&)> >(__gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, __gnu_cxx::__normal_iterator<X*, std::vector<X, std::allocator<X> > >, <lambda(const X&, const X&)>) (__first=..., __last=..., __comp=...)
    at /usr/include/c++/5/bits/stl_algo.h:4729
#7  0x0000000000400d1e in main () at main.cpp:32

ZegalurПостоялецwww8 окт. 201718:31#6
=A=L=X=
он вообще не вызывает swap, даже если изменить порядок на > (https://ideone.com/KkYFc9)
кароче, что происходит? :)

Правка: 8 окт. 2017 18:32

=A=L=X=Постоялецwww8 окт. 201718:36#7
Zegalur
> он вообще не вызывает swap

А, ну это возможно - тот же std::sort в GCC не пользуется свапом для малых массивов - это в твоих тестах видно, там просто какой то совсем уж простой алгоритм запускается и ему типа свап не нужен.
Возможно в stable_sort тоже чего то там намутили, что swap им не нужен. Бывает.
Короче хочешь сделать как надо - сделай сам...

ZegalurПостоялецwww8 окт. 201718:49#8
=A=L=X=
https://ideone.com/SkfoLt
здесь вроде большой из рандома, тоже 0
kiparПостоялецwww8 окт. 201722:13#9
=A=L=X=
> quicksort же вроде такой ересью не должен заниматься...
там introsort вроде.
*Lain*Забаненwww8 окт. 201722:55#10
=A=L=X=
timsort ок. пиши его. все остальное для школоты
totoroПользовательwww9 окт. 20171:05#11
=A=L=X=
> Зачем std::sort свапает хоть что-то в уже отсортированном массиве где нет
> равных элементов?
Узкое место не в свопах, узкое место в кол-ве операций сравнения. Тот же quicksort в худшем случае покажет O(n^2).

> quicksort же вроде такой ересью не должен заниматься...
std::sort - это алгоритм общего назначения, он должен соответствовать заявленной сложности, но его реализация может быть различной.

=A=L=X=Постоялецwww9 окт. 20179:39#12
totoro
> Узкое место не в свопах, узкое место в кол-ве операций сравнения

Да мне плевать было на узкие места, мне надо было чтобы отсортированный массив не модифицировался.

Правка: 9 окт. 2017 9:39

FordPerfectПостоялецwww9 окт. 20179:43#13
Zegalur
stable_sort вроде обычно через merge sort делают, там обмены не обязательны.
Стандарт вроде так  говорит: а если не хватит памяти, то in-place, за O(n log^2 n). Да, я в курсе что существует in-place merge_sort за O(n log n).
1 frag / 2 deathsУчастникwww9 окт. 201712:12#14
=A=L=X=
> Да мне плевать было на узкие места, мне надо было чтобы отсортированный массив
> не модифицировался.
А он и не модифицируется. Порядок элементов до и после остаётся прежним. То, что внутри некоторые элементы туда-сюда поменяли, а потом обратно вернули - не имеет значения.

FordPerfect
> Да, я в курсе что существует in-place merge_sort за O(n log n).
Подожди, вот тот ужас, в котором выделают конец массива под не помню уже что, он не квадрат логарифма?

Страницы: 1 2 3 Следующая »

/ Форум / Флейм / Программирование

2001—2017 © GameDev.ru — Разработка игр