제가 어떻게 양말을 효율적으로 더미에서 짝맞추어 나갈 수 있을까요?

어제는 깨끗한 빨래에서 양말을 짝지어 주었는데, 내가 그것을 하는 방식은 매우 효율적이지 않다는 것을 깨달았다. 나는 단순한 검색을 하고 있었는데, 양말 하나를 선택하고 짝을 찾기 위해 순서대로 양말을 조작했다. 이는 평균적으로 n/2 * n/4 = n 2 /8 양말을 순회해야 한다.

컴퓨터 과학자로써, 제가 할 수 있는 일은 무엇일까 고민했습니다. 크기/색상 등을 기준으로 정렬하는 것은 O(NlogN)의 해결책을 얻을 수 있다는 생각이 들었습니다.

해싱이나 다른 인플레이스 솔루션은 선택할 수 없습니다. 내 양말을 복제할 수 없기 때문입니다 (복제할 수 있다면 좋겠지만).

그래서, 질문은 기본적으로 다음과 같습니다.

양말 쌍이 # $ # $ & $ & $ & $ & $ # 원소를 포함한 쌓여있는 상태에서 (각 양말이 정확히 하나의 일치하는 쌍을 가진다고 가정), 최적의 방법은 로그를 초과하지 않는 추가 공간으로 효율적으로 짝을 지어주는 것입니다? (필요한 경우 그 양만큼의 정보를 기억할 수 있다고 믿습니다.)

다음 측면을 다룬 답변에 대해 감사하겠습니다:

대량의 양말에 대한 일반적인 이론적 해결책.

양말의 실제 수는 크지 않으며, 제 배우자와 저는 30쌍 이상을 가지고 있지 않은 것 같습니다. (또한 제 양말과 그녀의 양말을 분별하는 것은 꽤 쉽습니다. 이것도 사용할 수 있을까요?)

element distinctness problem 와 동일한가요?

답변 1

정렬 솔루션이 제안되었지만, 정렬은 조금 지나친 기능입니다. 우리는 순서를 필요로하지 않고, 단지 동등한 그룹이 필요합니다.

해싱만으로 충분합니다 (그리고 더 빠릅니다).

양말의 각 색상마다 한 더미를 만듭니다. 입력 바구니의 모든 양말을 반복하고 색상 더미에 나누어 넣습니다.

각 더미를 순환하고 다른 지표 (예: 패턴)로 두 번째 더미 집합으로 분산시킵니다.

당신이 모든 양말을 시각적으로 즉시 처리할 수 있는 아주 작은 더미로 분산시킬 때까지이 계획을 재귀적으로 적용하십시오.

이러한 재귀적 해시 파티셔닝은 대규모 데이터 세트에서 해시 조인 또는 해시 집계가 필요할 때 SQL Server에 의해 실제로 수행됩니다. 이는 빌드 입력 스트림을 많은 독립적인 파티션으로 분산시키는 것입니다. 이 체계는 데이터 양과 다중 CPU에 대해 선형적으로 확장됩니다.

만약 충분한 버킷 크기를 제공하여 각 버킷을 매우 빠르게 처리할 수 있도록 하는 분산 키 (해시 키)를 찾을 수 있다면 재귀적인 분할이 필요하지 않습니다. 불행히도, 양말에는 이러한 속성이 없다고 생각합니다.

각 양말마다 PairID라는 정수가 있으면 PairID % 10 (마지막 숫자)에 따라 쉽게 10 개의 버킷으로 분배할 수 있습니다.

제 생각에는 현실적인 분할 방법 중에서 가장 좋은 방법은 더미의 직사각형을 만드는 것입니다. 한 쪽은 색상이고 다른 쪽은 무늬입니다. 왜 직사각형인가요? 더미에 무작위로 접근하기 위해서는 O (1)의 무작위 액세스가 필요하기 때문입니다. (3D cuboid 도 작동하지만, 실용적이지 않습니다.)

업데이트:

병렬성은 어떻게 되나요? 여러 명의 인간이 양말을 더 빨리 짝지을 수 있나요?

가장 간단한 병렬화 전략은 여러 작업자가 입력 바구니에서 양말을 가져와 더미에 올리는 것입니다. 그러나 이 전략은 한계가 있습니다. 10개의 더미를 놓기 위해 100명이 싸우는 상황은 상상해 볼 수 있을 것입니다. 싱크로나이제이션 비용(손 충돌과 인간 간 통신으로 나타나는)은 효율성과 속도를 손상시킵니다 ( Universal Scalability Law! 참조). 이것이 교착 상태에 빠지기 쉬울까요? 아니요, 왜냐하면 각 작업자는 한 번에 하나의 더미에만 액세스하면 되기 때문입니다. 하나의 잠금만 있으면 교착 상태가 발생할 수 없습니다. 인간이 더미에 액세스하는 방법에 따라 충돌만 일어나는 라이브락이 가능합니다. 그들은 물리적 수준에서 네트워크 카드가 네트워크 선에 독점적으로 액세스할 수 있는 카드를 결정하는 것과 같은 방식을 사용할 수 있습니다. 이게 NICs 작동하는 방식이라면, 인간에게도 작동할 것입니다.

각 작업자가 자체적인 양말 더미를 가지고 있다면, 거의 무제한으로 확장 가능합니다. 작업자들은 입력 바구니에서 대규모 양말 덩어리를 가져 갈 수 있으며 (드물게 수행하기 때문에 매우 적은 경합이 있음), 양말을 분배할 때 동기화할 필요가 없습니다 (스레드 지역 더미를 가지고 있기 때문입니다). 마지막으로, 모든 작업자는 자신의 더미 집합을 연결해야합니다. 작업자가 집계 트리를 형성하면 O(log (작업자 수 * 작업자 당 더미 수))에 수행할 수 있다고 믿습니다.

element distinctness problem 에 대해서 어떻게 생각하세요? 기사에서 언급한 대로, 원소 구별 문제는 O(N) 에서 해결할 수 있습니다. 이는 양말 문제에 대해서도 동일합니다 (한 번의 분배 단계만 필요하다면 O(N) 동일합니다 (여러 단계가 제안된 이유는 인간이 계산을 잘 못하기 때문이며, 모든 속성의 완전한 해시인 md5(color, length, pattern, ...) 에 분배하는 한 단계면 충분합니다)).

분명히, 더 빠르게 나아갈 수 없으므로 우리는 최적 하한에 도달했습니다.

출력물은 정확히 같지 않지만 (한 경우에는 단일 부울 값, 다른 경우에는 양말 쌍), 극한 복잡도는 동일합니다.

답변 2

양말을 쌓은 상태에서 효율적으로 양말을 짝짓는 방법에 대하여 알아보자. 여러분이 양말을 짝지어야 할 때마다, 구석 구석 뒤지면서 필요한 양말을 찾는 일이 매우 번거롭고 시간도 많이 걸린다. 이런 경우, 효율적인 방법을 사용하여 빠르고 쉽게 양말을 짝지을 수 있도록 해보자.

첫 번째 방법은 쌓아 둔 양말을 분류하는 것이다. 양말을 쌓아 두는 경우, 크기, 색상 및 디자인을 기반으로 분류하여 양말을 그룹으로 만들어 놓으면 굉장히 편리하다. 예를 들어, 검은색 양말, 하얀색 양말, 연한 색 양말, 진한 색 양말 등의 색상별 그룹으로 만들면, 필요한 양말을 쉽게 찾을 수 있다.

두 번째 방법은 짝을 이룰 양말을 미리 추려놓는 것이다. 양말을 세로로 접어 놓은 후에 짝을 이룰 양말을 미리 추려놓으면, 양말을 짝지을 때 시간을 많이 절약할 수 있다.

세 번째 방법은 짝지을 양말을 일치시키는 것이다. 양말을 짝지을 때, 크기 및 디자인이 완전히 일치하는 것이 중요하다. 따라서 양말을 짝지을 때, 양말의 크기, 디자인 및 색상을 모두 고려하여 일치시켜야 한다.

양말을 모든 사람들이 하루 종일 신고 다니기 때문에 지속적으로 처리해야 하는 불가피한 작업 중 하나이다. 이것이 얼마나 시간과 노력이 들어갈 수 있는지 모를 수 있다. 다만, 위에서 제시한 방법을 따른다면 효율적이고 빠르게 양말을 짝짓을 수 있을 것이다. 이를 통해 생활 속 작은 문제를 쉽게 해결할 수 있으며, 일상 생활에 불필요한 스트레스를 줄일 수 있다.