디시인사이드 갤러리

갤러리 이슈박스, 최근방문 갤러리

갤러리 본문 영역

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

ㅇㅇ(123.109) 2018.12.15 04:02:35
조회 1532 추천 15 댓글 59
														

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

코세가 높이 치하한 WikiSort:
    O(1) inplace merge 를 사용하는 sort 들.
    https://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 머지소트 조차
순수 성능향상을 목적으로 선택하기에는 기본적으로 느리다는 것은 돌려 봤으면 안다는 것은 변함이 없다.


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


추천 비추천

15

고정닉 4

1

댓글 영역

전체 댓글 0
본문 보기

하단 갤러리 리스트 영역

왼쪽 컨텐츠 영역

갤러리 리스트 영역

갤러리 리스트
번호 제목 글쓴이 작성일 조회 추천
설문 연말 모임 가는 곳마다 가장 인싸일 것 같은 스타는? 운영자 25/12/08 - -
이슈 [디시人터뷰] 솔직함을 리뷰하는 유튜버, 흑백리뷰 운영자 25/12/09 - -
AD 루틴 ON! 운동 찐템! 지금 할인 중 운영자 25/11/27 - -
공지 프로그래밍 갤러리 이용 안내 [98] 운영자 20.09.28 48870 65
2907512 개발자 말고 애퍼 어떻냐? 헬마스터갤로그로 이동합니다. 23:31 11 0
2907511 마취 없는 절단→임산부 실험…인간 생체실험 고발 '731' 개봉 발명도둑잡기(118.216) 23:25 7 0
2907509 “수용소에 가둬 폭파해 죽인다” 한국판 홀로코스트? 발명도둑잡기(118.216) 23:08 8 0
2907508 이 사람 문제있다 [3] 노력갤로그로 이동합니다. 23:08 22 1
2907507 [국가보안법을 박물관으로] 말의 세계에 감금된 것들 전시회 해설 영상 발명도둑잡기(118.216) 23:06 6 0
2907506 국가보안법이 뭐냐구요? 우리랑 무슨 상관이냐구요? 발명도둑잡기(118.216) 23:04 7 0
2907505 [풀영상] 심리스릴러 다큐멘터리 게임의 전환 발명도둑잡기(118.216) 23:03 7 0
2907504 문이과 통합 통섭 사이언스 첨단 전공 학과!% 프갤러(121.142) 23:01 10 1
2907503 [기획영상] 당신들 여태 뭘한거요? 발명도둑잡기(118.216) 23:00 9 0
2907502 SEJEONG(세정) _ Tunnel(터널) 발명도둑잡기(118.216) 22:56 7 0
2907501 中 민간 드론, 타이완 진먼섬 침투해 전단 살포 / YTN 발명도둑잡기(118.216) 22:54 7 0
2907499 문성근 "'블랙리스트' 가장 큰 피해자는 배우 김민선" / YTN 발명도둑잡기(118.216) 22:39 7 0
2907498 '문성근-김여진 합성사진' 재판... "참담하다" 국정원 직원의 눈물 발명도둑잡기(118.216) 22:38 8 0
2907497 국정원 블랙리스트에 '찍힌 연예인' 집단 소송 움직임 발명도둑잡기(118.216) 22:34 10 0
2907496 국가보안법과 헌법의 충돌 현장! | 변호인(영화-2013) | 노무현 발명도둑잡기(118.216) 22:30 7 0
2907495 국가보안법과 표현의 자유는 양립불가 [1] 발명도둑잡기(118.216) 22:24 10 0
2907494 정지영 감독, "국보법 때문에 나도 '자기검열' 해야 했다." [1] 발명도둑잡기(118.216) 22:22 10 0
2907492 국가보안법 철폐가 3 - 노래패 우리나라 발명도둑잡기(118.216) 22:16 9 0
2907491 국가보안법 철폐가 2 발명도둑잡기(118.216) 22:15 9 0
2907490 국가보안법 철폐가 발명도둑잡기(118.216) 22:12 9 0
2907489 쿠팡 패스워드가 뚫린 것 같습니다. ㅠㅠ [4] 나르시갤로그로 이동합니다. 21:26 38 0
2907488 부트캠프란 용어는 미제 군국주의의 잔재다 [8] 발명도둑잡기(118.216) 21:14 32 0
2907486 ◆ 볼보트럭 정비사 VS 개발자 [1] ㅇㅇ갤로그로 이동합니다. 21:04 37 0
2907485 님들 화면이 깜빡이다가, 소리 나오면 잘 나와요. 넥도리아(220.74) 21:03 9 0
2907484 NetBSD 이식성 유사 운영체제 발명도둑잡기(118.216) 20:57 41 0
2907483 NetBSD 부러운 점이 하드웨어 이식성 발명도둑잡기(118.216) 20:50 18 0
2907482 나 대학생 때는 리눅스 커널 버전이 2.2대였는데 2.4로 올라가면서 발명도둑잡기(118.216) 20:45 17 0
2907481 요즘 구형 컴퓨터 에뮬레이터는 FDD, HDD 소리도 내주네 발명도둑잡기(118.216) 20:39 14 0
2907480 이거 음악 제목 아시는 분 발명도둑잡기(118.216) 20:25 14 0
2907479 프로그래머스 국비 경쟁률 왜케 빡셈 프갤러(175.214) 20:21 22 0
2907477 아~ 한남패죽이기 딱 좋은날이다 [8] 개멍청한유라갤로그로 이동합니다. 20:07 52 0
2907476 요즘 국비를 부캠이라고 함? [3] 헬마스터갤로그로 이동합니다. 19:58 50 0
2907475 FreeBSD용 Nimf 2025.12.10 출시합니다. [5] 나르시갤로그로 이동합니다. 19:49 24 0
2907474 부캠 투표 좀 [1] 프갤러(182.230) 19:37 32 0
2907472 좇센은 범죄자새끼들만 좇같은게아니라서 더 좇같은나라인거임 타이밍뒷.통수한방(1.213) 19:24 22 0
2907471 면 개발자 만으로 7년 느낀 점 hep갤로그로 이동합니다. 19:10 34 0
2907470 거이씹 모기새기 [3] ♥발라당냥덩♥갤로그로 이동합니다. 19:07 33 0
2907468 프로그래밍 1도 모르던 내가 게임모드 만들엇슴... 프갤러(183.104) 18:55 44 1
2907466 점심 간식 발명도둑잡기(39.7) 18:46 16 0
2907463 프리랜서랑 정규직 같이 해본 사람 있어? 야옹해갤로그로 이동합니다. 18:00 29 0
2907462 회사가 니네 누군지 모를 거 가틍ㅁ??? ㅋㅋ [3] ㅇㅇ(222.108) 17:58 72 0
2907461 임포스터 증후군을 체험하기 위한 가짜 자괴감 끝에 [2] chironpractor갤로그로 이동합니다. 17:52 31 0
2907458 신입 개발자 오늘 한 일. [8] cvs.갤로그로 이동합니다. 17:40 91 0
2907457 왜 프로그래머는 화가 많을 [1] ㅇㅇ(222.108) 17:40 41 0
2907456 쌩초보 강의 or 책 추천해주세요........ [8] 프갤러(211.50) 17:36 49 0
2907455 니네 ai 이용해서 수학 공부해라 [5] ㅇㅇ(222.108) 17:36 61 0
2907453 집에 가자 ! cvs.갤로그로 이동합니다. 17:20 15 0
2907452 Hex dump 에서 원본 복구 절대못하지? [3] 프갤러(106.101) 17:01 46 0
2907451 장사를 해보니 개발이 재밌었긴 했지만 [2] chironpractor갤로그로 이동합니다. 16:51 60 0
갤러리 내부 검색
제목+내용게시물 정렬 옵션

오른쪽 컨텐츠 영역

실시간 베스트

1/8

디시미디어

디시이슈

1/2