[algorithm] 더미에서 양말을 효율적으로 페어링하려면 어떻게해야합니까?

어제 나는 깨끗한 세탁물에서 양말을 페어링하고 있었고 내가하는 방식이 그렇게 효율적이지 않다는 것을 알았습니다. 나는 순진한 검색을하고있었습니다. 양말 하나를 골라서 짝을 찾기 위해 더미를 “추적”했습니다. 이 N / 2 * 4 / N = N 이상 반복 요구 ⁽²⁾ 평균 / 8 양말.

컴퓨터 과학자로서 내가 할 수있는 일을 생각하고 있었습니까? 물론 (크기 / 색상 / …에 따라) 정렬은 O (NlogN) 솔루션을 달성하기 위해 떠 올랐습니다.

내 양말을 복제 할 수 없기 때문에 해싱 또는 다른 비 현장 솔루션은 옵션이 아닙니다 (가능한 경우 좋을 수도 있지만).

따라서 문제는 기본적으로 다음과 같습니다.

요소를 n포함하는 양말 한 켤레가 주어지면 2n(각 양말마다 정확히 한 쌍의 짝이 있다고 가정) 최대 로그 공간까지 효율적으로 묶는 가장 좋은 방법은 무엇입니까? (필요하다면 그 정도의 정보를 기억할 수 있다고 생각합니다.)

다음과 같은 측면을 다루는 답변에 감사드립니다.

수많은 양말에 대한 일반적인 이론적 솔루션.
양말의 실제 개수는 그렇게 크지 않습니다. 배우자를 믿지 않으며 30 쌍 이상이 있습니다. (그리고 내 양말과 양말을 구별하는 것은 상당히 쉽습니다. 이것도 사용할 수 있습니까?)
요소 구별 문제 와 동등 합니까?

답변

정렬 솔루션이 제안되었지만 정렬이 너무 많습니다 . 주문이 필요하지 않습니다. 우리는 평등 그룹 만 있으면됩니다 .

따라서 해싱 이면 충분하고 빠릅니다.

양말의 각 색상에 대해 더미를 형성하십시오 . 입력 바구니에있는 모든 양말을 반복 하여 색상 더미에 분배 하십시오 .
각 파일을 반복하고 다른 메트릭 (예 : 패턴)으로 두 번째 파일 세트로 분배
시각적으로 즉시 처리 할 수있는 매우 작은 더미 에 모든 양말을 뿌릴 때 까지이 체계를 반복적으로 적용 하십시오.

이러한 종류의 재귀 해시 분할은 실제로 대규모 데이터 집합에 대한 조인 또는 해시 집계를 해시해야 할 때 SQL Server 에서 수행됩니다 . 빌드 입력 스트림을 독립된 많은 파티션으로 분배합니다. 이 체계는 임의의 양의 데이터와 여러 CPU로 선형 확장됩니다.

각 버킷이 매우 빠르게 처리 될 수있을만큼 충분한 버킷 을 제공 하는 배포 키 (해시 키)를 찾을 수있는 경우 재귀 분할이 필요하지 않습니다 . 불행히도 양말에는 그런 성질이 없다고 생각합니다.

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

내가 생각할 수있는 가장 실제 파티션은 사각형의 더미를 만드는 것입니다 . 한 차원은 색상이고 다른 차원은 패턴입니다. 왜 직사각형입니까? 우리는 파일에 O (1) 랜덤 액세스가 필요하기 때문입니다. (3D 직육면체 도 작동하지만 그다지 실용적이지 않습니다.)

최신 정보:

무엇에 대한 병렬 처리 ? 여러 사람이 양말을 더 빨리 맞출 수 있습니까?

가장 간단한 병렬화 전략은 여러 명의 작업자가 입력 바구니에서 가져 와서 양말을 더미에 놓는 것입니다. 이것은 너무 커집니다. 100 명이 10 개의 더미를 놓고 싸우는 것을 상상해보십시오. 동기화 비용 (수동 충돌 및 인적 커뮤니케이션으로 인한 피해) 은 효율성과 속도 향상을 파괴합니다 ( Universal Scalability Law ! 참조). 교착 상태 가 발생하기 쉽 습니까? 아니요, 각 작업자는 한 번에 하나의 파일에만 액세스하면됩니다. “잠금”이 하나만 있으면 교착 상태가 될 수 없습니다. 사람이 더미에 대한 접근을 조정하는 방법에 따라 라이브 록 이 가능할 수 있습니다. 그들은 단지 임의의 백 오프를 사용할 수 있습니다네트워크 카드와 같이 물리적 수준에서 네트워크 카드에 독점적으로 액세스 할 수있는 카드를 결정하기 위해이를 수행합니다. 그것이 작동하는 경우 NIC가 , 그것은 인간을 위해 일뿐만 아니라합니다.
각 작업자가 자신의 더미를 가지고 있다면 거의 무한정으로 확장됩니다 . 그런 다음 작업자는 입력 바구니에서 큰 양말 덩어리를 가져갈 수 있으며 (드물게하는 것처럼 아주 적은 경합) 양말을 분배 할 때 동기화 할 필요가 없습니다 (스레드 로컬 더미가 있기 때문에). 결국, 모든 노동자들은 말뚝 집합을 결합해야합니다. 작업자가 집계 트리를 구성하면 O (로그 (작업 자당 * 작업 자당 파일 수))로 수행 할 수 있다고 생각합니다 .

[정보] 어떤 요소 구별 성 문제 ? 기사에서 알 수 있듯이 요소 구별 문제는에서 해결할 수 있습니다 O(N). (또한이 양말 문제에 대해 동일 O(N)인간이 계산에 나쁜 이유만으로 당신은 단지 하나의 유통 단계 (I 여러 단계를 제안해야하는 경우 – 한 단계는 당신이에 배포 할 경우 충분하다 md5(color, length, pattern, ...), 즉 완벽한 해시 모든 속성의)).

분명히 하나보다 빠를 수 없으므로 최적의 하한에O(N) 도달했습니다 .

출력이 정확히 동일하지는 않지만 (한 경우 부울입니다. 다른 경우에는 양말 쌍), 점근 적 복잡성은 동일합니다.

답변

인간 두뇌의 구조는 현대의 CPU와 완전히 다르기 때문에이 질문은 실질적인 의미가 없습니다.

인간은 “일치하는 쌍 찾기”가 너무 크지 않은 세트에 대해 하나의 작업이 될 수 있다는 사실을 사용하여 CPU 알고리즘을 이길 수 있습니다.

내 알고리즘 :

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

적어도 이것이 실제 생활에서 사용하는 것이므로 매우 효율적입니다. 단점은 평평한 표면이 필요하지만 일반적으로 풍부하다는 것입니다.

답변

사례 1 : 모든 양말은 동일합니다 (실제로 제가하는 일입니다).

쌍을 만들기 위해 둘 중 하나를 선택하십시오. 일정한 시간.

사례 2 : 일정한 조합 (소유권, 색상, 크기, 질감 등)이 있습니다.

기수 정렬을 사용하십시오 . 비교가 필요하지 않기 때문에 이것은 단지 선형 시간입니다.

사례 3 : 조합 수는 미리 알려져 있지 않습니다 (일반 사례).

양말 두 개가 짝을 이루는 지 비교하기 위해 비교를해야합니다. O(n log n)비교 기반 정렬 알고리즘 중 하나를 선택하십시오 .

그러나 양말의 수가 상대적으로 적은 (일정한) 실제 생활에서는 이러한 이론적으로 최적의 알고리즘이 제대로 작동하지 않습니다. 이론적으로 2 차 시간이 필요한 순차 검색보다 시간이 더 걸릴 수 있습니다.

답변

비 알고리즘 대답이지만 내가 할 때 “효율적”입니다.

1 단계) 기존 양말을 모두 버립니다.
2 단계) Walmart 로 이동하여 10-n 개의 흰색 패킷과 m 개의 검은 패킷으로 구입하십시오. 일상 생활에서 다른 색상이 필요하지 않습니다.

그러나 때때로, 나는 이것을 다시해야합니다 (양말 양말, 손상된 양말 등), 나는 아주 좋은 양말을 너무 자주 버리는 것을 싫어합니다. 다른 접근법.

알고리즘 답변 :

당신이하고있는 것처럼 두 번째 양말 묶음에 양말을 하나만 그리는 것보다 순진한 검색에서 일치하는 양말을 찾을 확률은 매우 낮습니다.

따라서 5 개를 무작위로 집어 들고 모양이나 길이를 외우십시오.

왜 다섯? 일반적으로 인간은 작업 메모리에서 5 ~ 7 개의 서로 다른 요소를 기억하고 있습니다. RPN 스택 과 같은 약간의 요소입니다. 5는 안전한 기본값입니다.

2n-5 스택에서 하나를 선택하십시오.
이제 당신이 그린 5 개 안에서 일치하는 것을 찾으십시오 (시각적 패턴 일치-사람은 작은 스택으로 잘합니다).
더미에서 양말을 무작위로 뽑아 5 + 1 양말과 비교하십시오. 스택이 커지면 성능이 저하되지만 확률은 높아집니다. 훨씬 더 빨리.

일치하는 확률이 50 % 일 때 얼마나 많은 샘플을 그려야하는지 계산하려면 공식을 적어 두십시오. IIRC는 초 지오메트리 법칙입니다.

나는 매일 아침 그렇게하고 거의 3 개 이상의 무승부를 필요로하지 않는다. 그러나 나는 모양의 흰색 양말 n과 비슷한 쌍 (약 10 개, 잃어버린 것을주고 받음)을 m가지고있다. 이제 주식의 스택 크기를 추정 할 수 있습니다 🙂

BTW , 나는 한 쌍이 필요할 때마다 모든 양말을 분류하는 데 드는 거래 비용의 합계가 한 번만하고 양말을 묶는 것보다 훨씬 적다는 것을 알았습니다. 양말을 묶을 필요가 없기 때문에 Just-in-Time이 더 잘 작동하며, 한계 수익도 줄어들고 있습니다. 양말을 맞추기 위해 시간을 잃어 버립니다).

답변

내가하는 것은 첫 양말을 집어 내려 놓는 것입니다 (세탁 그릇의 가장자리에). 그런 다음 다른 양말을 들고 첫 양말과 같은지 확인합니다. 그렇다면 둘 다 제거합니다. 그렇지 않은 경우 첫 양말 옆에 내려 놓습니다. 그런 다음 세 번째 양말을 집어 들고 첫 번째 양말과 비교하십시오 (아직 거기있는 경우). 기타.

~~양말을 “제거”하는 것이 옵션이라고 가정하면이 방법은 어레이에서 쉽게 구현할 수 있습니다.~~ 실제로, 양말을 “제거”할 필요조차 없습니다. 양말을 정렬 할 필요가 없다면 (아래 참조) 양말을 옮기고 모든 양말이 배열로 배열 된 배열로 끝낼 수 있습니다.

양말의 유일한 연산이 평등을 비교하는 것이라고 가정하면,이 알고리즘은 기본적으로 여전히 n ² 알고리즘이지만 평균 사례에 대해서는 알지 못합니다 (절대로 계산하는 법을 배우지 못했습니다).

물론 정렬은 효율성을 향상 시키며, 특히 두 양말 사이에 양말을 쉽게 “삽입”할 수있는 실제 생활에서 향상됩니다. 계산에서 트리를 통해 동일한 결과를 얻을 수 있지만 추가 공간입니다. 물론 NlogN으로 돌아갑니다 (또는 정렬 기준에 따라 동일하지만 동일한 쌍이 아닌 여러 양말이있는 경우).

그 외에는 아무 것도 생각할 수 없지만이 방법은 실제 생활에서는 꽤 효율적인 것 같습니다. 🙂

답변

이것은 잘못된 질문입니다. 올바른 질문은 왜 양말을 분류하는 데 시간을 보내고 있습니까? 선택한 X 통화 단위의 자유 시간을 소중하게 생각할 때 연간 비용은 얼마입니까?

그리고보다 더 자주는 아니지만, 이것은 단지 아니다 모든 그것의, 자유 시간 아침 당신이 침대에서 지출하거나 커피를 마시거나 조금 일찍 떠나 트래픽에서 잡은되지 할 수있는 자유 시간.

한 걸음 물러서서 문제를 해결하는 것이 좋습니다.

그리고 방법이 있습니다!

당신이 좋아하는 양말을 찾으십시오. 다양한 조명 조건에서의 색상, 전반적인 품질 및 내구성, 다양한 기후 조건에서의 편안함 및 냄새 흡수 등 모든 관련 기능을 고려하십시오. 또한 중요한 점은 보관시 탄성을 잃지 않아야하므로 천연 직물이 좋고 플라스틱 포장재로 제공해야한다는 것입니다.

왼쪽 발 양말과 오른쪽 발 양말 사이에 차이가 없다면 더 좋지만 중요하지는 않습니다. 양말이 좌우 대칭 인 경우 쌍을 찾는 것은 O (1) 연산이고 양말을 정렬하는 것은 대략 O (M) 연산입니다. 여기서 M은 집안의 장소 수이며 양말로 흩어진 곳은 이상적입니다. 작은 상수.

왼쪽과 오른쪽 양말이 다른 멋진 페어를 선택한 경우 왼쪽과 오른쪽 발 버킷에 전체 버킷 정렬을 수행하면 O (N + M)을 사용합니다. 여기서 N은 양말 수이고 M은 위와 같습니다. 다른 사람이 첫 번째 쌍을 찾는 평균 반복에 대한 공식을 제공 할 수 있지만 블라인드 검색을 사용하는 쌍을 찾는 최악의 경우는 N / 2 + 1이며 합리적인 N의 경우 천문학적으로는 거의 불가능합니다. 이는 고급 이미지를 사용하여 가속화 할 수 있습니다 Mk1 Eyeball을 사용 하여 분류되지 않은 양말 더미를 스캔 할 때 인식 알고리즘 및 휴리스틱 .

따라서 O (1) 양말 페어링 효율을 달성하기위한 알고리즘은 다음과 같습니다 (대칭 양말 가정).

남은 평생 동안 필요한 양말 한 켤레를 추정하거나 양말을 다시 착용 할 필요없이 은퇴하고 따뜻한 기후로 이동할 때까지 추정해야합니다. 당신이 어릴 경우, 우리 모두가 집에 양말 분류 로봇을 갖기까지 걸리는 시간을 추정 할 수 있으며, 모든 문제는 관련이 없습니다.
선택한 양말을 대량으로 주문할 수있는 방법과 비용, 배송 방법을 알아야합니다.
양말을 주문하십시오!
오래된 양말을 제거하십시오.

대안적인 3 단계는 수년에 걸쳐 한 번에 몇 쌍의 같은 양의 싼 양말을 구입하는 비용을 비교하고 양말을 분류하는 비용을 추가하는 것을 포함하지만 내 말을 들어보십시오. 대량 구매는 더 저렴합니다! 또한 스토리지의 양말은 주가 인플레이션 율에 따라 가치가 상승하므로 많은 투자에서 얻을 수있는 것 이상입니다. 그런 다음 스토리지 비용이 다시 발생하지만 양말은 옷장의 상단 선반에 많은 공간을 차지하지 않습니다.

문제 해결됨. 따라서 새 양말을 구입하고, 오래된 양말을 버리고 기부하고, 평생 동안 매일 돈과 시간을 절약하고 있다는 것을 알고 행복하게 살 수 있습니다.

답변

이론적으로 제한은 O (n)입니다. 왜냐하면 각 양말을 만져야하기 때문입니다 (일부는 이미 짝을 이루지 않는 한).

기수 정렬을 사용 하여 O (n)을 얻을 수 있습니다 . 버킷의 일부 속성 만 선택하면됩니다.

먼저 당신은 (그녀의, 광산)을 선택할 수 있습니다-그것들을 2 개의 더미로 나누고,
그런 다음 색상을 사용하십시오 (예 : 색상 이름을 기준으로 알파벳 순서대로 정렬 가능)-색상별로 말뚝으로 나눕니다 (같은 양말에있는 모든 양말에 대해 1 단계부터 초기 순서를 유지해야 함),
양말 길이
그런 다음 질감, ….

제한된 수의 속성을 선택할 수 있지만 각 쌍을 고유하게 식별 할 수있는 충분한 속성을 선택할 수있는 경우 k가 제한되는 것으로 간주 될 수있는 경우 O (n) 인 O (k * n)에서 수행해야합니다.