(cache)코세야 이게 니가 말한 O(1) inplace 머지소트의 속도다

프로그래밍 갤러리

1/2

std::inplace_merge 테스트 끝. 관리자권한으로 비쥬얼스튜디오를 실행해 먼저 할당을 막고 저장함 ( break )그러면 heap 할당을 포기하고 스택의 512개 캐시만 이용하게 됨 -> O(1)아랫부분 코드를 타게 된다.8MB 테스트.응 그래 별 차이 없어. 작성자 : codesa

최근 방문 갤러리

프로그래밍

최근 방문 갤러리가 없습니다.

코세야 이게 니가 말한 O(1) inplace 머지소트의 속도다

ㅇㅇ(123.109) 12-15 04:02:35

조회 120 추천 3 댓글 45

결론 부터 말하자면:
    직접 구현하는 머지소트의 성능 향상을 위해서 inplace 머지소트를 권하는 것은 error다.

코세가 높이 치하한 WikiSort:
    O(1) inplace merge 를 사용하는 sort 들.
    http://gall.dcinside.com/board/view/?id=programming&no=949810

//WikiSort, std::stable_sort, std::sort의 속도 비교
WikiSort:
    https://github.com/BonzaiThePenguin/WikiSort/blob/master/WikiSort.cpp
    ==> WikiSort와 std::stable_sort 벤치마크가 포함돼 있어서
        이 파일에 std::sort만 추가시켜서 테스트했다.

결과:
https://wandbox.org/permlink/Z94HpJDwknXCyRbY
//for vector(size_t); random 시퀀스
           | times(seconds)    |   ratios
       n | wiki   stable sort |   wiki stable sort
    ---------------------------------------------------
    200000| 0.039 0.034 0.034 |   1.14 1.00 1.00
    400000| 0.206 0.078 0.063 |   3.29 1.24 1.00
    600000| 0.144 0.123 0.100 |   1.44 1.23 1.00
    800000| 0.205 0.182 0.149 |   1.38 1.22 1.00
    1000000| 0.256 0.300 0.174 |   1.47 1.73 1.00
    1200000| 0.346 0.412 0.213 |   1.63 1.94 1.00
    1400000| 0.393 0.501 0.260 |   1.51 1.93 1.00
    1600000| 0.455 0.582 0.347 |   1.31 1.68 1.00
    1800000| 0.581 0.742 0.361 |   1.61 2.06 1.00
    2000000| 0.680 0.912 0.385 |   1.77 2.37 1.00
    # Tests completed in 9.82773 seconds
        total | 3.306 3.867 2.085 |   1.59 1.85 1.00

https://wandbox.org/permlink/MLzJahzaXsVozd85
//for vector(size_[3]); random 시퀀스
           | times(seconds)    |   ratios
           n | wiki   stable sort |   wiki stable sort
    ---------------------------------------------------
    200000| 0.075 0.077 0.071 |   1.07 1.09 1.00
    400000| 0.197 0.351 0.123 |   1.60 2.85 1.00
    600000| 0.323 0.664 0.214 |   1.51 3.11 1.00
    800000| 0.440 1.005 0.376 |   1.17 2.67 1.00
    1000000| 0.648 1.489 0.392 |   1.65 3.80 1.00
    1200000| 0.932 1.686 0.594 |   1.57 2.84 1.00
    1400000| 0.994 1.837 0.607 |   1.64 3.03 1.00
    1600000| 0.996 2.121 0.635 |   1.57 3.34 1.00
    1800000| 1.034 2.260 0.739 |   1.40 3.06 1.00
    2000000| 1.113 2.509 0.815 |   1.37 3.08 1.00
    # Tests completed in 29.8015 seconds
       total | 6.752 13.999 4.567 |   1.48 3.07 1.00

note: WikiSort건 std::stable_sort건 많이 느리다(1.59배,1.85배).
    특히 stable_sort는 element복사비용이 증가하면(즉, element 크기가 증가하면) 더 그렇다(3.07배).
    WikiSort, stable_sort가 가끔, std::sort와 비슷하거나 오히려 더 빠르게 나오는 경우도 있다.
    내 컴퓨터에서는 이렇게 까지 심하게 속도차가 나지는 않긴 한데, wandbox에서는 재실행해도 비슷하게 나옴

나도 착각을 한게 있는데, 완성된 함수로 구현된 알고리즘들은 외부 버퍼(O(1) 크기 등)를 사용하는 게 있다는 것을 깜박했었디.
오래전에 봤던 거에다 순수 inplace 머지에만 관심을 뒀었기 때문에 착각하고 과장되거나 부정확하게 언급한 부분이 있었던거 같다.
그러나 적당크기의 외부버퍼를 사용하는 inplace 머지소트도, 코세님 조차 높이 치하하는 잘 짜여진 inplace 머지소트 조차
순수 성능향상을 목적으로 선택하기에는 기본적으로 느리다는 것은 돌려 봤으면 안다는 것은 변함이 없다.

코세야 진짜 "짜보고서 떠든"거 맞어? 거짓말 친거 아니고?

고정닉 0

파워클릭 광고 판매자 상황에 따라 가격이 일치하지 않을 수 있습니다.

신청하기

전체 리플 46개

등록순

ㅇㅇ(218.54)
ㅂㅈㄷㄱㅅ ㅁㄴㅇㄹㅎ ㅋㅌㅊㅍ
12.15 04:04:52
ㅇㅇ(125.191)
1900년대나 in-place 따졌지 메모리도 넉넉한데 in place로 짜는건 효율성 ㅈㄴ게 떨어지는 거임.
12.15 04:31:15
ㅇㅇ(123.109)
위에 https://github.com/BonzaiThePenguin/WikiSort/blob/master/WikiSort.cpp는 WikiSort 만든사람이 제공하는 소스임. 나는 거기에 std::sort 테스트 코드 추가와 서식 변경만 하였음
12.15 04:32:04
- ㅇㅇ(123.109)
  아래 지워진 댓글은 본인의 댓글이 아님. 자작극이 의심되네
  12.15 05:51:40
해당 댓글은 삭제되었습니다.
- codesafer
  단순히 범용 정렬 성능을 원한다면 merge 를 쓸 이유가 없고, std::sort 조차 대부분의 경우에서 극도로 최적화한 소트들에 비해 성능이 별론데다, 그 이야기는 질문자가 merge 를 이야기 했기 때문에 최소한 stable sort 여야하는데 너는 포인트를 못잡고 있음.
  12.15 05:00:02
댓글돌이
"왜 나만 빼빼로 안 줘" 직원에 고성 지르고 물건 던진 임원

1/10
codesafer
지난 벤치글에도 업데이트 했지만, std::stable_sort 는 내부적으로 inplace_merge의 core 함수를 사용한다.
12.15 04:56:00
codesafer
정렬의 성능향상이 아닌, stable 하길 바랄때, 그것도 아니면 거의 정렬된 특수한 형태, 그러니까 이미지의 커널 median 필터등을 구현할때, 비용을 절감할수 있는 장점이 있기 때문에 merge 를 직접 짜 본거고, 거기에 대해서 니가 짜봤니 마니 할 필요가 없다. median 필터만 아이디어별로 수십개 만들어 본 사람이니까.
12.15 04:58:10
codesafer
그리고 더이상 내게 말을 붙이지 말길 바란다. 지금 글은 그나마 좀 젠틀하다만, 너의 지난 행동에 대한 사과가 선행되지 않았으므로 난 널 용납할 필요가 없다.
12.15 04:59:00
ㅇㅇ(123.109)
그래서 짜보고서 떠든거는 한거니?
12.15 04:59:44
- ㅇㅇ(123.109)
  오타 정정: 떠든거는 --> 떠든거긴
  12.15 05:01:04
ㅇㅇ(123.109)
앙?
12.15 05:00:05
codesafer
당연히 짜봤지. 정신병원은 다녀온거니?
12.15 05:01:21
codesafer
이상 말걸지 마라.
12.15 05:01:49
ㅇㅇ(123.109)
어케 속도가 잘 나오셨어? O(1)버퍼를 사용해야 속도가 그나마 나온다는 것도 무려 엇그제 아셨는데?
12.15 05:02:21
codesafer
첫 글 다시 읽어봐라.
12.15 05:03:24
- codesafer
  너는 내 첫 글 아직 하나도 이해 못했으니까 다시 읽어보든지, 아니면 발 딱고 자라
  12.15 05:09:31
- codesafer
  이해력 박살난 애 한테 시간 더이상 낭비하기 싫고,
  12.15 05:09:52
- codesafer
  니가 잘못을 뉘우치지 않고 스토킹하니 경찰이든 교수든 대동해서 사실 확인해 줄테니까, 전번 남기란거임.
  12.15 05:12:46
- ㅇㅇ(123.109)
  코세왈: "inplace(머지소트) 가 느린 이유는 swap 비용이 커서인데, 그 느린 정도도 일반 merge 랑 크게 차이나지 않아" 나: "알고나 떠드는 거냐? 그냥 들어 본거 붙이지 말고" 너: 짜보고 떠든다. 넌 뭐 개소리냐?;
  12.15 05:16:43
- codesafer
  내가 inplace merge 를 직접 구현했다고 한 적 없고 2N 버퍼 merge sort 를 만들었을때 셋을 같이 돌려봤었다고 했고, 벤치 돌려본건 사실이고 별차이 안나는것도 사실이고, O(1) 버퍼 모드로 돌려서도 10% 언저리 차이밖에 안났고, std::stable_sort 조차도 그 내부에서 마지막 단계에 inplace_merge 의 core 함수인 buffered inplace sort 코드를 사용함. 그러니까 이해력 떨어지는 애를 위해 다시 말해주면, stable_sort 조차도 O(1) inplace_merge 를 내부에서 사용함.
  12.15 05:21:05
- codesafer
  내가 swap 비용을 해결하기 위해 소스코드를 뜯어볼 필요가 있다고 이야기 했던거고, 넌 벤치돌리는데 소스를 왜 보냐고 비웃었음.
  12.15 05:21:59
- codesafer
  이제 그만하든지 전번 남기든지 둘 중 하나 택해 더이상 상대안함.
  12.15 05:25:07
- ㅇㅇ(123.109)
  너 정신과적인 문제가 있는거 같다 정말로.
  12.15 05:26:53
- codesafer
  전번까
  12.15 05:28:12
- codesafer
  넌 지금 범죄를 하고 있는거야
  12.15 05:28:23
- ㅇㅇ(123.109)
  교수님 대동하시고 사실을 확인해 주시게? 본인이 교수님인 줄 알았는데? 아니였는감? ㅎㅎ
  12.15 05:29:05
- codesafer
  전번까라 빨리.
  12.15 05:29:16
- ㅇㅇ(123.109)
  걍 바본가 보다
  12.15 05:29:50
- codesafer
  니 말이 팩트 같으면 전번까. 경찰에서 너한테 뭐라고 안할꺼아냐. 팩트가 중요하면 전번까. 내가 팩트인지 니가 팩트인지 분명히 알게 해줄께.
  12.15 05:30:02
- codesafer
  전번 못까면 도망가는거야.
  12.15 05:30:33
- ㅇㅇ(123.109)
  여기서 알게 해주시면 알되요? 본인이 교수님 같으신데. ㅎㅎ
  12.15 05:31:13
- codesafer
  알아듣지도 못하면서, 사실을 이해할 생각도 없으면서, 말걸질 말라니깐 이새끼가진짜.
  12.15 05:31:22
- ㅇㅇ(123.109)
  팩트가 뭐냐하면
  12.15 05:31:47
- ㅇㅇ(123.109)
  니가 교수다 ㅎㅎ
  12.15 05:32:10
- codesafer
  왜 사실확인 못해? 니가 주장만 하고 니 생각에 내가 주장만하는것 같으면 중재가 필요할꺼아냐? 난 이딴 시간낭비 하기 싫으니까, 교수랑 경찰 대동해줄테니 전번까.
  12.15 05:32:10
- ㅇㅇ(123.109)
  이지랄 언제까지 계속할거냐?
  12.15 05:33:13
- codesafer
  못하지? 그게 니 수준이야. merge sort 실컷 이야기하니 std::sort 랑 벤치 한번 돌려보는게 니 수준이야.
  12.15 05:33:26
- ㅇㅇ(123.109)
  참나 진지하게도 코미디 하네
  12.15 05:33:56
- codesafer
  정정당당하게 경찰앞에서 팩트확인 못할꺼면 더이상 말 붙이지 마라. 마지막 통보.
  12.15 05:34:16
- ㅇㅇ(123.109)
  어이구, 경찰이 뭘 확인해 주냐 이 이해력 좋은 ㅅㄲ야 ㅎㅎ 우리 경찰 불러서 사주에 대해서 얘깋해 보면 되겠네. 경찰이 명리학에 관한 팩트!를 체크해 주고!
  12.15 05:37:30
- codesafer
  알겠음. 너 조치하겠음.
  12.15 05:41:17
댓글돌이
‘공관을 딸 신혼집으로’ 이영주 갑질 사건, 경찰로

1/10
ㅇㅇ(123.109)
뭘다시 읽어?
12.15 05:03:43
codesafer
말 걸고 싶으면 전화번호 내 놓고 말걸어
12.15 05:04:19
ㅇㅇ(123.109)
전화번호 같은 소리 하고 있네. 너 뭐하자는 거냐? 쥐패게? 제발 말로해 주세요 ㅎㅎ
12.15 05:05:12
ㅇㅇ(123.109)
이거 댓글달기가 안된다. 테스트
12.15 05:26:04

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	날짜	조회	추천
설문	2018년 가장 기억에 남는 이슈는?	운영자	18/12/10	-	-
공지	프로그래밍 갤러리 FAQ(자주 하는 질문) 읽어주세요.... 흐극흐극 [85]	dlbo	12/01/31	70732	315
공지	프로그래밍과 관련된 사진과 내용이 있어야 합니다. [371]	운영자	05/06/21	681984	17
951589	대학4년이 많이중요한것같지않음? [1]	ㅎㅎㅎ(175.113)	12/15	19	0
951588	전부 캡쳐 완료 [1]	codesafer	12/15	18	0
951587	일본이 한국 경쟁상대나 되냐 [1]	ㅇㄷㅎ(174.225)	12/15	15	0
951586	아니 뭐가 좀 진짜 이상한 사람같음 [3]	Recursion	12/15	33	0
951585	와 에어비앤비 호스트 진짜 뭐같네 [1]	Recursion	12/15	29	0
951584	콜스택 크기 넘어서도록 스택을쌓으려면	ㅇㅇ(59.24)	12/15	20	0
951583	석사 월급 너무짠대 이거받고 어케사냐 [16]	점진적러스트(114.70)	12/15	87	0
951582	VS로 디버깅 못하면 뭘로하냐 니들 [2]	ㅇㅇ(59.24)	12/15	23	0
951581	무능은 죄악이다 [4]	Recursion	12/15	52	0
951580	누나 몸파는건 아니고 화류계쪽 일하는데 [3]	ㅇㄷㅎ(174.225)	12/15	51	0
951578	메모이제이션은 위대한거같다 [3]	aaa(125.186)	12/15	31	0
951577	여기에 드라이브에 올린 내 사진하고 영상들이 있는 건가	급진적자살(211.244)	12/15	17	0
951576	요즘 너무 일찍 자고 일찍 일어난다 [5]	땡칠도사	12/15	51	0
951574	나이들고보니 일진들도 필요한것같다	1234(223.33)	12/15	43	0
951573	비전공인데 이쪽전공하고싶으면 어떻게함?? 나이는 많아서 대학은 다시못갈듯	ㅇㅇ(121.166)	12/15	22	0
951572	일본 경력직 대우어떰?	급진적자살(110.70)	12/15	9	0
951571	과제 대행 해줄사람 있음? [1]	ㅇㅇ(116.122)	12/15	33	0
951570	나이들수록 양아치들이 안보이는이유가머임? [1]	1234(223.33)	12/15	47	0
	코세야 이게 니가 말한 O(1) inplace 머지소트의 속도다 [45]	ㅇㅇ(123.109)	12/15	120	3
951568	한 언어로만 만들어진 AAA급 게임 있음?	ㅇㄷㅎ(108.35)	12/15	30	0
951564	ssh 클라 머가 좋나욘 [2]	ㅇㅇ(185.92)	12/15	23	0
951560	공교육은 무너져야한다 [1]	Recursion	12/15	43	0
951558	그렿다자바는개발자를믿지않는다	Scala	12/15	40	0
951557	밤에만 공부 잘되는 애들 있냐? [3]	ㅇㅇ(113.59)	12/15	52	0
951556	서비스직이 최악의직종인듯 [1]	1234(223.33)	12/15	40	0
951555	유사시 도로 위 의전서열 어떻게되냐 [4]	ㅇㄷㅎ(108.35)	12/15	42	0
951554	근데 확실히 내가 모르던 거 타인이 쉽게 풀면	급진적자살(211.244)	12/15	36	0
951553	근데 대체 프로그래머 실력기준이 뭐냐?? [5]	ㅎㅎㅎ(175.113)	12/15	85	0
951552	이과 정시 41232 로 한양대 왜못가냐 [2]	ㅇㄷㅎ(174.225)	12/15	42	1
951551	프로그래머 대졸에 좀 버티기만하면 연봉많이받지않음? [6]	ㅎㅎㅎ(175.113)	12/15	82	0
951550	명지대 출신 프로그래머 초봉 얼마 가능함? [8]	명지대programmer	12/15	93	0
951549	규칙 찾기 문제 풀기 끗	綾香	12/15	34	0
951548	1.C언어배우고 C 하기 2.바로 C	ㅇㅇ(1.248)	12/15	37	0
951547	전자과 컴공복전생인데 질문점여	부싼사나이다임마	12/15	27	0
951546	프갤엔 어느분야 개발자가 많음 [4]	C++11(210.179)	12/15	70	0
951545	프로그래머 진입장벽 높은편이냐? [4]	ㅎㅎㅎ(175.113)	12/15	83	0
951544	디시 오늘 처음하는데 [6]	컴현(58.238)	12/15	62	0
951543	페이스북도 하버드 친목모임으로 시작함 [1]	Recursion	12/15	54	0
951542	내 로빈후드해보고싶은놈들은 [5]	개발자노무현	12/15	54	0
951541	한글이 진짜 위대한 언어 아니냐 [5]	ㅇㄷㅎ(108.35)	12/15	61	0
951540	3달간 노오력한 끝에 커뮤니티 사이트 만들었다! [5]	컴현(58.238)	12/15	76	0
951539	게임아이디어좀 [9]	개발자노무현	12/15	81	0
951538	다익스트라가 다익스트라 만듬?ㄷㄷ [1]	중앙대 불교학부(36.38)	12/15	42	0
951537	다익스트라가 운영체제랑 알고리즘 중요한이론 혼자다만든거냐	ㅇㅇ(223.39)	12/15	27	0
951536	STL 언제 나옴 [1]	ㅇㅇ(175.223)	12/15	27	0
951535	본인도어릴떈 수학이 좋았는데 [4]	네이노옴	12/15	73	0
951534	미호토노 최고다.. [4]	개발자노무현	12/15	36	0
951533	나도 고딩땐 수학 좋아했는데 [3]	ㅇㅇ	12/15	59	0