حل الكلمات المتقاطعة الملونة اليابانية بسرعة الضوء

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

يمكن أن يصل حجم الكلمات المتقاطعة إلى 150 × 150. يستخدم المشغل منطقًا خاصًا لحساب لون كل خلية. قد يستغرق الحل بضع دقائق على الألغاز المتقاطعة للمبتدئين وعشرات الساعات في الألغاز المعقدة.

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

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

قواعد اللعبة

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

في الكلمات المتقاطعة بالأبيض والأسود ، يوضح عدد الأرقام لكل صف (على يسار اللوحة) أو لكل عمود (أعلى اللوحة) عدد مجموعات الخلايا السوداء الموجودة في الصف أو العمود المقابل ، وتظهر الأرقام نفسها عدد الخلايا المدمجة في كل مجموعة من هذه المجموعات. مجموعة من الأرقام $$$[3، 2، 5]$ يعني أنه في صف معين هناك ثلاث مجموعات متتالية من $$$3$ ، $$$2$ و $$$5$ الخلايا السوداء على التوالي. يمكن ترتيب المجموعات بشكل متتالي بشكل عشوائي ، دون انتهاك الترتيب النسبي (تحدد الأرقام طولها ، ويجب تخمين الموقع) ، ولكن يجب فصلها بخلية بيضاء واحدة على الأقل.

مثال صحيح

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

ما هو ليس الكلمات المتقاطعة اليابانية

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

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

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

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

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

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

أبسط لغز الكلمات المتقاطعة الخاطئة:

|1 1| --+---+ 1| | 1| | --+---+ 

غالبًا ، لا يتم حل صورة البكسل المشفرة ، التي تستخدم نمط "رقعة الداما" لمحاكاة التدرج ، إلى الوراء. من الأفضل أن تفهم ما إذا كتبت "pixelart gradient" في البحث. التدرج هو مثل هذه الكلمات المتقاطعة 2x2 fayl.

الحلول الممكنة

لدينا حجم لغز الكلمات المتقاطعة ووصف للألوان وجميع الصفوف والأعمدة. كيف يمكنني تجميع صورة من هذا:

بحث كامل

لكل خلية ، نقوم بفرز جميع الحالات الممكنة والتحقق من أنها مرضية. تعقيد هذا الحل للكلمات المتقاطعة بالأبيض والأسود $$$O (N * M * {2} ^ {N * M})$ للون $$$O (N * M * {colors} ^ {N * M})$ . قياسا على فرز المهرج ، يمكن أيضا أن يسمى هذا الحل المهرج. انها مناسبة لحجم 5x5.

التراجع

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

بشكل منفصل لكل صف

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

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

قرار حقيقي حقا

سطر واحد ، لونان

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

• ربع نهائي ACM ICPC 2006 - يمكنك محاولة حل المشكلة بنفسك . الحد الزمني هو ثانية واحدة ، والحد الأقصى لعدد المجموعات هو 400 ، وطول السلسلة هو 400 أيضًا. ولديه مستوى عالٍ جدًا من التعقيد مقارنة بالمهام الأخرى.
• الأولمبياد الدولي للمعلوماتية 2016 - شرط لتمرير المهمة . الحد الزمني 2 ثانية ، والحد الأقصى لعدد المجموعات 100 ، وطول الصف 200'000. هذه القيود مفرطة ، ولكن حل مشكلة مع قيود ACM يكسب 80/100 نقطة في هذه المشكلة. هنا ، أيضًا ، لم يخيب المستوى ، طلاب المدارس من جميع أنحاء العالم بمستوى ذكاء قاسي يتدربون لعدة سنوات على حل الحيل المختلفة ، ثم يذهبون إلى الأولمبياد (يجب أن يمر 4 أشخاص فقط من الدولة) ، ويقررون جولتين من 5 ساعات وفي حالة الفوز الملحمي (البرونزية في سنوات مختلفة مقابل 138-240 نقطة من أصل 600) ، القبول في أكسفورد ، ثم عروض من شركات واضحة لقسم البحث ، حياة طويلة وسعيدة مع dakimakura.

يمكن أيضًا حل الخط الأحادي اللون بطرق مختلفة ، ولأجل $$$O (N * 2 ^ N)$ (تعداد جميع الخيارات ، والتحقق من صحتها ، واختيار الخلايا التي لها نفس اللون في جميع الخيارات) ، وأقل غباء بطريقة أو بأخرى.

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

 def EpicWin(group, cell): if cell >= last_cell: #   return group == group_size win = False #        if group < group_size #    and CanInsertBlack(cell, len[group]) #    and CanInsertWhite(cell + len[group], 1) #    and EpicWin(group + 1, cell + len[group] + 1): #    win = True can_place_black[cell .. (cell + len[group] - 1)] = True can_place_white[cell + len[group]] = True; #         if CanInsertWhite(cell, 1) and EpicWin(group, cell + 1): win = True can_place_white[cell] = True return win EpicWin(0, 0) 

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

هناك حاجة إلى CanInsertBlack/CanInsertWhite للتحقق مما إذا كان من الممكن نظريًا وضع مجموعة من الحجم الصحيح في المكان الصحيح. كل ما يحتاجون إليه هو التحقق من عدم وجود خلية "بيضاء 100٪" (للوظيفة الأولى) أو "100٪ أسود" (للثانية) في نطاق الخلايا المشار إليه. حتى يتمكنوا من العمل $$$O (1)$ يمكن القيام بذلك باستخدام كميات جزئية:

 white_counter = [ 0, 0, ..., 0 ] #   n def PrecalcWhite(): for i in range(0, (n-1)): if is_anyway_white[i]: # 1,  i-  100%  white_counter[i]++ if i > 0: white_counter[i] += white_counter[i - 1] def CanInsertBlack(cell, len): #     [cell, cell + len - 1] ans = white_counter[cell + len - 1] if cell > 0: ans -= white_counter[cell - 1] #  ans -     cell  (cell + len - 1) return ans == 0 

تنتظر الشعوذة نفسها ذات المبالغ الجزئية سطرًا من النموذج

 can_place_black[cell .. (cell + len[group] - 1)] = True 

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

 #     for i in range(L, R + 1): array[i]++ 

يمكنك القيام بذلك:

 #     array[L]++ array[R + 1]-- #    for i in range(1, n): array[i] += array[i - 1] 

وهكذا ، تعمل الخوارزمية بأكملها $$$O (k * n)$ أين $$$k$ - عدد مجموعات الخلايا السوداء ، $$$n$ هو طول السلسلة. ونذهب إلى نصف النهائي من ACM ICPC أو نحصل على البرونزية للمتدرب. ACM Solution (Java) . حل IOI (C ++) .

سطر واحد ، ألوان كثيرة

عندما ننتقل إلى nonograms متعددة الألوان ، والتي لا تزال غير واضحة حول كيفية حلها ، نتعلم حقيقة رهيبة - اتضح أن كل عمود يتأثر بشكل سحري بجميع الأعمدة! هذا أوضح من خلال مثال:

المصدر - طرق حل الكلمات المتقاطعة اليابانية

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

لكن هذه النكتة قابلة للتقدير رياضياً - يجب إعطاء كل خلية رقماً ، أين $$$i$ يعني بت إيث ما إذا كان يمكن إعطاء هذه الخلية $$$i$ اللون عشر. في البداية ، كل الخلايا لها قيمة $$$2 ^ {الألوان} - 1$ . لن يتغير قرار الديناميكيات كثيرًا.

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

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

 source = [...] #   result = [0, 0, ..., 0] #   len = [...] #    clrs = [...] #    def CanInsertColor(color, cell, len): for i in range(cell, cell + len): if (source[i] & (1 << color)) == 0: #     color    return False; return True def PlaceColor(color, cell, len): for i in range(cell, cell + len): result[i] |= (1 << color) #   color  OR def EpicWinExtended(group, cell): if cell >= last_cell: #   return group == group_size win = False #        if group < group_size #    and CanInsertColor(clrs[group], cell, len[group]) #    and SequenceCheck() #       ,  #         and EpicWin(group + 1, cell + len[group]): #    win = True PlaceColor(clrs[group], cell, len[group]) PlaceColor(0, cell + len[group], 1) #   -    #         #   -  0 if CanInsertWhite(0, cell, 1) and EpicWinExtended(group, cell + 1): win = True PlaceColor(0, cell, 1) return win 

خطوط كثيرة ، ألوان كثيرة

القيام باستمرار بتحديث حالات جميع الصفوف والأعمدة ، الموضحة في الفقرة الأخيرة ، حتى لا توجد خلية واحدة بأكثر من بت واحد. في كل تكرار ، بعد تحديث جميع الصفوف والأعمدة ، نقوم بتحديث حالة جميع الخلايا فيها من خلال AND المتبادل.

النتائج الأولى

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

دعونا نلقي نظرة على وقت البرنامج ، الذي يقرأ اللغز من الملف ويحله بالكامل. يجدر تقييم مزايا الآلة التي كُتبت عليها واختبرت كل هذه الأشياء:

 RAM - 4GB  - AMD E1-2500,  1400MHz  L1 - 128KiB, 1GHz  L2 - 1MiB, 1GHz  - 2,  - 2   « SoC   »   2013    28  

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

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

لون الكلمات المتقاطعة رقم 9596 ، أكبر صعوبة

للاختبار السريع ، تم عمل وظائف للمعيار. للحصول على بيانات له ، أقوم بنسخ 4683 كلمة متقاطعة ملونة (من 10906 ) و 1406 بالأبيض والأسود (من 8293 ) من nonograms.ru (هذا هو أحد أكبر المحفوظات غير الإلكترونية على الإنترنت) باستخدام برنامج نصي خاص وحفظها بتنسيق يفهمه البرنامج. يمكننا أن نفترض أن هذه الكلمات المتقاطعة هي عينة عشوائية ، لذا فإن المعيار سيعرض قيمًا متوسطة مناسبة. أيضًا ، تم تسجيل عدد من العشرات من أكثر الكلمات المتقاطعة "تعقيدًا" (وهي أيضًا الأكبر في الحجم وعدد الألوان) في برنامج نصي للتحميل بالأقلام.

التحسين

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

في وقت كتابة الخوارزمية

• وظائف خاصة لعمليات البت ، في حالتنا __builtin_popcount لوحدات العد في ترميز ثنائي لرقم ، و __builtin_ctz لعدد الأصفار قبل أول وحدة أصغر. قد لا تظهر هذه الوظائف في بعض المترجمين. بالنسبة لنظام التشغيل Windows ، تكون هذه النظائر مناسبة:

 #ifdef _MSC_VER # include <intrin.h> # define __builtin_popcount __popcnt #endif 

• تنظيم الصفيف - حجم أصغر يأتي أولاً. على سبيل المثال ، من الأفضل استخدام الصفيف [2] [3] [500] [1024] من [1024] [500] [3] [2].
• الشيء الأكثر أهمية هو كفاية التعليمات البرمجية العامة وتجنب المخاوف غير الضرورية للحسابات.

ما يقلل من وقت العمل

• إشارة -O2 عند الترجمة.
• من أجل عدم إلقاء الصف / العمود الذي تم حله بالكامل في الخوارزمية مرة أخرى ، يمكنك تعيين العلامات لكل صف في std :: vector / array منفصل ، ووضع علامة عليها بحل كامل ، وعدم تركها إذا لم يكن هناك المزيد لحلها.
• تشير تفاصيل حل متعدد التكرارات لمشكلة ديناميكية إلى أنه يجب إعادة ضبط مصفوفة خاصة تحتوي على علامات تشير إلى أجزاء "محسوبة" بالفعل من المشكلة في كل مرة يتم فيها إنشاء حل جديد. في حالتنا ، هذا صفيف / ناقل ثنائي الأبعاد ، حيث البعد الأول هو عدد المجموعات ، والثاني هو الخلية الحالية (انظر EpicWin pseudocode أعلاه ، حيث لا يكون هذا الصفيف ، ولكن الفكرة واضحة). بدلاً من التصفير ، يمكنك القيام بذلك - دعنا نحصل على متغير "مؤقت" ، ويتكون الصفيف من أرقام تظهر "آخر" وقت تم فيه سرد هذه القطعة للمرة الأخيرة. عند بدء مهمة جديدة ، يزيد "المؤقت" بمقدار 1. بدلاً من التحقق من العلامة المنطقية ، يجب عليك التحقق من المساواة بين عنصر الصفيف و "المؤقت". يعد هذا فعالًا خاصة في الحالات التي تكون فيها الخوارزمية مغطاة بعيدًا عن جميع الحالات الممكنة (مما يعني أن التصفير الصفيف "هل اعتبرنا ذلك بالفعل" يستغرق جزءًا كبيرًا من الوقت).
• استبدال العمليات البسيطة من نفس النوع (الحلقات مع التخصيص ، وما إلى ذلك) مع نظائرها في STL أو أشياء أكثر ملاءمة. في بعض الأحيان يعمل بشكل أسرع من الدراجة.
• std::vector<bool> في C ++ بضغط جميع القيم المنطقية إلى وحدات بت فردية بالأرقام ، والتي تعمل على الوصول بشكل أبطأ قليلاً مما لو كانت قيمة عادية في العنوان. إذا كان البرنامج يستخدم مثل هذه القيم في كثير من الأحيان ، فإن استبدال قيمة منطقية بنوع صحيح يمكن أن يكون له تأثير جيد على الأداء.
• يمكن البحث عن نقاط ضعف أخرى من خلال المحللون وتحريرها. أنا نفسي أستخدم Valgrind ، تحليل أدائه مناسب للنظر في kCachegrind. يتم إنشاء ملفات التعريف في العديد من IDEs.

تبين أن هذه التعديلات كافية للحصول على مثل هذه البيانات في المعيار:

 izaron@izaron:~/nonograms/build$ ./nonograms_solver -x ../../nonogram/source2/ -e [2018-08-04 22:57:40.432] [Nonograms] [info] Starting a benchmark... [2018-08-04 22:58:03.820] [Nonograms] [info] Average time: 0.00497556, Median time: 0.00302781, Max time: 0.215925 [2018-08-04 22:58:03.820] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 22:58:03.820] [Nonograms] [info] 0.215925 seconds, file 9596 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.164579 seconds, file 4462 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.105828 seconds, file 15831 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.08827 seconds, file 18353 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0874717 seconds, file 10590 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0831248 seconds, file 4649 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0782811 seconds, file 11922 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0734325 seconds, file 4655 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.071352 seconds, file 10828 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0708263 seconds, file 11824 

 izaron@izaron:~/nonograms/build$ ./nonograms_solver -x ../../nonogram/source/ -e -b [2018-08-04 22:59:56.308] [Nonograms] [info] Starting a benchmark... [2018-08-04 23:00:09.781] [Nonograms] [info] Average time: 0.0095679, Median time: 0.00239274, Max time: 0.607341 [2018-08-04 23:00:09.781] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 23:00:09.781] [Nonograms] [info] 0.607341 seconds, file 5126 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.458932 seconds, file 19510 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.452245 seconds, file 5114 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.19975 seconds, file 18627 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.163028 seconds, file 5876 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.161675 seconds, file 17403 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.153693 seconds, file 12771 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.146731 seconds, file 5178 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.142732 seconds, file 18244 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.136131 seconds, file 19385 

قد تلاحظ أن الكلمات المتقاطعة بالأسود والأبيض هي "أصعب" في المتوسط ​​من الكلمات المتقاطعة الملونة. هذا يؤكد ملاحظات عشاق اللعبة ، الذين يعتقدون أيضًا أن "اللون" يتم حله في المتوسط ​​بشكل أسهل.

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

مزيد من التحسين

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

• إعادة كتابة الرمز على غرار C وغيرها عام 1972. نستبدل ifstream بالنظير التناظري ، وناقلات المصفوفات ، ونتعلم جميع خيارات المترجم ونقاتل لكل دورة ساعة للمعالج.
• موازاة. على سبيل المثال ، يوجد في الكود قطعة يتم فيها تحديث الصفوف بالتسلسل ، ثم الأعمدة:

  ... if (!UpdateGroupsState(solver, dead_rows, row_groups, row_masks)) { return false; } if (!UpdateGroupsState(solver, dead_cols, col_groups, col_masks)) { return false; } return true; 

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

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

إذا كانت المهمة جادة ولدي الكثير من البيانات والأجهزة متعددة النواة ، فسوف أذهب إلى أبعد من ذلك - يمكنك إنشاء العديد من سلاسل العمليات الثابتة ، وسيكون لكل منها كائن OneLineSolver الخاص به ، وهيكل آخر آمن للخيط يتحكم في توزيع العمل وعند الطلب إلى أنه يعطي إشارة إلى الصف / العمود التالي للحل. الخيوط بعد حل مشكلة أخرى تتحول إلى الهيكل مرة أخرى لحل شيء آخر. من حيث المبدأ ، يمكن البدء في مشكلة غير برمجية دون إكمال المشكلة السابقة ، على سبيل المثال ، عندما تشارك هذه البنية في المتبادل AND لجميع الخلايا ، وبعد ذلك تكون بعض التدفقات مجانية ولا تفعل شيئًا. يمكن القيام بمزيد من التوازي على GPU عبر CUDA - هناك العديد من الخيارات.

• استخدام هياكل البيانات الكلاسيكية. يرجى ملاحظة - عندما عرضت كودًا زائفًا للحل للونوغرامات الملونة ، لا تعمل وظائف CanInsertColor و PlaceColor على الإطلاق $$$O (1)$ ، على عكس nonograms بالأبيض والأسود. يبدو هذا في برنامج:

 bool OneLineSolver::CanPlaceColor(const vector<int>& cells, int color, int lbound, int rbound) { // Went out of the border if (rbound >= cells.size()) { return false; } // We can paint a block of cells with a certain color if and only if it is // possible for all cells to have this color (that means, if every cell // from the block has color-th bit set to 1) int mask = 1 << color; for (int i = lbound; i <= rbound; ++i) { if (!(cells[i] & mask)) { return false; } } return true; } void OneLineSolver::SetPlaceColor(int color, int lbound, int rbound) { // Every cell from the block now can have this color for (int i = lbound; i <= rbound; ++i) { result_cells_[i] |= (1 << color); } } 

أي أنه يعمل من أجل الخط $$$O (N)$ (في وقت لاحق سيكون هناك تفسير لمعنى مثل هذا الرمز فقط).

دعونا نرى كيف يمكنك الحصول على أفضل تعقيد. خذ CanPlaceColor . تتحقق هذه الوظيفة من أنه من بين جميع أرقام المتجه في المقطع $$$[lbound، rbound]$ رقم بت $$$color$ تعيين إلى 1. يعادل هذا ، يمكنك أن تأخذ $$$و$ جميع أرقام هذا الجزء وتحقق من رقم البت $$$color$ . باستخدام حقيقة أن العملية $$$و$ تبادلي ، بالإضافة إلى مجموع ، الحد الأدنى / الحد الأقصى ، المنتج ، أو العملية $$$Xor$ ، للعد السريع $$$و$ , . :

1. SQRT-. $$$O(\sqrt{N})$ , $$$O(\sqrt{N})$ . .
2. . $$$O(N\log{N})$ , $$$O(\log{N})$ . .
3. (Sparse Table). $$$O(N\log{N})$ , $$$O(1)$ . .

, - ( $$$O(N)$ , $$$O(1)$ ) , , , $$$\ varphi$ , $$$\varphi(\alpha, \beta) \in \{\alpha, \beta\}$ , — (, ...)

SetPlaceColor . . SQRT- ( " "). - .

- — .

, — , ? :

1. . $$$\log$ , , — ( magic number , ). , $$$N=10^{5}$ , $$$O(N^2)$ 10 , $$$O(N\log{N})$ 0.150 , $$$N$ , . , ( ): $$$O(N\sqrt{N})$ versus $$$O(N\log^2{N})$ . $$$N$ ( ) — 15-30.
2. , .

— , - — $$$N$ , . , ~25% ~11% , . - , , , .

— , . .

• . , , - . : , , "" ? , , ! . , .
• (, 1337 1000x1000) . std::bitset , — , .

, . "" . , C++ ( rope , ), hashtable , 3-6 / 4-10 /, unordered_map. , boost.

ROFL Omitting Format Language

, , , -.

ROFL — , "GNU's Not Unix". , , , , , . Omitting — (, , : — ).

, Matroska — 4 [52][4F][46][4C], , , , 3 , — , .

, MIT, — , .

GitHub . , , (, ). Magick++ args .

, ( ). nonograms.ru , , .

nonograms.ru .. KyberPrizrak , , , ! nonograms.ru, .

.