MCPcopy Create free account
hub / github.com/apache/arrow / FindDifferences

Function FindDifferences

cpp/src/parquet/chunker_internal_test.cc:439–521  ·  view source on GitHub ↗

* Finds the differences between two sequences of chunk lengths or sizes. * Uses a longest common subsequence algorithm to identify matching elements * and extract the differences between the sequences. * * @param first The first sequence of chunk values * @param second The second sequence of chunk values * @return A vector of differences, where each difference is a pair of * subsequ

Source from the content-addressed store, hash-verified

437 * subsequences (one from each input) that differ
438 */
439std::vector<ChunkDiff> FindDifferences(const ChunkList& first, const ChunkList& second) {
440 // Compute the longest common subsequence using dynamic programming
441 size_t n = first.size(), m = second.size();
442 std::vector<std::vector<size_t>> dp(n + 1, std::vector<size_t>(m + 1, 0));
443
444 // Fill the dynamic programming table
445 for (size_t i = 0; i < n; i++) {
446 for (size_t j = 0; j < m; j++) {
447 if (first[i] == second[j]) {
448 // If current elements match, extend the LCS
449 dp[i + 1][j + 1] = dp[i][j] + 1;
450 } else {
451 // If current elements don't match, take the best option
452 dp[i + 1][j + 1] = std::max(dp[i + 1][j], dp[i][j + 1]);
453 }
454 }
455 }
456
457 // Backtrack through the dynamic programming table to reconstruct the common
458 // parts and their positions in the original sequences
459 std::vector<std::pair<size_t, size_t>> common;
460 for (size_t i = n, j = m; i > 0 && j > 0;) {
461 if (first[i - 1] == second[j - 1]) {
462 // Found a common element, add to common list
463 common.emplace_back(i - 1, j - 1);
464 i--, j--;
465 } else if (dp[i - 1][j] >= dp[i][j - 1]) {
466 // Move in the direction of the larger LCS value
467 i--;
468 } else {
469 j--;
470 }
471 }
472 // Reverse to get indices in ascending order
473 std::reverse(common.begin(), common.end());
474
475 // Build the differences by finding sequences between common elements
476 std::vector<ChunkDiff> result;
477 size_t last_i = 0, last_j = 0;
478 for (auto& c : common) {
479 auto ci = c.first;
480 auto cj = c.second;
481 // If there's a gap between the last common element and this one,
482 // record the difference
483 if (ci > last_i || cj > last_j) {
484 result.push_back({{first.begin() + last_i, first.begin() + ci},
485 {second.begin() + last_j, second.begin() + cj}});
486 }
487 // Move past this common element
488 last_i = ci + 1;
489 last_j = cj + 1;
490 }
491
492 // Handle any remaining elements after the last common element
493 if (last_i < n || last_j < m) {
494 result.push_back(
495 {{first.begin() + last_i, first.end()}, {second.begin() + last_j, second.end()}});
496 }

Callers 2

TESTFunction · 0.85

Calls 7

emplace_backMethod · 0.80
push_backMethod · 0.80
backMethod · 0.80
sizeMethod · 0.45
beginMethod · 0.45
endMethod · 0.45
emptyMethod · 0.45

Tested by

no test coverage detected