Pertanyaan Bagaimana cara memasangkan kaus kaki dari tumpukan secara efisien?


Kemarin saya memasangkan kaus kaki dari cucian bersih dan menemukan cara yang saya lakukan itu tidak terlalu efisien. Saya melakukan pencarian yang naif - memilih satu kaus kaki dan "mengulangi" tumpukan untuk menemukan pasangannya. Ini membutuhkan iterasi lebih dari n / 2 * n / 4 = n2/ 8 kaus kaki rata-rata.

Sebagai ilmuwan komputer, saya berpikir apa yang bisa saya lakukan? Menyortir (menurut ukuran / warna / ...) tentu saja muncul dalam pikiran untuk mencapai solusi O (NlogN).

Hashing atau solusi tidak-di-tempat lainnya bukanlah pilihan, karena saya tidak dapat menduplikasi kaus kaki saya (meskipun itu bisa menyenangkan jika saya bisa).

Jadi, pertanyaannya pada dasarnya adalah:

Diberikan setumpuk n pasang kaus kaki, mengandung 2n elemen (menganggap setiap kaus kaki memiliki tepat satu pasangan yang cocok), apa cara terbaik untuk memasangkannya secara efisien dengan ruang ekstra logaritmik? (Saya yakin saya dapat mengingat informasi sebanyak itu jika diperlukan.)

Saya akan menghargai jawaban yang membahas aspek-aspek berikut:

  • Seorang jenderal teoretis solusi untuk sejumlah besar kaus kaki.
  • Jumlah sebenarnya kaus kaki tidak begitu besar, saya tidak percaya pasangan saya dan saya memiliki lebih dari 30 pasang. (Dan cukup mudah membedakan antara kaus kakiku dan miliknya; bisakah ini digunakan juga?)
  • Apakah itu setara dengan masalah perbedaan elemen?

3501
2018-01-19 15:34


asal


Jawaban:


Solusi penyortiran telah diusulkan, tetapi penyortiran terlalu banyak: Kami tidak perlu memesan; kita hanya butuh kelompok kesetaraan.

Begitu hashing akan cukup (dan lebih cepat).

  1. Untuk setiap warna kaus kaki, membentuk tumpukan. Iterate atas semua kaus kaki di keranjang masukan Anda dan mendistribusikannya ke tumpukan warna.
  2. Iterasi atas setiap tumpukan dan mendistribusikannya dengan beberapa metrik lainnya (mis. pola) ke set tumpukan kedua
  3. Secara rekursif menerapkan skema ini sampai Anda mendistribusikan semua kaus kaki ke tumpukan yang sangat kecil yang dapat Anda proses secara visual dengan segera

Jenis partisi hash rekursif ini sebenarnya sedang dilakukan oleh SQL Server ketika perlu hash bergabung atau agregat hash atas set data besar. Ini mendistribusikan aliran input membangun ke banyak partisi yang independen. Skema ini skala ke sejumlah data acak dan beberapa CPU secara linear.

Anda tidak perlu partisi rekursif jika Anda dapat menemukan kunci distribusi (kunci hash) itu menyediakan cukup banyak ember bahwa setiap ember cukup kecil untuk diproses dengan sangat cepat. Sayangnya, saya tidak berpikir kaus kaki memiliki properti seperti itu.

Jika setiap kaos kaki memiliki bilangan bulat yang disebut "PairID", seseorang dapat dengan mudah mendistribusikannya ke dalam 10 ember sesuai PairID % 10 (digit terakhir).

Partisi dunia nyata terbaik yang dapat saya pikirkan adalah menciptakan a persegi panjang tumpukan: satu dimensi berwarna, yang lain adalah pola. Mengapa sebuah persegi panjang? Karena kita membutuhkan O (1) akses acak ke tumpukan. (A 3D berbentuk kubus juga akan berhasil, tetapi itu tidak terlalu praktis.)


Memperbarui:

Bagaimana dengan paralelisme? Bisakah banyak manusia mencocokkan kaos kaki lebih cepat?

  1. Strategi paralelisasi yang paling sederhana adalah memiliki beberapa pekerja mengambil dari keranjang input dan meletakkan kaus kaki ke tumpukan. Ini hanya skala begitu banyak - bayangkan 100 orang bertempur lebih dari 10 tumpukan. Biaya sinkronisasi (Mewujudkan diri mereka sebagai tabrakan tangan dan komunikasi manusia) menghancurkan efisiensi dan mempercepat (lihat UU Skalabilitas Universal!). Apakah ini rentan kebuntuan? Tidak, karena setiap pekerja hanya perlu mengakses satu tumpukan pada satu waktu. Hanya dengan satu "kunci" tidak mungkin ada jalan buntu. Livelocks mungkin dimungkinkan tergantung pada bagaimana manusia mengoordinasikan akses ke tumpukan. Mereka mungkin hanya menggunakannya backoff acak seperti kartu jaringan melakukan itu pada tingkat fisik untuk menentukan kartu apa yang dapat secara eksklusif mengakses kabel jaringan. Jika berhasil NIC, itu harus bekerja untuk manusia juga.
  2. Itu skala hampir tanpa batas jika setiap pekerja memiliki tumpukan tumpukannya sendiri. Pekerja kemudian dapat mengambil potongan besar kaus kaki dari keranjang input (sangat sedikit pertengkaran karena mereka jarang melakukannya) dan mereka tidak perlu melakukan sinkronisasi ketika mendistribusikan kaos kaki sama sekali (karena mereka memiliki tumpukan benang-lokal). Pada akhirnya, semua pekerja harus menyatukan tumpukan mereka. Saya percaya itu bisa dilakukan di O (log (jumlah pekerja * tumpukan per pekerja)) jika pekerja membentuk pohon agregasi.

Bagaimana tentang masalah perbedaan elemen? Sebagaimana dinyatakan artikel, masalah perbedaan elemen dapat dipecahkan O(N). Ini sama untuk masalah kaus kaki (juga O(N), jika Anda hanya memerlukan satu langkah distribusi (saya mengusulkan beberapa langkah hanya karena manusia buruk dalam perhitungan - satu langkah sudah cukup jika Anda mendistribusikannya md5(color, length, pattern, ...), yaitu a hash sempurna dari semua atribut)).

Jelas, seseorang tidak bisa pergi lebih cepat daripada O(N), jadi kami telah mencapai batas bawah yang optimal.

Meskipun output tidak persis sama (dalam satu kasus, hanya boolean. Dalam kasus lain, pasangan kaus kaki), kompleksitas asimtotik adalah sama.


2176
2017-10-19 20:47



Karena arsitektur otak manusia sama sekali berbeda dengan CPU modern, pertanyaan ini tidak masuk akal.

Manusia dapat memenangkan algoritma CPU menggunakan fakta bahwa "menemukan pasangan yang cocok" dapat menjadi satu operasi untuk satu set yang tidak terlalu besar.

Algoritme saya:

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

Setidaknya inilah yang saya gunakan dalam kehidupan nyata, dan saya merasa sangat efisien. Kelemahannya adalah membutuhkan permukaan yang datar, tetapi biasanya berlimpah.


522
2018-05-27 19:13



Kasus 1: Semua kaus kaki identik (inilah yang saya lakukan dalam kehidupan nyata dengan cara).

Pilih dua dari mereka untuk membuat pasangan. Waktu yang konstan.

Kasus 2: Ada sejumlah kombinasi konstan (kepemilikan, warna, ukuran, tekstur, dll.).

Menggunakan semacam radix. Ini hanya waktu linear karena perbandingan tidak diperlukan.

Kasus 3: Jumlah kombinasi tidak diketahui sebelumnya (kasus umum).

Kami harus melakukan perbandingan untuk memeriksa apakah dua kaus kaki datang berpasangan. Pilih salah satu dari O(n log n) algoritma pemilahan berbasis perbandingan.

Namun dalam kehidupan nyata ketika jumlah kaus kaki relatif kecil (konstan), algoritma yang secara teoritis optimal ini tidak akan berfungsi dengan baik. Mungkin butuh lebih banyak waktu daripada pencarian berurutan, yang secara teoritis membutuhkan waktu kuadratis.


231



Jawaban non-algoritmik, namun "efisien" ketika saya melakukannya:

  • Langkah 1) buang semua kaus kaki Anda yang ada

  • langkah 2) pergi ke Walmart dan membelinya dengan paket paket 10 - n paket putih dan m hitam. Tidak perlu warna lain dalam kehidupan sehari-hari kehidupan.

Namun berkali-kali, saya harus melakukan ini lagi (kehilangan kaus kaki, kaus kaki rusak, dll.), Dan saya benci untuk membuang kaus kaki yang terlalu baik terlalu sering (dan saya berharap mereka terus menjual referensi kaus kaki yang sama!), Jadi saya baru-baru ini mengambil pendekatan yang berbeda.

Jawaban algoritme:

Pertimbangkan daripada jika Anda hanya menggambar satu kaus kaki untuk tumpukan kedua kaus kaki, seperti yang Anda lakukan, peluang Anda untuk menemukan kaus kaki yang cocok dalam pencarian yang naif cukup rendah.

  • Jadi ambil lima dari mereka secara acak, dan hafalkan bentuk atau panjangnya.

Kenapa lima? Biasanya manusia baik mengingat antara lima dan tujuh elemen yang berbeda dalam memori kerja - sedikit mirip dengan manusia RPN stack - lima adalah default yang aman.

  • Ambil satu dari tumpukan 2n-5.

  • Sekarang cari kecocokan (pencocokan pola visual - manusia pandai dengan tumpukan kecil) di dalam lima yang Anda gambar, jika Anda tidak menemukannya, maka tambahkan ke lima Anda.

  • Simpan kaus kaki secara acak dari tumpukan dan bandingkan dengan kaus kaki 5 + 1 Anda untuk sebuah pertandingan. Ketika tumpukan Anda tumbuh, itu akan mengurangi kinerja Anda tetapi meningkatkan peluang Anda. Lebih cepat.

Jangan ragu untuk menuliskan rumus untuk menghitung berapa banyak sampel yang harus Anda gambar untuk kemungkinan 50% dari suatu pertandingan. IIRC itu adalah hukum hipergeometrik.

Saya melakukannya setiap pagi dan jarang membutuhkan lebih dari tiga kali imbang - tetapi saya memilikinya n pasangan yang sama (sekitar 10, memberi atau mengambil yang hilang) dari m kaus kaki putih berbentuk. Sekarang Anda dapat memperkirakan ukuran tumpukan saham saya :-)

BTWSaya menemukan bahwa jumlah biaya transaksi untuk menyortir semua kaus kaki setiap kali saya membutuhkan sepasang mata uang jauh lebih sedikit daripada melakukannya sekali dan mengikat kaus kaki. Just-in-time bekerja lebih baik karena Anda tidak perlu mengikat kaos kaki, dan ada juga marginal return yang berkurang (yaitu, Anda terus mencari dua atau tiga kaus kaki itu ketika di suatu tempat di laundry dan yang Anda butuhkan untuk menyelesaikan pencocokan kaus kaki Anda dan Anda kehilangan waktu untuk itu).


144



Apa yang saya lakukan adalah saya mengambil kaus kaki pertama dan meletakkannya (misalnya, di tepi mangkuk cucian). Lalu saya mengambil kaus kaki lain dan memeriksa untuk melihat apakah itu sama dengan kaus kaki pertama. Jika ya, saya menghapus keduanya. Jika tidak, saya meletakkannya di sebelah kaus kaki pertama. Lalu saya mengambil kaus kaki ketiga dan membandingkannya dengan dua yang pertama (jika masih ada). Dan lain-lain

Pendekatan ini dapat dengan mudah diimplementasikan dalam sebuah array, dengan asumsi bahwa "menghapus" kaus kaki adalah sebuah opsi. Sebenarnya, Anda bahkan tidak perlu "melepas" kaus kaki. Jika Anda tidak perlu memilah-milah kaus kaki (lihat di bawah), maka Anda bisa memindahkannya dan berakhir dengan array yang memiliki semua kaus kaki diatur berpasangan dalam array.

Dengan asumsi bahwa operasi hanya untuk kaus kaki adalah untuk membandingkan kesetaraan, algoritma ini pada dasarnya masih merupakan n2 algoritma, meskipun saya tidak tahu tentang kasus rata-rata (tidak pernah belajar untuk menghitungnya).

Menyortir, tentu saja meningkatkan efisiensi, terutama dalam kehidupan nyata di mana Anda dapat dengan mudah "memasukkan" kaus kaki antara dua kaus kaki lainnya. Dalam komputasi, hal yang sama dapat dicapai oleh sebuah pohon, tetapi itu adalah ruang ekstra. Dan, tentu saja, kita kembali di NlogN (atau sedikit lebih, jika ada beberapa kaus kaki yang sama dengan kriteria penyortiran, tetapi tidak dari pasangan yang sama).

Selain itu, saya tidak bisa memikirkan apa pun, tetapi metode ini tampaknya cukup efisien dalam kehidupan nyata. :)


92



Ini menanyakan pertanyaan yang salah. Pertanyaan yang tepat untuk ditanyakan adalah, mengapa saya menghabiskan waktu menyortir kaus kaki? Berapa biaya per tahun, ketika Anda menghargai waktu luang Anda untuk unit moneter X pilihan Anda?

Dan lebih sering daripada tidak, ini bukan hanya apa saja waktu luang, itu pagi waktu luang, yang dapat Anda habiskan di tempat tidur, atau menghirup kopi Anda, atau meninggalkan sedikit lebih awal dan tidak terjebak dalam lalu lintas.

Sering kali baik untuk mundur selangkah, dan memikirkan jalan keluar dari masalah.

Dan ada jalan!

Temukan kaus kaki yang Anda suka. Perhatikan semua fitur yang relevan: warna dalam kondisi pencahayaan yang berbeda, kualitas dan daya tahan secara keseluruhan, kenyamanan dalam berbagai kondisi iklim, dan penyerapan bau. Yang juga penting adalah, mereka tidak boleh kehilangan elastisitas dalam penyimpanan, jadi kain alami itu bagus, dan mereka harus tersedia dalam pembungkus plastik.

Lebih baik jika tidak ada perbedaan antara kaus kaki kiri dan kanan, tetapi itu tidak penting. Jika kaus kaki kiri-kanan simetris, menemukan sepasang adalah O (1) operasi, dan menyortir kaos kaki adalah perkiraan operasi O (M), di mana M adalah jumlah tempat di rumah Anda, yang telah dikotori dengan kaus kaki, idealnya beberapa angka konstan kecil.

Jika Anda memilih pasangan yang mewah dengan kaus kaki kiri dan kanan yang berbeda, lakukan semacam ember penuh ke ember kaki kiri dan kanan, ambil O (N + M), di mana N adalah jumlah kaus kaki dan M sama seperti di atas. Orang lain dapat memberikan rumus untuk iterasi rata-rata untuk menemukan pasangan pertama, tetapi kasus terburuk untuk menemukan pasangan dengan pencarian buta adalah N / 2 + 1, yang menjadi kasus yang tidak mungkin secara astronomi untuk N. wajar. Hal ini dapat dipercepat dengan menggunakan gambar lanjutan algoritme pengenalan dan heuristik, saat memindai tumpukan kaus kaki yang disortir Mk1 Eyeball.

Jadi, algoritma untuk mencapai O (1) efisiensi pemasangan pasangan (dengan asumsi kaus kaki simetris) adalah:

  1. Anda perlu memperkirakan berapa banyak kaus kaki yang akan Anda butuhkan selama sisa hidup Anda, atau mungkin sampai Anda pensiun dan pindah ke iklim yang lebih hangat tanpa perlu memakai kaus kaki lagi. Jika Anda muda, Anda juga dapat memperkirakan berapa lama sebelum kita semua memiliki robot penyortir kaus kaki di rumah kita, dan seluruh masalah menjadi tidak relevan.

  2. Anda perlu mencari tahu bagaimana Anda dapat memesan kaus kaki pilihan Anda dalam jumlah besar, dan berapa biayanya, dan apa yang mereka berikan.

  3. Pesan kaus kaki!

  4. Singkirkan kaus kaki lama Anda.

Sebuah langkah alternatif 3 akan melibatkan membandingkan biaya membeli jumlah yang sama dari kaus kaki yang lebih murah mungkin beberapa pasang pada suatu waktu selama bertahun-tahun dan menambahkan biaya menyortir kaus kaki, tetapi mengambil kata saya untuk itu: membeli dalam jumlah besar lebih murah! Juga, kaus kaki dalam penyimpanan meningkat nilainya pada tingkat inflasi harga saham, yang lebih dari yang akan Anda dapatkan dari banyak investasi. Kemudian lagi ada juga biaya penyimpanan, tetapi kaus kaki benar-benar tidak memakan banyak ruang di rak atas lemari.

Masalah dipecahkan. Jadi, dapatkan kaus kaki baru, buang / sumbangkan yang lama, dan hidup bahagia setelah mengetahui Anda menghemat uang dan waktu setiap hari selama sisa hidup Anda.


50



Batas teoritis adalah O (n) karena Anda perlu menyentuh setiap kaus kaki (kecuali beberapa sudah dipasangkan entah bagaimana).

Anda dapat mencapai O (n) dengan semacam radix. Anda hanya perlu memilih beberapa atribut untuk bucket.

  1. Pertama Anda dapat memilih (miliknya, milikku) - membaginya menjadi 2 tumpukan,
  2. kemudian gunakan warna (dapat memiliki urutan apa pun untuk warna, misalnya menurut abjad dengan nama warna) - bagi mereka menjadi warna demi tumpukan (ingat untuk menjaga urutan awal dari langkah 1 untuk semua kaus kaki di tumpukan yang sama),
  3. lalu panjang kaus kaki,
  4. lalu tekstur, ....

Jika Anda dapat memilih jumlah atribut yang terbatas, tetapi cukup atribut yang dapat mengidentifikasi setiap pasangan secara unik, Anda harus melakukannya dalam O (k * n), yang O (n) jika kita dapat menganggap k terbatas.


47



Sebagai solusi praktis:

  1. Cepat membuat tumpukan kaus kaki yang mudah dibedakan. (Ucapkan berdasarkan warna)
  2. Quicksort setiap tumpukan dan gunakan panjang kaus kaki untuk perbandingan. Sebagai manusia Anda dapat membuat keputusan yang cukup cepat yang digunakan untuk partisi yang menghindari kasus terburuk. (Anda dapat melihat beberapa kaus kaki secara paralel, gunakan itu untuk keuntungan Anda!)
  3. Berhenti menyortir tumpukan ketika mereka mencapai ambang di mana Anda merasa nyaman untuk menemukan pasangan tempat dan kaus kaki yang tidak berpasangan secara instan

Jika Anda memiliki 1000 kaus kaki, dengan 8 warna dan distribusi rata-rata, Anda dapat membuat 4 tumpukan dari setiap 125 kaus kaki dalam waktu c * n. Dengan ambang 5 kaus kaki, Anda dapat mengurutkan setiap tumpukan dalam 6 lintasan. (Menghitung 2 detik untuk melempar kaus kaki di tumpukan kanan, Anda akan membutuhkan sedikit di bawah 4 jam.)

Jika Anda hanya memiliki 60 kaus kaki, 3 warna dan 2 jenis kaus kaki (milik Anda / istri Anda), Anda dapat mengurutkan setiap tumpukan 10 kaus kaki dalam 1 kali (Sekali lagi ambang = 5). (Menghitung 2 detik, Anda membutuhkan waktu 2 menit).

Penyortiran bucket awal akan mempercepat proses Anda, karena membagi n kaus kaki Anda ke dalam k ember c*n waktu daripada yang harus Anda lakukan c*n*log(k) kerja. (Tidak memperhitungkan ambang batas). Jadi semua yang Anda lakukan n*c*(1 + log(k)) bekerja, di mana c adalah waktu untuk melempar kaus kaki di atas tumpukan.

Pendekatan ini akan menguntungkan dibandingkan dengan apa pun c*x*n + O(1) metode kira-kira selama log(k) < x - 1.


Dalam ilmu komputer, ini dapat membantu: Kami memiliki koleksi n sesuatu, urutan pada mereka (panjang) dan juga hubungan kesetaraan (informasi tambahan, misalnya warna kaus kaki). Hubungan kesetaraan memungkinkan kita untuk membuat partisi dari koleksi asli, dan di setiap kelas kesetaraan pesanan kami masih dipertahankan. Pemetaan a benda untuk itu kelas kesetaraan dapat dilakukan dalam O (1), sehingga hanya O (n) diperlukan untuk menetapkan setiap item ke kelas. Sekarang kami telah menggunakan informasi tambahan kami dan dapat melanjutkan dengan cara apa pun untuk mengurutkan setiap kelas. Keuntungannya adalah bahwa set data sudah jauh lebih kecil.

Metode ini juga dapat diulang, jika kita memiliki beberapa hubungan kesetaraan -> membuat tumpukan warna, daripada dalam setiap partisi tumpukan pada tekstur, daripada mengurutkan panjangnya. Setiap relasi ekuivalensi yang menciptakan partisi dengan lebih dari 2 elemen yang memiliki ukuran hampir sama akan membawa peningkatan kecepatan daripada penyortiran (asalkan kita dapat langsung menetapkan kaus kaki ke tumpukannya), dan pemilahan dapat terjadi dengan sangat cepat pada kumpulan data yang lebih kecil.


31



Pertanyaan ini sebenarnya sangat filosofis. Pada intinya adalah apakah kekuatan orang untuk memecahkan masalah ("wetware" dari otak kita) setara dengan apa yang dapat dicapai oleh algoritma.

Algoritma yang jelas untuk menyortir kaus kaki adalah:

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

Sekarang ilmu komputer dalam masalah ini adalah tentang langkah-langkahnya

  1. "jika ada pasangan dengan t kaus kaki di N". Seberapa cepat kita dapat "mengingat" apa yang telah kita lihat sejauh ini?
  2. "hapus t dari N" dan "tambahkan s ke N". Seberapa mahal melacak apa yang telah kita lihat sejauh ini?

Manusia akan menggunakan berbagai strategi untuk mempengaruhi ini. Ingatan manusia aku s asosiatif, sesuatu seperti tabel hash di mana set fitur dari nilai yang disimpan dipasangkan dengan nilai yang sesuai itu sendiri. Misalnya, konsep peta "mobil merah" untuk semua mobil merah yang mampu diingat oleh seseorang. Seseorang dengan ingatan sempurna memiliki pemetaan yang sempurna. Kebanyakan orang tidak sempurna dalam hal ini (dan sebagian besar lainnya). Peta asosiatif memiliki kapasitas terbatas. Pemetaan mungkin bleep keluar dari keberadaan dalam berbagai keadaan (satu bir terlalu banyak), dicatat dalam kesalahan ("Saya meskipun namanya Betty, bukan Nettie"), atau tidak pernah ditimpa meskipun kita mengamati bahwa kebenaran telah berubah ("mobil ayah" membangkitkan "oranye Firebird" ketika kita benar-benar tahu dia akan menukarkannya dengan Camaro merah).

Dalam hal kaos kaki, ingatan sempurna berarti melihat kaus kaki s selalu menghasilkan memori saudara kandungnya t, termasuk informasi yang cukup (di mana itu di papan setrika) untuk mencari t dalam waktu yang konstan. Seseorang dengan memori fotografi menyelesaikan 1 dan 2 secara konstan tanpa gagal.

Seseorang dengan memori kurang sempurna mungkin menggunakan beberapa kelas kesetaraan masuk akal berdasarkan fitur dalam kemampuannya untuk melacak: ukuran (papa, mama, bayi), warna (hijau, merah, dll), pola (argyle, polos, dll.) , gaya (footie, setinggi lutut, dll.). Jadi papan setrika akan dibagi menjadi beberapa bagian untuk kategori. Ini biasanya memungkinkan kategori ditempatkan dalam waktu yang konstan oleh memori, tetapi kemudian pencarian linear melalui kategori "bucket" diperlukan.

Seseorang yang tidak memiliki memori atau imajinasi sama sekali (maaf) hanya akan menyimpan kaus kaki dalam satu tumpukan dan melakukan pencarian linear dari seluruh tumpukan.

Orang aneh yang rapi mungkin menggunakan label numerik untuk pasangan seperti yang disarankan seseorang. Ini membuka pintu untuk pemesanan total, yang memungkinkan manusia untuk menggunakan algoritma yang sama persis dengan CPU: pencarian biner, pohon, hash, dll.

Jadi, algoritme "terbaik" bergantung pada kualitas perangkat basah / perangkat keras / perangkat lunak yang menjalankannya dan kesediaan kita untuk "menipu" dengan menerapkan total pesanan pada pasangan. Tentu saja "terbaik" meta-algorithm adalah untuk menyewa penyortir kaus kaki terbaik di dunia: seseorang atau mesin yang dapat memperoleh dan dengan cepat menyimpan set atribut N besar kaus kaki dalam memori asosiatif 1-1 dengan pencarian waktu yang konstan, masukkan, dan hapus. Baik orang maupun mesin seperti ini bisa dibeli. Jika Anda memilikinya, Anda dapat memasangkan semua kaus kaki dalam waktu O (N) untuk pasangan N, yang optimal. Total tag pesanan memungkinkan Anda menggunakan hashing standar untuk mendapatkan hasil yang sama dengan komputer manusia atau perangkat keras.


25



Anda mencoba memecahkan masalah yang salah.

Solusi 1: Setiap kali Anda menaruh kaus kaki kotor di keranjang cucian Anda, ikat dengan simpul kecil. Dengan begitu Anda tidak perlu melakukan pemilahan setelah mencuci. Anggap saja seperti mendaftarkan indeks dalam basis data Mongo. Sedikit kerja di depan untuk beberapa penghematan CPU di masa depan.

Solusi 2: Jika musim dingin, Anda tidak harus memakai kaus kaki yang cocok. Kami adalah programmer. Tidak ada yang perlu tahu, selama itu berhasil.

Solusi 3: Sebarkan pekerjaan. Anda ingin melakukan proses CPU yang rumit secara asynchronous, tanpa memblokir UI. Ambil tumpukan kaus itu dan masukkan ke dalam tas. Hanya mencari pasangan saat Anda membutuhkannya. Dengan cara itu, jumlah pekerjaan yang dibutuhkan tidak terlalu terlihat.

Semoga ini membantu!


23