Fungsi dijamin tidak akan pernah mengembalikan nilai yang sama dua kali [ditutup]

Ini adalah pertanyaan yang saya tanyakan pada wawancara kerja, dan saya tidak dapat menemukan jawaban yang mereka cari, jadi saya berharap seseorang di sini mungkin memiliki beberapa ide. Tujuannya adalah untuk menulis fungsi yang dijamin tidak akan pernah mengembalikan nilai yang sama dua kali. Asumsikan bahwa fungsi ini akan diakses oleh beberapa mesin secara bersamaan.

Ide saya adalah untuk memberikan setiap mesin id unik dan meneruskan nilai itu ke fungsi pembuat nilai unik:

var i = 0;
function uniq(process_id, machine_id) {
   return (i += 1).toString() + machine_id + "-" + process_id;
}

Ini akan menghindari kejatuhan dari kondisi balapan karena bahkan jika dua proses atau lebih membaca nilai yang sama i, setiap nilai kembali ditandai kombinasi unik id proses dan id mesin. Namun, pewawancara saya tidak suka jawaban ini karena membawa mesin lain secara online melibatkan menetapkannya sebagai id.

Jadi adakah yang bisa memikirkan cara lain untuk menyelesaikan ini yang tidak melibatkan mengkonfigurasi setiap mesin untuk memiliki id yang unik? Saya ingin mendapat jawaban kalau-kalau pertanyaan ini muncul lagi. Terima kasih.

Jangan suka, cukup lempar penghitung sederhana (threadsafe) di balik titik akhir komunikasi (WCF, layanan web, apa pun):

   long x = long.MinValue;
   public long ID(){
       return Interlocked.Increment(ref x);
   }

Ya, pada akhirnya akan meluap. Ya, itu tidak menangani reboot. Ya, itu tidak acak. Ya, seseorang dapat menjalankan ini di beberapa server.

Ini adalah hal paling sederhana yang memenuhi persyaratan praktis. Lalu biarkan mereka menjadi orang-orang yang menindaklanjuti masalah-masalah itu (untuk memastikan mereka memahami keterbatasan, apakah mereka benar - benar berpikir Anda membutuhkan lebih dari 2 ^ 64 id), sehingga Anda kemudian dapat bertanya tentang trade-off apa yang baik-baik saja. Apakah itu perlu selamat dari reboot? Bagaimana dengan kegagalan hard drive? Bagaimana dengan perang nuklir? Apakah perlu acak? Seberapa acak?

Jika saya ditanya pertanyaan itu, dan mereka menjelaskan bahwa itu harus unik di reboot dan di mesin yang berbeda, saya akan memberi mereka fungsi yang memanggil mekanisme standar untuk membuat GUID baru, apa pun yang terjadi di bahasa yang digunakan.

Pewawancara mengatakan metode ini akan dipanggil bersamaan, bukan paralel; cukup kembalikan tanggal / waktu ke tempat desimal sebanyak yang Anda bisa.

Mengapa semua orang terlalu memikirkan ini? Anda akan mati lama sebelum keterbatasan dikeluarkan dan Anda tidak memiliki peluang tabrakan.

Jika Anda khawatir hal itu mengembalikan waktu yang sama, tambahkan penundaan untuk jumlah waktu terkecil yang dapat diukur.

Jika Anda khawatir tentang mengatur mundur jam untuk waktu musim panas (mengalami 1 kali dua kali), tambahkan konstanta pada waktu kedua kalinya Anda mengalaminya.

Pertama, Anda ingin menanyakan dua pertanyaan kepada pewawancara.

Pertanyaan 1.

apakah pewawancara mengharapkan satu atau lebih "mesin pusat" yang akan digunakan untuk menetapkan beberapa nomor unik, atau blok nomor unik.

Pertanyaan 2.

Apakah pewawancara mengharapkan mekanisme untuk mendeteksi tabrakan, atau sebaliknya menerima risiko yang dihitung dari kemungkinan tabrakan yang sangat kecil tanpa secara eksplisit mendeteksi mereka.

Ada juga pendekatan pertahanan-mendalam, di mana seseorang memasukkan beberapa bagian ID pengguna ke dalam keacakan (dengan demikian, tidak sepenuhnya acak). Karena itu kemungkinan pengguna yang sama mengalami tabrakan di dalam konten yang dibuat oleh pengguna yang sama itu diturunkan.

Ada pertanyaan tersirat 3, ...

Tetapi Anda harus mengukur diri sendiri tanpa bertanya, karena sangat tidak sopan untuk bertanya kepada pewawancara Anda.

Apakah pewawancara mengasumsikan pengetahuan tentang probabilitas, risiko, dan beberapa teknik sederhana yang digunakan dalam sistem kriptografi dan keamanan informasi.

Jenis pengetahuan pertama memastikan Anda tidak berusaha meyakinkan orang yang tidak ilmiah untuk menerima konsep ilmiah yang tidak akan mereka terima.

Jenis pengetahuan kedua memastikan bahwa Anda mengatasi masalah yang selain kemungkinan belaka. Dengan kata lain, cara mempertahankan diri dari "penyerang" yang ingin secara sengaja merusak skema pengacakan Anda, dengan memanipulasi mesin (s) atau host virtual mereka untuk memaksa dua mesin untuk menghasilkan nilai yang sama.

Kenapa bertanya.

Alasannya adalah bahwa jika pewawancara mengharapkannya dengan satu atau lain cara, mencoba menjawab dengan pendekatan yang berlawanan tidak akan pernah membuat pewawancara bahagia.

Alasan yang lebih dalam adalah bahwa beberapa orang tidak menyukai gagasan mengatakan, 1.0e-20peluang untuk gagal. (Saya akan mencoba untuk tidak mengemukakan argumen filosofis atau agama di sini.)

Pertama-tama "namespace" angka acak dibuat menjadi hierarki, dengan jumlah bit tertentu dialokasikan ke satu sumber pengacakan, dan jumlah bit lainnya dialokasikan untuk beberapa cara lain, dll.

Pendekatan terpusat bergantung pada beberapa otoritas pusat untuk secara unik menetapkan bit tingkat pertama. Kemudian, mesin lain dapat mengisi sisa bit.

Ada beberapa pendekatan desentralisasi:

• Hanya menghasilkan angka acak sebaik yang bisa dilakukan, dan menerima peluang praktis nol untuk gagal dibenarkan oleh perhitungan.
• Gunakan cara kriptografi menghasilkan nilai acak dari sumber deterministik, katakanlah, nilai yang bertambah.

Jadi, mengingat bahwa ini adalah pertanyaan wawancara dan bukan skenario kehidupan nyata yang sebenarnya, saya percaya pendekatan yang benar (dan mungkin apa yang pewawancara cari) adalah mengajukan pertanyaan klarifikasi, atau menulis "Tidak bisa dilakukan "dan terus maju. Inilah sebabnya.

Apa yang Pewawancara Bertanya:

Tulis fungsi yang dijamin tidak akan pernah mengembalikan nilai yang sama dua kali. Asumsikan bahwa fungsi ini akan diakses oleh beberapa mesin secara bersamaan.

Apa yang Dibutuhkan Pewawancara:

Apakah kandidat ini secara efektif mengevaluasi persyaratan dan mencari input tambahan saat diminta?

Jangan pernah berasumsi.

Ketika seorang insinyur diberikan persyaratan (melalui SOW atau Spesifikasi atau dokumen persyaratan lainnya), beberapa sudah jelas, dan yang lain sama sekali tidak jelas. Ini adalah contoh sempurna dari yang terakhir. Seperti yang ditunjukkan oleh jawaban sebelumnya, tidak ada cara untuk menanggapi persyaratan ini tanpa membuat beberapa asumsi utama baik (a) mengenai sifat pertanyaan atau (b) seperti sifat sistem, karena persyaratan tidak dapat dipenuhi seperti yang tertulis (tidak mungkin).

Sebagian besar jawaban membuat satu upaya atau yang lain dalam memecahkan masalah melalui serangkaian asumsi. Seseorang secara khusus merekomendasikan untuk menyelesaikannya dengan cepat dan membiarkan pelanggan khawatir tentang hal itu jika itu salah.

Ini benar-benar pendekatan yang buruk. Sebagai pelanggan, jika saya memberikan persyaratan yang tidak jelas, dan insinyur pergi dan membuat saya solusi yang tidak berhasil, saya akan marah karena mereka pergi bekerja dan menghabiskan uang saya tanpa repot-repot bertanya kepada saya terlebih dahulu. Pengambilan keputusan yang berani seperti itu menunjukkan kurangnya kerja tim, ketidakmampuan untuk berpikir kritis, dan penilaian yang buruk. Ini dapat mengarah pada segala bentuk konsekuensi negatif, termasuk hilangnya nyawa dalam sistem kritis keselamatan.

Mengapa Mengajukan Pertanyaan?

Intinya jika latihan ini mahal dan menghabiskan waktu untuk membangun persyaratan yang ambigu. Dalam kasus OP, Anda telah diberi tugas yang mustahil. Tindakan pertama Anda harus meminta klarifikasi - apa yang diperlukan? Tingkat keunikan apa yang dibutuhkan? Apa yang terjadi jika suatu nilai tidak unik? Jawaban atas pertanyaan-pertanyaan ini dapat berupa perbedaan antara beberapa minggu waktu dan beberapa menit. Di dunia nyata, salah satu pendorong terbesar biaya dalam sistem yang kompleks (termasuk banyak sistem perangkat lunak) adalah persyaratan yang tidak jelas dan kurang dipahami. Hal ini menyebabkan bug yang mahal dan memakan waktu, desain ulang, frustrasi pelanggan dan tim, dan memalukan liputan media jika proyek tersebut cukup besar.

Apa Yang Terjadi Ketika Anda Menganggap?

Mengingat latar belakang saya di industri kedirgantaraan, dan karena sifat kegagalan kedirgantaraan yang sangat terlihat, saya ingin memunculkan contoh dari domain ini untuk menggambarkan poin-poin penting. Mari kita periksa sepasang misi Mars yang gagal - Mars Climate Orbiter dan Mars Polar Lander. Kedua misi gagal karena masalah perangkat lunak - karena insinyur membuat asumsi yang tidak valid, sebagian, karena persyaratan yang tidak jelas dan kurang dikomunikasikan.

Mars Climate Orbiter - kasus ini biasanya dikutip sebagai apa yang terjadi ketika NASA mencoba mengkonversi bahasa Inggris ke satuan Metrik. Namun, itu adalah representasi yang terlalu sederhana dan buruk dari apa yang sebenarnya terjadi. Benar, ada masalah konversi, tetapi itu karena persyaratan komunikasi yang buruk di tahap desain dan skema verifikasi / validasi yang tidak tepat. Lebih lanjut, ketika dua insinyur berbeda memperhatikan masalah ini karena jelas dari data lintasan penerbangan, mereka tidak mengangkat masalah ke tingkat yang tepat karena mereka menganggap itu adalah kesalahan transmisi. Seandainya tim ops misi disadarkan akan masalah ini, ada cukup waktu untuk memperbaikinya dan menyelamatkan misi. Dalam hal ini, ada kondisi logis yang mustahil yang tidak dikenali apa adanya, yang menyebabkan kegagalan misi yang mahal.

Mars Polar Lander- kasus ini sedikit kurang terkenal, tetapi mungkin lebih memalukan karena kedekatan temporal dengan kegagalan Mars Climate Orbiter. Dalam misi ini, peranti lunak itu mengendalikan pendaratan roket ke permukaan Mars. Pada titik 40 meter di atas permukaan, kaki pendarat dikerahkan untuk persiapan pendaratan. Ada juga sensor pada kaki yang mendeteksi gerakan (untuk memberi sinyal ketika mereka berdampak) untuk memberitahu perangkat lunak untuk mematikan mesin. Tebakan terbaik NASA tentang apa yang terjadi (karena ada beberapa kemungkinan kegagalan dan data yang tidak lengkap) adalah bahwa getaran acak di kaki akibat penyebarannya secara bersamaan dan secara tidak tepat memicu mekanisme penutupan 40 m di atas permukaan, yang mengakibatkan tabrakan dan penghancuran $ 110 Pesawat ruang angkasa M Kemungkinan ini diangkat dalam pengembangan, tapi tidak pernah disapa. Pada akhirnya, tim perangkat lunak membuat asumsi yang tidak valid tentang bagaimana kode ini perlu dijalankan (salah satu anggapan tersebut adalah bahwa sinyal palsu akan terlalu pendek untuk diambil, meskipun tes menunjukkan sebaliknya), dan asumsi tersebut tidak pernah dipertanyakan sampai setelah faktanya.

Pertimbangan Tambahan

Mewawancarai dan mengevaluasi orang adalah bisnis yang sulit. Ada beberapa dimensi calon yang ingin dieksplorasi oleh pewawancara, tetapi salah satu yang paling penting adalah kemampuan individu untuk berpikir kritis. Karena berbagai alasan, tidak terkecuali bahwa berpikir kritis tidak didefinisikan dengan baik, kami memiliki waktu yang sangat sulit untuk mengevaluasi keterampilan berpikir kritis.

Sebagai instruktur teknik, salah satu cara favorit saya untuk mengevaluasi kemampuan siswa untuk berpikir kritis adalah dengan mengajukan pertanyaan yang agak ambigu. Siswa yang lebih tajam akan mengambil premis yang salah dari pertanyaan, mencatatnya, dan entah menjawab premis atau menolak untuk menjawab sama sekali. Biasanya, saya akan mengajukan pertanyaan yang serupa dengan yang berikut:

Anda mengambil gambar dari tumpukan pekerjaan Anda. Gambar itu berisi berbagai info yang berbeda, tetapi poin paling penting ke permukaan horizontal dan mengatakan "Sempurna datar". Permukaannya 5 "lebar 16" panjang, dan bagian terbuat dari aluminium. Bagaimana Anda akan mengolah bagian untuk membuat fitur ini?

(Ngomong-ngomong, Anda akan terkejut dengan seberapa sering spesifikasi yang buruk seperti itu muncul di tempat kerja.)

Saya berharap bahwa siswa akan mengenali bahwa tidak mungkin untuk membuat fitur yang sempurna, dan bahwa mereka akan menyatakan ini dalam jawaban mereka. Saya biasanya akan memberikan poin bonus jika mereka mengatakan akan kembali ke desainer dan meminta klarifikasi sebelum membuat bagian. Jika seorang siswa melanjutkan untuk memberi tahu saya bagaimana mereka akan mencapai .001 planaritas atau nilai-nilai lainnya, saya memberikan nol poin. Ini membantu saya menunjukkan kepada siswa saya bahwa mereka perlu memikirkan gambaran yang lebih besar.

Intinya

Jika saya mewawancarai seorang insinyur (atau profesi serupa), saya mencari seseorang yang dapat berpikir kritis dan mempertanyakan apa yang telah ditempatkan di depannya. Saya ingin seseorang yang mengajukan pertanyaan, "Apakah ini masuk akal?" .

Tidak masuk akal untuk meminta bagian yang benar-benar rata, karena tidak ada yang namanya sempurna. Tidak masuk akal untuk meminta fungsi yang tidak pernah mengembalikan nilai duplikat, karena tidak mungkin untuk membuat jaminan seperti itu. Dalam pemrograman, kita sering mendengar ungkapan "sampah masuk, sampah keluar." Jika Anda diberikan sampah untuk persyaratan, itu adalah tanggung jawab etis Anda untuk berhenti dan mengajukan pertanyaan apa pun yang membantu Anda memperoleh maksud sebenarnya. Jika saya mewawancarai seorang kandidat, dan saya memberi mereka persyaratan yang tidak jelas, saya akan mengharapkan pertanyaan klarifikasi.

Menjamin keunikan sulit karena komputer tidak memiliki variabel besar tak terhingga. Tidak ada mesin Turing dunia nyata yang bisa.

Cara saya melihatnya ada dua masalah di sini, dan keduanya memiliki solusi yang mapan.

• Konkurensi. Beberapa mesin mungkin membutuhkan nilai pada saat bersamaan. Untungnya, CPU modern memiliki built-in concurrency dan beberapa bahasa menyediakan fasilitas yang ramah pengembang untuk mengambil keuntungan dari ini.
• Keunikan. Walaupun tidak mungkin untuk menjamin keunikan, kita dapat memiliki variabel-variabel besar yang sewenang-wenang yang dapat menyimpan nilai-nilai begitu besar sehingga sistem dunia nyata akan memiliki waktu yang sangat sulit melelahkan semua nilai unik

Inilah solusi saya di Jawa:

public class Foo {
  private static BigInteger value = BigInteger.ZERO;
  private static final Lock lock = new ReentrantLock();

  public static BigInteger nextValue() {
    try {
      lock.lock();
      value = value.add(BigInteger.ONE);
      return value;
    }
    finally {
      lock.unlock();
    }
  }
}

BigInteger adalah tipe integer ukuran arbitrer. Itu dapat tumbuh untuk memegang nilai-nilai yang cukup besar, bahkan jika tidak terbatas. Kunci memastikan konkurensi, sehingga nilai yang sama tidak dapat dikembalikan dua kali oleh dua permintaan simultan yang dilayani oleh utas terpisah.

Saya akan mengekspos fungsi melalui port di server; untuk memanggil fungsi, mesin yang meminta meminta koneksi dan diberikan satu, sementara pada saat yang sama dialokasikan kode pengidentifikasi (nomor urut untuk kesederhanaan). Setiap kali pesan dikirim ke port yang meminta nilai unik, nilai dihasilkan dengan menggabungkan hash MD5 dari tanggal dan waktu saat ini dengan hash MD5 dari kode identifikasi.

Jika mereka menginginkan solusi yang lebih anti peluru, mereka harus menentukan persyaratan aktual mereka daripada menjadi tidak jelas tentang berbagai hal.

string uniq(string machine_id) 
{
   static long u = long.MinValue;
   Interlocked.Increment(ref u);

   //Time stamp with millisecond precison
   string timestamp = DateTime.UtcNow.ToString("yyyy-MM-dd HH:mm:ss.fff",
                                            CultureInfo.InvariantCulture);

   return machine_id + "-" + timestamp + "-" + u;
}

Dengan cara di atas kita dapat memastikan bahwa nilai kembali berbeda meskipun ada restart atau bahkan jika dipanggil secara bersamaan dari mesin yang berbeda.