Stl pq clear 없는거 좀 치명적이네

코딩 채널

알림 알림 중 알림 취소

구독자 4410명 알림수신 85명 @은월영

프로그래밍 및 코딩 채널

무야호원순

추천 0 비추천 0 댓글 13 조회수 149 작성일 2023-08-29 12:32:04 수정일 2023-08-29 12:32:29

https://arca.live/b/programmer/84953533

함수 진입시에 priority_queue<int> pq 혹은 pq={} 식으로 초기화 했는데

쿼리 무식하게 들어올때마다 이지랄하면

성능저하 체감 엄청되네

arr에 직접 힙 구현하고 heapSize만 0으로 초기화하는 방식이랑 같은 알고리즘 문제 제출시 5배 차이가나네

이거 좋은 초기화 방법이 있나? 찾아봐도

위에껄로 초기화하는게 대부분이던데

댓글 [13] 글쓰기

ㅇㅇ (175.159)

2023-08-29 13:29:06 삭제 수정 답글

최적화 필요하면 algorithms에 heap operations 맀으니까 그거 쓰셈.

펼쳐보기▼

정규식

2023-08-29 13:31:15 답글

std::priority_queue<int> pq;
for (size_t i = 0; i < 100; i++)
	pq.push(rand());
reinterpret_cast<decltype(pq)::container_type*>(&pq)->clear();
std::cout << pq.size();

흑마법 써봤는데 진심 개지랄이라고밖에는 생각이 안듬

펼쳐보기▼

정규식

2023-08-29 13:32:40 답글

*수정됨

비주얼 C++20에서는 동작하는거 확인했는데 버전을 내리거나 gcc만 가도 터지거나 심지어는 오동작할수도
아니면 겉보기에만 정상동작 하는걸수도 있고..

펼쳐보기▼

무야호원순

2023-08-29 16:19:21 답글

채점서버가 c++17인데 함 테스트해봐야겠네

펼쳐보기▼

정규식

2023-08-29 13:54:59 답글

https://stackoverflow.com/questions/1185252/is-there-a-way-to-access-the-underlying-container-of-stl-container-adaptors

Stack Overflow

Is there a way to access the underlying container of STL container adaptors?

Is there a standard way to access the underlying container of stack, queue, priority_queue ? I found a method called : _Get_container() in VS2008 implementation of stack and queue, but no one for

스프

2023-08-29 16:16:14 답글

좀 다른 의미로 흑마법이긴 한데, std::set도 사실 내부적으로 RBT고 원소들이 정렬돼 있거든. 그래서 rbegin() 으로 가장 큰 원소의 itr 따오고 *itr로 원소 접근, 그 뒤에 erase(itr) 해버리면 pq랑 유사하게 쓸 수 있어. rbegin() 쓰는 게 맘에 안 들면 set 선언할 때 comparator를 std::greater 로 바꿔주면 되고.

근데 혹시 알고리즘이 strictly pq가 필요한 상황인지 한 번 고민해보는 것도 좋을 듯. 정확히 어떤 걸 구현하는진 모르겠지만 pq를 루프마다 초기화해야 하는 상황이 어떤 게 있을지 잘 모르겠어서...

펼쳐보기▼

무야호원순

2023-08-29 16:18:26 답글

문제에서 매 쿼리마다 bfs를 돌리는건데 그냥 대놓고 우선순위 pq문제라서.. set써봣는데 stl pq랑 생각보다 차이가 별로 안나더라고 근데 stl쓰는거랑 쌩구현이랑 차이가 꽤나네

펼쳐보기▼

스프

2023-08-29 16:25:45 답글

아 BFS면은 어쩔 수가 없지... 윗댓 말대로 std::deque에다가 std::push_heap 써서 작업하고 루프 끝날 때마다 deque erase 해주는 게 제일 깔끔하고 성능 보전할 수 있는 방법 같아.

STL이 std 라이브러리 말하는 거면 거기 구현체들이 어지간한 프로그래머들이 할 수 있는 것보다 훨씬 수준 높고 고성능으로 짜여 있어서 웬만하면 다시 짜는 게 훨씬 비효율적이야 ㅇ.ㅇ

펼쳐보기▼

스프

2023-08-29 16:26:39 답글

https://en.cppreference.com/w/cpp/algorithm/push_heap

이거 참조. 대충 max heap 성질을 보전하도록 알아서 insert 해주는 함수 같음.

cppreference.com

std::push_heap - cppreference.com

이거 참조. 대충 max heap 성질을 보전하도록 알아서 insert 해주는 함수 같음.

펼쳐보기▼

무야호원순

2023-08-30 06:24:32 답글

이거 적용해봤는데 내부 container가 vector라 그런지 매번 새로 만들때마다 메모리 할당해서 그런지 큰차이가 안나는거 같음..

Stl priority queue 랑 비교했을때

혹시나해서 vector capacity fix 해놓고 해봐도 영향이 없네

걍 이런 쿼리문제는 가급적 정적배열로 heap 구현 해야겠다

펼쳐보기▼

스프

2023-08-30 14:40:39 답글

새로 만들지 말고 매 루프마다 erase() 만 하는 식이면 좀 덜하지 않나?

펼쳐보기▼

무야호원순

2023-08-31 03:57:05 답글

Pq erase가 없어서 그래하려면 pq empty까지 pop 해야하는데 이러면 남아있는 원소갯수만큼 nlogn 이지않나?

펼쳐보기▼

스프

2023-08-31 04:12:42 답글

어차피 deque나 vector 위에서 작업하니까, deque erase 쓰면 capacity는 보전한 채로 O(1) erase 되니까 괜찮을 거 같은데

펼쳐보기▼

댓글 작성

업로드 중

0초

녹음 중지 삭제

글쓰기

전체글 개념글

최근 최근 방문 채널

최근 방문 채널

전체 공지 정보 질문 잡담 유머 C/C++ C# Python Java Front-end Back-end 앱·겜 AI·Data 그 외

번호 제목

작성자 작성일 조회수 추천

현직 개발자들 챗GPT 쓰는지 궁금함 [9]

ㅇㅇ 2023.08.30 332 0

잡담 이력서 100군데 뿌린 후기 [16]

나리 2023.08.30 552 1

고대 유물 [3]

반으로_갈라져_죽었다 2023.08.30 131 0

요즘 매일 겪는 일 [2]

농즈 2023.08.29 129 1

질문 Native CSS nesting 질문 [3]

ㅇㅇ (112.216) 2023.08.29 96 0

앱·겜 생각없이 머리박는거 은근 재밌다 [1]

악해병당고가너무좋아준코님 2023.08.29 241 0

Back-end edgedb 좋음? [1]

침대위사과 2023.08.29 86 0

잡담 진짜 애플 앱스토어 리뷰 짜증나네 [1]

Naolin 2023.08.29 129 0

질문 mit app inventor로 코딩중인데

Popcat1 2023.08.29 54 -1

질문 CSS flex, grid 없을 땐 레이아웃 어떻게 짰음? [4]

ㅇㅇ (112.216) 2023.08.29 141 0

Stl pq clear 없는거 좀 치명적이네 [13]

무야호원순 2023.08.29 149 0

깃 프로그램 다들 뭐씀? [12]

Seol 2023.08.29 230 0

문제 풀고나서 다른 답안보면 [1]

ㅇㅇ 2023.08.29 76 0

잡담 개인플젝하는데 [4]

일하기짱시름 2023.08.29 199 0

이런거 할 때 쓰는 패턴 있었는데.. [2]

Zeya 2023.08.29 108 0

잡담 ... [1]

나리 2023.08.29 122 0

질문 yt-dlp 7월 6일 패치 이후 써본사람 있음? [6]

뭉게먹구름 2023.08.29 168 1

앱·겜 팀 스위니 싸인받음 [4]

로켓곰군 2023.08.29 161 0

내가 맥을 산 이유

보빗보빗보비빗 2023.08.29 110 1

그 외 Lua에 관해 잘 아시는 분 계시나요? [1]

비사코딜 2023.08.29 160 0

글쓰기

전체글 개념글