Làm thế nào tôi có thể ghép đôi tất từ ​​một đống một cách hiệu quả?

3959
amit 2013-01-20 05:34.

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

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

Băm hoặc các giải pháp không đúng vị trí khác không phải là một lựa chọn, vì tôi không thể sao chép tất của mình (mặc dù có thể rấ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đôi tất, có chứa 2ncác phần tử (giả sử mỗi chiếc tất có đúng một đôi phù hợp), cách tốt nhất để ghép chúng một cách hiệu quả với không gian thừa lên đến logarit là gì? (Tôi tin rằng tôi có thể nhớ 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:

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

30 answers

2479
usr 2013-01-20 12:27.

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

Vì vậy, băm sẽ là đủ (và nhanh hơn).

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

Loại phân vùng băm đệ quy này thực sự đang được thực hiện bởi SQL Server khi nó cần tham gia băm hoặc tổng hợp băm trên các tập dữ liệu lớn. 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 chia tỷ lệ tuyến tính với lượng dữ liệu tùy ý và nhiều CPU.

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 mà mỗi nhóm đủ nhỏ để được xử lý rất nhanh. Thật không may, tôi không nghĩ rằng tất có tính chất như vậy.

Nếu mỗi chiếc tất 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).

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


Cập nhật:

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

Còn vấn đề về tính khác biệt của nguyên tố thì sao? Như bài báo đã nêu, vấn đề về tính khác 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 bài toán vớ (ngoài ra 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 kém tính toán - một bước là đủ nếu bạn phân phối trên md5(color, length, pattern, ...), tức là một hàm 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 ta đã đạt đến giới hạn dưới tối ưu .

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

590
dpc.ucore.info 2013-01-21 01:21.

Vì 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 thực tế.

Con người có thể chiến thắng các thuật toán CPU bằng cách sử dụng thực tế rằng "tìm một cặp phù hợp" có thể là một hoạt động đối với 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 rất nhiều.

265
Terry Li 2013-01-20 11:48.

Trường hợp 1 : Tất cả tất giống hệt nhau (nhân tiện đây là những gì mình làm ngoài đời).

Chọn bất kỳ hai trong số họ để tạo thành một cặp. Thời gian không đổi.

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

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

Trường hợp 3 : Không biết trước số tổ hợp (trường hợp tổng quát).

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

Tuy nhiên, trong cuộc sống thực khi số lượng tất 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 so với tìm kiếm tuần tự, về mặt lý thuyết đòi hỏi thời gian bậc hai.

158
guylhem 2013-01-20 17:34.

Câu trả lời không theo thuật toán, nhưng "hiệu quả" khi tôi thực hiện nó:

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

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

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

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

Hãy cân nhắc thay vì bạn chỉ rút một chiếc tất cho chồng tất thứ hai, như cách bạn đang làm, tỷ lệ tìm thấy chiếc tất phù hợp trong một tìm kiếm ngây thơ là khá thấp.

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

Tại sao năm? Thông thường, con người giỏi ghi nhớ từ năm đến bảy phần tử khác nhau trong bộ nhớ làm việc - giống như con người tương đương với ngăn xếp RPN - năm là một mặc định an toàn.

  • Chọn một từ ngăn xếp 2n-5.

  • Bây giờ, hãy tìm một kết quả phù hợp (đối sánh mẫu trực quan - con người giỏi về điều đó với một ngăn xếp nhỏ) bên trong năm hình bạn đã vẽ, nếu bạn không tìm thấy một hình, thì hãy thêm thứ đó vào năm

  • Tiếp tục chọn ngẫu nhiên tất từ ​​ngăn xếp và so sánh với 5 + 1 tất của bạn để khớp. Khi ngăn xếp của bạn tăng lên, nó sẽ làm 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 ra công thức để tính xem bạn phải vẽ bao nhiêu mẫu để có tỷ lệ cược 50% của một trận đấu. IIRC đó là một định luật siêu tỷ lệ.

Tôi làm điều đó vào mỗi buổ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ó nnhững đôi tương tự (khoảng 10, cho hoặc lấy đôi bị mất) của mđôi tất trắng có hình dạng. Bây giờ bạn có thể ước tính kích thước của chồng cổ phiếu của tôi :-)

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

107
Vilx- 2013-01-20 05:49.

Những gì tôi làm là tôi nhặt chiếc tất đầu tiên và đặt nó xuống (ví dụ, trên mép của bát giặt). Sau đó, tôi chọn một chiếc tất khác và kiểm tra xem nó có giống chiếc tất đầ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 tất đầu tiên. Sau đó, tôi chọn chiếc tất thứ ba và so sánh nó với hai chiếc đầu tiên (nếu chúng vẫn còn ở đó). Vân vân.

Cách tiếp cận này có thể khá dễ dàng được thực hiện trong một mảng, giả sử rằng "loại bỏ" tất là một tùy chọn. Trên thực tế, bạn thậm chí không cần phải "loại bỏ" tất. Nếu bạn không cần phân loại tất (xem bên dưới), thì bạn 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 tất được sắp xếp thành từng cặp trong mảng.

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

Tất nhiên, sắp xếp sẽ 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 "nhét" một chiếc tất vào giữa hai chiếc tất khác. Trong máy tính, cây cũng có thể đạt được điều tương tự, nhưng đó là không gian thừa. Và, tất nhiên, chúng tôi đã trở lại NlogN (hoặc hơn một chút, nếu có một số đôi tất giống nhau theo tiêu chí phân loại, nhưng không phải từ cùng một đôi).

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. :)

60
hyde 2013-02-08 21:42.

Đây là câu hỏi sai. Câu hỏi đúng cần đặt ra là, tại sao tôi lại dành thời gian phân loại tất? Chi phí hàng năm là bao nhiêu khi bạn định giá thời gian rảnh của mình cho X đơn vị tiền tệ 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 nào , đó là thời gian rảnh buổi sáng , bạn có thể nằm trên giường, nhâm nhi cà phê, hoặc về sớm một chút và không bị kẹt xe.

Việc lùi lại một bước và suy nghĩ cách giải quyết vấn đề thường là điều tốt.

Và có một cách!

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

Sẽ tốt hơn nếu không có sự khác biệt giữa tất chân trái và tất chân phải, nhưng nó không quá quan trọng. Nếu tất đối xứng từ trái sang phải, việc tìm một đôi là phép toán O (1) và sắp xếp tất là phép toán gần đúng với O (M), trong đó M là số nơi trong nhà mà bạn đã vứt đầy tất, lý tưởng là một số số không đổi nhỏ.

Nếu bạn chọn một đôi ưa thích với tất bên trái và bên phải khác nhau, thực hiện phân loại toàn bộ chiếc tất cho chiếc tất bên trái và bên phải lấy O (N + M), trong đó N là số chiếc tất và M tương tự như trên. Người khác có thể đưa ra công thức cho số 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 một cặp với tìm kiếm mù là N / 2 + 1, điều này trở thành trường hợp khó xảy ra về mặt thiên văn đối với 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à khám nghiệm, khi quét đống tất chưa được phân loại bằng Nhãn cầu Mk1 .

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

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

  2. Bạn cần tìm hiểu làm thế nào bạn có thể đặt hàng với số lượng lớn chiếc tất đã chọn của mình, giá bao nhiêu và họ có giao hàng không.

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

  4. Loại bỏ tất cũ của bạn.

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

Vấn đề đã được giải quyết. Vì vậy, chỉ cần mua những đôi tất mới, vứt / tặng những đôi tất cũ của bạn và sống hạnh phúc mãi mãi sau khi biết rằng bạn đang tiết kiệm tiền và thời gian mỗi ngày trong suốt quãng đời còn lại.

52
andredor 2013-01-20 10:40.

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

Bạn có thể đạt được O (n) với sắp xếp cơ số . Bạn chỉ cần chọn một số thuộc tính cho 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 đống,
  2. sau đó sử dụng màu sắc (có thể có bất kỳ thứ tự nào cho các màu, ví dụ theo thứ tự bảng chữ cái theo tên màu) - chia chúng thành từng đống 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 đó là chiều dài của tất,
  4. rồi kết cấu,….

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

33
Samuel 2013-01-21 05:18.

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

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

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

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

Việc phân loại xô ban đầu sẽ đẩy nhanh quá trình của bạn, bởi vì nó chia n chiếc tất của bạn thành k xô trong c*nthời gian để bạn 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ả những gì bạn làm về n*c*(1 + log(k))công việc, trong đó c là thời gian để ném một chiếc tất lên một đống.

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


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

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

28
Nikolay Dyankov 2015-10-20 10:47.

Bạn đang cố gắng giải quyết vấn đề sai.

Giải pháp 1: Mỗi lần bạn cho tất bẩn vào giỏ giặt, hãy buộc chúng lại bằng một nút nhỏ. Bằng cách đó, bạn sẽ không phải phân loại sau khi giặt. Hãy nghĩ về nó giống như đăng ký một chỉ mục trong cơ sở dữ liệu Mongo. Trước mắt một chút để tiết kiệm CPU trong tương lai.

Giải pháp 2: Nếu là mùa đông, bạn không nhất thiết phải đi tất phù hợp. Chúng tôi là những nhà lập trình. Không ai cần biết, miễn là nó hoạt động.

Giải pháp 3: Dàn trải công việc. Bạn muốn thực hiện một quá trình CPU phức tạp như vậy một cách không đồng bộ, mà không chặn giao diện người dùng. Lấy đống tất đó và nhét chúng vào một chiếc túi. Chỉ tìm kiếm một cặp khi bạn cần. Bằng cách đó, khối lượng công việc cần thực hiện sẽ ít được chú ý hơn nhiều.

Hi vọng điêu nay co ich!

27
Gene 2013-01-23 18:12.

Câu hỏi này thực sự mang tính triết học sâu sắc. Trọng tâm là vấn đề liệu sức mạnh của con người để giải quyết vấn đề ("phần mềm" của bộ não chúng ta) có tương đương với những gì có thể đạt được bằng các thuật toán hay không.

Một thuật toán rõ ràng để phân loại sock là:

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

Bây giờ khoa học máy tính trong vấn đề này là tất cả về các bước

  1. "if s ghép với một sock t trong N". Chúng ta có thể "nhớ" những gì chúng ta đã thấy cho đến nay nhanh đến mức nào?
  2. "loại bỏ t khỏi N" và "thêm s vào N". Theo dõi những gì chúng ta đã thấy cho đến nay đắt như thế nào?

Con người sẽ sử dụng các chiến lược khác nhau để thực hiện những điều này. Bộ nhớ của con người liên kết , giống như một bảng băm trong đó các tập hợp tính năng của các giá trị được lưu trữ được ghép nối với chính các giá trị tương ứng. Ví dụ, khái niệm "ô tô màu đỏ" ánh xạ cho tất cả các ô tô màu đỏ mà một người có thể nhớ được. Một người có trí nhớ hoàn hảo có một bản đồ hoàn hảo. Hầu hết mọi người đều không hoàn hảo trong vấn đề này (và hầu hết những người khác). Bản đồ liên kết có dung lượng hạn chế. Ánh xạ có thể bleep ra sự tồn tại trong điều kiện khác nhau (một bia quá nhiều), được ghi do lỗi ( "Tôi mặc dù tên của bà là Betty, không Nettie"), hoặc không bao giờ được ghi đè mặc dù chúng tôi nhận thấy rằng sự thật đã thay đổi ( "cha xe hơi "gợi lên" Firebird màu cam "khi chúng tôi thực sự biết anh ấy đã đổi cái đó để lấy chiếc Camaro màu đỏ).

Trong trường hợp tất, việc thu hồi hoàn hảo có nghĩa là nhìn vào một chiếc tất sluôn tạo ra ký ức về người anh em của nó t, bao gồm đủ thông tin (vị trí của nó trên bàn ủi) để xác định vị trí ttrong thời gian không đổi. Một người có trí nhớ nhiếp ảnh hoàn thành cả 1 và 2 trong thời gian liên tục mà không thất bại.

Một người nào đó có trí nhớ kém hoàn hảo có thể sử dụng một vài lớp tương đương thông thường dựa trên các đặc điểm trong khả năng theo dõi của anh ta: kích thước (bố, mẹ, em bé), màu sắc (xanh lục, hơi đỏ, v.v.), mẫu (argyle, trơn, v.v.) , kiểu dáng (cao đến đầu gối, v.v.). Vì vậy, bàn ủi sẽ được chia thành các phần cho các loại. Điều này thường cho phép danh mục được định vị theo thời gian cố định trong bộ nhớ, nhưng sau đó cần tìm kiếm tuyến tính thông qua "nhóm" danh mục.

Ai đó không có trí nhớ hoặc trí tưởng tượng (xin lỗi) sẽ chỉ giữ những chiếc tất trong một đống và thực hiện tìm kiếm tuyến tính toàn bộ đống.

Một kẻ kỳ quặc gọn gàng có thể sử dụng nhãn số cho các cặp như ai đó đã đề xuất. Điều này mở ra cánh cửa cho một thứ tự tổng thể, cho phép con người sử dụng chính xác các thuật toán mà chúng ta có thể làm với CPU: tìm kiếm nhị phân, cây, băm, v.v.

Vì vậy, thuật toán "tốt nhất" phụ thuộc vào chất lượng của phần mềm / phần cứng / phần mềm đang chạy nó và khả năng sẵn sàng "gian lận" của chúng tôi bằng cách áp đặt tổng thứ tự cho các cặp. Chắc chắn một thuật toán meta "tốt nhất" là thuê người phân loại sock tốt nhất thế giới: một người hoặc máy móc có thể thu thập và nhanh chóng lưu trữ một tập N khổng lồ các bộ thuộc tính sock trong bộ nhớ liên kết 1-1 với việc tra cứu thời gian liên tục, chèn, và xóa. Cả người và máy móc như thế này đều có thể được mua sắm. Nếu bạn có một chiếc, bạn có thể ghép tất trong thời gian O (N) cho N đôi là tối ưu. Các thẻ thứ tự tổng số cho phép bạn sử dụng phép băm chuẩn để có được kết quả tương tự với máy tính con người hoặc phần cứng.

22
1-----1 2013-01-20 12:19.

Chi phí: Di chuyển tất -> cao, tìm / tìm tất trong hàng -> nhỏ

Những gì chúng tôi muốn làm là giảm số lần di chuyển và bù đắp bằng số lượng tìm kiếm. Ngoài ra, chúng ta có thể sử dụng môi trường đa chủng tộc của người Homo Sapiens để lưu giữ nhiều thứ hơn trong bộ nhớ đệm không chính xác.

X = Của bạn, Y = Vợ / chồng của bạn

Từ đống A của tất cả:

Chọn hai chiếc tất, đặt chiếc tất X tương ứng vào dòng X và chiếc tất Y vào dòng Y ở vị trí có sẵn tiếp theo.

Làm cho đến khi A rỗng.

Đối với mỗi dòng X và Y

  1. Chọn chiếc tất đầu tiên trong hàng, tìm kiếm dọc theo hàng cho đến khi tìm thấy chiếc tất tương ứng.

  2. Đặt vào dòng tất thành phẩm tương ứng.

  3. Tùy chọn Trong khi bạn đang tìm kiếm dòng và và chiếc tất hiện tại bạn đang xem giống với chiếc trước đó, hãy thực hiện bước 2 cho những chiếc tất này.

Theo tùy chọn ở bước một, bạn chọn hai chiếc tất từ ​​dòng đó thay vì hai chiếc, vì bộ nhớ đệm đủ lớn, chúng tôi có thể nhanh chóng xác định xem một trong hai chiếc tất có khớp với chiếc hiện tại trên đường dây bạn đang quan sát hay không. Nếu bạn đủ may mắn để có ba cánh tay, bạn có thể phân tích ba chiếc tất cùng một lúc với điều kiện bộ nhớ của đối tượng đủ lớn.

Làm cho đến khi hết cả X và Y.

Làm xong

Tuy nhiên, vì điều này có độ phức tạp mô phỏng khi sắp xếp lựa chọn, thời gian thực hiện ít hơn nhiều do tốc độ của I / O (di chuyển tất) và tìm kiếm (tìm kiếm dòng cho một chiếc tất).

22
sdcvvc 2013-01-21 10:18.

Đây là giới hạn dưới Omega (n log n) trong mô hình dựa trên so sánh. (Thao tác hợp lệ duy nhất là so sánh hai chiếc tất.)

Giả sử rằng bạn biết rằng 2n chiếc tất của bạn được sắp xếp theo cách này:

p 1 p 2 p 3 ... p n p f (1) p f (2) ... p f (n)

trong đó f là một hoán vị chưa biết của tập {1,2, ..., n}. Biết được điều này không thể làm cho vấn đề khó hơn. Có n! kết quả đầu ra có thể có (so khớp giữa nửa đầu và nửa sau), có nghĩa là bạn cần so sánh log (n!) = Omega (n log n). Điều này có thể đạt được bằng cách sắp xếp.

Vì bạn quan tâm đến các kết nối với vấn đề về tính khác biệt của phần tử: việc chứng minh Omega (n log n) ràng buộc cho sự khác biệt của phần tử là khó hơn, bởi vì đầu ra là nhị phân có / không. Ở đây, đầu ra phải phù hợp và số lượng đầu ra có thể đủ để có được một giới hạn phù hợp. Tuy nhiên, có một biến thể được kết nối với sự khác biệt của phần tử. Giả sử bạn được tặng 2n chiếc tất và tự hỏi liệu chúng có thể được ghép đôi độc đáo hay không. Bạn có thể nhận được mức giảm từ ED bằng cách gửi (a 1 , a 2 , ..., a n ) tới (a 1 , a 1 , a 2 , a 2 , ..., a n , a n ). (Về mặt thẩm mỹ, bằng chứng về độ cứng của ED rất thú vị, thông qua cấu trúc liên kết .)

Tôi nghĩ rằng nên có một Omega (n 2 ) ràng buộc cho bài toán ban đầu nếu bạn chỉ cho phép các bài kiểm tra bình đẳng. Trực giác của tôi là: Hãy xem xét một đồ thị trong đó bạn thêm một cạnh sau khi kiểm tra và lập luận rằng nếu đồ thị không dày đặc thì kết quả đầu ra không được xác định duy nhất.

19
KeithS 2013-01-22 13:12.

Đây là cách tôi thực sự làm điều đó, đối với p đôi tất ( n = 2p đôi tất riêng lẻ):

  • Lấy ngẫu nhiên một chiếc tất từ ​​đống quần áo.
  • Đối với chiếc tất đầu tiên, hoặc nếu tất cả những chiếc tất được chọn trước đó đã được ghép đôi, bạn chỉ cần đặt chiếc tất vào "khe" đầu tiên của một "mảng" tất chưa được ghép trước mặt bạn.
  • Nếu bạn có một hoặc nhiều đôi tất chưa ghép đôi đã chọn, hãy kiểm tra chiếc tất hiện tại của bạn so với tất cả những chiếc tất chưa ghép đôi trong mảng.
    • Có thể tách tất thành các lớp hoặc loại chung (trắng / đen, mắt cá chân / húi cua, thể thao / váy) khi xây dựng mảng của bạn và "xem chi tiết" để chỉ so sánh tương tự.
    • Nếu bạn thấy phù hợp có thể chấp nhận được, hãy đặt cả hai chiếc tất lại với nhau và loại bỏ chúng khỏi mảng.
    • Nếu không, hãy đặt chiếc tất hiện tại vào khe mở đầu tiên trong mảng.
  • Lặp lại với mỗi chiếc tất.

Trường hợp xấu nhất của sơ đồ này là mỗi đôi tất khác nhau đến mức nó phải được khớp chính xác và n / 2 chiếc tất đầu tiên bạn chọn đều khác nhau. Đây là kịch bản O (n 2 ) của bạn và nó cực kỳ khó xảy ra. Nếu số loại tất duy nhất t ít hơn số đôi p = n / 2 và tất trong mỗi loại đủ giống nhau (thường là liên quan đến mặc) thì bất kỳ chiếc tất nào của loại đó đều có thể được ghép nối với bất kỳ khác, sau đó như tôi suy luận ở trên, số lượng đôi tất tối đa bạn sẽ phải so sánh là t , sau đó cái tiếp theo bạn kéo sẽ khớp với một trong những chiếc tất chưa được ghép đôi. Trường hợp này có nhiều khả năng xảy ra trong ngăn kéo sock trung bình hơn trường hợp xấu nhất và giảm độ phức tạp của trường hợp xấu nhất xuống O (n * t) trong đó thường là t << n .

18
Peter Mortensen 2013-04-02 09:37.

Cách tiếp cận thế giới thực:

Nhanh chóng nhất có thể, hãy lấy tất ra khỏi đống chưa được phân loại một cách nhanh chóng và đặt thành đống trước mặt bạn. Các cọc nên được sắp xếp sao cho hiệu quả về không gian, với tất cả đều hướng về cùng một hướng; số lượng cọc bị giới hạn bởi khoảng cách bạn có thể dễ dàng tiếp cận. Việc lựa chọn một đống để đặt một chiếc tất phải - càng nhanh càng tốt - bằng cách đặt một chiếc tất vào một đống có vẻ giống như tất; lỗi loại I (bỏ một chiếc tất lên một đống mà nó không thuộc về nó) hoặc loại II (đặt một chiếc tất vào đống tất của chính nó khi có một đống tất giống như vậy) có thể được chấp nhận - điều quan trọng nhất cần cân nhắc là tốc độ .

Sau khi tất cả tất đã thành đống, hãy nhanh chóng đi qua đống nhiều chiếc tất để tạo cặp và loại bỏ chúng (chúng đang hướng đến ngăn kéo). Nếu có những chiếc tất không khớp trong đống, hãy xếp lại đống tất sao cho phù hợp nhất (trong phạm vi hạn chế càng nhanh càng tốt). Khi tất cả các cọc nhiều bít tất đã được xử lý, hãy so khớp những đôi bít tất còn lại chưa được ghép đôi do lỗi loại II. Ồ, bạn đã hoàn thành - và tôi có rất nhiều tất và không giặt chúng cho đến khi một phần lớn bị bẩn. Một lưu ý thực tế khác: Tôi lật mặt trên của một đôi tất xuống dưới mặt kia, tận dụng đặc tính đàn hồi của chúng, để chúng ở lại với nhau khi được vận chuyển đến ngăn kéo và khi ở trong ngăn kéo.

15
Stephan Eggermont 2013-01-23 12:05.

Từ câu hỏi của bạn, rõ ràng là bạn không có nhiều kinh nghiệm thực tế về giặt ủi :). Bạn cần một thuật toán hoạt động tốt với một số lượng nhỏ tất không thể ghép nối.

Các câu trả lời cho đến bây giờ không tận dụng tốt khả năng nhận dạng khuôn mẫu của con người. Trò chơi Set cung cấp manh mối về cách làm tốt điều này: đặt tất trong không gian hai chiều để bạn có thể vừa nhận ra chúng vừa dễ dàng lấy chúng bằng tay. Điều này giới hạn bạn trong một khu vực khoảng 120 * 80 cm hoặc lâu hơn. Từ đó chọn các cặp mà bạn nhận ra và loại bỏ chúng. Đặt thêm tất vào chỗ trống và lặp lại. Nếu bạn giặt cho những người có tất dễ nhận biết (nhớ đến trẻ nhỏ), bạn có thể phân loại cơ số bằng cách chọn những đôi tất đó trước. Thuật toán này chỉ hoạt động tốt khi số lượng tất đơn ít

15
justinfay 2013-11-29 00:19.

Chọn một chiếc tất đầu tiên và đặt nó trên bàn. Bây giờ chọn một chiếc tất khác; nếu nó khớp với cái được chọn đầu tiên, hãy đặt nó lên trên cái đầu tiên. Nếu không, hãy đặt nó trên bàn một khoảng nhỏ so với chiếc đầu tiên. Chọn một chiếc tất thứ ba; nếu nó khớp với một trong hai cái trước, hãy đặt nó lên trên chúng hoặc đặt nó một khoảng cách nhỏ so với cái thứ ba. Lặp lại cho đến khi bạn đã chọn tất cả các tất.

12
SpaceTrucker 2013-01-29 21:07.

Để nói việc ghép đôi vớ từ một đống hiệu quả như thế nào, trước tiên chúng ta phải xác định máy, bởi vì việc ghép đôi không được thực hiện cho dù bằng bộ điều chỉnh hay bằng máy truy cập ngẫu nhiên, thường được sử dụng làm cơ sở cho phân tích thuật toán.

Máy

Máy móc là sự trừu tượng của một yếu tố trong thế giới thực được gọi là con người. Nó có thể đọc từ môi trường thông qua một đôi mắt. Và mô hình máy của chúng tôi có thể điều khiển môi trường bằng cách sử dụng 2 cánh tay. Các phép toán logic và số học được tính toán bằng bộ não của chúng ta (hy vọng là ;-)).

Chúng ta cũng phải xem xét thời gian chạy nội tại của các hoạt động nguyên tử có thể được thực hiện với các thiết bị này. Do những hạn chế về mặt vật lý, các hoạt động được thực hiện bằng tay hoặc mắt có độ phức tạp về thời gian không thay đổi. Điều này là do chúng ta không thể di chuyển một đống tất lớn vô tận bằng một cánh tay cũng như mắt thường không thể nhìn thấy chiếc tất trên cùng trên một đống tất lớn vô tận.

Tuy nhiên, vật lý cơ học cũng cung cấp cho chúng ta một số lợi ích. Chúng tôi không bị giới hạn chỉ di chuyển nhiều nhất một chiếc tất bằng một cánh tay. Chúng tôi có thể di chuyển cả một vài trong số chúng cùng một lúc.

Vì vậy, tùy thuộc vào phân tích trước đó, các phép toán sau nên được sử dụng theo thứ tự giảm dần:

  • phép toán logic và số học
  • đọc môi trường
  • sửa đổi môi trường

Chúng ta cũng có thể tận dụng thực tế là mọi người chỉ có một số lượng rất hạn chế tất. Vì vậy, một sửa đổi môi trường có thể liên quan đến tất cả các tất trong đống.

Thuật toán

Vì vậy, đây là gợi ý của tôi:

  1. Trải tất cả tất trong đống ra sàn.
  2. Tìm một đôi bằng cách nhìn vào những chiếc tất trên sàn.
  3. Lặp lại từ 2 cho đến khi không ghép được nữa.
  4. Lặp lại từ 1 cho đến khi không còn tất trên sàn.

Thao tác 4 là cần thiết, vì khi trải tất ra sàn, một số chiếc tất có thể che mất những chiếc khác. Đây là phân tích của thuật toán:

Phân tích

Thuật toán kết thúc với xác suất cao. Điều này là do thực tế là một người không thể tìm thấy đôi tất ở bước số 2.

Đối với phân tích thời gian chạy sau đây về việc ghép nđôi các đôi tất, chúng tôi giả sử rằng ít nhất một nửa số 2ntất không bị ẩn sau bước 1. Vì vậy, trong trường hợp trung bình, chúng tôi có thể tìm thấy n/2các đôi. Điều này có nghĩa là vòng lặp là bước 4 được thực hiện O(log n)lần. Bước 2 được thực hiện O(n^2)lần. Vì vậy, chúng tôi có thể kết luận:

  • Thuật toán liên quan đến O(ln n + n)các sửa đổi môi trường (bước 1 O(ln n)cộng với việc chọn mọi cặp vớ từ sàn nhà)
  • Thuật toán liên quan đến việc O(n^2)đọc môi trường từ bước 2
  • Thuật toán bao gồm O(n^2)các phép toán logic và số học để so sánh một chiếc vớ với một chiếc vớ khác ở bước 2

Vì vậy, chúng tôi có tổng độ phức tạp thời gian chạy là O(r*n^2 + w*(ln n + n))đâu rwlà các yếu tố cho các hoạt động đọc môi trường và ghi môi trường tương ứng cho một lượng vớ hợp lý. Chi phí của các phép toán logic và số học được bỏ qua, bởi vì chúng tôi cho rằng cần một lượng không đổi các phép toán logic và số học để quyết định xem 2 chiếc tất có thuộc cùng một cặp hay không. Điều này có thể không khả thi trong mọi tình huống.

12
Chad 2013-01-23 06:32.
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);
  }
}
12
Sasa 2013-01-24 02:24.

Tôi đã đưa ra một giải pháp khác sẽ không hứa hẹn ít hoạt động hơn, cũng không tiêu tốn ít thời gian hơn, nhưng nó nên được thử xem liệu nó có thể là một phương pháp kinh nghiệm đủ tốt để cung cấp ít thời gian tiêu thụ hơn trong một loạt cặp sock khổng lồ hay không.

Điều kiện tiên quyết: Không có gì đảm bảo rằng có những đôi tất giống nhau. Nếu chúng có cùng màu không có nghĩa là chúng có cùng kích thước hoặc kiểu dáng. Tất được xáo trộn ngẫu nhiên. Có thể có số lượng lẻ đôi tất (một số bị thiếu, chúng tôi không biết là bao nhiêu). Chuẩn bị để ghi nhớ một biến "chỉ mục" và đặt nó thành 0.

Kết quả sẽ có một hoặc hai cọc: 1. "khớp" và 2. "thiếu"

Heuristic:

  1. Tìm chiếc tất đặc biệt nhất.
  2. Tìm sự phù hợp của nó.
  3. Nếu không trùng khớp thì đưa lên cọc “thiếu”.
  4. Lặp lại từ 1. cho đến khi không còn chiếc tất nào khác biệt nhất.
  5. Nếu có ít hơn 6 chiếc tất, đến 11 chiếc.
  6. Ghép đôi tất một cách mù quáng với người hàng xóm của nó (không đóng gói nó)
  7. Tìm tất cả các cặp phù hợp, đóng gói nó và di chuyển các cặp đã đóng gói vào đống "phù hợp"; Nếu không có kết quả phù hợp mới - tăng "chỉ số" lên 1
  8. Nếu "chỉ số" lớn hơn thì 2 (giá trị này có thể phụ thuộc vào số chiếc tất vì với số lượng tất nhiều hơn, ít có cơ hội để ghép chúng một cách mù quáng hơn) đi đến 11
  9. Xáo trộn phần còn lại
  10. Đi đến 1
  11. Quên "chỉ mục"
  12. Chọn một chiếc tất
  13. Tìm cặp của nó
  14. Nếu không có cặp cho chiếc tất, hãy chuyển nó vào đống "còn thiếu"
  15. Nếu tìm thấy phù hợp, hãy ghép nối nó, đóng gói cặp và chuyển nó vào đống "đã khớp"
  16. Nếu vẫn còn nhiều hơn thì một chiếc tất đi thành 12 chiếc
  17. Nếu chỉ còn một, hãy chuyển đến 14
  18. Nụ cười hài lòng :)

Ngoài ra, cũng có thể kiểm tra thêm những đôi tất bị hỏng, như thể loại bỏ những đôi tất đó. Nó có thể được chèn từ 2 đến 3, và từ 13 đến 14.

Tôi mong muốn được nghe về bất kỳ kinh nghiệm hoặc sửa chữa nào.

11
Andrew Hill 2013-10-23 21:56.

Khi tôi phân loại tất, tôi thực hiện sắp xếp theo cơ số gần đúng , thả tất gần những chiếc tất khác có cùng màu / kiểu mẫu. Ngoại trừ trường hợp khi tôi có thể thấy một sự trùng khớp chính xác tại / gần vị trí tôi sắp thả chiếc tất, tôi sẽ rút cặp tại thời điểm đó.

Hầu như tất cả các thuật toán khác (bao gồm cả câu trả lời cho điểm cao nhất theo usr ) sắp xếp, sau đó loại bỏ các cặp. Tôi thấy rằng, là một con người, tốt hơn là nên giảm thiểu số lượng tất được xem xét cùng một lúc.

Tôi làm điều này bằng cách:

  1. Chọn một chiếc tất đặc biệt (bất cứ thứ gì đập vào mắt tôi đầu tiên trong đống).
  2. Bắt đầu sắp xếp cơ số từ vị trí khái niệm đó bằng cách kéo tất từ ​​đống dựa trên sự tương tự với cái đó.
  3. Đặt chiếc tất mới gần với đống hiện tại, với khoảng cách dựa trên mức độ khác nhau của nó. Nếu bạn thấy mình đặt chiếc tất này lên trên chiếc tất khác vì nó giống hệt nhau, hãy tạo thành cặp ở đó và loại bỏ chúng. Điều này có nghĩa là các so sánh trong tương lai tốn ít công sức hơn để tìm ra vị trí chính xác.

Điều này tận dụng khả năng của con người để so khớp mờ trong thời gian O (1), tương đương với việc thiết lập một bản đồ băm trên một thiết bị máy tính.

Bằng cách kéo những chiếc tất đặc biệt trước, bạn để lại khoảng trống để "phóng to" những đặc điểm ít đặc biệt hơn, để bắt đầu.

Sau khi loại bỏ những đôi tất có màu fluro, những đôi tất có sọc và ba đôi tất dài, bạn có thể kết thúc với những đôi tất chủ yếu là màu trắng được sắp xếp theo cách chúng mặc.

Tại một số thời điểm, sự khác biệt giữa các đôi tất đủ nhỏ để người khác không nhận ra sự khác biệt và không cần nỗ lực kết hợp thêm.

10
trpt4him 2013-01-20 12:25.

Bất cứ khi nào bạn nhặt một chiếc tất, hãy cất nó vào một chỗ. Sau đó, bạn chọn chiếc tất tiếp theo, nếu nó không khớp với chiếc tất đầu tiên, hãy đặt nó bên cạnh chiếc đầu tiên. Nếu có, có một cặp. Bằng cách này, nó không thực sự quan trọng có bao nhiêu sự kết hợp và chỉ có hai khả năng cho mỗi chiếc tất bạn chọn - hoặc nó có một sự phù hợp đã có trong mảng tất của bạn, hoặc nó không, nghĩa là bạn thêm nó vào một vị trí trong mảng.

Điều này cũng có nghĩa là bạn gần như chắc chắn sẽ không bao giờ có tất của mình trong mảng, bởi vì tất sẽ bị loại bỏ khi chúng khớp với nhau.

10
Arvind 2013-01-23 03:33.

Hãy xem xét một bảng băm có kích thước 'N'.

Nếu chúng ta giả sử phân phối chuẩn, thì số lượng 'chèn' ước tính để có ít nhất một sock được ánh xạ vào một nhóm là NlogN (tức là tất cả các nhóm đều đầy)

Tôi đã suy ra điều này như một phần của một câu đố khác, nhưng tôi sẽ rất vui khi được chứng minh là sai. Đây là bài viết trên blog của tôi về cùng một

Gọi 'N' tương ứng với giới hạn trên gần đúng về số màu / mẫu tất độc đáo mà bạn có.

Một khi bạn có một va chạm (hay còn gọi là: một trận đấu), bạn chỉ cần tháo đôi tất đó ra. Lặp lại thí nghiệm tương tự với lô vớ NlogN tiếp theo. Cái hay của nó là bạn có thể thực hiện so sánh song song NlogN (độ phân giải va chạm) do cách trí óc con người hoạt động. :-)

10
mozboz 2013-01-23 15:25.

Tất, cho dù là thật hay một số cấu trúc dữ liệu tương tự, sẽ được cung cấp theo cặp.

Câu trả lời đơn giản nhất là trước khi cho phép tách đôi tất, một cấu trúc dữ liệu duy nhất cho đôi nên được khởi tạo có chứa một con trỏ đến chiếc tất trái và phải, do đó cho phép tất được tham chiếu trực tiếp hoặc thông qua đôi của chúng. Một chiếc tất cũng có thể được mở rộng để chứa một con trỏ đến đối tác của nó.

Điều này giải quyết bất kỳ vấn đề ghép nối tính toán nào bằng cách loại bỏ nó bằng một lớp trừu tượng.

Áp dụng ý tưởng tương tự vào vấn đề thực tế của việc ghép đôi tất, câu trả lời rõ ràng là: đừng cho phép đôi tất của bạn không được ghép đôi. Vớ được cung cấp như một đôi, để trong ngăn kéo như một đôi (có thể bằng cách cuộn chúng lại với nhau), mặc như một đôi. Tuy nhiên, điểm mà bạn có thể thực hiện là ở máy giặt, vì vậy tất cả những gì cần thiết là một cơ chế vật lý cho phép các đôi tất dính chặt vào nhau và được giặt sạch một cách hiệu quả.

Có hai khả năng vật lý:

Đối với một đối tượng 'cặp' giữ một con trỏ vào mỗi chiếc tất, chúng ta có thể có một chiếc túi vải mà chúng ta sử dụng để giữ các đôi tất lại với nhau. Điều này có vẻ giống như chi phí lớn.

Nhưng đối với mỗi chiếc tất để giữ tham chiếu đến chiếc khác, có một giải pháp gọn gàng: một popper (hoặc 'nút chụp nhanh' nếu bạn là người Mỹ), chẳng hạn như sau:

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

Sau đó, tất cả những gì bạn làm là chụp đôi tất lại với nhau ngay sau khi cởi ra và cho vào giỏ giặt, và một lần nữa, bạn đã loại bỏ được vấn đề cần phải đi đôi tất của mình với khái niệm 'đôi' trừu tượng.

8
SF. 2014-09-21 22:49.

Nếu thao tác "di chuyển" khá tốn kém và thao tác "so sánh" rẻ và dù sao thì bạn cũng cần phải di chuyển toàn bộ tập hợp vào bộ đệm nơi tìm kiếm nhanh hơn nhiều so với trong bộ nhớ ban đầu ... chỉ cần tích hợp sắp xếp vào phần bắt buộc di chuyển.

Tôi thấy việc tích hợp quy trình phân loại vào treo để sấy khô làm cho nó trở nên dễ dàng. Dù sao thì tôi cũng cần phải nhặt từng chiếc tất và treo nó (di chuyển) và tôi chẳng tốn kém gì nếu treo nó ở một nơi cụ thể trên dây. Bây giờ chỉ cần không bắt buộc tìm kiếm toàn bộ bộ đệm (dây), tôi chọn đặt tất theo màu sắc / bóng râm. Bên trái tối hơn, bên phải sáng hơn, mặt trước nhiều màu sắc hơn, v.v. Bây giờ trước khi treo mỗi chiếc tất, tôi nhìn vào "vùng lân cận bên phải" của nó xem đã có một chiếc tất phù hợp chưa - điều này giới hạn "quét" ở 2-3 chiếc tất khác - và nếu có , Tôi treo chiếc còn lại ngay bên cạnh. Sau đó, tôi cuộn chúng thành từng cặp khi tháo ra khỏi dây, khi đã khô.

Bây giờ điều này có vẻ không khác gì so với "hình thành các cọc theo màu sắc" được đề xuất bởi các câu trả lời hàng đầu nhưng trước tiên, bằng cách không chọn các cọc rời rạc mà là các dãy, tôi không gặp vấn đề gì khi phân loại xem "màu tím" chuyển thành "màu đỏ" hay "màu xanh"; nó chỉ đi giữa. Và sau đó bằng cách tích hợp hai hoạt động (treo để làm khô và sắp xếp), chi phí phân loại trong khi treo giống như 10% của việc phân loại riêng biệt.

8
maestro 2013-10-28 08:45.

Tôi đã hoàn thành việc ghép đôi tất của mình ngay bây giờ và tôi thấy rằng cách tốt nhất để làm điều đó là:

  • Chọn một trong những chiếc tất và cất đi (tạo một chiếc 'xô' cho đôi đó)
  • Nếu cái tiếp theo là cặp của cái trước, thì hãy đặt nó vào nhóm hiện có, nếu không hãy tạo một cái mới.

Trong trường hợp xấu nhất, điều đó có nghĩa là bạn sẽ có n / 2 chiếc xô khác nhau và bạn sẽ có n-2 lần xác định xem chiếc xô nào chứa cặp chiếc tất hiện tại. Rõ ràng, thuật toán này hoạt động tốt nếu bạn chỉ có một vài cặp; Tôi đã làm điều đó với 12 cặp.

Nó không phải là quá khoa học, nhưng nó hoạt động tốt :)

8
wrzasa 2015-05-28 09:13.

Giải pháp của tôi không hoàn toàn tương ứng với yêu cầu của bạn, vì nó chính thức yêu cầu O(n)không gian "bổ sung". Tuy nhiên, xem xét các điều kiện của tôi, nó rất hiệu quả trong ứng dụng thực tế của tôi. Vì vậy, tôi nghĩ rằng nó sẽ được thú vị.

Kết hợp với Nhiệm vụ khác

Điều kiện đặc biệt trong trường hợp của tôi là tôi không sử dụng máy sấy, chỉ treo đồ trên máy sấy vải thông thường. Treo vải đòi hỏi các O(n)hoạt động (nhân tiện, tôi luôn xem xét vấn đề đóng gói thùng rác ở đây) và vấn đề về bản chất của nó đòi hỏi không gian tuyến tính "phụ". Khi tôi lấy một chiếc tất mới từ thùng, tôi để thử treo nó bên cạnh cặp của nó nếu cặp đã được treo. Nếu nó là một chiếc tất từ ​​một đôi mới, tôi để một khoảng trống bên cạnh nó.

Máy Oracle tốt hơn ;-)

Rõ ràng là nó đòi hỏi một số công việc bổ sung để kiểm tra xem có chiếc bít tất phù hợp đã được treo ở đâu đó hay không và nó sẽ hiển thị giải pháp O(n^2)với hệ số khoảng 1/2cho một máy tính. Nhưng trong trường hợp này, "yếu tố con người" thực sự là một lợi thế - tôi thường có thể rất nhanh chóng (gần như O(1)) xác định được chiếc sock phù hợp nếu nó đã được treo (có thể có một số bộ nhớ đệm trong não không thể nhận thấy được) - hãy coi đó là một loại giới hạn "oracle" như trong Máy Oracle ;-) Chúng tôi, con người có những lợi thế này so với máy kỹ thuật số trong một số trường hợp ;-)

Có nó gần như O(n)!

Vì vậy, kết nối vấn đề ghép đôi vớ với vấn đề treo vải, tôi nhận được O(n)"thêm không gian" miễn phí, và có một giải pháp O(n)đúng lúc, chỉ đòi hỏi nhiều công việc hơn một chút so với việc treo vải đơn giản và cho phép truy cập ngay vào đôi tất hoàn chỉnh. vớ ngay cả trong một buổi sáng thứ Hai rất tồi tệ ... ;-)

8
Philipp Flenker 2014-04-30 23:18.

Tôi hy vọng tôi có thể đóng góp một cái gì đó mới cho vấn đề này. Tôi nhận thấy rằng tất cả các câu trả lời đều bỏ qua thực tế rằng có hai điểm mà bạn có thể thực hiện tiền xử lý mà không làm chậm hiệu suất giặt chung của bạn.

Ngoài ra, chúng ta không cần phải giả định một số lượng lớn tất, ngay cả đối với những gia đình đông người. Những đôi tất được lấy ra khỏi ngăn kéo và mặc vào, sau đó chúng được ném vào một nơi (có thể là thùng) nơi chúng ở trước khi được giặt. Mặc dù tôi sẽ không gọi bin đã nói là LIFO-Stack, nhưng tôi muốn nói rằng sẽ an toàn khi cho rằng

  1. mọi người ném gần như cả hai chiếc tất của họ vào cùng một khu vực của thùng,
  2. thùng không được ngẫu nhiên hóa tại bất kỳ điểm nào, và do đó
  3. bất kỳ tập hợp con nào được lấy từ trên cùng của thùng này thường chứa cả hai chiếc tất của một đôi.

Vì tất cả các máy giặt mà tôi biết đều có kích thước giới hạn (bất kể bạn phải giặt bao nhiêu chiếc tất) và sự ngẫu nhiên thực tế xảy ra trong máy giặt, bất kể chúng tôi có bao nhiêu chiếc tất, chúng tôi luôn có những tập con nhỏ hầu như không chứa người độc thân.

Hai công đoạn sơ chế của chúng tôi là "đặt tất vào dây phơi" và "Lấy tất từ ​​dây phơi", chúng tôi phải làm để có được đôi tất không chỉ sạch mà còn khô. Cũng như đối với máy giặt, dây phơi là hữu hạn và tôi giả định rằng chúng ta có toàn bộ phần của dây mà chúng ta đặt tất của mình trong tầm mắt.

Đây là thuật toán cho 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 
 }
}

Đừng lãng phí thời gian của bạn để di chuyển tất xung quanh hoặc tìm kiếm sự phù hợp nhất, tất cả điều này nên được thực hiện trong O (n), mà chúng tôi cũng sẽ cần chỉ để đặt chúng vào hàng không được sắp xếp. Tất chưa được ghép nối, chúng tôi chỉ có một số cụm tương tự trên đường dây. Thật hữu ích khi chúng tôi có một bộ tất có giới hạn ở đây, vì điều này giúp chúng tôi tạo ra các cụm "tốt" (ví dụ: nếu chỉ có tất đen trong bộ tất, thì việc nhóm theo màu sẽ không phải là cách tốt nhất)

Đây là thuật toán cho 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
 }

Tôi nên chỉ ra rằng để cải thiện tốc độ của các bước còn lại, điều khôn ngoan là không chọn ngẫu nhiên chiếc tất tiếp theo, mà hãy tuần tự lấy chiếc tất này đến chiếc tất khác từ mỗi cụm. Cả hai bước sơ chế đều không mất nhiều thời gian hơn là chỉ đặt tất lên dây chuyền hoặc vào giỏ, mà chúng ta phải làm bất kể việc gì, vì vậy điều này sẽ nâng cao hiệu suất giặt là đáng kể.

Sau đó, thật dễ dàng để thực hiện thuật toán phân vùng băm. Thông thường, khoảng 75% tất đã được ghép nối, để lại cho tôi một tập hợp con rất nhỏ của tất và tập hợp con này đã (phần nào) được nhóm lại (tôi không đưa nhiều entropy vào giỏ của mình sau các bước tiền xử lý). Một điều khác là các cụm còn lại có xu hướng đủ nhỏ để xử lý cùng một lúc, vì vậy có thể lấy cả cụm ra khỏi giỏ.

Đây là thuật toán cho sort_remaining_clusters ():

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

Sau đó, chỉ còn lại một vài chiếc tất. Đây là nơi tôi đưa những chiếc tất chưa được ghép đôi trước đó vào hệ thống và xử lý những chiếc tất còn lại mà không cần bất kỳ thuật toán đặc biệt nào - những chiếc tất còn lại rất ít và có thể được xử lý trực quan rất nhanh.

Đối với tất cả những chiếc tất còn lại, tôi cho rằng những chiếc tất còn lại của chúng vẫn chưa được giặt và cất chúng đi cho lần lặp tiếp theo. Nếu bạn ghi nhận sự phát triển của những đôi tất không cặp theo thời gian ("sự cố rò rỉ tất"), bạn nên kiểm tra thùng của mình - nó có thể được phân loại ngẫu nhiên (bạn có mèo ngủ trong đó không?)

Tôi biết rằng các thuật toán này đưa ra rất nhiều giả định: một cái thùng hoạt động như một loại ngăn xếp LIFO, một máy giặt bình thường có giới hạn và một dây phơi thông thường, có giới hạn - nhưng điều này vẫn hoạt động với số lượng rất lớn tất.

Về song song: Chỉ cần bạn ném cả hai chiếc tất vào cùng một thùng, bạn có thể dễ dàng xếp song song tất cả các bước đó.

8
Scott Brickey 2013-09-08 06:06.

Tôi đã thực hiện các bước đơn giản để giảm nỗ lực của mình vào một quy trình mất O (1) thời gian.

Bằng cách giảm đầu vào của tôi xuống một trong hai loại tất (tất trắng để giải trí, tất đen để đi làm), tôi chỉ cần xác định xem tôi có trong tay loại tất nào trong số hai loại tất. (Về mặt kỹ thuật, vì chúng không bao giờ được rửa cùng nhau, tôi đã giảm quy trình xuống còn O (0) thời gian.)

Cần phải có một số nỗ lực trả trước để tìm được đôi tất ưng ý và mua đủ số lượng để loại bỏ nhu cầu về những đôi tất hiện có của bạn. Vì tôi đã làm điều này trước khi tôi cần đến tất đen, nỗ lực của tôi là rất ít, nhưng số dặm có thể thay đổi.

Một nỗ lực trả trước như vậy đã được nhìn thấy nhiều lần trong mã rất phổ biến và hiệu quả. Các ví dụ bao gồm # DEFINE'ing pi thành một số số thập phân (các ví dụ khác tồn tại, nhưng đó là cái tôi nghĩ ngay bây giờ).

7
viper110110 2013-09-09 10:07.

Tạo một bảng băm sẽ được sử dụng cho những chiếc tất không khớp, sử dụng mẫu làm bảng băm. Lặp đi lặp lại từng chiếc tất một. Nếu chiếc tất có mẫu trùng khớp trong bảng băm, hãy lấy chiếc tất ra khỏi bàn và tạo thành một cặp. Nếu chiếc tất không có khớp, hãy đặt nó vào bàn.

7
Fred Mitchell 2013-10-09 12:47.

Bài toán sắp xếp n đôi tất của bạn là O (n) . Trước khi ném chúng vào giỏ giặt , bạn luồn chiếc bên trái sang chiếc bên phải. Khi lấy chúng ra, bạn cắt sợi chỉ và đặt từng cặp vào ngăn kéo của bạn - 2 phép toán trên n cặp, do đó O (n).

Bây giờ câu hỏi tiếp theo chỉ đơn giản là bạn giặt quần áo của riêng bạn và vợ bạn giặt quần áo của cô ấy. Đó là một vấn đề có thể xảy ra trong một lĩnh vực vấn đề hoàn toàn khác . :)

Related questions

MORE COOL STUFF

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett đã bất chấp những lời khuyên hẹn hò điển hình khi cô gặp chồng mình.

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Michael Sheen là một diễn viên phi lợi nhuận nhưng chính xác thì điều đó có nghĩa là gì?

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Ngôi sao của Hallmark Colin Egglesfield chia sẻ về những cuộc gặp gỡ với người hâm mộ ly kỳ tại RomaDrama Live! cộng với chương trình INSPIRE của anh ấy tại đại hội.

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Bạn sẽ phải phủi sạch đầu đĩa Blu-ray hoặc DVD để xem tại sao Northern Exposure trở thành một trong những chương trình nổi tiếng nhất của thập niên 90.

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

8 công dụng tuyệt vời của Baking Soda và Giấm

8 công dụng tuyệt vời của Baking Soda và Giấm

Bạn biết đấy, hai sản phẩm này là nguồn điện để làm sạch, riêng chúng. Nhưng cùng với nhau, chúng có một loạt công dụng hoàn toàn khác.

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Thủy điện rất cần thiết cho lưới điện của Hoa Kỳ, nhưng nó chỉ tạo ra năng lượng khi có nước di chuyển. Bao nhiêu nhà máy thủy điện có thể gặp nguy hiểm khi các hồ và sông cạn kiệt?

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Tóc tỉa từ các tiệm và các khoản quyên góp cá nhân có thể được tái sử dụng như những tấm thảm thấm dầu và giúp bảo vệ môi trường.

Một thương hiệu kế thừa khác có được cuộc sống mới khi những người chủ mới của Black Opal có được Hội chợ thời trang

Một thương hiệu kế thừa khác có được cuộc sống mới khi những người chủ mới của Black Opal có được Hội chợ thời trang

Desiree Rogers, trái, và Cheryl Mayberry McKissack Chuyển sang, Fenty Beauty và Pat McGrath, có một đế chế làm đẹp mới do phụ nữ làm chủ đang trỗi dậy. Sau thương vụ mua lại mỹ phẩm Black Opal vào tháng 9, đội ngũ quyền lực của Giám đốc điều hành công ty Desiree Rogers và Chủ tịch Cheryl Mayberry McKissack đã thông báo mua lại thương hiệu làm đẹp tiên phong Fashion Fair từ người sáng lập Johnson Publishing Company (JPC).

Ngoài việc trở nên vô nghĩa, các bên bộc lộ giới tính giờ đây đã trở nên chết người

Ngoài việc trở nên vô nghĩa, các bên bộc lộ giới tính giờ đây đã trở nên chết người

Đối với những người có quá nhiều thời gian, tiệc tiết lộ giới tính là một cách thú vị để không cần áp đặt những định kiến ​​hạn chế lên thai nhi trước một đối tượng bạn bè giả vờ quan tâm một cách lịch sự. Tuy nhiên, việc chỉ dựa vào những chiếc bánh nướng có màu nhân tạo để biểu thị một tiếng hoo-ha hoặc một đứa trẻ đi tè đã trở nên xa xỉ trong các bậc cha mẹ trên Instagram.

Kirstjen Nielsen đang cố gắng đổi mới bản thân với tư cách là một người phụ nữ 'nói ra sự thật cho sức mạnh'

Kirstjen Nielsen đang cố gắng đổi mới bản thân với tư cách là một người phụ nữ 'nói ra sự thật cho sức mạnh'

Hôm thứ Tư, cựu Bộ trưởng An ninh Nội địa Kirstjen Nielsen vì một lý do nào đó đã được đưa ra một diễn đàn để phát biểu tại Hội nghị thượng đỉnh Những người phụ nữ quyền lực nhất của Fortune. Và có thể đoán trước được, người phụ nữ giám sát các nỗ lực (đang diễn ra) của chính quyền Trump nhằm chia cắt các gia đình ở biên giới đã sử dụng thời gian của mình như một cơ hội để tự bảo vệ mình và tự nhận mình là người — và hãy hít thở sâu ở đây — “đã nói sự thật với quyền lực.

Toyota Racing Development sẽ cho ra mắt Supra 3000GT Concept, Massive Wing vào tháng tới

Toyota Racing Development sẽ cho ra mắt Supra 3000GT Concept, Massive Wing vào tháng tới

Vì thế hệ mới nhất của chiếc xe điều chỉnh được yêu thích trên thế giới hiện đã có mặt tại đây, nên chỉ có điều kiện là Toyota Racing Development sẽ đưa phiên bản Supra thế hệ thứ năm sửa đổi của riêng mình đến SEMA vào tháng tới. Toyota đã cho chúng tôi một gợi ý về những gì sẽ xảy ra trong tuần này: một chiếc Concept GR Supra 3000GT hiện đại.

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Rothschild's luggage got lost, but luckily she has an incredible closet to shop: Sister Paris Hilton's!

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa. Từ Hollywood đến New York và mọi nơi ở giữa, hãy xem các ngôi sao yêu thích của bạn đang làm gì!

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

Các nhà điều tra đang xem xét liệu nhóm và nghi phạm có biết nhau trước vụ tấn công hay không

Thanh thiếu niên, Gia đình Florida Hội đồng quản trị trường học về Luật 'Không nói đồng tính': 'Buộc chúng tôi tự kiểm duyệt'

Thanh thiếu niên, Gia đình Florida Hội đồng quản trị trường học về Luật 'Không nói đồng tính': 'Buộc chúng tôi tự kiểm duyệt'

Vụ kiện, nêu tên một số học khu, lập luận rằng dự luật "Không nói đồng tính" được ban hành gần đây của Florida "có hiệu quả im lặng và xóa bỏ học sinh và gia đình LGBTQ +"

Đường băng hạ cánh

Đường băng hạ cánh

Cuối hè đầu thu là mùa hoài niệm. Những chiếc đèn đường chiếu ánh sáng của chúng qua những con đường đẫm mưa, và những chiếc lá dưới chân - màu đỏ cam tắt trong bóng chạng vạng - là lời nhắc nhở về những ngày đã qua.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Vào năm 2021, tôi khuyến khích bạn suy nghĩ lại mọi thứ bạn biết về khách hàng mà bạn phục vụ và những câu chuyện bạn kể cho họ. Lùi lại.

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Vào ngày sinh nhật thứ 9 của Felix The Cat, tôi nhớ về một trong những mất mát lớn nhất trong cuộc đời trưởng thành của tôi - Sophie của tôi vào năm 2013. Tôi đã viết bài luận này và chia sẻ nó trên nền tảng này một thời gian ngắn vào năm 2013.

Khi bạn không thể trở thành người mà Internet muốn bạn trở thành

Khi bạn không thể trở thành người mà Internet muốn bạn trở thành

Tôi ghét từ "tàu đắm". Mọi người cảm thấy thoải mái trong la bàn đạo đức của riêng mình, và khi làm như vậy, họ thấy mình vượt qua sự phán xét.

Language