Combinatorics, C ++ และการเพิ่มประสิทธิภาพ

Question

หมายเหตุ: ฉันมีวิธีแก้ปัญหาที่ใช้งานได้คำถามของฉันเกี่ยวกับการเพิ่มประสิทธิภาพและแนวทางอื่น ๆ

คำอธิบายปัญหา

สวัสดีฉันอีกครั้งการเขียนโปรแกรมเดิมที่ผมทำที่แก้nonograms ในการแก้ปัญหาฉันสร้างอาร์เรย์ (สำหรับบางบรรทัด) อาร์เรย์ของวิธีที่เป็นไปได้ทั้งหมดเพื่อให้พอดีกับตัวเลข

ฉันต้องการสร้างโค้ดชิ้นหนึ่งซึ่งจะวนซ้ำตำแหน่งทั้งหมดที่ฉันสามารถใส่ช่องว่างได้ตัวอย่างเช่นหากมีเส้นที่มีขนาด5และตัวเลข1, 1มีหลายวิธีในการเรียงลำดับตัวเลขเช่น1-1--, 1--1-, 1---1, --1-1, ...( -คือ กล่องสีขาวในขณะที่1จะเป็นสีดำ)

การแจกแจงปัญหา

ดังนั้นหากเราดูตัวอย่างด้านบนเราสามารถอธิบายตัวเลือกได้ดังนี้:

1. ขนาดทั้งหมดคือ 5 และเรามีสองกล่อง1ดังนั้นเราจึงมี2กล่องสีขาวให้เล่น (1 ต้องอยู่ระหว่างตัวเลข) ฉันมีฟังก์ชันอื่นที่คำนวณ "พื้นที่ว่าง" นั้น

2. เราสามารถดัชนีสถานที่เป็นไปได้สำหรับช่องว่างทางนี้หมายถึงช่องว่างสามารถไปในแต่ละ[0] 1 [1] 1 [2][indexes]

3. ตัวเลือกทั้งหมดของการวางช่องว่างสามารถแก้ไขได้ด้วยการวนซ้ำแบบซ้อนกัน แต่เนื่องจาก "พื้นที่ว่าง" และดัชนีที่เป็นไปได้นั้นเป็นแบบไดนามิกจึงไม่ใช่ตัวเลือก

4. สำหรับวิธีแก้ปัญหาฉันพยายามสร้างลูปที่ซ้อนกัน "ไดนามิก" โดยมีช่วงและความลึกใด ๆ คำถามคือ:

มีวิธีที่มีประสิทธิภาพมากกว่านี้หรือไม่?

แนวทางแก้ไขที่เป็นไปได้

ขอบเขตที่คำถามของฉันอ้างถึงไม่เกี่ยวข้องกับการแก้ nonorgram หรือแม้แต่ภาษาใดภาษาหนึ่งโดยเฉพาะ แต่เนื่องจากฉันเขียนสิ่งนี้ใน C ++ ฉันจะโพสต์ความพยายามของฉันสำหรับรหัสที่ทำเช่นนั้น:

#include <vector>
#include <iostream>

using namespace std;

int main() {
    int iterators_number = 3; // Number of iterators, bubble sort for example uses 2, note: this is not for bubble sorting.
    int iterators_range = 3; // The maximum value for the iterators values, can be the size of the array for example.
    int move_index;

    vector<int> options_iteration(iterators_number, 0);

    while (true) {
        for (int i = 0; i < iterators_number; i++) cout << options_iteration[i] << " ";
        cout << endl;

        for (move_index = iterators_number - 1;
             (move_index >= 0) && (options_iteration[move_index] > iterators_range - 1); move_index--);
        if (move_index < 0) break;
        int new_value = options_iteration[move_index] + 1;
        for (; move_index < iterators_number; move_index++) options_iteration[move_index] = new_value;
    }

    return 0;
}

เอาท์พุต:

0 0 0 
0 0 1 
0 0 2 
0 0 3 
0 1 1 
0 1 2 
0 1 3 
0 2 2 
0 2 3 
0 3 3 
1 1 1 
1 1 2 
1 1 3 
1 2 2 
1 2 3 
1 3 3 
2 2 2 
2 2 3 
2 3 3 
3 3 3 

ถ้าใครมีความสนใจในการดำเนินการเมื่อมีการทำและเอกสารครบถ้วนผมจะอัปโหลดไปยังฉันบัญชี GitHub

ขอบคุณล่วงหน้าสำหรับผู้ช่วยเหลือและผู้แสดงความคิดเห็น

Answer 1

ข้อสังเกตโดยรวม

ยิ่งคุณใส่รหัสมากเท่าไหร่คุณก็จะได้รับบทวิจารณ์ที่ดีขึ้นเท่านั้น มีข้อความ 2 ข้อความ 1 ในคำถามและ 1 ในความคิดเห็นหลังจากคำถามที่เกือบจะทำให้มันไม่ตรงประเด็นสำหรับไซต์ Code Review:

1. ... my real code does not print for each iteration, this is for easy testing.
2. I have another function that calculates that "free space".

ตามที่ระบุไว้ในคำถามโค้ดแทบไม่สามารถอ่านได้ดังนั้นจึงเป็นปัญหาในการบำรุงรักษา ถ้าฉันเป็นครูที่ให้คะแนนรหัสนี้เป็นเกรดที่ดีที่สุดฉันจะให้ได้คือ C (70%) เพราะมันรวบรวมและรัน ชื่อตัวแปรมีความหมาย ในสภาพแวดล้อมที่เป็นมืออาชีพหากฉันเป็นผู้จัดการของคุณเราจะคุยกันเป็นการส่วนตัวเป็นเวลานานว่าเหตุใดการทำให้โค้ดอ่านง่ายขึ้นจึงเป็นเรื่องสำคัญ

ในสภาพแวดล้อมแบบมืออาชีพคุณไม่น่าจะเป็นคนเดียวที่ดูแลรักษาโค้ดด้วยเหตุผลหลายประการ:

1. คุณอาจได้รับการเลื่อนตำแหน่งและไม่ได้รับมอบหมายให้ดูแลรหัสอีกต่อไป
2. คุณอาจลาออกและได้งานอื่น
3. ข้อบกพร่องอาจมีอยู่ในโค้ดที่ต้องได้รับการแก้ไขและคุณได้รับมอบหมายให้กับโปรเจ็กต์ที่มีลำดับความสำคัญสูงกว่าเพื่อให้คนอื่นได้รับมอบหมายให้แก้ไขโค้ด

มีเหตุผลมากกว่า 3 ข้อข้างต้น ด้วยเหตุผลทั้งหมดนี้ฉันจะพูดถึงรูปแบบการเข้ารหัสที่นี่

การเพิ่มประสิทธิภาพที่เป็นไปได้

กฎข้อแรกของการเพิ่มประสิทธิภาพคืออย่าปรับให้เหมาะสมอย่างที่สองคือค้นหาคอขวดทั้งหมดในโค้ด (คอขวดเป็นฟังก์ชันที่ทำให้โค้ดช้าลง) วิธีหลักในการปรับโค้ด C ++ ให้เหมาะสมคือการใช้การเพิ่มประสิทธิภาพคอมไพเลอร์ในตัวโดยใช้บรรทัดคำสั่งคอมไพเลอร์ -O ถึง -O3 โดยทั่วไปจะสร้างโค้ดที่รวดเร็วมาก จะเป็นการยากมากที่จะจัดเตรียมการเพิ่มประสิทธิภาพสำหรับโค้ดนี้ตามที่นำเสนอในปัจจุบัน แต่ถ้าคุณกำลังรวบรวมเพื่อดีบักการเพิ่มประสิทธิภาพที่เป็นไปได้อย่างใดอย่างหนึ่งอาจเป็นการใช้ตัววนซ้ำ C ++ ที่มีให้สำหรับแต่ละคลาสของคอนเทนเนอร์เช่นvector.

คุณอาจต้องการสร้างตัวแปรiterators_numberและiterators_rangeค่าคงที่เนื่องจากไม่เปลี่ยนแปลง

    const int iterators_number = 3;
    const int iterators_range = 3;

หลีกเลี่ยง using namespace std;

หากคุณเขียนโค้ดอย่างมืออาชีพคุณอาจจะต้องเลิกใช้using namespace std;คำสั่งดังกล่าว โค้ดจะกำหนดได้ชัดเจนยิ่งขึ้นว่าcoutมาจากไหนและตัวระบุอื่น ๆ ( std::cin, std::cout) เมื่อคุณเริ่มใช้เนมสเปซในโค้ดของคุณจะเป็นการดีกว่าที่จะระบุว่าแต่ละฟังก์ชันมาจากที่ใดเนื่องจากอาจมีการชนกันของชื่อฟังก์ชันจากเนมสเปซที่ต่างกัน ตัวระบุที่coutคุณสามารถแทนที่ภายในชั้นเรียนของคุณเองและคุณอาจแทนที่ตัวดำเนินการ<<ในชั้นเรียนของคุณเองได้เช่นกัน นี้คำถามที่แตกล้นกล่าวถึงนี้ในรายละเอียดมากขึ้น

ประกาศตัวแปรตามความจำเป็น

เท่าที่ฉันสามารถบอกได้ว่าตัวแปรmove_indexไม่จำเป็นต้องรักษาค่าระหว่างการวนซ้ำwhile (true)ดังนั้นจึงควรประกาศภายในลูปการประกาศควรรวมการเริ่มต้นของตัวแปรในเกือบทุกกรณี แต่ในกรณีนี้แน่นอน

อย่าใช้ One line forLoops หรือifStatements

รหัสประกอบด้วยบรรทัดนี้:

        for (int i = 0; i < iterators_number; i++) cout << options_iteration[i] << " ";

ในครั้งแรกที่ฉันใช้รหัสฉันพลาดข้อเท็จจริงที่ว่า for loop มีการดำเนินการ รหัสนี้ควรมีอย่างน้อย 2 บรรทัด แต่ควรเป็น 4. 2 บรรทัด:

        for (int i = 0; i < iterators_number; i++)
            cout << options_iteration[i] << " ";

ทำไมต้อง 4 บรรทัด? หนึ่งในข้อผิดพลาดที่ง่ายที่สุดในการรักษาโค้ดคือการเพิ่มคำสั่งลงในคำสั่ง for loop หรือ if โดยไม่ต้องเพิ่มวงเล็บปีกกาที่จำเป็นเพื่อให้เป็นส่วนหนึ่งของลูป ดังนั้นเมื่อสร้างรหัสใหม่ควรเพิ่มเพื่อเริ่มต้นด้วย:

        for (int i = 0; i < iterators_number; i++)
        {
            std::cout << options_iteration[i] << " ";
        }

ฉันไม่ได้คิดสิ่งนี้ขึ้นมามันถูกบังคับโดยมาตรฐานการเข้ารหัสของ บริษัท อย่างไรก็ตามฉันเห็นคุณค่าของมันที่ทำผิดพลาดแบบนั้นหลายครั้ง

รหัสรุ่นนี้ยาวกว่าเล็กน้อย แต่ Muc อ่านง่ายกว่าและดูแลรักษาง่ายกว่า:

#include <vector>
#include <iostream>

int main() {
    int iterators_number = 3; // Number of iterators, bubble sort for example uses 2, note: this is not for bubble sorting.
    int iterators_range = 3; // The maximum value for the iterators values, can be the size of the array for example.

    std::vector<int> options_iteration(iterators_number, 0);

    while (true) {
        for (int i = 0; i < iterators_number; i++)
        {
            std::cout << options_iteration[i] << " ";
        }
        std::cout << std::endl;

        int move_index = iterators_number - 1;
        for ( ;
            (move_index >= 0) && (options_iteration[move_index] > iterators_range - 1);
            move_index--)
            ;
        if (move_index < 0)
            break;

        int new_value = options_iteration[move_index] + 1;
        for ( ; move_index < iterators_number; move_index++)
        {
            options_iteration[move_index] = new_value;
        }
    }

    return 0;
}