갤러리 이슈박스, 최근방문 갤러리
개념글 리스트
1/2
- 코세야 이게 니가 말한 O(1) inplace 머지소트의 속도다 ㅇㅇ
- std::inplace_merge 테스트 끝. codesa
- 코세가 인정해야하는거 통암기공부법
- 코세야 오늘도 거짓말로 주접을 떨었구나 ㅇㅇ
- 이정도 스펙이면 IT기업 취업 가능? 야옹이랑
갤러리 본문 영역
O(1) 머지소트 결론이뭐냐앱에서 작성
ㅇㅇ(221.153) 12-15 07:19:01
조회 118 추천 2 댓글 15
하단 갤러리 리스트 영역
왼쪽 컨텐츠 영역
갤러리 리스트 영역
| 번호 | 제목 | 글쓴이 | 날짜 | 조회 | 추천 |
|---|---|---|---|---|---|
| 설문 | 2018년 가장 기억에 남는 이슈는? | 운영자 | 18/12/10 | - | - |
| 공지 | 프로그래밍 갤러리 FAQ(자주 하는 질문) 읽어주세요.... 흐극흐극 [85] | dlbo | 12/01/31 | 70746 | 315 |
| 공지 | 프로그래밍과 관련된 사진과 내용이 있어야 합니다. [371] | 운영자 | 05/06/21 | 681985 | 17 |
| 952118 | 아니 씨발 코드 5자리뭐냐 | ㅇㅇ(175.223) | 12/15 | 1 | 0 |
| 952117 | 일본 경제 완전 부활, '기업 연이어 역대 최고 실적 기염' | 일본학과(222.99) | 12/15 | 7 | 0 |
| 952116 | 웹 땔감의 삶이란.. | ㅇㅇ(223.33) | 12/15 | 19 | 0 |
| 952115 | ssafy는 무시하더라도 구성원은 무시하지말자 프갤러들아 [1] | fpdkf | 12/15 | 24 | 0 |
| 952114 | 여자가 개발 싫어한다는건 편견임 [5] | Recursion | 12/15 | 44 | 0 |
| 952113 | 원서 솔직히 허세다 [3] | ㅇㅇ(112.153) | 12/15 | 27 | 0 |
| 952110 | 형님들 opengl 조명설정좀 여쭙겠습니다 | ㅇㅇ(125.184) | 12/15 | 14 | 0 |
| 952109 | 컴공도 암기과목 있음? | ㅇㅇ(223.38) | 12/15 | 13 | 0 |
| 952106 | c언어 도와주십시오 행님들 | 아메맄노(115.138) | 12/15 | 21 | 0 |
| 952105 | 시험끝나니깐 롤도 재미없음 | 리액트JS | 12/15 | 6 | 0 |
| 952103 | 여자중에서 코딩잘하는애 딱한명있었다. | 후쿠오카 | 12/15 | 25 | 0 |
| 952098 | 오늘 하루 집에서 쉬는데 지겨움 | 리액트JS | 12/15 | 11 | 0 |
| 952095 | 컴공나온 여자들은 나중에 뭐함? [2] | ㅇㅇ(219.241) | 12/15 | 42 | 0 |
| 952094 | 애니 안본지 오래됐는데 [2] | 落花流水 | 12/15 | 13 | 0 |
| 952091 | 근데 왜 여자들은 개발하는거 싫어함? [1] | ㅇㅇ(219.241) | 12/15 | 30 | 0 |
| 952090 | 딥러닝 뭔가 멋져보인다 [1] | 落花流水 | 12/15 | 21 | 0 |
| 952089 | 알고리즘 문제 하나 개삽질하고 있었는데 [1] | 에로망가센세 | 12/15 | 25 | 0 |
| 952088 | OpenGL 고수님들 조명설정좀 여쭙겠습니다 도와주세요 | ㅇㅇ(125.184) | 12/15 | 15 | 0 |
| 952087 | 이헤갤이 뭔가했더니 [3] | ㅇㅇ(175.223) | 12/15 | 34 | 0 |
| 952082 | 니들 스택오버플로 쓰냐? [5] | ㅇㅇ(211.36) | 12/15 | 30 | 0 |
| 952080 | 그런데 코드 등록 또 사라지는 것 아니냐 | W10updsrv7(192.160) | 12/15 | 10 | 0 |
| 952079 | 파이썬2도 현역인 마당에 쟈-바가 죽는다?? | ㅋㄷ(49.165) | 12/15 | 21 | 0 |
| 952078 | 중앙대 불교학부 저새끼 경상대아니냐 [1] | ㅇㅇ(223.62) | 12/15 | 37 | 1 |
| 952077 | 수정)학교에서 C언어에 관해서 문제 물어본 학생입니다. 코드가.. [6] | 형님들(118.238) | 12/15 | 57 | 0 |
| 952076 | c# DateTime.Today.ToString 이거 시간가 갑자기 표 [7] | 연지타 | 12/15 | 23 | 0 |
| 952075 | 나이들수록 양아치가 안보이는이유가 있긴한듯 [5] | ㅎㅎㅎ(175.113) | 12/15 | 50 | 0 |
| 952074 | 분탕충 시발새끼때문에 | 중앙대 불교학부(36.38) | 12/15 | 28 | 0 |
| 952073 | c언어 예제 모아놓은 사이트 있음? [1] | 미멍(223.33) | 12/15 | 20 | 0 |
| 952072 | 객체지향 잘 모르겠으면 go 한번 하면 됨 | ㅇㅇ(113.199) | 12/15 | 39 | 0 |
| 952071 | 코드등록 미쳤냐 ㅋㅋㅋ | ㄹㅇㄴㅁ(123.212) | 12/15 | 26 | 0 |
| 952070 | 아싸들은 함수형이나 하시면 됩니다 | ㅇㅇ(110.70) | 12/15 | 23 | 0 |
| 952069 | 객체지향 현실? 현업에서 아무도 정답을 모른다는거 [8] | ㅇㅇ(125.191) | 12/15 | 75 | 0 |
| 952068 | 아시발 개어이없노 [12] | 중앙대 불교학부(36.38) | 12/15 | 97 | 0 |
| 952067 | 아조시들 c린이 도와죠 [11] | ㅇㅇ(223.62) | 12/15 | 77 | 0 |
| 952065 | 아싸들은 함수형을 잘함 | ㅇㅇ(110.70) | 12/15 | 27 | 0 |
| 952064 | 프린이 C언어 포인터 보고있는데 [2] | ㅇㅇ(115.86) | 12/15 | 39 | 0 |
| 952063 | 객체지향을 어려워 하는 사람들은 공통적인 특징이 있음 [4] | ㅇㅇ(110.70) | 12/15 | 69 | 0 |
| 952062 | SIMD 어려움? [1] | 우물안개구리(210.103) | 12/15 | 17 | 0 |
| 952061 | 씨언어 안맞으면 전과가답임? [5] | ㅇㅇ(219.241) | 12/15 | 50 | 0 |
| 952060 | 아직도 객체 지향은 제대로 이해가 안된다. [3] | 綾香 | 12/15 | 50 | 0 |
| 952059 | 괘씸죄의 무서움 | ㅇㅇ(49.239) | 12/15 | 21 | 0 |
| 952058 | 오늘. 비트박스 배워봄 | ㅇㅇ(223.38) | 12/15 | 10 | 0 |
| 952057 | 난 프로그래밍에 재능 없다고 생각하는데 [1] | ㅇㅇ(110.70) | 12/15 | 44 | 0 |
| 952056 | 개추 노래. 하나 선발 해봄 | ㅇㅇ(223.38) | 12/15 | 13 | 0 |
| 952055 | c언어 파일입출력 여기 어려운부분임? [7] | ㅇㅇ(219.241) | 12/15 | 57 | 0 |
| 952054 | 노래. 불러봄 [1] | ㅇㅇ(223.38) | 12/15 | 25 | 0 |
| 952053 | 치킨, 피자, 라면 등 먹으면 코딩 못해짐 [5] | ㅇㅇ(110.70) | 12/15 | 49 | 0 |
| 952052 | 자바로 안드로이드 개발해도 상관없겠지? [2] | 학시기(211.246) | 12/15 | 44 | 0 |
오른쪽 컨텐츠 영역
로그인을 해 주시기 바랍니다.
댓글 영역
1. merge sort 는 어차피 다른 sort 들에 대해 일반적으론 느림.
유동은 std::sort 와 성능비교를 한 것 뿐. 아무 의미 없음.
2. 단순히 일반적으로 성능좋은 sort 를 원한다면 적은 갯수의 정렬에서 insertion 을 쓰는게 맞고, 메모리의 여유나 캐싱 가능성에 따라 퀵과 다른 소트들을 혼합해야함. GPU 같은데서 적당한 알고리즘은 별도로 있고 말야.
3. std::stable_sort 도 내부적으론 마지막 단계어서 std::inplace_sort 의 core 코드를 사용함. 그러니 순수한 merge 가 아니고, 성능에 O(1) inplace_sort 가 긍정적인 영향을 주는 케이스들이 있음. ( 느리면 굳이 왜 썼겠음 )
마지막단계에서 inplace쓰는게 더 빠른거? 이부분이 이해가안되네
O( n * log n ) 인 논리 복잡도에서도 실제로 캐시빨 받으면 달라지는 경우가 많아. heap vs quick 도 그렇잖아. 메모리가 충분하면 heap 이 빨라야 하는데 quick 을 못따라감. 인접 캐시 히트율 땜에.
아 캐시히트...이래서 로우레벨이 재밌는듯
그러다 보니 quick sort 도 대개 O ( n ) 으로 성능이 측정되고, 지난 테스트에서 fixed buffer ( O(1) ) inplace 도 O( n ) 이 나오더라고. 아마도 제작자들이 두가지 버전을 시험해 보고 시험중 빠른걸 선택했을테고
stable_sort 마지막 스테이지의 정렬된 두 영역을 합칠때 inplace core 를 써 버린거겠지.
heap vs quick 도 그렇잖아. 메모리가 충분하면 heap 이 빨라야 하는데 quick 을 못따라감. <- 이거 잘못됨 worst case O(n^2) 인 quick 을 heap 이 못따라감 이라고 해야함.
heap 은 추가메모리를 안쓰니까.
근데 왜 유동이 돌린코드에서 inplace가 더 빠른거임? 어케돌린거지
4. 즉 merge sort 는 꼭 필요한 사용처에만 쓰는게 좋음. merge sort 류가 강력해지는 경우는 정렬되어있을 경우잖아.
유동은 내가 예시로 올렸던 두가지 O(1) 변종 inplace 코드들 돌린거잖아.
내가 median filter 를 설명한 이유가 원형 커널을 이동하면서 중앙값을 뽑아올때 매번 원만큼을 새롭게 정렬하는건 엄청난 비용이지만, 커널이 지나온 곳에 있던 값을 삭제하고 정렬된 데이타 1을 얻고, 새로 들어오는 원호 만큼의 데이타만 작게 정렬해서, 둘을 합치는 형태에서 median 을 뽑으면 꽤 쓸만해지는 것 처럼. 정렬된 형태를 최대한 재사용하는 곳에 써야한단 말.