2
\$\begingroup\$

Below is a simple method which compares contents of two excel files ignoring the line order.

This method is working as expected.

But, one of my peers in their code review mentioned that initializing and using 4 sets for this might not be the best way performance/memory-consumption wise and that the code can be optimized by using lesser number of sets.

I can't figure out how to reduce the number of sets though, to achieve the same functionality.

Do you have any clue and/or suggestions?

Code:

/** Compares contents of two excel files. Ignores line order of the contents.
     * @param logger            Logger instance
     * @param actualFilePath    Actual xlsx file
     * @param baselineFilePath   Baseline xlsx file
     * @return                  true if the files match, false otherwise
     * @throws Exception
     */
    public boolean compareTwoXlsxFilesIgnoreLineOrder(Logger logger, String actualFilePath, String baselineFilePath) throws Exception {
        File baselineFile = new File(baselineFilePath);
        File actualFile = new File(actualFilePath);
        FileInputStream baselineFileStream = null;
        FileInputStream actualFileStream = null;
        XSSFWorkbook baselineWorkbook = null;
        XSSFWorkbook actualWorkbook = null;
        XSSFExcelExtractor baselineExtractor = null;
        XSSFExcelExtractor actualExtractor = null;
        try {
            if (!baselineFile.exists()) {
                logger.severe("FAIL: Could not access the baseline file: " + baselineFile.getPath());
                return false;
            }
            logger.info("baseline file: " + baselineFilePath);
            if (!actualFile.exists()) {
                logger.severe("FAIL: Could not access the actual file: " + actualFile.getPath());
                return false;
            }
            logger.info("Actual file: " + actualFilePath);
            baselineFileStream = new FileInputStream(baselineFile);
            actualFileStream = new FileInputStream(actualFile);
            baselineWorkbook = new XSSFWorkbook(baselineFileStream);
            actualWorkbook = new XSSFWorkbook(actualFileStream);
            baselineExtractor = new XSSFExcelExtractor(baselineWorkbook);
            actualExtractor = new XSSFExcelExtractor(actualWorkbook);
            String baselineFileText = baselineExtractor.getText();
            String actualFileText = actualExtractor.getText();
            //Split by line break, trim whitespaces and remove empty lines.
            Set<String> baselineLinesSet = Arrays.stream(baselineFileText.split("\\r?\\n")).map(String::trim).filter(line -> !line.isEmpty()).collect(Collectors.toSet());
            Set<String> actualLinesSet = Arrays.stream(actualFileText.split("\\r?\\n")).map(String::trim).filter(line -> !line.isEmpty()).collect(Collectors.toSet());
            Set<String> actualMinusbaseline = new HashSet<>(actualLinesSet);
            actualMinusbaseline.removeAll(baselineLinesSet);
            logger.fine("Size of actualMinusbaseline: " + actualMinusbaseline.size());
            Set<String> baselineMinusActual = new HashSet<>(baselineLinesSet);
            baselineMinusActual.removeAll(actualLinesSet);
            logger.fine("Size of baselineMinusActual: " + baselineMinusActual.size());

            if (!actualMinusbaseline.isEmpty() || !baselineMinusActual.isEmpty()) {
                logger.info("FAIL: Lines present in actual file but not in baseline file: " + actualMinusbaseline);
                logger.info("FAIL: Lines present in baseline file but not in actual file: " + baselineMinusActual);
                logger.info("**************** Mismatch info End *******************");
                return false;
            } else {
                logger.info("VERIFIED: Actual file contents match with the baseline file contents.");
                return true;
            }
        } catch (IOException e) {
            logger.severe("Error while comparing files: " + e.getMessage());
            throw e;
        } finally {
            if (baselineExtractor != null) {
                baselineExtractor.close();
            }
            if (actualExtractor != null) {
                actualExtractor.close();
            }
            if (baselineWorkbook != null) {
                baselineWorkbook.close();
            }
            if (actualWorkbook != null) {
                actualWorkbook.close();
            }
            if (baselineFileStream != null) {
                baselineFileStream.close();
            }
            if (actualFileStream != null) {
                actualFileStream.close();
            }
        }
    }
\$\endgroup\$

4 Answers 4

3
\$\begingroup\$

Filtering the line sets while parsing the actualFileText, that is removing from baselineLinesSet the lines contained by actualFileText while also filtering them out from the actualLinesSet, at the end of parsing results two sets containing the difference between each other.

Set<String> baselineLinesSet = Arrays.stream(baselineFileText.split("\\r?\\n"))
                                     .map(String::trim)
                                     .filter(line -> !line.isEmpty())
                                     .collect(Collectors.toSet());

Set<String> actualLinesSet = Arrays.stream(actualFileText.split("\\r?\\n"))
                                   .map(String::trim)
                                   .filter(line -> !line.isEmpty())
                                   .map(line -> { 
                                        if (baselineLinesSet.remove(line)) {
                                            return null;
                                        } else {
                                            return line; 
                                        }
                                    })
                                   .filter(line -> line != null)
                                   .collect(Collectors.toSet());


if ( actualLinesSet.size() == 0 && baselineLinesSet.size() == 0 ) {
    
    . . .

    return true;
} else {
    
    . . .

    return false;
}
\$\endgroup\$
3
  • \$\begingroup\$ Nice approach!. Note that code in streams should not have side effects, and yours does. \$\endgroup\$ Dec 21, 2023 at 6:32
  • \$\begingroup\$ Instead of collecting the lines to a set in the second stream, just find first non-null and return false if anything is found. This lets you stop the processing as soon as you know the files are different instead of always going through every line. \$\endgroup\$ Dec 21, 2023 at 12:34
  • \$\begingroup\$ And going on... to remove one if, use map(line -> baselineLinesSet.remove(line)) to convert the line to a boolean value about whether it existed in baselineLinesSet, filter out all true values and find first false. \$\endgroup\$ Dec 21, 2023 at 12:40
2
\$\begingroup\$

As @J_H pointed out, neither the original code or the accepted answer take into account duplicate lines. Here is a Java version that does not suffer from that issue and will not fail if a hash collisions occurs.

Both files are placed into a priority queue, which provides an efficient way to retrieve values in sorted order. Then just pick the first value from both files and stop if they differ.

PriorityQueue<String> baseline = Arrays
    .stream(baselineFileText.split("\\r?\\n"))
    .map(String::trim)
    .filter(line -> !line.isEmpty())
    .collect(Collectors.toCollection(PriorityQueue::new));

PriorityQueue<String> actual = Arrays
    .stream(actualFileText.split("\\r?\\n"))
    .map(String::trim)
    .filter(line -> !line.isEmpty())
    .collect(Collectors.toCollection(PriorityQueue::new));

if (baseline.size() != actual.size()) 
    return false;
}

while (! baseline.isEmpty()) {
    if (! Objects.equals(baseline.poll, actual.poll()) {
        return false;
    }
}

return true;

This of course can be modified to use hash codes too by adding one line:

    .filter(line -> !line.isEmpty())
    .map(line -> line.hashCode())
    .collect(Collectors.toCollection(PriorityQueue::new));

The performance could be improved by writing a PriorityQueue implementation that constructs the heap from an existing array instead of using the Java standard implementation, which requires adding the values one by one.

The beauty of a priority queues in this compared to two sorted lists is that you don't need to sort the whole file. You only need the lines fully sorted until the first difference occurs. And a priority queue here lets you get away with a lot of unnecessary comparisons.

\$\endgroup\$
2
\$\begingroup\$

If all we care about is Yes / No, without being interested in how contents differ, then an approach that doesn't exploit hashing is an approach that will do more work than necessary. A hash function lets us turn enormous rows into something that is conveniently small, suitable for sorting. Or potentially for placing into a set, though that technique doesn't seem applicable.

compares contents of two excel files ignoring the line order.

The OP code does not appear to implement that specification. Consider a one-row sheet that has cell A1 saying "hello". And a two-row "hello", "hello" sheet. The sheets are not the same (modulo row re-ordering), as we can readily see when we compare the sorted rows. But collapsing values in a HashSet destroys the cardinality information and leads to an incorrect assessment of "identical!" for non-identical sheets.

Here is a memory-efficient approach, in another language.

from collections import Counter
from hashlib import sha3_224
from pathlib import Path
from typing import Generator
import openpyxl
import typer


def hash_spreadsheet(
    in_file: Path, birthday_nybbles: int = 16
) -> Generator[str, None, None]:
    """Turns rows of first sheet into hashes.

    Hang on to a long enough hash prefix to make a birthday collision unlikely;
    64 bits works fine until input sheets start having more than about four billion rows.
    https://en.wikipedia.org/wiki/Birthday_problem
    """
    wb = openpyxl.load_workbook(in_file)
    ws = wb.active
    for row in ws.iter_rows(values_only=True):
        yield sha3_224(str(row).encode()).hexdigest()[:birthday_nybbles]


def identical_sheets_sort(in_file1: Path, in_file2: Path) -> bool:
    """True if the two spreadsheets have the same rows, in any order."""
    hashes1 = " ".join(sorted(hash_spreadsheet(in_file1)))
    hashes2 = " ".join(sorted(hash_spreadsheet(in_file2)))
    return hashes1 == hashes2


def main(in_file1: Path, in_file2: Path) -> None:
    not_ = "" if identical_sheets_sort(in_file1, in_file2) else "n't"
    print(f"The two spreadsheets are{not_} identical.\t", in_file1, in_file2)


if __name__ == "__main__":
    typer.run(main)

But there's no need to suffer the O(N log N) time complexity, when linear O(N) would do, using multisets.

def identical_sheets_multiset(in_file1: Path, in_file2: Path) -> bool:
    """True if the two spreadsheets have the same rows, in any order."""
    hashes = Counter(hash_spreadsheet(in_file1))
    hashes.subtract(hash_spreadsheet(in_file2))
    return sum(map(abs, hashes.values())) == 0
\$\endgroup\$
0
\$\begingroup\$

Wow, that looks like a lot of work! And a lot of memory.

Just export a pair of .CSV's. Then what you're looking for is:

$ sort  < file1.csv  > file1.txt
$ sort  < file2.csv  > file2.txt
$
$ diff -u file{1,2}.txt

(This assumes newlines within cells show up as \n or have otherwise been dealt with, so that records may be handled by line-oriented utilities.)

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Might want to use comm rather than diff to get separate lists of lines present in one file or the other. \$\endgroup\$ Dec 20, 2023 at 9:41
  • 1
    \$\begingroup\$ Downvote. CSV can contain multi-line strings, which will cause this code not to work. You already noted this, so why give this incomplete answer? \$\endgroup\$ Dec 20, 2023 at 13:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.