algorithm - كيفية إقران الجوارب من كومة بكفاءة؟




sorting language-agnostic matching (25)

التكلفة: نقل الجوارب -> الجوارب العالية ، والبحث / البحث في الطابور -> صغير

ما نريد القيام به هو تقليل عدد الحركات ، والتعويض بعدد عمليات البحث. أيضا ، يمكننا الاستفادة من بيئة multithreded من Homo Sapiens لعقد المزيد من الأشياء في ذاكرة التخزين المؤقت descision.

X = لك ، Y = زوجك

من كومة من جميع الجوارب:

اختيار اثنين من الجوارب ، ووضع X سوك المقابلة في خط X ، و Y سوك في خط Y في الموقف التالي المتاح.

افعل حتى A فارغ.

لكل سطر X و Y

  1. اختر أول جورب في السطر ، ابحث على طول الخط حتى يجد الجورب المقابل.

  2. وضعت في خط الانتهاء من الجوارب المقابلة.

  3. اختياري بينما تقوم بالبحث في السطر ، والسخرية الحالية التي تبحث عنها مماثلة للسابقة السابقة ، قم بالخطوة الثانية لهذه الجوارب.

بشكل اختياري للخطوة الأولى ، يمكنك التقاط جورب من هذا الخط بدلاً من اثنين ، حيث أن ذاكرة التخزين المؤقت كبيرة بما يكفي لتحديد ما إذا كان أي من الجورب يطابق التيار الحالي على الخط الذي تراقبه. إذا كنت محظوظًا بما يكفي للحصول على ثلاثة أذرع ، فيمكنك أن تحلل ثلاث جوارب في نفس الوقت نظرًا لأن ذاكرة الموضوع كبيرة بما يكفي.

افعل حتى يصبح كل من X و Y فارغين.

فعله

ومع ذلك ، بما أن هذا يتميز بتعقيد simillar كاختيار فرز ، فإن الوقت المستغرق هو أقل بكثير بسبب سرعات I / O (نقل الجوارب) والبحث (البحث عن خط لجورب).

بالأمس كنت أقرن الجوارب من الغسيل النظيف وحسبت الطريقة التي كنت أفعلها ليست فعالة جدا. كنت أفعل بحثًا ساذجًا - اختيار جورب واحد و "تكرار" الكومة من أجل العثور على زوجها. يتطلب هذا تكرار أكثر من n / 2 * n / 4 = n 2/8 جورب في المتوسط.

بصفتي عالما في مجال الكمبيوتر ، كنت أفكر في ما يمكنني القيام به؟ وبالطبع ، جاء الفرز (حسب الحجم / اللون / ...) إلى الذهن لتحقيق حل O (NlogN).

لا يعد خيار التجزئة أو الحلول الأخرى غير الموجودة في الموقع خيارًا ، لأنني غير قادر على تكرار الجوارب الخاصة بي (على الرغم من أنه يمكن أن يكون من الجيد إذا استطعت).

لذا ، فإن السؤال هو في الأساس:

بالنظر إلى كومة من أزواج من الجوارب ، تحتوي على عناصر 2n (افترض أن كل جورب لديه زوج متطابق تمامًا) ، ما أفضل طريقة لإقرانها بكفاءة مع مساحة إضافية لوغاريتمية؟ (أعتقد أنني أستطيع تذكر ذلك الكم من المعلومات إذا لزم الأمر.)

سوف أقدر إجابة تتناول الجوانب التالية:

  • حل نظري عام لعدد ضخم من الجوارب.
  • العدد الفعلي للجوارب ليس كبيرًا ، لا أصدق زوجتي ولدي أكثر من 30 زوجًا. (ومن السهل التمييز بين جواربي وبلدي ؛ هل يمكن استخدام ذلك أيضًا؟)
  • هل هو معادلة لمشكلة عنصر مميزة ؟

ضع في اعتبارك جدول تجزئة بحجم 'N'.

إذا افترضنا التوزيع الطبيعي ، فإن العدد التقديري "للإدخال" ليكون على الأقل جوربًا واحدًا تم تعيينه إلى مجموعة واحدة هو NlogN (أي أن جميع الدلاء ممتلئة)

لقد استنتجت ذلك كجزء من لغز آخر ، ولكن سأكون سعيدًا لإثبات خطأه. هنا مقالتي بلوق على نفسه

دع 'N' تقابل الحد الأعلى التقريبي لعدد عدد الألوان / أنماط الجوارب الفريدة لديك.

بمجرد حصولك على تصادم (الملقب: مباراة) ، عليك ببساطة إزالة هذا الزوج من الجوارب. كرر نفس التجربة مع الدفعة التالية من جوارب NlogN. جمال ذلك هو أنه يمكنك جعل مقارنات متوازية NlogN (الاصطدام - قرار) بسبب الطريقة التي يعمل بها العقل البشري. :-)


من سؤالك من الواضح أنك لا تملك الكثير من الخبرة الفعلية مع الغسيل :). أنت في حاجة إلى خوارزمية تعمل بشكل جيد مع عدد صغير من الجوارب غير القابلة للجدل.

الإجابات حتى الآن لا تستفيد من قدراتنا في التعرف على الأنماط البشرية. تقدم لعبة Set فكرة عن كيفية القيام بذلك بشكل جيد: ضع كل الجوارب في مساحة ثنائية الأبعاد بحيث يمكنك التعرف عليها بشكل جيد والوصول إليها بسهولة باستخدام يديك. هذا يحد من مساحة 120 * 80 سم أو نحو ذلك. من هناك ، حدد الأزواج التي تتعرف عليها وأزلها. ضع جوارب إضافية في المساحة الحرة وكرّرها. إذا قمت بالغسيل للأشخاص الذين يعانون من الجوارب التي يسهل التعرف عليها (الأطفال الصغار يتبادرون إلى الذهن) ، فيمكنك القيام بفرز جذر عن طريق اختيار تلك الجوارب أولاً. هذه الخوارزمية تعمل بشكل جيد فقط عندما يكون عدد الجوارب المنفردة منخفضًا


هذا هو كيف تفعل ذلك في الواقع، ل ص أزواج من الجوارب ( ن = 2P الجوارب الفردية):

  • الاستيلاء على جورب عشوائيا من كومة.
  • بالنسبة للجورب الأول ، أو إذا تم إقران جميع الجوارب التي تم اختيارها مسبقًا ، ببساطة ضع الجورب في أول "فتحة" من "مجموعة" من الجوارب غير المبطنة أمامك.
  • إذا كان لديك واحد أو أكثر من الجوارب المختارة غير المحددة ، تحقق من جوربك الحالي ضد كل الجوارب المزركشة في الصفيف.
    • من الممكن فصل الجوارب إلى فصول أو أنواع عامة (أبيض / أسود ، الكاحل / الطاقم ، رياضي / لباس) عند بناء مصفوفة الخاص بك ، و "الحفر لأسفل" لمقارنة فقط مثل لمثل.
    • إذا وجدت تطابقًا مقبولًا ، ضع كل من الجوارب معًا وإزالتها من الصفيف.
    • إذا لم تقم بذلك ، ضع الجورب الحالي في الفتحة المفتوحة الأولى في الصفيف.
  • كرر مع كل جورب.

السيناريو الأسوأ من هذا المخطط هو أن كل زوج من الجوارب مختلف يكفي أنه يجب أن تكون مطابقة تماما، وأن أول ن / 2 الجوارب اخترت كلها مختلفة. هذا هو سيناريو O (n 2 ) الخاص بك ، وهو أمر مستبعد للغاية . وإذا كان عدد من الأنواع الفريدة من جورب ر أقل من عدد أزواج ص = ن / 2 ، والجوارب في كل نوع على حد سواء بما فيه الكفاية (عادة من حيث المتعلقة ارتداء) أن أي جورب من هذا النوع يمكن إرفاقها مع أي غيرها ، ثم كما استنتجت أعلاه ، فإن الحد الأقصى لعدد الجوارب التي سوف تضطر إلى مقارنة هو ر ، وبعد ذلك سوف يتم سحب واحدة بعد ذلكتطابق واحدة من الجوارب غير المربوطة. هذا السيناريو أكثر احتمالية في متوسط ​​درج الجورب من أسوأ الحالات ، ويقلل من تعقيد الحالة الأسوأ إلى O (n * t) حيث عادة t << n .


كحل عملي:

  1. بسرعة جعل أكوام من الجوارب المميزة بسهولة. (قل بالألوان)
  2. Quicksort كل كومة واستخدام طول جورب للمقارنة. بصفتك إنسانًا ، يمكنك اتخاذ قرار سريع إلى حد ما يستخدم في التقسيم لتجنب أسوأ الحالات. (يمكنك أن ترى عدة جوارب بالتوازي ، استخدم ذلك لصالحك!)
  3. التوقف عن فرز أكوام عندما وصلت إلى عتبة التي كنت مريحة للعثور على أزواج موضعية وجوارب لا يطاق على الفور

إذا كان لديك 1000 جورب ، مع 8 ألوان ومتوسط ​​التوزيع ، يمكنك عمل 4 أكوام من كل 125 جورب في وقت c * n. مع عتبة من 5 جوارب يمكنك فرز كل كومة في 6 أشواط. (بعد مرور ثانيتين على رمي جورب على الكومة اليمنى ، سيستغرق الأمر أقل من 4 ساعات).

إذا كان لديك فقط 60 جورب و 3 ألوان و 2 نوع من الجوارب (لك / زوجتك) يمكنك فرز كل كومة من 10 جورب في مرة واحدة (عتبة مرة أخرى = 5). (بعد العد 2 ثانية سوف يستغرق 2 دقيقة).

سيؤدي فرز الجرافة الأولي إلى تسريع العملية ، لأنه يقسم الجوارب الخاصة بك إلى دلاء k في وقت c*n بحيث لا يتطلب الأمر سوى عمل c*n*log(k) . (لا تأخذ بعين الاعتبار العتبة). كل ذلك في كل ما تفعله بشأن n*c*(1 + log(k)) ، حيث c هو وقت رمي ​​الجورب على كومة.

سيكون هذا الأسلوب مواتياً مقارنة بأي طريقة c*x*n + O(1) تقريباً طالما أن log(k) < x - 1 .

في علم الحاسوب ، قد يكون هذا مفيدًا: لدينا مجموعة من الأشياء n ، وترتيب عليها (الطول) وكذلك علاقة تكافؤ (معلومات إضافية ، على سبيل المثال لون الجوارب). تسمح لنا علاقة التكافؤ بعمل تقسيم للمجموعة الأصلية ، وفي كل فصل من فصول التكافؤ ، ما زال يتم الاحتفاظ بترتيبنا. يمكن إجراء تخطيط لشيء ما لفئة التكافؤ الخاصة بها في O (1) ، لذلك لا يلزم سوى O (n) لتعيين كل عنصر لفئة. الآن ، استخدمنا معلوماتنا الإضافية ويمكننا المتابعة بأي طريقة لفرز كل صف. الميزة هي أن مجموعات البيانات أصغر بالفعل.

يمكن أيضاً أن تتداخل الطريقة ، إذا كان لدينا علاقات تكافؤ متعددة -> جعل أكوام اللون ، من داخل كل قسم من قوام النسيج على النسيج ، من الفرز على الطول. إن أي علاقة تكافؤ تؤدي إلى إنشاء قسم يحتوي على أكثر من عنصرين لهما حتى حجم سيحققان تحسناً للسرعة على الفرز (بشرط أن نتمكن من تعيين جورب بشكل مباشر إلى كومة) ، ويمكن أن يحدث الفرز بسرعة كبيرة على مجموعات البيانات الأصغر.


عندما أقوم بتصنيف الجوارب ، فأنا أقوم بفرز نوع تقريبي ، أسقط الجوارب بالقرب من جوارب أخرى من نفس النوع من اللون / النمط. باستثناء في حالة ما إذا كنت أرى تطابقًا دقيقًا في / بالقرب من الموقع ، فأنا على وشك إسقاط الجورب ، فأنا أستخرج هذا الزوج عند هذه النقطة.

تقريبا جميع الخوارزميات الأخرى (بما في ذلك أعلى إجابة التسجيل بواسطة usr ) ، ثم أزِل أزواجًا. أجد أنه ، كإنسان ، من الأفضل تقليل عدد الجوارب التي يتم النظر فيها في وقت واحد.

أفعل هذا عن طريق:

  1. اختيار جورب مميز (أيا كان يمسك عيني أولا في كومة).
  2. بدء تشغيل نوع الجذر من هذا الموقع المفاهيمي عن طريق سحب الجوارب من كومة على أساس التشابه لتلك واحدة.
  3. ضع الجورب الجديد بالقرب من الكومة الحالية ، مع وجود مسافة تعتمد على مدى اختلافها. إذا وجدت نفسك تضع الجورب فوق آخر لأنه مطابق ، قم بتشكيل الزوج هناك ، وقم بإزالته. هذا يعني أن المقارنات المستقبلية تأخذ مجهودًا أقل للعثور على المكان الصحيح.

هذا يستفيد من القدرة البشرية على المبادلة غامض في وقت O (1) ، وهو ما يعادل إلى حد ما إنشاء خريطة التجزئة على جهاز الحوسبة.

من خلال سحب الجوارب المميزة أولاً ، يمكنك ترك مساحة "تكبير" في الميزات التي هي أقل تميزًا ، لتبدأ بها.

بعد القضاء على اللون الملون ، والجوارب ذات الخطوط ، والأزواج الثلاثة من الجوارب الطويلة ، قد ينتهي بك الأمر مع جوارب بيضاء في الغالب يتم فرزها حسب حجمها.

في مرحلة ما ، تكون الاختلافات بين الجوارب صغيرة بما يكفي بحيث لا يلاحظ الآخرون الفرق ، ولا يلزم أي جهد إضافي للمطابقة.


الجوارب ، سواء كانت حقيقية أو بعض بنية البيانات المماثلة ، سيتم توفيرها في أزواج.

إن أبسط إجابة هي قبل السماح بفصل الزوج ، يجب تهيئة هيكل بيانات وحيد للزوج يحتوي على مؤشر إلى الجورب الأيمن والأيسر ، مما يسمح بإحالة الجوارب مباشرة أو عبر زوجها. قد يتم أيضاً توسيع جورب لاحتواء مؤشر إلى شريكه.

هذا يحل أي مشكلة الاقتران الحسابية عن طريق إزالته مع طبقة من التجريد.

بتطبيق الفكرة نفسها على المشكلة العملية المتمثلة في إقران الجوارب ، فإن الإجابة الظاهرة هي: لا تسمح لجواربك بالانزعاج. يتم توفير الجوارب كزوج ، ووضعها في الدرج كزوج (ربما عن طريق ربطهما معاً) ، يتم ارتداؤه كزوج. لكن النقطة التي يكون فيها الإلغاء غير ممكن في الغسالة ، لذلك كل ما هو مطلوب هو آلية فيزيائية تسمح للجوارب بالبقاء معًا وغسلها بكفاءة.

هناك احتمالان ماديان:

بالنسبة إلى كائن "زوج" يحتفظ بمؤشر لكل جورب ، يمكن أن يكون لدينا كيس قماش نستخدمه للحفاظ على الجوارب. هذا يبدو مثل النفقات العامة الضخمة.

ولكن بالنسبة لكل جورب للإبقاء على إشارة إلى الآخر ، هناك حل أنيق: بوبر (أو "زر" إذا كنت أمريكيًا) ، مثل:

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

ثم كل ما عليك فعله هو أن تشق الجوارب الخاصة بك مباشرة بعد خلعها ووضعها في سلة الغسيل ، ومرة ​​أخرى قمت بإزالة مشكلة الحاجة إلى إقران الجوارب الخاصة بك مع التجريد المادي لمفهوم "الزوج".


إذا كانت عملية "النقل" مكلفة إلى حد ما ، وكانت عملية "المقارنة" رخيصة ، وتحتاج إلى نقل المجموعة بأكملها على أي حال ، إلى مخزن مؤقت حيث يكون البحث أسرع بكثير من التخزين الأصلي ... فقط دمج التصنيف في الفرض نقل.

لقد وجدت دمج عملية الفرز في المعلقة لتجف يجعلها نسيم. أنا بحاجة إلى التقاط كل جورب على أي حال ، وتعليقه (تحرك) ويكلفني شيئا عن تعليقه في مكان محدد على السلاسل. الآن فقط ليس لإجبار البحث عن المخزن المؤقت كله (السلاسل) اخترت وضع الجوارب حسب اللون / الظل. أغمق لليسار ، أكثر إشراقا لليمين ، أكثر ملونًا في الأمام وما إلى ذلك. الآن قبل أن أعلق كل جورب ، أنظر في "المنطقة المجاورة" إذا كان هناك تطابق واحد بالفعل - هذا الحد "مسح" إلى 2-3 جوارب أخرى - وإذا كان ، أعلق واحدة أخرى بجواره. ثم أقوم بتحويلها إلى أزواج أثناء إزالة الأوتار ، عندما تجف.

الآن قد لا يبدو هذا مختلفًا عن "تشكيل أكوام بالألوان" التي تقترحها الأجوبة الأعلى لكن أولاً ، بعدم اختيار أكوام منفصلة ولكن نطاقات ، ليس لدي مشكلة في تصنيف ما إذا كان "الأرجواني" يذهب إلى كومة "حمراء" أو "زرقاء". يذهب فقط بين. ومن ثم عن طريق دمج عمليتين (تعليق لتجف وفرز) ، فإن الحمل الزائد أثناء التعليق يشبه 10٪ مما سيكون عليه الفرز المنفصل.


لقد خرجت بحل آخر لا يعد بعمليات أقل ، ولا يستغرق وقتًا أقل في الاستهلاك ، ولكن يجب أن نحاول معرفة ما إذا كان يمكن أن يكون مفيدًا كافيًا لتوفير قدر أقل من استهلاك الوقت في سلسلة ضخمة من الاقتران.

الشروط المسبقة: ليس هناك ما يضمن وجود نفس الجوارب. إذا كانت من نفس اللون ، فهذا لا يعني أنها تملك نفس الحجم أو النمط. يتم خلط الجوارب عشوائيا. يمكن أن يكون هناك عدد فردي من الجوارب (بعضها مفقود ، لا نعرف عددهم). الاستعداد لتذكر متغير "فهرس" وتعيينه إلى 0.

والنتيجة سيكون لها واحدة أو مجموعتين: 1. "مطابقة" و2. "مفقود"

ارشادي:

  1. البحث عن معظم جورب مميزة.
  2. العثور على المباراة.
  3. إذا لم تكن هناك مباراة ، ضعها على كومة "مفقودة".
  4. كرر من 1. حتى لا توجد أكثر الجوارب المميزة.
  5. إذا كان هناك أقل من 6 جوارب ، انتقل إلى 11.
  6. إقران جميع الجوارب بشكل أعمى (لا تقم بحزمها)
  7. البحث عن جميع أزواج المتطابقة ، وحزمها ونقل أزواج معبأة إلى كومة "المتطابقة" ؛ إذا لم تكن هناك مطابقات جديدة - زيادة "الفهرس" بمقدار 1
  8. إذا كان "الفهرس" أكبر من 2 (يمكن أن يعتمد هذا على رقم جورب لأنه مع وجود عدد أكبر من الجوارب يكون هناك فرصة أقل لإقرانهم بشكل أعمى) انتقل إلى 11
  9. خلط الباقي
  10. انتقل إلى 1
  11. نسيت "الفهرس"
  12. اختر جورب
  13. العثور على زوجها
  14. إذا لم يكن هناك زوج للجورب ، فقم بنقله إلى كومة "مفقودة"
  15. إذا كان هناك تطابق بين الزوجين ، فقم بحزم زوجك ونقله إلى كومة "متطابقة"
  16. إذا كان لا يزال هناك أكثر من الجوارب واحدة تذهب إلى 12
  17. إذا كان هناك واحد فقط اليسار انتقل إلى 14
  18. ابتسامة راضية :)

أيضا ، يمكن أن يكون هناك شيك إضافي للجوارب التالفة أيضا ، كما لو كان إزالة تلك. يمكن إدراجها بين 2 و 3 ، وبين 13 و 14.

أتطلع إلى سماع أي تجارب أو تصحيحات.


هذا السؤال هو في الواقع فلسفي عميق. في القلب ، يتعلق الأمر بما إذا كانت قدرة الأشخاص على حل المشاكل ("الأبله الرطبة" لأدمغتنا) تعادل ما يمكن إنجازه بواسطة الخوارزميات.

الخوارزمية الواضحة لفرز الجوارب هي:

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

يدور علم الكمبيوتر الآن في هذه المشكلة حول الخطوات

  1. "إذا كانت s أزواج مع t جورب في N". ما مدى سرعة "تذكر" ما رأيناه حتى الآن؟
  2. "إزالة t من N" و "add s to N". ما مدى تكلفة تتبع ما رأيناه حتى الآن؟

سوف يستخدم البشر استراتيجيات مختلفة لتنفيذ هذه. الذاكرة البشرية هي ارتباطية ، شيء مثل جدول تجزئة حيث يتم إقران مجموعات الميزات من القيم المخزنة مع القيم المقابلة نفسها. على سبيل المثال ، يقوم مفهوم "السيارة الحمراء" بالتخطيط لكل السيارات الحمراء التي يستطيع الشخص تذكرها. يتمتع شخص ما بذاكرة مثالية بتخطيط مثالي. معظم الناس غير كامل في هذا الصدد (ومعظم الآخرين). الخريطة الترابطية لها قدرة محدودة. قد يتم نسخ التنقيط من الوجود في ظل ظروف مختلفة (بيرة واحدة أكثر من اللازم) ، يتم تسجيلها بالخطأ ("على الرغم من أن اسمها كان بيتي ، وليس Nettie") ، أو لا يمكن الكتابة فوقها على الرغم من أننا نلاحظ أن الحقيقة قد تغيرت ("أبي سيارة "تثير" البرتقالي فايربيرد "عندما كنا نعلم فعلا أنه كان يتاجر في لامارو الأحمر).

في حالة الجوارب ، يعني الاسترجاع المثالي أن النظر إلى جورب ينتج دومًا ذاكرة شقيقه ، بما في ذلك معلومات كافية (حيث توجد على لوح الكي) لتحديد موقع t في وقت ثابت. ينجز الشخص ذا الذاكرة التصويرية كل من الرقمين 1 و 2 في وقت ثابت دون الإخفاق.

قد يستخدم شخص ما لديه ذاكرة أقل من الكمال عددًا قليلاً من فصول التكافؤ المنطقي استنادًا إلى ميزات في حدود قدرته على تتبع: الحجم (بابا ، ماما ، طفل) ، لون (أخضر ، أحمر ، إلخ) ، نمط (ثقافاتنا ، عادي ، إلخ) والاسلوب (footie ، الركبة عالية ، وما إلى ذلك). لذلك سيتم تقسيم لوحة الكي إلى أقسام للفئات. ويسمح هذا عادةً بوضع الفئة في وقت ثابت حسب الذاكرة ، ولكن عندئذٍ يلزم إجراء بحث خطي عبر "مجموعة البيانات" للفئة.

شخص ما مع عدم وجود ذاكرة أو خيال على الإطلاق (آسف) سوف يحفظ فقط الجوارب في كومة واحدة ويقوم بعملية بحث خطية للكومة بأكملها.

قد يستخدم شخص غريب مهذب تسميات رقمية للأزواج كما اقترح شخص ما. وهذا يفتح الباب أمام طلب إجمالي ، والذي يسمح للإنسان باستخدام نفس الخوارزميات التي قد نستخدمها تمامًا مع وحدة المعالجة المركزية: البحث الثنائي ، والأشجار ، والتجزئات ، وما إلى ذلك.

لذا تعتمد خوارزمية "أفضل" على صفات البرامج / الأجهزة / البرمجيات الرطبة التي تقوم بتشغيلها ورغبتنا في "الغش" عن طريق فرض أمر إجمالي على أزواج. من المؤكد أن أفضل خوارزمية ميتا هي توظيف أفضل عوامات جرداء في العالم: شخص أو آلة يمكن أن تقوم بحياكة وتخزين مجموعة كبيرة من مجموعات السناكات N في الذاكرة الزوجية 1-1 مع البحث المستمر عن الوقت ، وحذف. كل من الناس والآلات مثل هذا يمكن شراؤها. إذا كان لديك واحد ، يمكنك إقران جميع الجوارب في وقت O (N) للأزواج N ، وهو الأمثل. تسمح لك علامات الترتيب الإجمالية باستخدام التجزئة القياسية للحصول على نفس النتيجة مع أي جهاز كمبيوتر أو كمبيوتر.


تم اقتراح حلول الفرز ، ولكن الفرز كثير جدًا : لا نحتاج إلى طلب ؛ نحن بحاجة فقط لمجموعات المساواة .

لذا فإن التجزئة ستكون كافية (وأسرع).

  1. لكل لون من الجوارب ، تشكل كومة . يتكرر على جميع الجوارب في سلة مدخلاتك وتوزيعها على أكوام اللون .
  2. يتكرر فوق كل كومة ويوزعها عن طريق بعض المقاييس الأخرى (على سبيل المثال النمط) في المجموعة الثانية من الأكوام
  3. قم بتطبيق هذا النظام بشكل متكرر حتى تقوم بتوزيع جميع الجوارب على أكوام صغيرة جدًا يمكنك معالجتها بشكل فوري

يتم بالفعل إجراء هذا النوع من التجزئة التجزئة العودية بواسطة SQL Server عندما يحتاج إلى تجزئة الانضمام أو تجزئة تجميع عبر مجموعات بيانات ضخمة. تقوم بتوزيع دفق إدخال البناء الخاص بها إلى العديد من الأقسام المستقلة. يتسع نطاق هذا المخطط إلى كميات عشوائية من البيانات ووحدات معالجة مركزية متعددة خطية.

لا تحتاج إلى تقسيم متكرر إذا كان بإمكانك العثور على مفتاح توزيع (مفتاح التجزئة) الذي يوفر عددًا كافيًا من الدلاء بحيث يكون كل مجموعة صغيرة بما يكفي ليتم معالجتها بسرعة كبيرة. لسوء الحظ ، لا أعتقد أن الجوارب لها مثل هذه الخاصية.

إذا كان لكل جورب عدد صحيح يسمى "PairID" ، يمكن للمرء توزيعه بسهولة في 10 دلاء وفقًا لـ PairID % 10 (الرقم الأخير).

أفضل تقسيم في العالم الحقيقي يمكنني التفكير فيه هو إنشاء مستطيل من أكوام : أحد الأبعاد هو اللون ، والآخر هو النمط. لماذا مستطيل؟ لأننا بحاجة O (1) الوصول العشوائي إلى أكوام. (سوف يعمل cuboid ثلاثي الأبعاد أيضًا ، ولكن هذا ليس عمليًا جدًا).

تحديث:

ماذا عن التوازي ؟ هل يمكن أن يتطابق البشر المتعددين مع الجوارب أسرع؟

  1. إن أبسط إستراتيجية الموازاة هي جعل العديد من العمال يأخذون من سلة المدخلات ويضعون الجوارب على الأكوام. هذا يتطور فقط إلى حد كبير - تخيل 100 شخص يقاتلون أكثر من 10 أكوام. تدمر تكاليف التزامن (التي تظهر على أنها تصادمات يدوية والتواصل البشري) الكفاءة والتسريع (انظر قانون الشمولية العالمي !). هل هذا عرضة للمأزق ؟ لا ، لأن كل عامل يحتاج فقط إلى الوصول إلى كومة واحدة في كل مرة. مع "قفل" واحد فقط لا يمكن أن يكون هناك طريق مسدود. قد تكون الأغنام ممكنة اعتمادًا على كيفية قيام البشر بتنسيق الوصول إلى الأكوام. قد يستخدمون فقط إبطاء عشوائي مثل بطاقات الشبكة على المستوى المادي لتحديد البطاقة التي يمكنها الوصول إلى سلك الشبكة بشكل خاص. إذا كان يعمل مع NICs ، يجب أن يعمل مع البشر كذلك.
  2. وهي تتسارع إلى ما لا نهاية تقريباً إذا كان لكل عامل مجموعته الخاصة من الأكوام . يمكن للعمال بعد ذلك أخذ أجزاء كبيرة من الجوارب من سلة المدخلات (تنافس ضئيل للغاية كما يفعلون ذلك نادرا) ولا يحتاجون إلى التزامن عند توزيع الجوارب على الإطلاق (لأن لديهم أكوام خيطية محلية). في النهاية ، يحتاج جميع العمال إلى اتحاد مجموعات الأكوام الخاصة بهم. أعتقد أنه يمكن القيام بذلك في O (سجل (عدد العمال * أكوام لكل عامل)) إذا كان العمال يشكلون شجرة تجميع .

ماذا عن مشكلة مشكلة العنصر ؟ كما تنص المقالة ، يمكن حل مشكلة التمييز العنصر في O(N) . هذا هو نفسه لمشكلة الجوارب (أيضا O(N) ، إذا كنت بحاجة إلى خطوة توزيع واحدة فقط (اقترحت خطوات متعددة فقط لأن البشر سيئون في الحسابات - خطوة واحدة كافية إذا قمت بالتوزيع على md5(color, length, pattern, ...) ، أي تجزئة مثالية لجميع الصفات)).

بوضوح ، لا يمكن للمرء أن يذهب أسرع من O(N) ، لذلك وصلنا إلى الحد الأدنى الأمثل .

على الرغم من أن المخرجات ليست متماثلة تمامًا (في حالة واحدة ، مجرد منطقية. وفي الحالة الأخرى ، أزواج الجوارب) ، فإن التعقيدات التقاربية هي نفسها.


وبما أن بنية الدماغ البشري تختلف تمامًا عن وحدة المعالجة المركزية الحديثة ، فإن هذا السؤال لا معنى له من الناحية العملية.

يمكن أن يفوز البشر بخوارزميات وحدة المعالجة المركزية (CPU) باستخدام حقيقة أن "إيجاد زوج مطابق" يمكن أن يكون عملية واحدة لمجموعة ليست كبيرة جدًا.

خوارزميتي:

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

على الأقل هذا هو ما أستخدمه في الحياة الحقيقية ، وأجده فعالاً للغاية. الجانب السلبي هو أنه يتطلب سطح مسطح ، لكنه عادة ما يكون وفير.


إنشاء جدول تجزئة الذي سيتم استخدامه لجوارب لا مثيل لها ، وذلك باستخدام نمط مثل التجزئة. يتكرر فوق الجوارب واحدة تلو الأخرى. إذا كان الجورب يتطابق مع نمط في جدول التجزئة ، خذ الجورب من الطاولة وقم بعمل زوج. إذا لم يكن لدى الجورب تطابق ، ضعه في الجدول.


من أجل تحديد مدى كفاءة إقران الجوارب من كومة ، يجب أن نحدد الجهاز أولاً ، لأن الإقران لا يتم سواء عن طريق تورينج أو من خلال جهاز الوصول العشوائي ، والذي يستخدم عادة كأساس التحليل الخوارزمي.

الآلة

الآلة هي تجريد لعنصر حقيقي يدعى الإنسان. وهي قادرة على القراءة من البيئة عبر زوج من العيون. ونموذج الآلة قادر على التعامل مع البيئة باستخدام ذراعين. يتم حساب العمليات المنطقية والحساب باستخدام دماغنا (نأمل ؛-)).

علينا أيضا أن ننظر في وقت التشغيل الجوهري للعمليات الذرية التي يمكن القيام بها مع هذه الأدوات. بسبب القيود المادية ، فإن العمليات التي يتم تنفيذها بواسطة الذراع أو العين لها تعقيد زمني غير ثابت. هذا لأننا لا نستطيع تحريك كومة كبيرة غير منتهية من الجوارب بذراع ولا يمكن للعين أن ترى الجورب العلوي على كومة كبيرة من الجوارب.

ومع ذلك ، تعطينا الفيزياء الميكانيكية بعض الأشياء الجيدة أيضًا. نحن لا يقتصر على التحرك في جورب واحد مع ذراع واحد. يمكننا نقل اثنين منها في وقت واحد.

بناءً على التحليل السابق ، يجب استخدام العمليات بترتيب تنازلي:

  • العمليات المنطقية والحسابية
  • يقرأ البيئة
  • التعديلات البيئية

يمكننا أيضا الاستفادة من حقيقة أن الناس لديهم فقط كمية محدودة جدا من الجوارب. لذلك يمكن أن يشمل التعديل البيئي جميع الجوارب في الوبر.

الخوارزمية

إذن هذا هو اقتراحي:

  1. انتشر كل الجوارب في كومة على الأرض.
  2. ابحث عن زوج من خلال النظر إلى الجوارب على الأرض.
  3. كرر من 2 حتى لا يمكن صنع أي زوج.
  4. كرر من 1 حتى لا توجد جوارب على الأرض.

العملية 4 ضرورية ، لأنه عند نشر الجوارب على الأرض قد تخفي بعض الجوارب الآخرين. هنا هو تحليل الخوارزمية:

التحليل

الخوارزمية تنتهي باحتمالية عالية. هذا يرجع إلى حقيقة أن أحد غير قادر على العثور على أزواج من الجوارب في الخطوة رقم 2.

بالنسبة لتحليل وقت التشغيل التالي nلزوج الاقتران من الجوارب ، نفترض أن نصف 2nالجوارب على الأقل لا يتم إخفاؤها بعد الخطوة 1. وهكذا في الحالة المتوسطة ، يمكن أن نجد n/2أزواجًا. هذا يعني أن الحلقة هي الخطوة 4 يتم تنفيذها O(log n)مرات. يتم تنفيذ الخطوة 2 O(n^2)مرات. حتى نتمكن من استنتاج:

  • الخوارزمية تتضمن O(ln n + n)تعديلات بيئية (الخطوة 1 O(ln n)بالإضافة إلى اختيار كل زوج من الجورب من الأرضية)
  • تتضمن الخوارزمية O(n^2)القراءات البيئية من الخطوة 2
  • تتضمن الخوارزمية عمليات O(n^2)منطقية وحسابية للمقارنة بين جورب وآخر في الخطوة 2

لذلك لدينا تعقيد وقت التشغيل الكلي من O(r*n^2 + w*(ln n + n))حيث rو wهي عوامل لعمليات القراءة البيئية والكتابة البيئية على التوالي للحصول على كمية معقولة من الجوارب. يتم حذف تكلفة العمليات المنطقية والحسابية ، لأننا نفترض أن الأمر يتطلب كمية ثابتة من العمليات المنطقية والحسابية لتقرير ما إذا كانت هناك جوربتان تخصان نفس الزوج. قد لا يكون هذا ممكنًا في كل سيناريو.


أنت تحاول حل المشكلة الخاطئة.

الحل الأول: في كل مرة تضع فيها الجوارب القذرة في سلة الغسيل ، اربطها في عقدة صغيرة. بهذه الطريقة لن تضطر إلى القيام بأي فرز بعد الغسيل. فكر في الأمر مثل تسجيل فهرس في قاعدة بيانات Mongo. القليل من العمل في المستقبل لتحقيق بعض وفورات وحدة المعالجة المركزية في المستقبل.

الحل 2: إذا كان فصل الشتاء ، لا يتعين عليك ارتداء الجوارب المناسبة. نحن مبرمجون. لا يحتاج أحد إلى معرفة ما دام يعمل.

الحل 3: نشر العمل. تريد إجراء عملية معقدة مثل وحدة المعالجة المركزية بشكل غير متزامن ، دون حظر واجهة المستخدم. خذ تلك الكومة من الجورب وحشوها في حقيبة. ابحث فقط عن زوج عند الحاجة إليه. وبهذه الطريقة ، فإن مقدار العمل الذي يتطلبه الأمر أقل بكثير.

أتمنى أن يساعدك هذا!


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

لقد انتهيت من إقران الجوارب الخاصة بي الآن ، ووجدت أن أفضل طريقة للقيام بذلك هي ما يلي:

  • اختر واحدة من الجوارب وقم بوضعها (قم بإنشاء "دلو" لهذا الزوج)
  • إذا كان الرقم التالي هو الزوج السابق ، فضعه في المجموعة الحالية ، وإلا فأنشئ واحدة جديدة.

في أسوأ الحالات ، يعني ذلك أنه سيكون لديك مجموعة مختلفة من n / 2 ، وسيكون لديك تحديدات n-2 حول ذلك الدلو الذي يحتوي على زوج الجورب الحالي. من الواضح أن هذه الخوارزمية تعمل بشكل جيد إذا كان لديك بضعة أزواج فقط ؛ أنا فعلت هذا مع 12 زوجا.

انها ليست علمية جدا ، لكنها تعمل بشكل جيد :)


ما أقوم به هو أن أقوم بأخذ الجورب الأول ووضعه (على سبيل المثال ، على حافة وعاء الغسيل). ثم ألتقط جوربًا آخر وتحقق لمعرفة ما إذا كان هو نفس الجورب الأول. إذا كان الأمر كذلك ، فأنا أزلهما. إذا لم يكن كذلك ، أضعه بجوار الجورب الأول. ثم ألتقط الجورب الثالث وأقارنه بالأول والثاني (إذا كان لا يزال هناك). إلخ.

يمكن تنفيذ هذا النهج بسهولة في مصفوفة ، على افتراض أن "إزالة" الجوارب هو خيار. في الواقع ، لا تحتاج حتى إلى "إزالة" الجوارب. إذا كنت لا تحتاج إلى فرز الجوارب (انظر أدناه) ، يمكنك فقط تحريكها ونهاية مع صفيف يحتوي على جميع الجوارب مرتبة في أزواج في الصفيف.

بافتراض أن العملية الوحيدة للجوارب هي المقارنة من أجل المساواة ، فإن هذه الخوارزمية لا تزال في الأساس خوارزمية n 2 ، على الرغم من أنني لا أعرف عن الحالة المتوسطة (لم نتعلم حساب ذلك).

الفرز ، بالطبع يحسن الكفاءة ، وخاصة في الحياة الحقيقية حيث يمكنك بسهولة "إدراج" جورب بين اثنين من الجوارب الأخرى. في الحوسبة يمكن أن يتحقق نفس الشجرة ، ولكن هذا هو مساحة إضافية. وبالطبع ، عدنا إلى NlogN (أو أكثر قليلاً ، إذا كان هناك العديد من الجوارب التي هي نفسها من خلال معايير الفرز ، ولكن ليس من نفس الزوج).

بخلاف ذلك ، لا أستطيع التفكير في أي شيء ، ولكن يبدو أن هذه الطريقة فعالة إلى حد كبير في الحياة الحقيقية. :)


التقط أول جورب وضعه على الطاولة. الآن اختيار جورب آخر. إذا كان يطابق الأول التقط ، ضعه فوق الأول. إذا لم يكن كذلك ، ضعه على الطاولة على بعد صغير من الأول. اختر جوربًا ثالثًا إذا كان يتطابق مع أي من الاثنين السابقين ، ضعه فوقها أو ضعه على مسافة صغيرة من الثلث. كرر ذلك حتى تحصل على جميع الجوارب.


مشكلة فرز أزواج n من الجوارب هي O (n) . قبل أن ترميهم في سلة الغسيل ، تقوم بتدوير اليسار إلى اليمين. عند إخراجها ، يمكنك قطع الخيط ووضع كل زوج في الدرج - 2 عمليات على أزواج n ، لذلك O (n).

والسؤال التالي الآن هو ببساطة ما إذا كنت تقوم بغسيل ملابسك بنفسك أم زوجتك أم لا. هذه مشكلة محتملة في نطاق مختلف تمامًا من المشكلات . :)


الحد النظري هو O (n) لأنك تحتاج إلى لمس كل جورب (ما لم يتم إقران بعضها بطريقة ما).

يمكنك تحقيق O (n) بفرز radix . كل ما تحتاجه هو اختيار بعض السمات الخاصة بالدلاء.

  1. أولا يمكنك اختيار (راتبها ، لي) - تقسيمها إلى 2 أكوام ،
  2. ثم استخدم الألوان (يمكن أن يكون أي ترتيب للألوان ، أبجديًا حسب اسم اللون) - تقسيمها إلى أكوام حسب اللون (تذكر الاحتفاظ بالطلب الأولي من الخطوة 1 لجميع الجوارب في نفس الوبر) ،
  3. ثم طول الجورب ،
  4. ثم الملمس ، ....

إذا كان بإمكانك اختيار عدد محدود من السمات ، ولكن سمات كافية يمكنها تحديد كل زوج بشكل فريد ، فيجب إجراؤها في O (k * n) ، وهو O (n) إذا كان بإمكاننا اعتبار k محدودًا.


وهنا أوميغا (ن السجل ن) الحد الأدنى في النموذج القائم على المقارنة. (العملية الوحيدة الصالحة هي مقارنة اثنين من الجوارب).

لنفترض أنك تعرف أن الجوارب 2n مرتبة بهذه الطريقة:

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

حيث f عبارة عن تحويل غير معروف للمجموعة {1،2، ...، n}. معرفة هذا لا يمكن أن يجعل المشكلة أكثر صعوبة. هناك ن! المخرجات المحتملة (تطابق بين الشوط الأول والنصف الثاني) ، مما يعني أنك بحاجة إلى تسجيل (n!) = مقارنات أوميغا (n log n). هذا هو ممكن عن طريق الفرز.

بما أنك مهتم بالارتباطات بمشكلة مميزة للعنصر: فإن إثبات أن أوميغا (n log n) المرتبطة بتمييز العنصر أصعب ، لأن الناتج هو ثنائي نعم / لا. هنا ، يجب أن يكون الناتج مطابقاً ويكفي عدد النواتج الممكنة للحصول على حد لائق. ومع ذلك ، هناك متغير متصل بميزة العنصر. لنفترض أنك أعطيت الجوارب 2n وتساءل عما إذا كان يمكن إقرانه بشكل فريد. يمكنك الحصول على تخفيض من ED عن طريق إرسال (أ 1 ، أ 2 ، ...، و ن ) إلى (أ 1 ، أ 1 ، أ 2 ، و 2 ، ...، و ن ، و ن ). (من الناحية القانونية ، دليل صلابة الضعف الجنسي مثير جدا للاهتمام ،عبر طوبولوجيا .)

أعتقد أنه يجب أن يكون هناك أوميغا (ن 2 ) ملزمة للمشكلة الأصلية إذا سمحت اختبارات المساواة فقط. حدسي هو: النظر في الرسم البياني حيث تضيف حافة بعد الاختبار ، ويقول أنه إذا كان الرسم البياني ليست كثيفة لا يتم تحديد الإخراج بشكل فريد.


آمل أن أتمكن من المساهمة بشيء جديد في هذه المشكلة. لقد لاحظت أن جميع الإجابات تتجاهل حقيقة أن هناك نقطتين يمكنك من خلالهما إجراء المعالجة المسبقة ، دون إبطاء أداء الغسيل الكلي الخاص بك.

أيضا ، نحن لسنا بحاجة إلى تحمل عدد كبير من الجوارب ، حتى بالنسبة للعائلات الكبيرة. يتم إخراج الجوارب من الدرج ويتم ارتداؤها ، ويتم رميها في مكان (ربما بن) حيث تبقى قبل غسلها. في حين أنني لن أتصل بـ (بن سيف) (LIFO-Stack) ، أقول أنه من الآمن أن نفترض ذلك

  1. يمسك الناس كل من الجوارب الخاصة بهم في نفس المنطقة من سلة المهملات ،
  2. بن ليست عشوائية في أي نقطة ، وبالتالي
  3. أي مجموعة فرعية أخذت من أعلى هذا الصندوق تحتوي عادة على كل من جوارب زوج.

بما أن جميع الغسالات التي أعرفها محدودة الحجم (بغض النظر عن عدد الجوارب التي يجب غسلها) ، ويحدث التعشية الفعلية في الغسالة ، بغض النظر عن عدد الجوارب التي لدينا ، فلدينا دائمًا مجموعات فرعية صغيرة تحتوي على سنغلتونس.

إن مرحلتنا السابقة للتجهيز هي "وضع الجوارب على حبل الغسيل" و "أخذ الجوارب من حبل الغسيل" ، وهو ما يتعين علينا القيام به ، من أجل الحصول على الجوارب التي ليست نظيفة فحسب ، بل جافة أيضًا. كما هو الحال مع الغسالات ، خطوط الغسيل محدودة ، وأفترض أن لدينا الجزء الكامل من الخط الذي نضع فيه جواربنا في الأفق.

إليك خوارزمية put_socks_on_line ():

while (socks left in basket) {
 take_sock();
 if (cluster of similar socks is present) { 
   Add sock to cluster (if possible, next to the matching pair)
 } else {
  Hang it somewhere on the line, this is now a new cluster of similar-looking socks.      
  Leave enough space around this sock to add other socks later on 
 }
}

لا تضيع وقتك في تحريك الجوارب أو تبحث عن أفضل تطابق ، يجب أن يتم كل هذا في O (n) ، والتي نحتاجها أيضًا لوضعها على السطر غير مجزأة. لم يتم إقران الجوارب حتى الآن ، لدينا فقط العديد من مجموعات التشابه على الخط. من المفيد أن يكون لدينا مجموعة محدودة من الجوارب هنا ، لأن هذا يساعدنا على إنشاء مجموعات "جيدة" (على سبيل المثال ، إذا لم يكن هناك سوى الجوارب السوداء في مجموعة الجوارب ، فإن التجميع حسب الألوان لن يكون هو الطريق المناسب)

إليك خوارزمية take_socks_from_line ():

while(socks left on line) {
 take_next_sock();
 if (matching pair visible on line or in basket) {
   Take it as well, pair 'em and put 'em away
 } else {
   put the sock in the basket
 }

يجب أن أشير إلى أنه من أجل تحسين سرعة الخطوات المتبقية ، من الحكمة عدم اختيار الجورب التالي بشكل عشوائي ، ولكن من أجل أخذ جورقات بعد كل جروح من كل مجموعة. لا تستغرق خطوات المعالجة المسبقة وقتًا أطول من مجرد وضع الجوارب على الخط أو في السلة ، وهو ما يتعين علينا القيام به بغض النظر عن أي شيء ، لذلك يجب أن يعزز ذلك من أداء الغسيل بشكل كبير.

بعد ذلك ، من السهل القيام بخوارزمية تجزيء التجزئة. عادة ، يتم إقران حوالي 75 ٪ من الجوارب ، وترك لي مع مجموعة فرعية صغيرة جدا من الجوارب ، وهذه المجموعة الفرعية بالفعل (إلى حد ما) العنقودية (أنا لا أدخل الكثير من الانتروبيا في سلتي بعد خطوات المعالجة المسبقة). شيء آخر هو أن المجموعات المتبقية تميل إلى أن تكون صغيرة بما يكفي ليتم التعامل معها في وقت واحد ، لذلك من الممكن أخذ كتلة كاملة من السلة.

إليك خوارزمية sort_remaining_clusters ():

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

بعد ذلك ، لا يوجد سوى عدد قليل من الجوارب المتبقية. هذا هو المكان الذي أقوم فيه بتقديم جوارب غير مزاوجة من قبل في النظام ومعالجة الجوارب المتبقية بدون أي خوارزمية خاصة - الجوارب المتبقية قليلة جدًا ويمكن معالجتها بصريًا سريعًا جدًا.

بالنسبة لجميع الجوارب المتبقية ، أفترض أن نظرائهم لا يزالون غير مغسلين ويضعونها بعيدا عن التكرار التالي. إذا قمت بتسجيل نمو في الجوارب غير المزدحمة بمرور الوقت ("تسريب جورب") ، يجب أن تتحقق من صندوقك - قد يتم الحصول عليه بشكل عشوائي (هل لديك قطط تنام هناك؟)

أعلم أن هذه الخوارزميات تأخذ الكثير من الافتراضات: صندوق يعمل بمثابة نوع من مكدس LIFO ، وغسالات محدودة عادية ، وخط غسيل محدود ، ولكن هذا لا يزال يعمل مع أعداد كبيرة جدًا من الجوارب.

حول التوازي: طالما كنت ترمي كل من الجوارب في نفس الصندوق ، يمكنك بسهولة موازاة كل تلك الخطوات.


الإجابة غير الخوارزمية ، لكنها "فعالة" عندما أقوم بذلك:

  • الخطوة 1) تجاهل جميع الجوارب الموجودة لديك

  • الخطوة 2) الذهاب إلى Walmart وشرائها عن طريق حزم من 10 - ن حزمة من الأبيض والأسود الحزم م. لا حاجة للألوان الأخرى في حياة كل يوم.

ومع ذلك ، يجب أن أفعل ذلك مراراً وتكراراً (مثل الجوارب المفقودة والجوارب المدمرة وما إلى ذلك) ، وأكره أن أتخلص من الجوارب الجيدة في كثير من الأحيان (وكنت أتمنى لو أنهم استمروا في بيع نفس إشارة الجوارب) ، مقاربة مختلفة.

الإجابة الخوارزمية:

فكر في ما إذا كنت ترسم جوربًا واحدًا فقط للمجموعة الثانية من الجوارب ، كما تفعل ، فإن احتمالات العثور على جورب مطابق في بحث ساذج منخفضة للغاية.

  • لذا اختر خمسة منهم عشوائياً واحفظ شكلهم أو طولهم.

لماذا خمسة؟ عادةً ما يتذكر البشر جيدًا ما بين خمسة وسبعة عناصر مختلفة في الذاكرة العاملة - تشبه إلى حدٍ ما المكافئ البشري لمكدس RPN - خمسة هي RPN آمن.

  • التقط واحدة من كومة 2n-5.

  • الآن ابحث عن مطابقة (تطابق النمط المرئي - البشر جيدون في ذلك مع مكدس صغير) داخل الخمسة الذين قمت برسمهم ، إذا لم تجد واحدًا ، ثم أضف ذلك إلى خمسة.

  • احرص على اختيار الجوارب بشكل عشوائي من المكدس ومقارنتها بالجوارب 5 + 1 لمباراة. كلما كبرت مجموعتك ، ستقلل من أدائك ولكنها ستزيد من احتمالاتك. أسرع بكثير

لا تتردد في كتابة الصيغة لحساب عدد العينات التي يجب عليك رسمها للحصول على 50٪ من احتمالات التطابق. آي آي آر سي إنه قانون فائق السرعة.

أفعل ذلك كل صباح ونادراً ما أحتاج إلى أكثر من ثلاثة تعادلات - ولكن لديّ أزواج مماثلة (حوالي 10 أزواج ، أعطي أو خسروا) جوارب بيضاء على شكل m . الآن يمكنك تقدير حجم رصيدي من الأسهم :-)

راجع للشغل ، وجدت أن مجموع تكاليف المعاملات لفرز كل الجوارب في كل مرة كنت بحاجة إلى زوج أقل بكثير من القيام بذلك مرة واحدة وملزمة الجوارب. يعمل فقط في الوقت المناسب بشكل أفضل لأنك لا تحتاج إلى ربط الجوارب ، وهناك أيضًا تناقص هامشي متراجع (وهذا يعني أنك ستبحث عن اثنين أو ثلاثة جورب في مكان ما في مغسلة الملابس التي تحتاج إليها لإنهاء مطابقة الجوارب الخاصة بك وتضيع الوقت على ذلك).


While I really like the swap macro provided:

#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))
#define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }

I see an improvement (which a good compiler might make):

#define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; }

We take note of how min and max work and pull the common sub-expression explicitly. This eliminates the min and max macros completely.





algorithm sorting language-agnostic matching