Besten Weg durch Pyramide finden
-
Timon Paßlick schrieb:
Ich hab ne Frage: In Zeile 37 geht line ja eigentlich out of scope. Verlängert move() die Lebenszeit oder müsste line static sein?
line geht in Zeile 38 (eine nach 37) out of scope, nämlich mit der
}
. Move verlängert keine Lebenszeit und da muss auch nichts static sein.Ich möchte mit dem move nur eine Kopie des Line-Vectors sparen. Nach dem
move(line)
darf ich mit dem line-Objekt praktisch außer löschen (und neu zuweisen) nichts mehr machen. Und in Zeile 38 wird gelöscht. Also alles gut.
-
Das heißt, dein vector hat Elemente, die out of scope sind, das macht aber nichts?
-
Timon Paßlick schrieb:
Das heißt, dein vector hat Elemente, die out of scope sind, das macht aber nichts?
Hä? Verstehe die Frage nicht.
-
Hat sich erledigt, habe die Referenz zu move() durchgelesen.
War tatsächlich alles in Ordnung.
-
Habe max_path_value() ein wenig optimiert:
int max_path_value(vector< vector<int> > pyramid) { // call by value to modify pyramid for (size_t line = pyramid.size() - 2; line <= pyramid.size() - 1; --line) for (size_t col = 0; col != pyramid[line].size(); ++col) pyramid[line][col] += max(pyramid[line + 1][col], pyramid[line + 1][col + 1]); return pyramid[0][0]; }
Ich geh einfach von unten nach oben und spar damit Rechenaufwand. Cool, oder?
-
Habe jetzt den SoloLearn Eintrag geändert und euch Credits gegeben:
https://code.sololearn.com/cllzC9Lc4Evg/?ref=app#cpp
-
So ein Müll, jetzt hab ich wieder ne Speicherzugriffsverletzung:
/* Challenge: 'The Golden Mountain' At one international Olympiad in Informatics, the following task was given. Let's solve it! 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 The figure shows an example of a triangle of numbers. Write a program that calculates the largest sum of numbers through which the path starts, starting at the top and ending somewhere on the bottom. Each step can go diagonally down to the right or diagonally to the left. In the example - this is the path 7 -> 3 -> 8 -> 7 -> 5, given a max amount of 30. */ /* This code was created together with some friendly people of the German C++ forum (particularly a user called wob): https://www.c-plusplus.net/forum/345800-full */ #include <algorithm> #include <iostream> #include <sstream> #include <vector> using namespace std; struct path { int value; vector<int> data; void print(ostream &os, const vector< vector<int> > &pyramid) const { os << value << ": "; for (int i = data.size() - 1; i > 0; ++i) os << pyramid[i][data[i]] << " -> "; os << pyramid[0][data[0]] << endl; /* os << value << ": "; const auto last_elem_idx = data.size() - 1; for (int i = 0; i < last_elem_idx; ++i) os << pyramid[i][data[i]] << " -> "; os << pyramid[last_elem_idx][data[last_elem_idx]] << endl; */ } }; vector< vector<int> > read_pyramid(istream &is) { vector< vector<int> > result; while (true) { vector<int> line; for (int i = 0; i <= result.size(); ++i) { int n; if (!(is >> n)) { if (!line.empty()) cout << "The last line is not complete and therefore ignored." << endl; return result; } line.push_back(n); } result.push_back(move(line)); } } void dfs_internal(const vector< vector<int> > pyramid, path &p, vector<path> &best_paths) { if (p.data.size() < pyramid.size()) { int left = p.data.empty() ? 0 : p.data.back(); auto line = p.data.size(); p.data.push_back(left); p.value += pyramid[line][left]; dfs_internal(pyramid, p, best_paths); ++p.data.back(); p.value += pyramid[line][left + 1] - pyramid[line][left]; dfs_internal(pyramid, p, best_paths); p.value -= pyramid[line][left + 1]; p.data.pop_back(); } else if (best_paths.empty() || p.value == best_paths.front().value) best_paths.push_back(p); else if (p.value > best_paths.front().value) { best_paths.clear(); best_paths.push_back(p); } } vector<path> dfs(const vector< vector<int> > &pyramid) { vector<path> best_paths; if (!pyramid.empty()) { path p = { pyramid[0][0],{ 0 } }; dfs_internal(pyramid, p, best_paths); } return best_paths; } path best_path(const vector< vector<int> > &pyramid) { vector<path> good; for (int i = 0; i != pyramid.back().size(); ++i) good.push_back(path{ pyramid.back()[i],{ i } }); for (int line = pyramid.size() - 2; line >= 0; --line) { vector<path> newgood; for (int col = 0; col != pyramid[line].size(); ++col) { auto right_path = (good[col].value > good[col + 1].value) ? good[col] : good[col + 1]; right_path.value += pyramid[line][col]; right_path.data.push_back(col); newgood.push_back(right_path); } good = newgood; } return good[0]; } int max_path_value(vector< vector<int> > pyramid) { // call by value to modify pyramid for (int line = pyramid.size() - 2; line >= 0; --line) for (int col = 0; col != pyramid[line].size(); ++col) pyramid[line][col] += max(pyramid[line + 1][col], pyramid[line + 1][col + 1]); return pyramid[0][0]; } int main() { stringstream testinput( " 1 " " 1 3 " " 3 9 2 " " 9 1 1 1 " ); stringstream testinput2( " 7 " " 3 8 " " 8 1 0 " " 2 7 4 4 " " 4 5 2 6 5 " ); auto pyramid = read_pyramid(testinput); // change to "read_pyramid(cin)" for custom input cout << "max_path_value = " << max_path_value(pyramid) << '\n'; auto best = best_path(pyramid); best.print(cout, pyramid); /*auto best_paths = dfs(pyramid); for (const auto &path : best_paths) path.print(cout, pyramid);*/ }
-
Stimmt, von unten nach oben ist es deutlich kürzer, aber praktisch nicht schneller.
Um schneller zu werden, muss man die Kopie vermeiden. Zum Beispiel so:
int max_path_value_no_copy(const vector<vector<int>> &pyramid) { vector<int> workline(pyramid.back()); for (size_t line = pyramid.size() - 2; line != (size_t) -1; --line) for (size_t col = 0; col != pyramid[line].size(); ++col) workline[col] = pyramid[line][col] + max(workline[col], workline[col + 1]); return workline[0]; }
Ich habe es mal gebenchmarkt:
----------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------- BM_MPV/8 581 ns 581 ns 1223745 BM_MPV/64 5938 ns 5937 ns 117898 BM_MPV/512 221748 ns 221722 ns 3200 BM_MPV/1024 1135833 ns 1135691 ns 617 BM_MPV2/8 552 ns 552 ns 1273185 BM_MPV2/64 5911 ns 5910 ns 119182 BM_MPV2/512 220894 ns 220866 ns 3180 BM_MPV2/1024 1201114 ns 1200935 ns 582 BM_MPV_NO_COPY/8 90 ns 90 ns 7887087 BM_MPV_NO_COPY/64 1224 ns 1224 ns 582609 BM_MPV_NO_COPY/512 54624 ns 54618 ns 12835 BM_MPV_NO_COPY/1024 264116 ns 264087 ns 2591
MPV ist mein Original, MPV2 deine Modifizierung von unten nach oben und NO_COPY spricht für sich
-
Timon Paßlick schrieb:
So ein Müll, jetzt hab ich wieder ne Speicherzugriffsverletzung
Vielleicht solltest du mal einen Debugger nutzen?
Deine Loop im Print sieht falsch aus:
for (int i = data.size() - 1; i > 0; ++i)
Im 2. Durchlauf ist i gleich der size und dann kracht es.
-
NO_COPY ist ja wirklich extrem kürzer.
-
Habe noch die Pfadsuche mit der workline implementiert, bin mir aber nicht sicher, wie effektiv das ist:
/* Challenge: 'The Golden Mountain' At one international Olympiad in Informatics, the following task was given. Let's solve it! 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 The figure shows an example of a triangle of numbers. Write a program that calculates the largest sum of numbers through which the path starts, starting at the top and ending somewhere on the bottom. Each step can go diagonally down to the right or diagonally to the left. In the example - this is the path 7 -> 3 -> 8 -> 7 -> 5, given a max amount of 30. */ /* This code was created together with some friendly people of the German C++ forum (particularly a user called wob): https://www.c-plusplus.net/forum/345800-full */ #include <algorithm> #include <iostream> #include <sstream> #include <vector> using namespace std; struct path { int value; vector<int> data; void print(ostream &os) const { if (data.empty()) { os << "0: empty" << endl; return; } os << value << ": "; for (size_t i = data.size() - 1; i != 0; --i) os << data[i] << " -> "; os << data[0] << endl; } }; vector< vector<int> > read_pyramid(istream &is) { vector< vector<int> > result; while (true) { vector<int> line; for (int i = 0; i <= result.size(); ++i) { int n; if (!(is >> n)) { if (!line.empty()) cout << "The last line is not complete and therefore ignored." << endl; return result; } line.push_back(n); } result.push_back(move(line)); } } // returns the top most left best path path best_path(const vector< vector<int> > &pyramid) { if (pyramid.empty()) return path{ 0,{} }; if (pyramid.size() == 1) return path{ pyramid[0][0],{ pyramid[0][0] } }; vector<path> workline(pyramid.back().size()); for (int i = 0; i != workline.size(); ++i) workline[i] = path{ pyramid.back()[i],{} }; for (size_t line = pyramid.size() - 2; line != size_t(-1); --line) for (int col = 0; col != line + 1; ++col) { auto right_col = (workline[col].value >= workline[col + 1].value) ? col : col + 1; workline[col].value = pyramid[line][col] + workline[right_col].value; workline[col].data = workline[right_col].data; workline[col].data.push_back(pyramid[line + 1][right_col]); } workline[0].data.push_back(pyramid[0][0]); return workline[0]; } int max_path_value(const vector< vector<int> > &pyramid) { if (pyramid.empty()) return 0; if (pyramid.size() == 1) return pyramid[0][0]; vector<int> workline(pyramid.back()); for (size_t line = pyramid.size() - 2; line != size_t(-1); --line) for (size_t col = 0; col != pyramid[line].size(); ++col) workline[col] = pyramid[line][col] + max(workline[col], workline[col + 1]); return workline[0]; } int main() { stringstream testinput1( " 1 " " 1 3 " " 3 9 2 " " 9 1 1 1 " ); stringstream testinput2( " 7 " " 3 8 " " 8 1 0 " " 2 7 4 4 " " 4 5 2 6 5 " ); auto pyramid = read_pyramid(testinput1); // change to "read_pyramid(cin)" for custom input cout << "max_path_value = " << max_path_value(pyramid) << '\n'; auto best = best_path(pyramid); best.print(cout); }