priority queue 는 보통 heap 트리로 구현하는데,
힙트리는 lock 없이, 또는 lock 을 가볍게 만들기가 굉장히 힘듬
원소 하나 pop 하는 순간 트리를 reheap 해야돼서 ㅇㅇ
근데 병렬 알고리즘들이 생각보다 pq 를 쓰는 경우가 많아서 pq 를 scalable 하게 만드는게 몇년간 화두였는데,
그래서 나온게 뭐냐
relaxed priority queue
관련해서 나온 가장 최근 논문은 아래
https://dl.acm.org/doi/10.1145/2755573.2755616
priority 의 정확한 정렬을 그냥 포기함 ㅇㅇ
그래서 concurrent priority queue 안에 pq 를 잔뜩 넣고,
round robin 형식으로 새로 접근하는 애들마다 pq 를 빠르게 하나 줘서 lock 이 걸리는 시간을 최소화함
그 다음으로 접근하는 애들은 바로 다음 pq 를 줘버림
각 pq 끼리는 priority 정렬이 안되니까 그건 그냥 포기
오늘의 교훈: '정확한 답' 만을 요구하는 PS 문제풀이는 현실에서 별로 쓸모가 업따
정석을 알아야 변화를 주긴 하지
잘 몰라서 물어보는건데 목록에서 값을 원하는거 하나 빼서 주고 싶은데 이러면 다시 정렬해야 하니 그냥 목록 자체를 존나게 만들어서 여기서 원하는거 빼서 쓰라고 하는건가
pq 가 하나만 있으면 그거 정렬하는 동안 남들이 기다려야되니까, 여러개 만들어서 이미 정렬중인거 쓸 필요 없이 아무도 안 쓰고 있는걸 주자는 아이디어임 - return 0;
메모리를 대가로 속도를 빠르게 하나보네
이 동네에서는 메모리 별로 걱정 안 함. priority 의 정렬이 보장되는걸 포기하는게 크지 - return 0;
유머요소 ㅇㄷ
근데 정확하지않으면 의미가있음?
용도에 따라 다르죠 ㅇㅇ 근데 막상 보면 pq 가 쓰이는 경우들이 정확성을 그렇게 요구하지 않음. 예시: A* 알고리즘 - return 0;
오잉...A*는 무조건 최단거리보장 아니엇슴? 잘 몰라서 물어봄
A* 가 다익스트라의 탐색 속도를 pq 이용해서 단축하는 아이디어인데, pq 의 정렬순서가 보장될 필요가 없지 - return 0;
글로 요약되어져있는 설명만 봤을땐 아무리 "relaxed"한 priority_queue라지만 array(priority_queue, threadCount)같은 naive implementation에서 priority queue에 "priority"란 단어를 붙이기도 애매한수준의 형편없는 정확성의 우선순위가 보장될거같아서 별 기대는 안하고 읽었는데 threadCount * 2혹은 4만큼의 queue를 관리하면서 밖에서 pop할때마다 내부queue 2개에서 element비교 후 뱉어내는식으로 정확성을 끌어올린 재밌는물건이었네. 덕분에 오랜만에 재밌는내용 읽고감. 혹시 위에 논문에 나온 cpq가 현 state of the art cpq임?