2
\$\begingroup\$

This is the Hash-Matrix that I used in order to process the matrix for my quadratic sieve algorithm. You can find the full code at here(it's java 7), but I only want you to review this class.

My prime focus is performance and any feedback will be welcome. The entry point is the solve method, you can skip the init part as I didn't put to much thought to it and it might change. Jump strait to where it says: "Start To Solve". I explained this algorithm in more details at here.

public class HashMatrix extends Logger {
    private static final Object CELL = new Object();
    private ArrayList<ConcurrentHashMap<Integer, Object>> columns = new ArrayList<>();
    private ArrayList<ConcurrentHashMap<Integer, Object>> rows = new ArrayList<>();
    private HashMatrix solutionMatrix;
    private ArrayList<VectorData> vectorDatas;

    public ArrayList<ArrayList<VectorData>> solve(ArrayList<VectorData> vectorDatas) {
        this.vectorDatas = vectorDatas;
        init(vectorDatas);
        solutionMatrix = new HashMatrix();
        solutionMatrix.setLogsEnabled(false);
        HashMap<Integer, Object> map = new HashMap<>();
        solutionMatrix.initWith1(Math.max(vectorDatas.size(), vectorDatas.get(0).vector.length));

        forceLog("Starting To Solve");

        for (int i = 0; i < columns.size(); i++) {
            ConcurrentHashMap<Integer, Object> mainColumn = columns.get(i);
            switch (mainColumn.size()){
                case 0:
                    continue;
                case 1:
                    map.put(mainColumn.keySet().iterator().next(), CELL);
                    continue;
            }

            Integer mainRow = null;

            for (Integer row :  mainColumn.keySet()) {
                if (!map.containsKey(row)) {
                    map.put(row, CELL);
                    mainRow = row;
                    break;
                }
            }

            if(mainRow != null){
                for (Integer row :  mainColumn.keySet()) {
                    if(row.equals(mainRow)){
                        continue;
                    }
                    for (Integer column : rows.get(mainRow).keySet()) {
                        xor(row,  column);
                    }
                    solutionMatrix.xorRows(mainRow,  row);
                }
            }
        }

        forceLog("Building solutions");

        ArrayList<ArrayList<VectorData>> solutions = new ArrayList<>();
        for (int i = 0; i < rows.size(); i++) {
            ConcurrentHashMap<Integer, Object> row = rows.get(i);
            if (row.size() == 0) {
                solutions.add(createSolution(i));
            }
        }

        forceLog("Solutions ready");

        return solutions;
    }

    private void xorRows(Integer mainRow, Integer row) {
        for (Integer localColumn : rows.get(mainRow).keySet()) {
            if(localColumn != null){
                xor(row,  localColumn);
            }
        }
    }

    private ArrayList<VectorData> createSolution(int row) {
        ArrayList<VectorData> solution = new ArrayList<>();
        for (Integer cell : solutionMatrix.rows.get(row).keySet()) {
            solution.add(vectorDatas.get(cell));
        }
        return solution;
    }

    private void initWith1(int size) {
        for (int i = 0; i < size; i++) {
            ConcurrentHashMap<Integer, Object> row = new ConcurrentHashMap<>();
            ConcurrentHashMap<Integer, Object> column = new ConcurrentHashMap<>();
            row.put(i, CELL);
            column.put(i, CELL);
            rows.add(row);
            columns.add(column);
        }
    }

    private void init(ArrayList<VectorData> vectorDatas) {
        for (int i = 0; i < vectorDatas.size(); i++) {
            rows.add(new ConcurrentHashMap<Integer, Object>());
        }
        int columnsCount = vectorDatas.get(0).vector.length;
        for (int i = 0; i < columnsCount; i++) {
            columns.add(new ConcurrentHashMap<Integer, Object>());
        }

        for (int row = 0; row < vectorDatas.size(); row++) {
            boolean[] cells = vectorDatas.get(row).vector;
            for (int cell = 0; cell < cells.length; cell++) {
                if (cells[cell]) {
                    add(cell, row);
                }
            }
        }
    }

    private void add(int row, int column) {
        rows.get(column).put(row, CELL);
        columns.get(row).put(column, CELL);
    }

    private void xor(int row, int column) {
        xor(rows.get(row), column);
        xor(columns.get(column), row);
    }

    private void xor(ConcurrentHashMap<Integer, Object> map, Integer cell) {
        if(map.containsKey(cell)){
            map.remove(cell);
        }
        else{
            map.put(cell, CELL);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Are you on Java 8? \$\endgroup\$ – h.j.k. Feb 8 '16 at 13:08
  • 1
    \$\begingroup\$ @h.j.k. I am on Java 7. Do you want me to add some thing java 8 related? \$\endgroup\$ – Ilya Gazman Feb 8 '16 at 13:10
  • \$\begingroup\$ Well, it lets answerers have a better idea of what they can suggest. :) \$\endgroup\$ – h.j.k. Feb 8 '16 at 13:11
1
\$\begingroup\$
public class HashMatrix extends Logger {

That's a nasty smell, which looks like a violation of the principle of preferring composition to inheritance.


    private static final Object CELL = new Object();

What purpose does this serve? I think that it could be eliminated by changing some Maps to Sets, which would make the code easier to read.


    private ArrayList<ConcurrentHashMap<Integer, Object>> columns = new ArrayList<>();
    private ArrayList<ConcurrentHashMap<Integer, Object>> rows = new ArrayList<>();

Why ConcurrentHashMap? The code looks single-threaded. Is this planning ahead for multi-threading?

Also, code to the interface rather than the type. At the very least, the fields should be List<...> rather than ArrayList<...>.


You said to ignore the init, but it really looks to me as though the meaning of this class is unclear. Should it be split into a Matrix class and a Solver class?


There's a mixture of foreach-style loops and indexed for loops which don't appear to use the variable for anything other than a single get at the start. Could they all be foreach loops?

\$\endgroup\$
  • \$\begingroup\$ foreach is more expensive in terms of performance and this all what this algorithm is about. ConcurrentHashMap allows you to modify the entry during the iteration, otherwise I need to create a special array to host the temporary result. I like your idea about matrix and solver, I try to adapt it, but it's out of scope for this question. \$\endgroup\$ – Ilya Gazman Feb 8 '16 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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