질문자 :amit
어제 나는 깨끗한 세탁소에서 양말을 짝을 지어서 내가 하고 있는 방식이 그다지 효율적이지 않다는 것을 알아냈습니다. 나는 순진한 검색을 하고 있었습니다. 양말 한 켤레를 선택하고 그 쌍을 찾기 위해 더미를 "반복"했습니다. 이를 위해서는 평균적으로 n/2 * n/4 = n 2 /8 양말을 반복해야 합니다.
컴퓨터 과학자로서 나는 무엇을 할 수 있을까? 물론 (크기/색상/...에 따른) 정렬은 O(NlogN) 솔루션을 달성하기 위해 마음에 떠올랐습니다.
내 양말을 복제할 수 없기 때문에 해싱 또는 기타 제자리에 있지 않은 솔루션은 옵션이 아닙니다(가능하면 좋을 수 있음).
따라서 질문은 기본적으로 다음과 같습니다.
2n n 쌍의 양말 더미가 주어지면(각 양말에 정확히 하나의 일치하는 쌍이 있다고 가정) 최대 로그 추가 공간과 효율적으로 쌍을 이루는 가장 좋은 방법은 무엇입니까? (필요한 경우 해당 정보를 기억할 수 있다고 생각합니다.)
다음과 같은 측면을 다루는 답변에 감사드립니다.
- 엄청난 수의 양말에 대한 일반적인 이론적 솔루션.
- 실제 양말의 수는 그렇게 많지 않습니다. 제 배우자와 저는 30켤레 이상을 가지고 있다고 믿지 않습니다. (그리고 내 양말과 그녀의 양말을 구별하기가 상당히 쉽습니다. 이것도 사용할 수 있습니까?)
- 요소 구별 문제 와 동일합니까?
답변자 : Community Wiki
정렬 솔루션이 제안되었지만 정렬이 너무 많습니다 . 순서가 필요하지 않습니다. 우리는 평등 그룹이 필요합니다 .
따라서 해싱 이면 충분하고 더 빠릅니다.
- 양말의 각 색상에 대해 더미를 만듭니다. 입력 바구니에 있는 모든 양말을 반복 하고 색상 더미에 배포합니다 .
- 각 더미를 반복하고 다른 메트릭(예: 패턴)에 따라 두 번째 더미 세트에 배포합니다.
- 즉시 시각적으로 처리할 수 있는 매우 작은 더미 에 모든 양말을 배포할 때까지 이 계획을 재귀적으로 적용합니다.
이러한 종류의 재귀 해시 분할은 거대한 데이터 세트에 대한 해시 조인 또는 해시 집계가 필요할 때 실제로 SQL Server에서 수행됩니다. 빌드 입력 스트림을 독립적인 많은 파티션에 배포합니다. 이 체계는 선형적으로 임의의 양의 데이터와 여러 CPU로 확장됩니다.
각 버킷이 매우 빠르게 처리될 수 있을 만큼 충분히 작은 버킷 을 제공하는 배포 키(해시 키)를 찾을 수 있다면 재귀적 분할이 필요하지 않습니다. 불행히도 양말에는 그런 속성이 없다고 생각합니다.
PairID % 10 (마지막 숫자)에 따라 10개의 버킷으로 쉽게 배포할 수 있습니다.
내가 생각할 수 있는 최고의 실제 파티셔닝 은 더미 의 직사각형을 만드는 것입니다. 한 차원은 색상이고 다른 차원은 패턴입니다. 왜 직사각형인가? 더미에 대한 O(1) 무작위 액세스가 필요하기 때문입니다. (3D 직육면체 도 작동하지만 그다지 실용적이지 않습니다.)
업데이트:
병렬 처리는 어떻습니까? 여러 사람이 양말을 더 빨리 맞출 수 있습니까?
- 가장 간단한 병렬화 전략은 여러 작업자가 입력 바구니에서 양말을 가져와 더미 위에 올려 놓도록 하는 것입니다. 이것은 너무 많이 확장됩니다. 100명이 10개의 말뚝을 놓고 싸우는 것을 상상해 보십시오. 동기화 비용 (수동 충돌 및 인간 통신으로 나타남) 은 효율성과 속도 향상을 파괴합니다 ( Universal Scalability Law ! 참조). 이것이 교착 상태에 빠지기 쉬운가? 아니요, 각 작업자는 한 번에 하나의 파일에만 액세스하면 되기 때문입니다. "잠금"이 하나만 있으면 교착 상태가 있을 수 없습니다. 인간이 더미에 대한 액세스를 조정하는 방법에 따라 Livelock이 가능할 수 있습니다. 그들은 네트워크 카드가 물리적 수준에서 수행하는 것처럼 임의의 백오프를 사용하여 어떤 카드가 네트워크 와이어에 독점적으로 액세스할 수 있는지 결정합니다. NIC 에서 작동한다면 인간에게도 작동해야 합니다.
- 각 작업자에 고유한 더미 세트가 있는 경우 거의 무한대로 확장됩니다. 그런 다음 작업자는 입력 바구니에서 많은 양의 양말을 가져올 수 있으며(거의 수행하지 않으므로 경합이 거의 없음) 양말을 배포할 때 동기화할 필요가 전혀 없습니다(스레드 로컬 더미가 있기 때문에). 결국 모든 근로자는 파일 세트를 결합해야 합니다. 작업자가 집계 트리를 형성하면 O(log (worker count * piles per worker))에서 수행할 수 있다고 생각합니다.
요소 구별 문제는 어떻습니까? 기사에서 알 수 있듯이 요소 구별 문제는 O(N) 에서 해결할 수 있습니다. 이것은 양말 문제(또한 O(N) 대해 동일하며, 하나의 배포 단계만 필요한 경우(인간이 계산을 잘 못하기 때문에 여러 단계를 제안했습니다 - md5(color, length, pattern, ...) , 즉 모든 속성의 완벽한 해시 )).
O(N) 보다 빨리 갈 수는 없으므로 최적의 하한에 도달했습니다.
출력이 정확히 같지는 않지만(한 경우에는 부울만, 다른 경우에는 양말 쌍) 점근적 복잡도는 동일합니다.
답변자 : Community Wiki
인간 두뇌의 구조는 현대 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); }
적어도 이것은 내가 실생활에서 사용하는 것이고, 매우 효율적이라고 생각합니다. 단점은 평평한 표면이 필요하지만 일반적으로 풍부합니다.
답변자 : Community Wiki
사례 1 : 모든 양말은 동일합니다.
둘 중 하나를 선택하여 쌍을 만드십시오. 일정한 시간.
사례 2 : 일정한 수의 조합(소유권, 색상, 크기, 질감 등)이 있습니다.
기수 정렬을 사용하십시오. 비교가 필요하지 않기 때문에 이것은 선형 시간일 뿐입니다.
Case 3 : 조합의 수를 미리 알 수 없는 경우(일반적인 경우).
양말 두 개가 짝이 맞는지 비교를 해야 합니다. O(n log n) 비교 기반 정렬 알고리즘 중 하나를 선택합니다.
그러나 양말의 수가 상대적으로 적은(일정한) 현실 생활에서 이러한 이론적으로 최적의 알고리즘은 잘 작동하지 않습니다. 이론적으로 2차 시간이 필요한 순차 검색보다 더 많은 시간이 소요될 수 있습니다.
답변자 : Community Wiki
알고리즘이 아닌 대답이지만 내가 할 때 "효율적"입니다.
그러나 때때로 나는 이것을 다시해야합니다 (양말 분실, 손상된 양말 등). 나는 완벽하게 좋은 양말을 너무 자주 버리는 것을 싫어합니다 (그리고 그들이 동일한 양말 참조를 계속 판매했으면 좋겠다!), 그래서 나는 최근에 가져갔습니다. 다른 접근.
알고리즘 답변:
두 번째 양말 더미에 대해 양말을 하나만 뽑는 경우보다 순진한 검색에서 일치하는 양말을 찾을 확률이 상당히 낮습니다.
- 그러니 무작위로 5개를 집어서 모양이나 길이를 외우세요.
왜 다섯? 일반적으로 인간은 작업 메모리에서 5개에서 7개의 서로 다른 요소를 잘 기억합니다(인간의 RPN 스택과 비슷합니다). 5개는 안전한 기본값입니다.
2n-5 스택에서 하나를 선택합니다.
이제 당신이 그린 5개에서 일치하는 항목(시각적 패턴 일치 - 인간은 작은 스택으로 잘 함)을 찾고, 찾지 못하면 5개에 추가합니다.
더미에서 무작위로 양말을 계속 선택하고 경기를 위해 5+1 양말과 비교하십시오. 스택이 커지면 성능은 떨어지지만 확률은 높아집니다. 훨씬 더 빨리.
50%의 일치 확률을 위해 얼마나 많은 샘플을 뽑아야 하는지 계산하는 공식을 자유롭게 적어보세요. IIRC는 초기하법칙입니다.
나는 매일 아침 그렇게 하고 3개 이상의 무승부가 필요한 경우는 거의 없지만 m 모양의 흰색 양말이 n 쌍(약 10개, 잃어버린 것을 주거나 받음)이 있습니다. 이제 내 주식 스택의 크기를 추정할 수 있습니다 :-)
BTW , 나는 한 켤레가 필요할 때마다 모든 양말을 분류하는 거래 비용의 합계가 한 번하고 양말을 묶는 것보다 훨씬 적음을 발견했습니다. 적시에 양말을 묶을 필요가 없고 한계 수익이 감소하기 때문에 적시가 더 효과적입니다. 양말 맞추기를 끝내고 시간을 잃습니다).
답변자 : Community Wiki
내가 하는 일은 첫 번째 양말을 집어서 내려놓는 것입니다(예: 빨래통 가장자리에). 그런 다음 다른 양말을 집어 들고 첫 번째 양말과 같은지 확인합니다. 그렇다면 둘 다 제거합니다. 그렇지 않으면 첫 번째 양말 옆에 둡니다. 그런 다음 세 번째 양말을 집어서 처음 두 양말과 비교합니다(아직 양말이 있는 경우). 등.
양말을 "제거"하는 것이 옵션이라고 가정하면 이 접근 방식은 어레이에서 상당히 쉽게 구현할 수 있습니다. 사실, 양말을 "제거"할 필요조차 없습니다. 양말을 정렬할 필요가 없다면(아래 참조), 양말을 이리저리 움직여서 배열에서 모든 양말이 쌍으로 배열된 배열로 끝낼 수 있습니다.
양말에 대한 유일한 작업이 평등을 비교하는 것이라고 가정하면 이 알고리즘은 기본적으로 여전히 n 2 알고리즘이지만 평균 사례에 대해서는 알지 못합니다(이를 계산하는 방법을 배운 적이 없음).
물론 분류는 효율성을 향상시킵니다. 특히 다른 두 양말 사이에 양말을 쉽게 "삽입"할 수 있는 실생활에서 더욱 그렇습니다. 컴퓨팅에서 트리로 동일한 작업을 수행할 수 있지만 이는 추가 공간입니다. 그리고 물론, 우리는 NlogN으로 돌아왔습니다.
그 외에는 생각나는 것이 없지만 이 방법은 실생활에서 꽤 효율적인 것 같습니다. :)
답변자 : Community Wiki
이것은 잘못된 질문을 하는 것입니다. 올바른 질문은 양말을 분류하는 데 시간을 보내는 이유는 무엇입니까? 선택한 X 화폐 단위로 여가 시간을 평가할 때 연간 비용은 얼마입니까?
그리고보다 더 자주는 아니지만, 이것은 당신이 침대에서 지출하거나 커피를 마시거나 조금 일찍 떠나 트래픽에서 잡은되지 않은 될 수있는, 그것의 아침, 자유 시간을 그냥 자유 시간이 아니다.
한발 물러서서 문제를 해결하는 방법을 생각하는 것이 종종 좋습니다.
그리고 방법이 있습니다!
마음에 드는 양말을 찾아보세요. 다양한 조명 조건에서의 색상, 전반적인 품질 및 내구성, 다양한 기후 조건에서의 편안함 및 냄새 흡수와 같은 모든 관련 기능을 고려하십시오. 또한 중요한 점은 보관 시 탄력이 떨어지지 않도록 하기 때문에 천연섬유가 좋으며 비닐포장이 되어 있어야 합니다.
왼발 양말과 오른발 양말의 차이가 없으면 더 좋겠지만 중요하지 않습니다. 양말이 좌우 대칭이면 한 켤레를 찾는 것이 O(1) 작업이고 양말을 분류하는 것은 대략적인 O(M) 작업입니다. 여기서 M은 집에서 양말로 흩어져 있는 장소의 수입니다. 작은 상수.
왼쪽과 오른쪽 양말이 다른 멋진 쌍을 선택한 경우 왼쪽 및 오른쪽 발 버킷에 전체 버킷 정렬을 수행하면 O(N+M)가 사용됩니다. 여기서 N은 양말 수이고 M은 위와 같습니다. 다른 사람이 첫 번째 쌍을 찾는 평균 반복에 대한 공식을 제공할 수 있지만 블라인드 검색으로 쌍을 찾는 최악의 경우는 N/2+1이며, 이는 합리적인 N에 대해 천문학적으로 가능성이 낮은 경우가 됩니다. 고급 이미지를 사용하여 속도를 높일 수 있습니다. Mk1 Eyeball 로 분류되지 않은 양말 더미를 스캔할 때 인식 알고리즘 및 휴리스틱.
따라서 O(1) 양말 페어링 효율성(대칭 양말 가정)을 달성하기 위한 알고리즘은 다음과 같습니다.
남은 평생 동안 또는 아마도 은퇴하여 양말을 다시 신을 필요가 없는 따뜻한 기후로 이사할 때까지 몇 켤레의 양말이 필요할지 추정해야 합니다. 당신이 젊다면 우리 모두가 집에 양말 분류 로봇을 갖게 되며 전체 문제가 무의미해지기까지 얼마나 걸릴지 예측할 수도 있습니다.
선택한 양말을 대량으로 주문할 수 있는 방법과 비용, 배송 여부를 알아야 합니다.
양말 주문!
당신의 오래된 양말을 버리십시오.
대안적인 3단계는 몇 년 동안 한 번에 몇 켤레의 더 싼 양말을 사는 것과 같은 양의 비용을 비교하고 양말을 분류하는 비용을 추가하는 것입니다. 그러나 제 말을 믿으십시오. 대량으로 사는 것이 더 저렴합니다! 또한 창고에 보관된 양말은 많은 투자를 통해 얻을 수 있는 것보다 더 많은 주가 인플레이션 비율로 가치가 증가합니다. 그리고 또 보관비도 들지만 양말은 사실 옷장 위 선반에 공간을 많이 차지하지 않습니다.
문제 해결됨. 그러니 새 양말을 구입하고, 낡은 양말을 버리거나 기부하고, 평생 동안 매일 돈과 시간을 절약할 수 있다는 사실을 알고 행복하게 오래오래 사십시오.
답변자 : Community Wiki
이론적 한계는 각 양말을 만져야 하기 때문에 O(n)입니다(일부는 이미 어떻게든 짝을 이루고 있지 않는 한).
기수 정렬을 사용 하여 O(n)을 얻을 수 있습니다. 버킷에 대한 몇 가지 속성만 선택하면 됩니다.
- 먼저 (그녀, 내 것)을 선택할 수 있습니다 - 2 개의 더미로 나눕니다.
- 그런 다음 색상을 사용합니다(예: 색상 이름에 따라 알파벳순으로 색상 순서 지정 가능) - 색상별로 더미로 나눕니다(같은 더미에 있는 모든 양말에 대해 1단계의 초기 순서를 유지하는 것을 기억하십시오).
- 그런 다음 양말의 길이,
- 다음 질감, ....
제한된 수의 속성을 선택할 수 있지만 각 쌍을 고유하게 식별할 수 있는 충분한 속성을 선택할 수 있다면 O(k * n)으로 수행해야 합니다. 이는 k가 제한적이라고 간주할 수 있는 경우 O(n)입니다.
답변자 : Community Wiki
실용적인 솔루션으로:
- 쉽게 구별할 수 있는 양말 더미를 빠르게 만드십시오. (색깔로 말하다)
- 모든 더미를 빠르게 분류하고 비교를 위해 양말의 길이를 사용하십시오. 인간으로서 당신은 최악의 경우를 피하는 파티션에 사용할 양말을 상당히 빠르게 결정할 수 있습니다. (여러 개의 양말이 나란히 있는 것을 볼 수 있으니 유용하게 활용하세요!)
- 스폿 페어와 페어링할 수 없는 양말을 즉시 찾을 수 있는 임계값에 도달하면 더미 분류를 중지합니다.
8가지 색상과 평균 분포를 가진 1000개의 양말이 있는 경우 c*n 시간에 각 125개 양말의 4개 더미를 만들 수 있습니다. 5개의 양말 임계값으로 모든 더미를 6번의 실행으로 분류할 수 있습니다. (양말을 오른쪽 더미에 던지는 데 2초를 계산하면 4시간 미만이 소요됩니다.)
60개의 양말, 3가지 색상 및 2가지 종류의 양말(귀하의/아내의 것)이 있는 경우 한 번에 10개의 양말 더미를 모두 분류할 수 있습니다(다시 임계값 = 5). (2초를 계산하면 2분이 걸립니다.)
c*n 시간에 n 양말을 k 버킷으로 나누 c*n*log(k) 작업만 수행하면 되기 때문에 프로세스 속도가 빨라집니다. (임계값을 고려하지 않음). 따라서 전체적으로 n*c*(1 + log(k)) 작업에 대해 수행합니다. 여기서 c는 더미에 양말을 던질 시간입니다.
이 접근 방식은 log(k) < x - 1 c*x*n + O(1) 방법에 비해 유리합니다.
컴퓨터 과학에서 이것은 도움이 될 수 있습니다. 우리는 n개의 물건 컬렉션, 그것들에 대한 순서(길이) 및 등가 관계(추가 정보, 예를 들어 양말 색상)를 가지고 있습니다. 등가 관계를 통해 원본 컬렉션의 파티션을 만들 수 있으며 모든 등가 클래스에서 순서가 계속 유지됩니다. 그것의 등가 클래스에 일의 매핑, O (1) 그렇게 만 O (N)를 수행 할 수는 클래스에 각 항목을 할당 할 필요가있다. 이제 우리는 추가 정보를 사용했으며 모든 클래스를 정렬하기 위해 어떤 방식으로든 진행할 수 있습니다. 이점은 데이터 세트가 이미 훨씬 더 작다는 것입니다.
여러 등가 관계가 있는 경우 메서드를 중첩할 수도 있습니다. -> 길이를 기준으로 정렬하는 것보다 텍스처의 모든 파일 파티션 내에서보다 색상 더미를 만듭니다. 크기가 거의 같은 2개 이상의 요소가 있는 파티션을 생성하는 등가 관계는 정렬보다 속도 향상을 가져오고(양말을 해당 더미에 직접 할당할 수 있는 경우) 정렬은 더 작은 데이터 세트에서 매우 빠르게 발생할 수 있습니다.
답변자 : Nikolay Dyankov
잘못된 문제를 해결하려고 합니다.
해결책 1: 더러운 양말을 세탁 바구니에 넣을 때마다 작은 매듭으로 묶으십시오. 이렇게 하면 세탁 후 분류를 할 필요가 없습니다. Mongo 데이터베이스에 색인을 등록하는 것과 같다고 생각하십시오. 앞으로 약간의 CPU 절약을 위해 조금 더 노력하십시오.
해결 방법 2: 겨울이라면 어울리는 양말을 신지 않아도 됩니다. 우리는 프로그래머입니다. 작동하는 한 아무도 알 필요가 없습니다.
해결 방법 3: 작업을 분산합니다. UI를 차단하지 않고 이러한 복잡한 CPU 프로세스를 비동기적으로 수행하려고 합니다. 그 양말 더미를 가져 와서 가방에 넣으십시오. 필요할 때만 한 쌍을 찾으십시오. 그렇게 하면 필요한 작업량이 훨씬 덜 눈에 띄게 됩니다.
도움이 되었기를 바랍니다!
답변자 : Community Wiki
이 질문은 실제로 매우 철학적입니다. 핵심은 문제를 해결하는 사람들의 힘(우리 두뇌의 "웻웨어")이 알고리즘으로 달성할 수 있는 것과 동등한지 여부에 관한 것입니다.
양말 분류를 위한 분명한 알고리즘은 다음과 같습니다.
Let N be the set of socks that are still unpaired, initially empty for each sock s taken from the dryer if s matches a sock t in N remove t from N, bundle s and t together, and throw them in the basket else add s to N
이제 이 문제의 컴퓨터 과학은 모든 단계에 관한 것입니다.
- "S가 N에서 양말 t와 쌍을 이루는 경우". 우리는 지금까지 본 것을 얼마나 빨리 "기억"할 수 있습니까?
- "N에서 t 제거" 및 "N에 s 추가". 우리가 지금까지 본 것을 추적하는 데 얼마나 많은 비용이 듭니까?
인간은 이를 달성하기 위해 다양한 전략을 사용할 것입니다. 인간의 기억 은 연관 되며, 저장된 값의 기능 세트가 해당 값 자체와 쌍을 이루는 해시 테이블과 같습니다. 예를 들어, "빨간 차"라는 개념은 사람이 기억할 수 있는 모든 빨간색 차에 매핑됩니다. 완벽한 기억을 가진 사람은 완벽한 매핑을 가지고 있습니다. 대부분의 사람들은 이 점에서(그리고 대부분의 다른 사람들) 불완전합니다. 연관 맵의 용량이 제한되어 있습니다. 매핑은 다양한 상황에서 삐 소리 가 나거나(맥주 한 잔이 너무 많음) 오류로 기록되거나("그녀의 이름은 Nettie가 아니라 Betty였습니다."), 진실이 변경되었음을 관찰하더라도 덮어쓰지 않을 수 있습니다("아빠의 car"는 "주황색 파이어버드"를 떠올리게 하며, 실제로 그가 빨간색 카마로와 교환했다는 것을 알았습니다.
양말의 경우 완벽한 회상은 양말 s t 대한 기억을 생성한다는 것을 의미합니다. 여기에는 일정한 시간에 t 를 찾을 수 있는 충분한 정보(다리미판 위의 위치)가 포함됩니다. 사진기억력이 있는 사람은 반드시 1번과 2번을 일정한 시간 안에 성취한다.
기억력이 완벽하지 않은 사람은 추적할 수 있는 기능 내에서 크기(아빠, 엄마, 아기), 색상(초록색, 붉은색 등), 패턴(아가일, 일반 등)을 기반으로 몇 가지 상식적 등가 클래스를 사용할 수 있습니다. , 스타일(풋티, 무릎 높이 등). 따라서 다리미판은 범주별로 섹션으로 나뉩니다. 이것은 일반적으로 범주가 메모리에 의해 일정한 시간에 위치하도록 허용하지만 범주 "버킷"을 통한 선형 검색이 필요합니다.
기억이나 상상력이 전혀 없는 사람은(죄송합니다) 양말을 한 더미에 보관하고 전체 더미를 선형 검색합니다.
깔끔한 괴물은 누군가가 제안한 것처럼 쌍에 숫자 레이블을 사용할 수 있습니다. 이것은 인간이 CPU와 정확히 동일한 알고리즘(바이너리 검색, 트리, 해시 등)을 사용할 수 있도록 하는 전체 순서 지정의 문을 엽니다.
따라서 "최상의" 알고리즘은 실행 중인 웨트웨어/하드웨어/소프트웨어의 품질과 쌍에 전체 순서를 부과하여 "속임수"하려는 우리의 의지에 달려 있습니다. 확실히 "최고의" 메타 알고리즘은 세계 최고의 양말 분류기를 고용하는 것입니다. 일정한 시간 조회, 삽입, 삭제합니다. 이와 같은 사람과 기계 모두 조달할 수 있습니다. 양말이 있으면 N 켤레에 대해 O(N) 시간에 모든 양말을 짝지을 수 있으므로 최적입니다. 총 주문 태그를 사용하면 표준 해싱을 사용하여 사람 또는 하드웨어 컴퓨터에서 동일한 결과를 얻을 수 있습니다.
답변자 : Community Wiki
비용: 양말 이동 -> 높음, 줄에서 양말 찾기/검색 -> 작은
우리가 원하는 것은 이동 횟수를 줄이고 검색 횟수로 보상하는 것입니다. 또한 Homo Sapiens의 다중 스레드 환경을 활용하여 결정 캐시에 더 많은 것을 저장할 수 있습니다.
X = 귀하, Y = 귀하의 배우자
모든 양말의 파일 A에서:
두 개의 양말을 선택하고 해당 X 양말을 X 라인에 놓고 Y 양말을 다음 사용 가능한 위치에 Y 라인에 놓습니다.
A가 비어 있을 때까지 하십시오.
각 라인 X 및 Y에 대해
줄에서 첫 번째 양말을 선택하고 해당 양말을 찾을 때까지 줄을 따라 검색합니다.
양말의 해당 라인에 넣어.
- 선택 사항 라인을 검색하고 현재 보고 있는 양말이 이전 양말과 동일한 경우 이 양말에 대해 2단계를 수행합니다.
선택적으로 1단계를 수행하려면 캐싱 메모리가 충분히 크기 때문에 해당 줄에서 두 개 대신 두 개의 양말을 선택합니다. 두 양말 중 하나가 관찰 중인 라인의 현재 양말과 일치하는지 빠르게 식별할 수 있습니다. 세 개의 팔을 가질 만큼 운이 좋다면 대상에 대한 기억이 충분히 크다면 동시에 세 개의 양말을 구문 분석할 수 있습니다.
X와 Y가 모두 비어 있을 때까지 수행합니다.
완료
그러나 이것은 선택 정렬과 유사한 복잡성을 가지므로 I/O(양말 이동) 및 검색(양말 줄 찾기)의 속도로 인해 소요 시간이 훨씬 줄어듭니다.
답변자 : Community Wiki
다음은 비교 기반 모델의 Omega(n log n) 하한입니다. (유일하게 유효한 작업은 두 개의 양말을 비교하는 것입니다.)
2n 양말이 다음과 같이 배열되어 있다는 것을 알고 있다고 가정합니다.
p 1 p 2 p 3 ... p n p f(1) p f(2) ... p f(n)
여기서 f는 집합 {1,2,...,n}의 알려지지 않은 순열입니다. 이것을 알면 문제가 더 어려워질 수 없습니다. n이 있습니다! 가능한 출력(전반기와 후반기 간의 일치), 즉 log(n!) = Omega(n log n) 비교가 필요합니다. 이것은 정렬을 통해 얻을 수 있습니다.
요소 구별 문제에 대한 연결에 관심이 있기 때문에 요소 구별에 대한 Omega(n log n) 경계를 증명하는 것이 더 어렵습니다. 출력이 이진 yes/no이기 때문입니다. 여기서 출력은 일치해야 하고 가능한 출력의 수는 적절한 범위를 얻기에 충분합니다. 그러나 요소 구별성과 관련된 변형이 있습니다. 당신에게 2n개의 양말이 주어지고 그것들이 유일하게 짝을 이룰 수 있는지 궁금하다고 가정해 보십시오. (a 1 , a 2 , ..., an n )을 (a 1 , a 1 , a 2 , a 2 , ..., an n , an n )로 보내면 ED에서 감소를 얻을 수 있습니다. (괄호로 ED의 경도 증명은 토폴로지를 통해 매우 흥미롭습니다.)
평등 테스트만 허용한다면 원래 문제에 대한 Omega(n 2 ) 경계가 있어야 한다고 생각합니다. 내 직감은 테스트 후 가장자리를 추가하는 그래프를 고려하고 그래프가 조밀하지 않으면 출력이 고유하게 결정되지 않는다고 주장합니다.
답변자 : Community Wiki
이것은 p 쌍의 양말에 대해 실제로 수행하는 방법 입니다( n = 2p 개별 양말).
- 더미에서 무작위로 양말을 가져옵니다.
- 첫 번째 양말의 경우 또는 이전에 선택한 모든 양말이 짝을 이루고 있는 경우에는 양말을 짝이 되지 않은 양말의 "배열" 중 첫 번째 "슬롯"에 놓기만 하면 됩니다.
- 짝을 이루지 않은 양말을 하나 이상 선택한 경우 배열에 있는 모든 짝이 없는 양말과 비교하여 현재 양말을 확인합니다.
- 어레이를 구축할 때 양말을 일반 클래스 또는 유형(흰색/검정색, 발목/승무원, 운동복/드레스)으로 분리하고 유사품만 비교하기 위해 "드릴다운"할 수 있습니다.
- 허용되는 일치 항목을 찾으면 두 양말을 함께 넣고 어레이에서 제거하십시오.
- 그렇지 않은 경우 현재 양말을 어레이의 첫 번째 열린 슬롯에 넣으십시오.
- 모든 양말로 반복하십시오.
이 계획의 최악의 시나리오는 모든 양말이 다르기 때문에 정확히 일치해야 하고 처음 선택한 n/2 양말이 모두 다르다는 것입니다. 이것은 당신의 O (n 2 ) 시나리오이며 극히 가능성이 낮습니다. 고유한 유형의 양말 t 의 수가 쌍의 수 p = n/2 보다 작고 각 유형의 양말이 충분히 비슷하여(일반적으로 착용 관련 용어로) 해당 유형의 양말은 어떤 양말과도 쌍을 이룰 수 있습니다. 다른, 내가 위에서 추정 한 후, 당신이 이제까지 비교해야합니다 양말의 최대 수는 당기 다음 하나가 짝 양말 중 하나와 일치되는 후 t이다. 이 시나리오는 최악의 경우보다 평균 양말 서랍에서 발생할 가능성이 훨씬 더 높으며 , 일반적으로 t << n 인 최악의 경우 복잡성을 O (n*t)로 줄입니다.
답변자 : Community Wiki
실제 접근 방식:
가능한 한 빨리 분류되지 않은 더미에서 양말을 한 번에 하나씩 꺼내서 더미에 놓으십시오. 말뚝은 모든 양말이 같은 방향을 가리키도록 공간 효율적으로 배열되어야 합니다. 말뚝의 수는 쉽게 도달할 수 있는 거리에 따라 제한됩니다. 양말을 놓을 더미의 선택은 가능한 한 빨리 양말처럼 보이는 더미 위에 양말을 올려 놓아야 합니다. 간헐적으로 유형 I(속하지 않는 더미에 양말 놓기) 또는 유형 II(기존에 양말 같은 더미가 있을 때 자체 더미에 양말 놓기) 오류는 용인될 수 있습니다. 가장 중요한 고려 사항은 속도입니다. .
모든 양말이 더미에 있으면 여러 양말 더미를 빠르게 통과하여 쌍을 만들고 제거합니다(서랍으로 향하고 있음). 더미에 일치하지 않는 양말이 있으면 최상의 상태로(가능한 한 빨리 제한 내에서) 다시 쌓습니다. 다중 양말 더미가 모두 처리되면 유형 II 오류로 인해 쌍을 이루지 못한 나머지 쌍이 가능한 양말을 일치시킵니다. 으윽, 다 됐어 -- 그리고 나는 양말을 많이 가지고 있고 많은 부분이 더러워질 때까지 세탁하지 않는다. 또 다른 실용적인 참고 사항: 저는 양말 한 켤레의 상단을 다른 양말 위로 뒤집어서 탄성 특성을 활용하여 서랍으로 운반되는 동안 그리고 서랍에 있는 동안 함께 유지됩니다.
답변자 : Community Wiki
귀하의 질문에 따르면 귀하는 세탁에 대한 실제 경험이 많지 않습니다. :) 짝을 이룰 수 없는 소수의 양말과 잘 작동하는 알고리즘이 필요합니다.
지금까지의 답변은 우리의 인간 패턴 인식 기능을 잘 활용하지 않습니다. 세트 게임은 이 작업을 잘 수행하는 방법에 대한 단서를 제공합니다. 모든 양말을 2차원 공간에 두어 양말을 잘 인식하고 손으로 쉽게 닿을 수 있도록 합니다. 이것은 약 120 * 80 cm 정도의 영역으로 제한합니다. 거기에서 인식하는 쌍을 선택하고 제거하십시오. 여유 공간에 여분의 양말을 넣고 반복하십시오. 쉽게 알아볼 수 있는 양말을 신은 사람을 위해 세탁을 하는 경우(어린 아이가 떠오름) 해당 양말을 먼저 선택하여 기수 정렬을 수행할 수 있습니다. 이 알고리즘은 단일 양말의 수가 적을 때만 잘 작동합니다.
답변자 : Community Wiki
첫 번째 양말을 집어 테이블 위에 놓습니다. 이제 다른 양말을 선택하십시오. 첫 번째 선택과 일치하는 경우 첫 번째 항목 위에 놓습니다. 그렇지 않은 경우 처음에서 약간 떨어진 테이블 위에 놓습니다. 세 번째 양말을 선택하십시오. 앞의 두 가지 중 하나와 일치하면 그 위에 배치하거나 세 번째에서 약간 떨어진 곳에 배치하십시오. 모든 양말을 집어들 때까지 반복하십시오.
답변자 : Community Wiki
더미에서 양말을 쌍으로 만드는 것이 얼마나 효율적인지 말하려면 먼저 기계를 정의해야 합니다. 왜냐하면 쌍은 일반적으로 기본으로 사용되는 튜링이나 랜덤 액세스 기계에 의해 수행되지 않기 때문입니다. 알고리즘 분석.
기계
기계는 인간이라는 현실 세계의 요소를 추상화한 것입니다. 그것은 한 쌍의 눈을 통해 환경에서 읽을 수 있습니다. 그리고 우리 기계 모델은 2개의 팔을 사용하여 환경을 조작할 수 있습니다. 논리 및 산술 연산은 우리의 두뇌를 사용하여 계산됩니다(잘하면 ;-)).
우리는 또한 이러한 도구로 수행할 수 있는 원자 연산의 고유 런타임을 고려해야 합니다. 물리적 제약으로 인해 팔이나 눈으로 수행되는 작업은 일정하지 않은 시간 복잡도를 갖습니다. 끝없이 많은 양말 더미를 팔로 움직일 수 없고, 끝없이 쌓여 있는 양말 더미 위의 양말을 눈으로 볼 수 없기 때문입니다.
그러나 기계 물리학은 우리에게 좋은 점을 주기도 합니다. 우리는 팔로 양말 한 개만 움직이도록 제한되지 않습니다. 한 번에 두 개를 모두 이동할 수 있습니다.
따라서 이전 분석에 따라 다음 작업을 내림차순으로 사용해야 합니다.
우리는 또한 사람들이 매우 제한된 양의 양말만을 가지고 있다는 사실을 이용할 수 있습니다. 따라서 환경 수정에는 더미에 있는 모든 양말이 포함될 수 있습니다.
알고리즘
제 제안은 다음과 같습니다.
- 더미에 있는 모든 양말을 바닥에 펼치십시오.
- 바닥에 있는 양말을 보고 한 켤레를 찾습니다.
- 쌍을 만들 수 없을 때까지 2부터 반복합니다.
- 바닥에 양말이 없을 때까지 1부터 반복합니다.
작업 4가 필요합니다. 바닥에 양말을 펼칠 때 일부 양말이 다른 양말을 숨길 수 있기 때문입니다. 알고리즘 분석은 다음과 같습니다.
분석
알고리즘은 높은 확률로 종료됩니다. 이것은 2단계에서 양말 한 켤레를 찾을 수 없기 때문입니다.
n 개의 양말 쌍에 대한 다음 런타임 분석을 2n 양말 중 적어도 절반이 1단계 이후에 숨겨져 있지 않다고 n/2 쌍을 찾을 수 있습니다. 이것은 루프가 4단계를 O(log n) 번 실행한다는 것을 의미합니다. 2단계는 O(n^2) 번 실행됩니다. 따라서 우리는 다음과 같이 결론을 내릴 수 있습니다.
- 알고리즘에는
O(ln n + n) 환경 수정이 포함됩니다(1단계 O(ln n) + 바닥에서 모든 양말 선택). - 알고리즘은
O(n^2) 환경 읽기를 포함합니다. - 알고리즘은 2단계에서 양말을 다른 양말과 비교하기 위한
O(n^2)
O(r*n^2 + w*(ln n + n)) 의 총 런타임 복잡성을 가집니다. 여기서 r 과 w 는 각각 적절한 양의 양말에 대한 환경 읽기 및 환경 쓰기 작업에 대한 요소입니다. 두 양말이 같은 쌍에 속하는지 여부를 결정하는 데 일정한 양의 논리 및 산술 연산이 필요하다고 가정하기 때문에 논리 및 산술 연산의 비용은 생략됩니다. 이것은 모든 시나리오에서 실현 가능하지 않을 수 있습니다.
답변자 : Community Wiki
List<Sock> UnSearchedSocks = getAllSocks(); List<Sock> UnMatchedSocks = new list<Sock>(); List<PairOfSocks> PairedSocks = new list<PairOfSocks>(); foreach (Sock newSock in UnsearchedSocks) { Sock MatchedSock = null; foreach(Sock UnmatchedSock in UnmatchedSocks) { if (UnmatchedSock.isPairOf(newSock)) { MatchedSock = UnmatchedSock; break; } } if (MatchedSock != null) { UnmatchedSocks.remove(MatchedSock); PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock)); } else { UnmatchedSocks.Add(NewSock); } }
답변자 : Community Wiki
더 적은 작업이나 더 적은 시간 소비를 약속하지 않는 또 다른 솔루션을 찾았지만 엄청난 양의 양말 페어링에서 더 적은 시간을 제공하기 위해 충분히 좋은 경험적 방법이 될 수 있는지 확인해야 합니다.
전제 조건: 동일한 양말이 있다는 보장은 없습니다. 색상이 같다고 해서 크기나 패턴이 같은 것은 아닙니다. 양말은 무작위로 섞입니다. 홀수 개의 양말이 있을 수 있습니다(일부는 누락되었으며 몇 개인지 알 수 없음). 변수 "index"를 기억할 준비를 하고 0으로 설정합니다.
결과 에는 1. "일치" 및 2. "누락"이라는 하나 또는 두 개의 더미가 있습니다.
휴리스틱:
- 가장 독특한 양말을 찾으십시오.
- 일치하는 항목을 찾으십시오.
- 일치하는 항목이 없으면 "누락된" 더미에 놓습니다.
- 가장 독특한 양말이 더 이상 없을 때까지 1.부터 반복합니다.
- 양말이 6개 미만이면 11개로 이동합니다.
- 모든 양말을 이웃에 맹목적으로 쌍으로 묶습니다(포장하지 마십시오).
- 일치하는 모든 쌍을 찾아 포장하고 포장된 쌍을 "일치하는" 더미로 옮깁니다. 새로운 일치 항목이 없는 경우 - "색인"을 1씩 증가
- "색인"이 2보다 크면(양말 수가 많을수록 맹목적으로 쌍을 이룰 기회가 적기 때문에 양말 번호에 따라 값이 달라질 수 있음) 11로 이동
- 나머지 셔플
- 1로 이동
- "색인"을 잊어 버리십시오.
- 양말 고르기
- 그 쌍을 찾으십시오
- 양말 한 켤레가 없으면 "누락된" 더미로 옮깁니다.
- 일치하는 항목을 찾으면 쌍으로 묶고 "일치하는" 더미로 옮깁니다.
- 양말이 하나 더 있으면 12로 가십시오.
- 1개만 남았다면 14화
- 스마일 만족합니다 :)
또한 양말을 벗는 것처럼 손상된 양말이 있는지 확인하는 추가 작업이 있을 수 있습니다. 2와 3 사이, 13과 14 사이에 삽입할 수 있습니다.
어떤 경험이나 수정 사항에 대해 듣고 싶습니다.
답변자 : Community Wiki
양말을 분류할 때 같은 색상/패턴 유형의 다른 양말 근처에 양말을 떨어뜨리는 대략적인 기수 정렬을 수행합니다. 양말을 떨어뜨리려는 위치/근처에서 정확히 일치하는 것을 볼 수 있는 경우를 제외하고는 그 지점에서 쌍을 추출합니다.
거의 모든 다른 알고리즘( usr 의 최고 득점 답변 포함)은 정렬한 다음 쌍을 제거합니다. 나는 인간으로서 한 번에 고려되는 양말의 수를 최소화하는 것이 낫다고 생각합니다.
나는 이것을 다음과 같이 한다:
- 독특한 양말 고르기(더미에서 가장 먼저 눈에 들어오는 것).
- 해당 개념적 위치에서 유사성을 기반으로 더미에서 양말을 당겨서 기수 정렬을 시작합니다.
- 새 양말을 현재 더미에 가까이 놓고 그것이 얼마나 다른지에 따라 거리를 두십시오. 양말이 동일하기 때문에 양말을 다른 양말 위에 올려 놓는 것을 발견하면 거기에서 쌍을 형성하고 제거하십시오. 이것은 미래의 비교가 정확한 위치를 찾는 데 덜 노력한다는 것을 의미합니다.
이것은 컴퓨팅 장치에 해시 맵을 설정하는 것과 어느 정도 동등한 O(1) 시간에 퍼지 일치를 수행하는 인간의 능력을 이용합니다.
독특한 양말을 먼저 잡아당기면 먼저 덜 구별되는 기능을 "확대"할 수 있는 공간이 생깁니다.
플루로 컬러, 줄무늬 양말, 긴 양말 세 켤레를 제거한 후에는 착용 정도에 따라 대략적으로 분류된 대부분의 흰색 양말이 될 수 있습니다.
어느 시점에서 양말의 차이는 다른 사람들이 그 차이를 알아차리지 못할 만큼 작아서 더 이상의 일치 노력이 필요하지 않습니다.
답변자 : Community Wiki
양말을 집어들 때마다 한 곳에 두십시오. 그런 다음 다음 양말을 집어 들었을 때 첫 번째 양말과 일치하지 않으면 첫 번째 양말 옆에 두십시오. 그렇다면 쌍이 있습니다. 이렇게 하면 얼마나 많은 조합이 있는지가 중요하지 않으며, 선택한 양말마다 두 가지 가능성만 있습니다. 이미 양말 배열에 일치하는 항목이 있거나 없는 경우입니다. 배열의 한 위치에 추가합니다.
이것은 또한 양말이 일치될 때 제거되기 때문에 어레이에 모든 양말을 가지고 있지 않을 것이 거의 확실하다는 것을 의미합니다.
답변자 : Community Wiki
크기가 'N'인 해시 테이블을 고려하십시오.
정규 분포를 가정하면 하나 이상의 양말이 하나의 버킷에 매핑되도록 예상되는 '삽입' 수는 NlogN입니다(즉, 모든 버킷이 가득 찼음).
나는 이것을 다른 퍼즐의 일부로 파생시켰지만, 틀렸다는 것이 밝혀지면 기쁠 것입니다. 다음은 같은 내용에 대한 내 블로그 기사입니다.
'N'은 가지고 있는 양말의 고유한 색상/패턴 수에 대한 대략적인 상한선에 해당합니다.
충돌(일명: 경기)이 발생하면 해당 양말을 제거하기만 하면 됩니다. 다음 NlogN 양말 배치로 동일한 실험을 반복합니다. 그것의 아름다움은 인간의 마음이 작동하는 방식 때문에 NlogN 병렬 비교(충돌 해결)를 할 수 있다는 것입니다. :-)
답변자 : Community Wiki
실제 양말이든 유사한 데이터 구조이든 양말은 쌍으로 제공됩니다.
가장 간단한 대답은 쌍을 분리하기 전에 왼쪽 및 오른쪽 양말에 대한 포인터를 포함하는 쌍에 대한 단일 데이터 구조가 초기화되어 양말이 직접 또는 쌍을 통해 참조될 수 있도록 하는 것입니다. 양말은 파트너에 대한 포인터를 포함하도록 확장될 수도 있습니다.
이것은 추상화 계층으로 제거하여 모든 계산 페어링 문제를 해결합니다.
양말을 짝을 짓는 실제 문제에 동일한 아이디어를 적용하면 명백한 답은 다음과 같습니다. 양말을 벗지 않도록 하십시오. 양말은 한 켤레로 제공되며 한 켤레로 서랍에 넣고(아마도 함께 뭉쳐서) 한 켤레로 착용합니다. 그러나 페어링 해제가 가능한 지점은 세탁기이므로 양말이 함께 머물고 효율적으로 세탁될 수 있도록 하는 물리적 메커니즘만 있으면 됩니다.
두 가지 물리적 가능성이 있습니다.
각 양말에 대한 포인터를 유지하는 '쌍' 개체의 경우 양말을 함께 보관하는 데 사용하는 천 가방을 사용할 수 있습니다. 이것은 엄청난 오버 헤드처럼 보입니다.
그러나 각 양말이 다른 양말에 대한 참조를 유지하려면 다음과 같은 깔끔한 해결책이 있습니다.
http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html
그런 다음 양말을 벗고 세탁 바구니에 넣은 직후에 양말을 함께 끼우면 '쌍' 개념의 물리적 추상화로 양말을 쌍으로 묶어야 하는 문제를 제거할 수 있습니다.
답변자 : Community Wiki
이 문제에 새로운 것을 기여할 수 있기를 바랍니다. 나는 모든 답변이 전체 세탁 성능을 저하시키지 않으면서 전처리 를 수행할 수 있는 두 가지 지점이 있다는 사실을 무시한다는 사실을 알아차렸습니다.
또한 대가족의 경우에도 많은 양의 양말을 가정할 필요가 없습니다. 양말은 서랍에서 꺼내 신은 다음 세탁하기 전에 머무를 장소(통일 수도 있음)에 버립니다. 내가 말한 bin을 LIFO-Stack이라고 부르지는 않겠지만 다음과 같이 가정하는 것이 안전하다고 말하고 싶습니다.
- 사람들은 두 양말을 쓰레기통의 같은 영역에 대충 던집니다.
- 빈은 어느 시점에서든 무작위화되지 않으므로
- 이 통의 상단에서 가져온 모든 하위 집합에는 일반적으로 한 쌍의 양말이 모두 포함됩니다.
내가 아는 모든 세탁기는 크기가 제한되어 있고(빨래해야 하는 양말의 수에 관계없이) 세탁기에서 실제 무작위 추출이 발생하기 때문에 우리가 가지고 있는 양말의 수와 상관없이 항상 거의 없는 작은 부분 집합이 있습니다. 싱글톤.
우리의 두 가지 전처리 단계는 "빨래줄에 양말 넣기"와 "빨래줄에서 양말 꺼내기"입니다. 이 작업은 깨끗할 뿐만 아니라 마른 양말을 얻기 위해 수행해야 합니다. 세탁기와 마찬가지로 빨랫줄은 한정되어 있고, 나는 우리가 양말을 놓는 라인의 전체 부분을 가지고 있다고 가정합니다.
put_socks_on_line()의 알고리즘은 다음과 같습니다.
while (socks left in basket) { take_sock(); if (cluster of similar socks is present) { Add sock to cluster (if possible, next to the matching pair) } else { Hang it somewhere on the line, this is now a new cluster of similar-looking socks. Leave enough space around this sock to add other socks later on } }
양말을 이리저리 옮기거나 가장 잘 맞는 것을 찾는 데 시간을 낭비하지 마십시오. 이 모든 것은 O(n)에서 수행되어야 하며, 정렬되지 않은 줄에 양말을 놓는 데도 필요합니다. 양말은 아직 짝을 이루지 않았으며 라인에 몇 가지 유사성 클러스터만 있습니다. 여기에 제한된 양말 세트가 있으면 "좋은" 클러스터를 만드는 데 도움이 됩니다.
다음은 take_socks_from_line() 알고리즘입니다.
while(socks left on line) { take_next_sock(); if (matching pair visible on line or in basket) { Take it as well, pair 'em and put 'em away } else { put the sock in the basket }
나머지 단계의 속도를 높이려면 다음 양말을 무작위로 선택하지 않고 각 클러스터에서 양말을 차례로 가져 오는 것이 현명하다는 점을 지적해야합니다. 두 전처리 단계 모두 양말을 줄이나 바구니에 넣는 것보다 더 많은 시간이 걸리지 않으며, 이는 우리가 무슨 일이 있어도 해야 하므로 세탁 성능을 크게 향상시킬 것입니다.
그런 다음 해시 분할 알고리즘을 수행하는 것이 쉽습니다. 일반적으로 양말의 약 75%가 이미 쌍을 이루고 있어 양말의 아주 작은 부분 집합만 남게 되며 이 부분 집합은 이미 (다소) 클러스터링되어 있습니다(전처리 단계 후에 바구니에 많은 엔트로피를 도입하지 않습니다). 또 다른 점은 나머지 클러스터는 한 번에 처리할 수 있을 만큼 작은 경향이 있으므로 바구니에서 전체 클러스터를 꺼낼 수 있다는 것입니다.
다음은 sort_remaining_clusters()에 대한 알고리즘입니다.
while(clusters present in basket) { Take out the cluster and spread it Process it immediately Leave remaining socks where they are }
그러면 양말이 몇 개 남지 않습니다. 여기에서 이전에 페어링되지 않은 양말을 시스템에 도입하고 특별한 알고리즘 없이 나머지 양말을 처리합니다. 나머지 양말은 매우 적고 시각적으로 매우 빠르게 처리할 수 있습니다.
남아 있는 모든 양말의 경우 양말이 아직 세탁되지 않은 것으로 가정하고 다음 반복을 위해 보관합니다. 시간이 지남에 따라 짝을 이루지 않은 양말의 증가("양말 누출")를 등록하는 경우 휴지통을 확인해야 합니다. 휴지통이 무작위로 지정될 수 있습니다(거기에서 자는 고양이가 있습니까?)
나는 이러한 알고리즘이 일종의 LIFO 스택 역할을 하는 통, 제한된 일반 세탁기, 제한된 일반 빨랫줄과 같은 많은 가정을 취한다는 것을 알고 있지만 이것은 여전히 매우 많은 수의 양말에서 작동합니다.
병렬 처리에 관하여: 두 양말을 같은 빈에 버리기만 하면 모든 단계를 쉽게 병렬화할 수 있습니다.
답변자 : Community Wiki
나는 O(1) 시간이 걸리는 프로세스로 내 노력을 줄이기 위해 간단한 조치를 취했습니다.
두 가지 유형의 양말(레크레이션용 흰색 양말, 작업용 검정색 양말) 중 하나로 입력을 줄임으로써 두 양말 중 손에 있는 양말만 결정하면 됩니다. (엄밀히 말하면 함께 씻지 않기 때문에 프로세스를 O(0) 시간으로 줄였습니다.)
원하는 양말을 찾고 기존 양말이 필요 없을 정도로 충분한 수량을 구매하려면 사전에 약간의 노력이 필요합니다. 검은색 양말이 필요하기 전에 이 작업을 수행했으므로 노력은 최소화했지만 마일리지는 다를 수 있습니다.
이러한 선행 노력은 매우 인기 있고 효과적인 코드에서 여러 번 볼 수 있습니다. 예에는 #DEFINE' 파이를 소수점 이하 자릿수까지 지정하는 것이 포함됩니다(다른 예가 있지만 지금 생각나는 것은 그 예입니다).
답변자 : Community Wiki
n개의 양말을 분류하는 문제 는 O(n) 입니다. 세탁 바구니 에 버리기 전에 왼쪽을 오른쪽에 끼우십시오. 그것들을 꺼낼 때 실을 자르고 각 쌍을 서랍에 넣습니다. n 쌍에 대해 2번 작업하므로 O(n)입니다.
이제 다음 질문은 단순히 당신이 당신 자신의 세탁을 하고 당신의 아내가 그녀의 세탁을 하는지 여부입니다. 그것은 문제의 완전히 다른 영역에 있을 가능성이 있는 문제입니다. :)
답변자 : Community Wiki
"이동" 작업이 상당히 비싸고 "비교" 작업이 저렴하고 어쨌든 전체 세트를 원래 저장소보다 검색이 훨씬 빠른 버퍼로 이동해야 하는 경우... 정렬을 필수 항목에 통합하기만 하면 됩니다. 이동하다.
나는 분류 과정을 걸고 말리는 과정을 통합하면 산들바람이 부는 것을 발견했습니다. 어쨌든 각 양말을 집어 들고 걸어야 하고(이동) 끈의 특정 위치에 걸어두는 데 비용이 거의 들지 않습니다. 이제 전체 버퍼(문자열)를 강제로 검색하지 않기 위해 색상/음영별로 양말을 배치하도록 선택합니다. 왼쪽이 더 어둡고 오른쪽이 더 밝고 앞이 더 화려합니다. 이제 각 양말을 걸기 전에 일치하는 양말이 이미 있는 경우 "오른쪽 부근"을 살펴봅니다. 이것은 "스캔"을 2-3개의 다른 양말로 제한합니다. , 다른 하나는 바로 옆에 걸었습니다. 그런 다음 건조되면 줄에서 제거하면서 쌍으로 굴립니다.
이제 이것은 최고 답변에서 제안한 "색상으로 더미 형성"과 크게 다르지 않은 것처럼 보일 수 있지만 먼저 개별 더미를 선택하지 않고 범위를 선택하여 "보라색"이 "빨간색" 또는 "파란색" 더미로 가는지 분류하는 데 문제가 없습니다. 그것은 단지 사이에 간다. 그런 다음 두 가지 작업(걸어서 건조 및 분류)을 통합하면 매달린 상태에서 분류하는 오버헤드가 개별 분류의 10%와 같습니다.
답변자 : Community Wiki
나는 지금 양말을 묶는 것을 끝내고 가장 좋은 방법은 다음과 같다는 것을 알게 되었습니다.
- 양말 중 하나를 선택하고 치워둡니다(해당 쌍에 대한 '양동이' 생성).
- 다음 버킷이 이전 버킷의 쌍이면 기존 버킷에 넣고 그렇지 않으면 새 버킷을 만듭니다.
최악의 경우에는 n/2개의 다른 버킷이 있고 어떤 버킷에 현재 양말 쌍이 포함되어 있는지에 대해 n-2개의 결정이 있음을 의미합니다. 분명히 이 알고리즘은 몇 개의 쌍만 있으면 잘 작동합니다. 12쌍으로 했어요.
그렇게 과학적이지는 않지만 잘 작동합니다 :)
답변자 : wrzasa
O(n) "추가" 공간이 필요하기 때문에 귀하의 요구 사항과 정확히 일치하지 않습니다. 그러나 내 조건을 고려하면 실제 적용에서 매우 효율적입니다. 따라서 흥미로워야 한다고 생각합니다.
다른 작업과 결합
제 경우에는 건조기를 사용하지 않고 그냥 일반 건조기에 옷을 걸어두는 것이 특기입니다. 옷걸이에는 O(n) 작업이 필요하며(그런데 여기에서 항상 빈 포장 문제를 고려합니다) 문제는 본질적으로 선형 "추가" 공간이 필요합니다. 양동이에서 새 양말을 꺼낼 때 양말이 이미 걸려 있다면 양말 옆에 걸어두려고 합니다. 새 양말의 경우 옆에 약간의 공간을 남겨 둡니다.
오라클 머신이 더 좋습니다 ;-)
일치하는 양말이 이미 어딘가에 매달려 있는지 확인하려면 분명히 약간의 추가 작업이 필요하며 컴퓨터의 경우 계수가 약 1/2 O(n^2) 그러나 이 경우 "인간적 요소"가 실제로 이점이 있습니다. 저는 일반적으로 양말이 이미 걸려 있는 경우(아마도 인지할 수 없는 뇌 내 캐싱이 관련되어 있는 경우) 일치하는 양말을 O(1) 그것은 Oracle Machine 에서와 같이 일종의 제한된 "oracle"입니다 ;-) 우리 인간은 어떤 경우에는 디지털 기계보다 이러한 이점을 가지고 있습니다 ;-)
거의 O(n) !
따라서 양말을 묶는 문제와 옷걸이 문제를 연결하면 O(n) "추가 공간"이 무료로 제공 O(n) 솔루션이 있으므로 간단한 옷걸이보다 약간 더 많은 작업이 필요합니다. 매우 나쁜 월요일 아침에도 완전한 양말 한 켤레에 즉시 액세스할 수 있습니다... ;-)
답변자 : Community Wiki
패턴을 해시로 사용하여 일치하지 않는 양말에 사용할 해시 테이블을 만듭니다. 양말을 하나씩 반복합니다. 양말의 해시 테이블에 패턴이 일치하면 테이블에서 양말을 꺼내 쌍을 만드십시오. 양말에 성냥이 없으면 테이블에 넣으십시오.
출처 : Here
출처 : http:www.stackoverflow.com/questions/14415881/how-can-i-pair-socks-from-a-pile-efficiently">