a

Câu hỏi Làm thế nào để ghép vớ từ một đống hiệu quả?


Hôm qua tôi đã ghép đôi tất từ ​​đồ giặt sạch và tìm ra cách tôi đang làm nó không hiệu quả lắm. Tôi đã làm một tìm kiếm ngây thơ - chọn một cái vớ và "lặp" đống để tìm cặp của nó. Điều này đòi hỏi phải lặp lại trên n / 2 * n / 4 = n2/ 8 vớ trung bình.

Là một nhà khoa học máy tính, tôi đã nghĩ tôi có thể làm gì? Phân loại (theo kích thước / màu / ...) tất nhiên đã đến với tâm trí để đạt được một giải pháp O (NlogN).

Đòn hay các giải pháp không phải tại chỗ không phải là một lựa chọn, bởi vì tôi không thể lặp lại vớ của tôi (mặc dù nó có thể được tốt đẹp nếu tôi có thể).

Vì vậy, câu hỏi về cơ bản là:

Cho một đống n cặp vớ, có chứa 2n phần tử (giả sử mỗi sock có chính xác một cặp phù hợp), cách tốt nhất để ghép nối chúng hiệu quả với tối đa không gian logarit là gì? (Tôi tin rằng tôi có thể nhớ số lượng thông tin đó nếu cần.)

Tôi sẽ đánh giá cao câu trả lời giải quyết các khía cạnh sau:

  • Chung lý thuyết giải pháp cho một số lượng lớn vớ.
  • Số lượng vớ thật không lớn đến thế, tôi không tin vợ chồng tôi và tôi có hơn 30 đôi. (Và nó khá dễ dàng để phân biệt giữa tất của tôi và của cô ấy, điều này có thể được sử dụng không?)
  • Nó có tương đương với vấn đề khác biệt về yếu tố?

3507
2018-01-19 15:34


gốc


Tôi sử dụng nguyên tắc lỗ chim bồ câu để ghép chính xác một cái từ đống đồ giặt. Tôi có 3 màu khác nhau của tất (màu đỏ, màu xanh và màu xanh lá cây) và 2 cặp của mỗi màu. Tôi nhặt 4 chiếc vớ mỗi lần và tôi luôn tạo nên một đôi và làm việc. - Srinivas
Tuy nhiên, một nguyên tắc lỗ chim bồ câu: nếu bạn có một tập con của n / 2 +1 vớ, có cần phải ít nhất một cặp trong tập hợp con này. - wildplasser
Câu hỏi tuyệt vời! Bạn có thể quan tâm đến bài viết của tôi về một vấn đề liên quan, đó là một cuộc thảo luận về xác suất kéo hai cặp phù hợp ra khỏi đống: blogs.msdn.com/b/ericlippert/archive/2010/03/22/… - Eric Lippert
Tại sao không sinh ra một đứa trẻ và waitpid để, như cha mẹ, bạn thậm chí không phân loại bất kỳ vớ mình? - Mxyk
Tôi giải quyết vấn đề này bằng cách chỉ sở hữu vớ cao đến đầu gối màu trắng. Tất cả đều phù hợp. Tôi có thể chỉ cần lấy bất kỳ hai vớ ngẫu nhiên từ đống và họ sẽ phù hợp. Tôi tiếp tục đơn giản hóa vấn đề bằng cách KHÔNG ghép nối vớ. Tôi có một ngăn kéo vớ mà tôi chỉ đơn giản là ném tất cả tất của tôi vào, bỏ ghép. Tôi lấy hai ngẫu nhiên từ ngăn kéo mỗi sáng. Tôi đã đơn giản hóa nó xuống O (0). Không thể đơn giản hơn thế. :) - Lee


Các câu trả lời:


Các giải pháp sắp xếp đã được đề xuất, nhưng phân loại hơi quá nhiều: Chúng tôi không cần lệnh; chúng ta chỉ cần các nhóm bình đẳng.

Vì thế băm sẽ là đủ (và nhanh hơn).

  1. Đối với mỗi màu vớ, tạo thành một đống. Lặp lại tất cả vớ trong giỏ hàng đầu vào của bạn và phân phối chúng trên các cọc màu.
  2. Lặp lại trên mỗi cọc và phân phối nó bằng một số chỉ số khác (ví dụ: mẫu) vào tập cọc thứ hai
  3. Áp dụng đệ quy lược đồ này cho đến khi bạn đã phân phối tất cả tất các cọc rất nhỏ mà bạn có thể xử lý ngay lập tức

Kiểu phân vùng băm đệ quy này thực sự đang được thực hiện bởi Máy chủ SQL khi nó cần phải băm tham gia hoặc băm tổng hợp trên các tập dữ liệu khổng lồ. Nó phân phối luồng đầu vào xây dựng của nó thành nhiều phân vùng độc lập. Lược đồ này quy mô số lượng dữ liệu tùy ý và nhiều CPU tuyến tính.

Bạn không cần phân vùng đệ quy nếu bạn có thể tìm thấy khóa phân phối (khóa băm) cung cấp đủ nhóm rằng mỗi thùng là đủ nhỏ để được xử lý rất nhanh chóng. Thật không may, tôi không nghĩ rằng vớ có một tài sản như vậy.

Nếu mỗi sock có một số nguyên được gọi là "PairID", người ta có thể dễ dàng phân phối chúng thành 10 nhóm theo PairID % 10 (chữ số cuối cùng).

Phân vùng thế giới thực tốt nhất mà tôi có thể nghĩ đến là tạo ra hình chữ nhật của cọc: một chiều là màu, cái kia là mẫu. Tại sao lại là hình chữ nhật? Bởi vì chúng ta cần O (1) truy cập ngẫu nhiên vào cọc. (3D hình khối cũng sẽ hoạt động, nhưng điều đó không thực tế lắm.)


Cập nhật:

Thế còn song song? Nhiều con người có thể kết hợp vớ nhanh hơn không?

  1. Chiến lược song song đơn giản nhất là có nhiều công nhân lấy từ rổ đầu vào và đặt tất vào các cọc. Điều này chỉ tăng lên rất nhiều - tưởng tượng 100 người chiến đấu trên 10 cọc. Chi phí đồng bộ hóa (thể hiện mình là va chạm tay và giao tiếp của con người) phá hủy hiệu quả và tăng tốc (xem Luật khả năng mở rộng toàn cầu!). Đây có phải là dễ bị deadlocks? Không, bởi vì mỗi công nhân chỉ cần truy cập vào một đống tại một thời điểm. Chỉ với một "khóa" không thể có một bế tắc. Livelocks có thể có thể tùy thuộc vào cách con người phối hợp tiếp cận với cọc. Họ chỉ có thể sử dụng -sự lùi ngẫu nhiên như thẻ mạng làm điều đó trên một mức độ vật lý để xác định những gì thẻ độc quyền có thể truy cập vào dây mạng. Nếu nó hoạt động NIC, nó cũng có tác dụng với con người.
  2. Nó quy mô gần như vô thời hạn nếu mỗi công nhân có một tập các cọc riêng. Người lao động sau đó có thể lấy một lượng lớn vớ từ giỏ đầu vào (rất ít tranh chấp khi họ hiếm khi làm) và họ không cần phải đồng bộ khi phân phối tất cả (vì chúng có cọc sợi địa phương). Cuối cùng, tất cả các công nhân cần phải kết hợp các bộ cọc của họ. Tôi tin rằng có thể được thực hiện trong O (đăng nhập (nhân viên đếm * cọc cho mỗi công nhân)) nếu các công nhân tạo thành một cây tập hợp.

Vậy còn vấn đề khác biệt về yếu tố? Như bài báo nói, vấn đề về tính riêng biệt của phần tử có thể được giải quyết trong O(N). Điều này cũng tương tự đối với vấn đề vớ (cũng O(N), nếu bạn chỉ cần một bước phân phối (tôi đã đề xuất nhiều bước chỉ vì con người có tính toán xấu - một bước là đủ nếu bạn phân phối md5(color, length, pattern, ...), tức là một băm hoàn hảo của tất cả các thuộc tính)).

Rõ ràng, người ta không thể đi nhanh hơn O(N), vì vậy chúng tôi đã đạt đến giới hạn dưới tối ưu.

Mặc dù các kết quả đầu ra không giống nhau (trong một trường hợp, chỉ là một boolean. Trong trường hợp khác, các cặp vớ), sự phức tạp tiệm cận là như nhau.


2180
2017-10-19 20:47



Đây chính xác là những gì tôi làm! Tôi làm cho cọc phụ thuộc vào phong cách mở của chiếc vớ (tôi chỉ có màu trắng), điều đó mang lại cho tôi đủ "xô" để nhanh chóng phù hợp với từng cái đó. - Scott Chamberlain
Tôi đã thử điều này với tất của tôi (tôi đã có dễ dàng hơn 30 cặp) và người đàn ông đó là NHANH. Một vấn đề tôi đã tìm thấy là khi tôi không thể có một thuật toán băm đủ tốt (tôi đã có rất nhiều vớ trắng mà không có bất kỳ mẫu nào) nên nó trở nên khó khăn. Trong trường hợp đó, cách tối ưu để làm điều đó là gì? - NothingsImpossible
@NothingsImpossible đó là cách các cuộc tấn công va chạm băm cảm thấy như thế nào đối với một máy chủ web kém! Các bít tất màu trắng có thể phân biệt bởi một số thuộc tính không? Phải có một cái gì đó bạn có thể phân phối chúng trên. Nếu không, bạn chỉ có thể hình thành các cặp tùy ý. - usr
Đây là một Radix Sort, mà tôi đồng ý là câu trả lời đúng. @ MarkPeters Tôi không nghĩ rằng bạn cần một bảng tra cứu. Một tuyến tính duy nhất vượt qua vớ có thể chuyển đổi tất để số vectơ, làm cho các bản đồ của "phân đoạn sock" để xô tầm thường. Các vớ có thể được gắn với các vectơ bằng chuỗi sao cho bạn không cần một đường truyền thẳng khác ở cuối. - Pointy
Một anh chàng tôi đã đi học đại học với thực tế đã có PairIDs. Nó được khâu trên mỗi đôi vớ bằng sợi: 1, 2, 3, 4 ... - Ryan Lundy


Do kiến ​​trúc của bộ não con người hoàn toàn khác với một CPU hiện đại, câu hỏi này không có ý nghĩa thiết thực.

Con người có thể giành chiến thắng trên thuật toán CPU bằng cách sử dụng thực tế là "tìm một cặp phù hợp" có thể là một hoạt động cho một tập hợp không quá lớn.

Thuật toán của tôi:

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);
}

Ít nhất đây là những gì tôi đang sử dụng trong cuộc sống thực, và tôi thấy nó rất hiệu quả. Nhược điểm là nó đòi hỏi một bề mặt phẳng, nhưng nó thường phong phú.


523
2018-05-27 19:13



khi số lượng vớ tăng lên, SIMD của con người trở nên không tốt hơn CPU. - Lie Ryan
Câu trả lời hay nhất, IMO. Mặc dù nó rất thú vị và thông minh (và thích hợp cho SO) để giảm một vấn đề hàng ngày đối với thuật toán máy tính, nó có ý nghĩa hơn nhiều khi sử dụng sức mạnh phân giải của mắt / não của con người với một bộ nhỏ ~ 60 vớ. - drug_user841417
@LieRyan Nếu vớ được phân phối đồng đều, bạn sẽ nhận thấy một cặp trong bất kỳ bộ vớ đủ nhỏ do nghịch lý sinh nhật (trừ khi bạn có thể phân biệt màu sắc với độ chính xác tùy ý, mà tôi nghi ngờ), vì vậy nút cổ chai ở đây sẽ không thuật toán kết hợp màu sắc của con người nhưng bước lan rộng. - Thomas
@ dpc.ucore.info Không, bởi vì chúng có các mẫu băng dệt thoi khác nhau, chiều dài còng, độ dài tổng thể và sắc thái của màu đen (vợ tôi có thể sẽ làm tổn thương tôi vì cái cuối cùng). - Christian
Bạn đã hy vọng tốt hơn bạn có một số thậm chí vớ, nếu không bạn sẽ được gấp vớ trong một thời gian dài ... - Patrick James McDougle


Trường hợp 1: Tất cả tất đều giống nhau (đây là những gì tôi làm trong cuộc sống thực bằng cách này).

Chọn bất kỳ hai người trong số họ để thực hiện một cặp. Thời gian liên tục.

Trường hợp 2: Có một số kết hợp liên tục (quyền sở hữu, màu sắc, kích thước, kết cấu, v.v.).

Sử dụng radix sắp xếp. Đây chỉ là thời gian tuyến tính vì không cần so sánh.

Trường hợp 3: Số lượng kết hợp không được biết trước (trường hợp chung).

Chúng ta phải so sánh để kiểm tra xem hai chiếc vớ có ghép đôi không. Chọn một trong số O(n log n) thuật toán phân loại dựa trên so sánh.

Tuy nhiên trong cuộc sống thực khi số lượng vớ tương đối nhỏ (không đổi), các thuật toán tối ưu về mặt lý thuyết này sẽ không hoạt động tốt. Nó có thể mất nhiều thời gian hơn tìm kiếm tuần tự, theo lý thuyết yêu cầu thời gian bậc hai.


231



> Nó có thể mất nhiều thời gian hơn tìm kiếm tuần tự, đòi hỏi thời gian bậc hai theo lý thuyết. Vâng, đó là lý do tại sao tôi ghét làm điều này, có lẽ tôi nên vứt bỏ tất cả vớ và bắt đầu với trường hợp 1. - Nils
Tôi tìm thấy nó dễ dàng hơn để có tất cả các vớ giống nhau là tốt. Mỗi vài năm tôi mua 10 trong số 6 bao vớ đó khi chúng được bán và ném tất cả tất cũ của tôi. Chỉ cần dễ dàng hơn để phù hợp với vớ giống nhau và họ nhìn tốt hơn sau đó vớ thánh cũ. Với điều này, chỉ cần một đầu tiên đơn giản ra khỏi đỉnh của đống là nhanh nhất cho tôi. - Michael D. Kirkpatrick
mặt trái của tất cả các vớ giống hệt nhau là chúng có xu hướng già đi ở các mức độ khác nhau. Vì vậy, bạn vẫn kết thúc cố gắng để phù hợp với họ dựa trên cách mòn họ. (khó hơn so với kết hợp đơn giản theo mẫu) - SDC
Vấn đề với việc có 60 cặp vớ giống hệt nhau "bởi vì nó giúp việc ghép nối dễ dàng hơn" là nó mang lại cho mọi người ấn tượng bạn làm việc với máy tính. - Steve Ives
Trường hợp 1 không phải là thời gian liên tục khi có một hoạt động liên quan, chẳng hạn như các cặp gấp lại với nhau. Trong trường hợp này, đó là thời gian tuyến tính với hệ số không đổi nhỏ nhất (bằng chứng được để lại dưới dạng bài tập cho người đọc). Một không thể cùng lúc xếp một đôi và một cái xô đầy vớ. Tuy nhiên, nó quy mô tuyến tính. Theo luật của Amdahl, nó có tốc độ không giới hạn, bỏ qua chi phí. Theo định luật Gustafson, bạn có thể gấp nhiều cặp để gấp một cặp cho đủ công nhân (số lượng còn lại là bài tập cho người đọc), bỏ qua chi phí. - acelent


Câu trả lời phi thuật toán, nhưng "hiệu quả" khi tôi làm điều đó:

  • bước 1) loại bỏ tất cả vớ hiện có của bạn

  • bước 2) đi đến Walmart và mua chúng bằng gói 10 - n gói màu trắng và m màu đen. Không cần màu sắc khác trong hàng ngày đời sống.

Tuy nhiên, đôi khi, tôi phải làm điều này một lần nữa (vớ bị mất, vớ bị hư hỏng, vv), và tôi ghét phải vứt vớ hoàn toàn quá thường xuyên (và tôi muốn họ tiếp tục bán cùng vớ tham khảo!), Vì vậy tôi mới lấy Một cách tiếp cận khác.

Câu trả lời thuật toán:

Xem xét hơn nếu bạn chỉ vẽ một cái vớ cho đống thứ hai của vớ, như bạn đang làm, tỷ lệ cược của bạn trong việc tìm kiếm các phù hợp vớ trong một tìm kiếm ngây thơ là khá thấp.

  • Vì vậy, hãy chọn năm trong số chúng một cách ngẫu nhiên và ghi nhớ hình dạng của chúng hoặc độ dài của chúng.

Tại sao năm? Thông thường con người tốt là nhớ giữa năm và bảy yếu tố khác nhau trong bộ nhớ làm việc - một chút giống như con người tương đương với một RPN ngăn xếp - năm là một mặc định an toàn.

  • Nhận một cái từ ngăn xếp 2n-5.

  • Bây giờ tìm kiếm một trận đấu (kết hợp mô hình trực quan - con người giỏi với một chồng nhỏ) bên trong năm bạn vẽ, nếu bạn không tìm thấy, sau đó thêm nó vào năm của bạn.

  • Hãy chọn ngẫu nhiên vớ từ ngăn xếp và so sánh với vớ 5 + 1 của bạn để phù hợp. Khi ngăn xếp của bạn phát triển, nó sẽ giảm hiệu suất của bạn nhưng tăng tỷ lệ cược của bạn. Nhanh hơn nhiều.

Hãy viết xuống công thức để tính số lượng mẫu bạn phải vẽ cho tỷ lệ cược 50% của một trận đấu. IIRC đó là một định luật hypergeometric.

Tôi làm điều đó mỗi sáng và hiếm khi cần nhiều hơn ba lần rút thăm - nhưng tôi có n các cặp tương tự (khoảng 10, tặng hoặc lấy những người bị mất) m vớ trắng hình. Bây giờ bạn có thể ước tính kích thước của đống cổ phiếu của tôi :-)

BTW, Tôi thấy rằng tổng chi phí giao dịch của phân loại tất cả các vớ mỗi khi tôi cần một đôi ít hơn rất nhiều so với làm một lần và ràng buộc tất. Một công việc vừa mới tốt hơn vì bạn không cần phải bó tất, và cũng có một sự trở lại cận hẹp (có nghĩa là bạn cứ tiếp tục tìm hai hoặc ba cái vớ khi ở đâu đó trong quần áo và bạn cần để kết thúc vớ của bạn và bạn mất thời gian trên đó).


144



Upvote cho câu trả lời 'phi thuật toán'. Đây chính xác là những gì tôi làm và nó hoạt động tuyệt vời. Vấn đề thay thế không phải là một vấn đề nếu bạn 'xoay' cổ phiếu của bạn bằng cách đặt tất sạch vào lưng và kéo từ phía trước ngăn kéo vào buổi sáng. Tất cả tất đều mặc đều. Khi tôi bắt đầu nhận thấy một số mặc trên một, tôi đưa vào danh sách mua sắm để thay thế hoàn toàn toàn bộ lớp vớ. Đối với những chiếc vớ cũ, tôi tặng 20% ​​tốt nhất cho thiện chí (được buộc trong một túi đựng đồ tạp hóa để chúng không bị lẫn lộn lại) và bày nốt phần còn lại. Bạn không lãng phí vớ, vào thời điểm này, 80% chỉ còn 6 tháng nữa thôi. - FastAl
BTW (1) Liên kết vớ của bạn với kết quả đàn hồi một được lưu trữ kéo dài và sẽ thất bại nhanh hơn nhiều. Hạn chế các loại vớ độc đáo bạn đã làm cho ràng buộc unneded. (2) Một bất lợi của việc hạn chế vớ độc đáo là đối với những người có mối quan tâm thời trang nhất định, phương pháp này có thể không phù hợp. - FastAl
Tôi đến đây đặc biệt để đăng câu trả lời "phi thuật toán" của bạn. Như trong khoa học máy tính thực sự, hầu hết mọi người không bao giờ chú ý đủ đến dữ liệu và cấu trúc của nó. - bkconrad
Tôi sử dụng cách tiếp cận thuật toán này mỗi sáng và nó hoạt động như một sự quyến rũ! Ngoài ra, tôi đặt tất ra vớ để một đống khác nhau để vứt bỏ sau này (tiếc là họ quản lý để có được đống gốc một lần nữa trước khi tôi tìm thấy thời gian để thùng rác nó). - Donatas Olsevičius
«N gói các gói màu trắng và m màu đen. Không cần màu sắc khác trong cuộc sống hàng ngày »Một quy tắc tiêu chuẩn tốt để lựa chọn vớ dễ dàng thực sự là chúng phải phù hợp với màu sắc của quần hoặc màu sắc của dây đai. Vì lý do này, các màu được sử dụng phổ biến nhất có thể là màu đen, xanh dương, xám và một số màu nâu. Thật khó tin rằng người ta cần nhiều vớ trắng. - Andrea Lazzarotto


Những gì tôi làm là tôi lấy cái vớ đầu tiên và đặt nó xuống (ví dụ, ở rìa bát giặt). Sau đó, tôi lấy một cái vớ khác và kiểm tra xem nó có giống cái vớ đầu tiên không. Nếu có, tôi loại bỏ cả hai. Nếu không, tôi đặt nó xuống bên cạnh chiếc vớ đầu tiên. Sau đó, tôi lấy cái vớ thứ ba và so sánh nó với cái đầu tiên (nếu chúng vẫn còn ở đó). Vv

Cách tiếp cận này có thể được thực hiện khá dễ dàng trong một mảng, giả sử rằng "loại bỏ" vớ là một lựa chọn. Trên thực tế, bạn thậm chí không cần phải "loại bỏ" vớ. Nếu bạn không cần phân loại tất (xem bên dưới), thì bạn chỉ có thể di chuyển chúng xung quanh và kết thúc với một mảng có tất cả các cặp được sắp xếp theo cặp trong mảng.

Giả sử rằng hoạt động duy nhất cho vớ là so sánh cho bình đẳng, thuật toán này về cơ bản vẫn là một n2 thuật toán, mặc dù tôi không biết về trường hợp trung bình (không bao giờ học để tính toán điều đó).

Phân loại, tất nhiên cải thiện hiệu quả, đặc biệt là trong cuộc sống thực, nơi bạn có thể dễ dàng "chèn" một chiếc vớ giữa hai vớ khác. Trong máy tính giống nhau có thể đạt được bằng một cây, nhưng đó là không gian thêm. Và, tất nhiên, chúng tôi trở lại NlogN (hoặc nhiều hơn một chút, nếu có một số vớ giống nhau bằng cách phân loại tiêu chí, nhưng không phải từ cùng một cặp).

Ngoài ra, tôi không thể nghĩ ra bất cứ điều gì, nhưng phương pháp này có vẻ khá hiệu quả trong cuộc sống thực. :)


92



Đây cũng là những gì tôi làm, (lưu ý rằng nếu bạn chỉ cần rời khỏi không gian thì chèn cũng là O (1)), nhưng nó quy mô kém với số lượng lớn về mặt lý thuyết của tất. - Mooing Duck
quy mô kém với số lượng lớn về mặt lý thuyết các loại vớ - Steven Lu
@StevenLu - như tôi đã nói - đó là n * n hoặc nLogn, tùy thuộc vào việc bạn có sắp xếp hay không. Vì vậy, nó quy mô về như kém như bất kỳ thuật toán phân loại. Nếu bạn muốn nhanh hơn, hãy đánh số chúng và sử dụng sắp xếp radix. - Vilx-
Đây là cơ bản lưu trữ vớ được tìm thấy nhưng không phù hợp trong một tra cứu dựa trên băm. Với một băm lý tưởng nó là O (n), nhưng nếu bạn có đủ vớ được lưu trữ mà băm bắt đầu thoái hóa, nó trở nên phức tạp hơn cho phù hợp. - Jon Hanna
những gì giá trị không chèn một vớ giữa 2 vớ khác cung cấp cho mục tiêu ghép nối vớ? không có cardinality vớ. : -x - JoeBrockhaus


Đây là câu hỏi sai. Câu hỏi đúng đắn đặt ra là, tại sao tôi lại dành thời gian phân loại vớ? Chi phí trên cơ sở hàng năm là bao nhiêu, khi bạn đánh giá thời gian rảnh của bạn cho các đơn vị tiền tệ X mà bạn chọn?

Và thường xuyên hơn không, đây không chỉ là bất kì thời gian rảnh, buổi sáng miễn phí thời gian, mà bạn có thể được chi tiêu trên giường, hoặc nhấm nháp cà phê của bạn, hoặc để lại một chút sớm và không bị bắt trong giao thông.

Nó thường tốt để lùi lại một bước, và suy nghĩ một cách xung quanh vấn đề.

Và có một cách!

Tìm một chiếc vớ bạn thích. Đưa tất cả các tính năng liên quan vào tài khoản: màu sắc trong điều kiện ánh sáng khác nhau, chất lượng tổng thể và độ bền, thoải mái trong điều kiện khí hậu khác nhau, và hấp thụ mùi. Cũng quan trọng là, chúng không nên mất độ đàn hồi trong kho, vì vậy vải tự nhiên là tốt, và chúng nên có sẵn trong một bao bì nhựa.

Sẽ tốt hơn nếu không có sự khác biệt giữa vớ chân trái và chân phải, nhưng nó không quan trọng. Nếu vớ là trái đối xứng, tìm một cặp là hoạt động O (1), và phân loại tất là hoạt động O (M), trong đó M là số chỗ trong ngôi nhà của bạn, mà bạn đã vứt vớ, lý tưởng là số không đổi nhỏ.

Nếu bạn đã chọn một cặp ưa thích với vớ trái và phải khác nhau, hãy thực hiện một kiểu xô đầy đủ cho các xô chân trái và chân phải lấy O (N + M), trong đó N là số lượng tất và M giống như trên. Ai đó có thể đưa ra công thức cho các lần lặp lại trung bình của việc tìm cặp đầu tiên, nhưng trường hợp xấu nhất để tìm kiếm một cặp với tìm kiếm mù là N / 2 + 1, trở thành trường hợp không chắc chắn về mặt thiên văn cho hợp lý N. Điều này có thể được tăng tốc bằng cách sử dụng hình ảnh nâng cao thuật toán nhận dạng và chẩn đoán, khi quét đống vớ chưa phân loại bằng Mk1 Eyeball.

Vì vậy, một thuật toán để đạt được hiệu quả ghép đôi S (1) vớ (giả sử vớ đối xứng) là:

  1. Bạn cần phải ước tính có bao nhiêu đôi vớ bạn sẽ cần cho phần còn lại của cuộc sống của bạn, hoặc có lẽ cho đến khi bạn nghỉ hưu và di chuyển đến vùng khí hậu ấm hơn mà không cần phải mang vớ bao giờ trở lại. Nếu bạn còn trẻ, bạn cũng có thể ước tính phải mất bao lâu trước khi tất cả chúng ta đều có robot phân loại trong nhà của chúng tôi, và toàn bộ vấn đề trở nên không liên quan.

  2. Bạn cần phải tìm hiểu làm thế nào bạn có thể đặt hàng vớ được chọn của bạn với số lượng lớn, và bao nhiêu chi phí, và họ cung cấp.

  3. Đặt hàng tất!

  4. Loại bỏ vớ cũ của bạn.

Một bước thay thế 3 sẽ liên quan đến so sánh chi phí mua cùng một số vớ rẻ hơn có thể một vài cặp tại một thời điểm trong những năm qua và thêm chi phí phân loại vớ, nhưng lấy từ của tôi cho nó: mua với số lượng lớn là rẻ hơn! Ngoài ra, vớ trong lưu trữ tăng giá trị theo tỷ lệ lạm phát giá cổ phiếu, đó là nhiều hơn bạn sẽ nhận được trên nhiều khoản đầu tư. Sau đó, một lần nữa cũng có chi phí lưu trữ, nhưng vớ thực sự không mất nhiều không gian trên kệ hàng đầu của một tủ quần áo.

Đã giải quyết được sự cố. Vì vậy, chỉ cần có được vớ mới, ném / tặng những người già của bạn đi, và sống hạnh phúc mãi mãi sau khi biết bạn đang tiết kiệm tiền và thời gian mỗi ngày cho phần còn lại của cuộc sống của bạn.


50



Một đời (giả sử 75 năm) cung cấp vớ (giả sử bạn xả 4 cặp / tháng, mà làm cho 3600 đôi) sẽ mất (giả sử một đôi vớ mới chiếm 20 inch khối) tổng cộng 1 1/2 cubic yards. Đó là một lượng lớn không gian. Giả sử họ đưa nó cho bạn trong một cái hộp gần bằng một khối lập phương, cái thùng đó sẽ dài khoảng 3 feet 4 inch. - AJMansfield
@AJMansfield quan tâm hợp lệ. Tuy nhiên, tôi không đồng ý với một vài con số của bạn. Tôi sẽ mất một khoảng thời gian chỉ 40 năm (25 ... 65) (thời gian giữa không sống ở cha mẹ / ký túc xá / vv và nghỉ hưu, xem ở trên). Ngoài ra, tôi nghĩ rằng một cặp mất nhiều hơn như 0,5x4x6 inch trong bao bì gốc. Những con số này làm cho không gian của bạn giảm xuống một chút! - hyde
Bước 4 là lãng phí không cần thiết, -1. - Dan Bechard
Hướng dẫn cho những người khác có thể bị nhầm lẫn bởi các phép đo của AJMansfield, một bản dịch thành số liệu: »sẽ mất (giả sử một đôi vớ mới chiếm 327 cm³) tổng cộng 1,14 m³. Đó là một lượng lớn không gian. Giả sử họ đưa nó cho bạn trong một cái hộp gần bằng một khối lập phương, cái thùng đó sẽ có kích thước khoảng 1,04 m ở một bên. - Joey


Giới hạn lý thuyết là O (n) bởi vì bạn cần phải chạm vào mỗi cái vớ (trừ khi một số đã được ghép nối bằng cách nào đó).

Bạn có thể đạt được O (n) với radix sắp xếp. Bạn chỉ cần chọn một số thuộc tính cho các nhóm.

  1. Đầu tiên bạn có thể chọn (của cô ấy, của tôi) - chia chúng thành 2 cọc,
  2. sau đó sử dụng màu sắc (có thể có bất kỳ thứ tự nào cho màu sắc, ví dụ: theo thứ tự bảng chữ cái theo tên màu) - tách chúng thành các cọc theo màu (nhớ giữ thứ tự ban đầu từ bước 1 cho tất cả tất trong cùng một đống),
  3. sau đó chiều dài của vớ,
  4. rồi kết cấu, ....

Nếu bạn có thể chọn một số thuộc tính hạn chế, nhưng đủ các thuộc tính có thể xác định duy nhất mỗi cặp, bạn nên thực hiện trong O (k * n), là O (n) nếu chúng ta có thể xem xét k bị hạn chế.


47



Bít tất thường đi vào 4 gói và lớn hơn, vì đó là rẻ hơn, nhưng điều đó cũng làm cho chúng không thể phân biệt được. Để chống lại điều này, vợ tôi nhét một dấu nhỏ lên mỗi cặp vớ mới mà tôi mua. Dấu có màu khác nhau cho mỗi cặp, hoặc hình dạng khác, nếu nó hết màu. Với cách tiếp cận này, bạn thậm chí không cần một tập hợp các thuộc tính giới hạn. Chỉ cần may một số duy nhất trên mỗi cặp. :) Đối với các điểm phụ, sử dụng nhị phân. - Vilx-
@ Vilx- TẠI SAO?!? Không phải là toàn bộ vấn đề mà họ không thể phân biệt được? - flup
@flup - Tôi nghĩ rằng toàn bộ vấn đề là bán các gói lớn hơn. :) Đối với tôi, điều này giúp để mặc chúng xuống theo cặp. Nếu không tôi có thể kết thúc với ba chiếc vớ rất mòn và một cái mới. Kinda ngớ ngẩn. - Vilx-
Tôi không đồng ý với việc tính O (n). $ K $ là gì? $ k $ là số thuộc tính. Tôi sẽ tranh luận $ k $ là $ O (log n) $ bởi vì nó phải đủ để xác định duy nhất mỗi cặp. Nếu bạn có 2 cặp (đen trắng), thì màu ($ k = 1, n = 2 $) là đủ. Nếu bạn có một cặp màu đen, ngắn; một cặp màu đen, dài; một cặp màu trắng, ngắn; và một cặp màu trắng, dài - rồi $ k = 2, n = 4 $. Sau đó, nếu chúng tôi giới hạn $ k $, chúng tôi đồng thời giới hạn $ n $. Nếu chúng ta sẽ giới hạn $ n $ thì phép tính thứ tự không có ý nghĩa nữa. - emory
@emory, tôi nghĩ rằng bạn đang tìm kiếm backtick, không phải là $ nhân vật, để làm cho công cụ của bạn trông mã-y. - Xymostech


Như một giải pháp thực tế:

  1. Nhanh chóng làm cho đống vớ dễ phân biệt. (Nói theo màu)
  2. Quicksort mỗi đống và sử dụng chiều dài của sock để so sánh. Là một con người, bạn có thể đưa ra quyết định khá nhanh chóng để sử dụng phân vùng tránh trường hợp xấu nhất. (Bạn có thể nhìn thấy nhiều vớ song song, sử dụng nó để lợi thế của bạn!)
  3. Dừng phân loại cọc khi chúng đạt đến ngưỡng mà bạn cảm thấy thoải mái khi tìm thấy cặp điểm và vớ không thể đeo được ngay lập tức

Nếu bạn có 1000 vớ, với 8 màu và phân bố trung bình, bạn có thể tạo 4 cọc mỗi 125 vớ trong thời gian c * n. Với ngưỡng 5 vớ bạn có thể sắp xếp mọi đống trong 6 lần chạy. (Đếm 2 giây để ném một cái vớ trên đống bên phải nó sẽ đưa bạn ít hơn 4 giờ.)

Nếu bạn chỉ có 60 vớ, 3 màu và 2 loại vớ (của bạn / của vợ bạn), bạn có thể sắp xếp mọi đống 10 vớ trong 1 lần chạy (Một lần nữa ngưỡng = 5). (Đếm 2 giây nó sẽ đưa bạn 2 phút).

Việc sắp xếp nhóm ban đầu sẽ đẩy nhanh quá trình của bạn, bởi vì nó chia đôi n của bạn thành các nhóm k trong c*n thời gian hơn bạn sẽ chỉ phải làm c*n*log(k) công việc. (Không tính đến ngưỡng). Vì vậy, tất cả trong tất cả các bạn làm về n*c*(1 + log(k)) công việc, trong đó c là thời gian để ném một cái vớ lên một cái cọc.

Cách tiếp cận này sẽ thuận lợi hơn so với bất kỳ c*x*n + O(1) phương pháp khoảng chừng nào log(k) < x - 1.


Trong khoa học máy tính, điều này có thể hữu ích: Chúng tôi có một bộ sưu tập của n nhiều thứ, một đơn đặt hàng trên chúng (chiều dài) và cũng là một mối quan hệ tương đương (thông tin bổ sung, ví dụ như màu vớ). Mối quan hệ tương đương cho phép chúng ta tạo ra một phân vùng của bộ sưu tập gốc, và trong mọi lớp tương đương, trật tự của chúng ta vẫn được duy trì. Ánh xạ của một Điều để nó tương đương lớp có thể được thực hiện trong O (1), do đó, chỉ O (n) là cần thiết để gán mỗi mục vào một lớp. Bây giờ chúng tôi đã sử dụng thông tin bổ sung của chúng tôi và có thể tiến hành theo bất kỳ cách nào để sắp xếp mọi lớp học. Ưu điểm là các tập dữ liệu đã nhỏ hơn đáng kể.

Phương pháp này cũng có thể được lồng nhau, nếu chúng ta có nhiều quan hệ tương đương -> tạo các cọc màu, hơn là trong mỗi phân vùng đống trên kết cấu, hơn là sắp xếp theo chiều dài. Bất kỳ mối quan hệ tương đương nào tạo ra một phân vùng có nhiều hơn 2 phần tử có kích thước thậm chí sẽ làm tăng tốc độ phân loại (miễn là chúng ta có thể gán trực tiếp một cái vớ cho cọc của nó) và sắp xếp có thể xảy ra rất nhanh trên các tập dữ liệu nhỏ hơn.


31



Tối ưu hóa con người: Tôi muốn tranh luận rằng với tư cách là con người, cho bước 2, bạn nên thắt tất xuống theo thứ tự tăng dần, sau đó lặp lại với độ chi tiết mịn hơn và mịn hơn cho đến khi được sắp xếp, giống như loại vỏ. Điều này sẽ nhanh hơn nhiều đối với con người (ước lượng trực quan) hơn là phương pháp dựa trên so sánh trao đổi. - AndrewC