Here are a few 'hacks' to speed up Sudoku Explainer (SE).
In the Patterns Game, a lot of time is spent re-rating puzzles for submission, so saving a few milliseconds here and there eventually accumulate to seconds, minutes (maybe hours!)...
The source to SE (1.2.1) was posted by rjamil here.
The serate code (1.2.1.3) can be downloaded from here.
1.
Remove the GUI bits (if using SE to rate puzzles only).
2.
Comment out all the 'assert' statements in the code, code changes required.
3.
Remove the puzzle 'checks' stuff (the puzzle is already a valid submission!), code changes required.
4.
Flatten the directory structure (i.e. ALL files in /sudoku), lots of code changes required.
5.
Remove other GUI bits (htmls, gifs), even GUI specific source and code (mostly html stuff).
6. Finally,
Remove all comments. Build. Obfuscate the jar file!
7. Testing
Use puzzles from a Patterns Game. Run thru once with vanilla SE. Verify that custom SE produces the same ratings.
[Edit 10 Aug] If the GUI is required, then the directory structure cannot be flattened.
.
Speeding up Sudoku Explainer
7 posts
• Page 1 of 1
Speeding up Sudoku Explainer
by 1to9only » Mon Aug 05, 2019 9:24 am
Last edited by 1to9only on Sat Aug 10, 2019 4:26 pm, edited 1 time in total.
-
1to9only - Posts: 4177
- Joined: 04 April 2018
Re: Speeding up Sudoku Explainer
by 1to9only » Mon Aug 05, 2019 9:25 am
These are changes made in SukakuExplainer here, but can be applied to SudokuExplainer to speed up serate of puzzles that contain chains.
1. In Chaining.java and ChainingHint.java
Comment out all 'assert' statements.
2. In Chaining.java
Move the cardinality assignment line:
to AFTER the if statement:
There are 2 of these, in methods getLoopHintList(...) and getMultipleChainsHintList(...).
3. In Chaining.java
Find and comment out these 4 lines:
This is the closing brace to the previous if statement.
4. In Chaining.java, in method getOffToOn(...)
Replace these lines:
with this line:
.
1. In Chaining.java and ChainingHint.java
Comment out all 'assert' statements.
2. In Chaining.java
Move the cardinality assignment line:
- Code: Select all
int cardinality = cell.getPotentialValues().cardinality();
if (cell.getValue() == 0) { // the cell is empty
to AFTER the if statement:
- Code: Select all
if (cell.getValue() == 0) { // the cell is empty
int cardinality = cell.getPotentialValues().cardinality();
There are 2 of these, in methods getLoopHintList(...) and getMultipleChainsHintList(...).
3. In Chaining.java
Find and comment out these 4 lines:
- Code: Select all
if (length >= 1) // Seems this can be removed!
- Code: Select all
if (length >= 1) // Seems this can be removed
- Code: Select all
if (!isParent(p, pOff)) { // Why this filter? (seems useless)
- Code: Select all
}
This is the closing brace to the previous if statement.
4. In Chaining.java, in method getOffToOn(...)
Replace these lines:
- Code: Select all
// Second rule: if there is only two positions for this potential, the other one gets on
List<Class<? extends Grid.Region>> partTypes = new ArrayList<Class<? extends Grid.Region>>(3);
partTypes.add(Grid.Block.class);
partTypes.add(Grid.Row.class);
partTypes.add(Grid.Column.class);
for (Class<? extends Grid.Region> partType : partTypes) {
with this line:
- Code: Select all
for (Class<? extends Grid.Region> partType : grid.getRegionTypes()) {
.
Last edited by 1to9only on Mon Aug 05, 2019 10:32 am, edited 1 time in total.
-
1to9only - Posts: 4177
- Joined: 04 April 2018
Re: Speeding up Sudoku Explainer
by 1to9only » Mon Aug 05, 2019 9:25 am
These 'hacks' are to remove code that are not needed for the serate process, and/or to extract more speed from SE serate.
1.
If the GUI has been removed, then the following can also be removed: Asker.java, Settings.java, SolvingTechnique.java, Tester.java, WarningHint.java, WarningHintProducer.java
Code changes are required to: Cell.java, Grid.java, Solver.java. In Solver.java, 'most' of the code can be commented out.
In Solver.java, in method getDifficulty(), the 'try' statement(s) can be commented out. The 'want' statements can be commented out if the feature ie not used.
2.
In CommonTuples.java, this is in method searchCommonTupleLight(...):
modify this to match similar code in method searchCommonTuple(...):
3.
In Chaining.java, there are a number of calls to initialize a new Potential class, e.g.
The String concatenation is wasted milliseconds, modify the string (which I've tried), or make the String empty or even null (which I've not tried!).
[Edit 10 Aug] 1-3.
.
1.
If the GUI has been removed, then the following can also be removed: Asker.java, Settings.java, SolvingTechnique.java, Tester.java, WarningHint.java, WarningHintProducer.java
Code changes are required to: Cell.java, Grid.java, Solver.java. In Solver.java, 'most' of the code can be commented out.
In Solver.java, in method getDifficulty(), the 'try' statement(s) can be commented out. The 'want' statements can be commented out if the feature ie not used.
2.
In CommonTuples.java, this is in method searchCommonTupleLight(...):
- Code: Select all
result.or(candidate);
if (candidate.cardinality() == 0)
return null;
modify this to match similar code in method searchCommonTuple(...):
- Code: Select all
if (candidate.cardinality() <= 1)
return null;
result.or(candidate);
3.
In Chaining.java, there are a number of calls to initialize a new Potential class, e.g.
- Code: Select all
result.add(new Potential(cell, p.value, false, p,
getRegionCause(region),
"the value can occur only once in the " + region.toString()));
The String concatenation is wasted milliseconds, modify the string (which I've tried), or make the String empty or even null (which I've not tried!).
[Edit 10 Aug] 1-3.
.
Last edited by 1to9only on Sat Aug 10, 2019 4:36 pm, edited 1 time in total.
-
1to9only - Posts: 4177
- Joined: 04 April 2018
Re: Speeding up Sudoku Explainer
by dobrichev » Mon Aug 05, 2019 2:46 pm
In diuf/sudoku/solver/rules/chaining/Chaining.java, protected List<ChainingHint> getHintList(Grid grid)
takes many minutes to sort a list of size ~18000.
Precomputing getDifficulty() and getComplexity() on a single pass should improve this.
This returns me back to the question why we don't share a single code repository for all these changes. Surely there are reasons, but can't we avoid some of them doing our life easier?
Update: With Nested Multiple Chains enabled, the same piece of code crashed the process after ~5% of the hint collection was performed on a really hard pencilmark-only puzzle.
- Code: Select all
Collections.sort(result, new Comparator<ChainingHint>() {
public int compare(ChainingHint h1, ChainingHint h2) {
double d1 = h1.getDifficulty();
double d2 = h2.getDifficulty();
if (d1 < d2)
return -1;
else if (d1 > d2)
return 1;
int l1 = h1.getComplexity();
int l2 = h2.getComplexity();
if (l1 == l2)
return h1.getSortKey() - h2.getSortKey();
return l1 - l2;
}
});
takes many minutes to sort a list of size ~18000.
Precomputing getDifficulty() and getComplexity() on a single pass should improve this.
This returns me back to the question why we don't share a single code repository for all these changes. Surely there are reasons, but can't we avoid some of them doing our life easier?
Update: With Nested Multiple Chains enabled, the same piece of code crashed the process after ~5% of the hint collection was performed on a really hard pencilmark-only puzzle.
Hidden Text: Show
- dobrichev
- 2016 Supporter
- Posts: 1863
- Joined: 24 May 2010
Re: Speeding up Sudoku Explainer
by 1to9only » Sat Aug 10, 2019 4:49 pm
dobrichev wrote:In diuf/sudoku/solver/rules/chaining/Chaining.java, protected List<ChainingHint> getHintList(Grid grid)
- Code: Select all
Collections.sort(result, new Comparator<ChainingHint>() {
public int compare(ChainingHint h1, ChainingHint h2) {
double d1 = h1.getDifficulty();
double d2 = h2.getDifficulty();
if (d1 < d2)
return -1;
else if (d1 > d2)
return 1;
int l1 = h1.getComplexity();
int l2 = h2.getComplexity();
if (l1 == l2)
return h1.getSortKey() - h2.getSortKey();
return l1 - l2;
}
});
I've tried a variation of this to rate submissions from a previous pattern game - the time savings did not amount to much. Maybe the savings would have been greater in sukaku chains.
When using the option -Xprof to profile the application, over two-thirds of the total time is spent in just two methods - Chaining.getOffToOn and Chaining.getOnToOff :
- Code: Select all
Compiled + native Method
42.4% 32475 + 699 diuf.sudoku.solver.rules.chaining.Chaining.getOffToOn
22.8% 16828 + 1003 diuf.sudoku.solver.rules.chaining.Chaining.getOnToOff
I don't think the 2 methods can be optimised, but maybe the methods they call can be looked at ...
.
-
1to9only - Posts: 4177
- Joined: 04 April 2018
Re: Speeding up Sudoku Explainer
by dobrichev » Sat Aug 10, 2019 6:44 pm
Of course everything can be optimized, even in java.
We must consider:
- the data model - much to do there;
- the number of calls (possible caching for avoiding duplicate calls);
- what you said.
If you read the update of my recent post, one of the causes for the slow sort is the memory pressure. Also the number of comparisons increases faster than O(N), therefore caching the compared keys is a must for larger lists.
We must consider:
- the data model - much to do there;
- the number of calls (possible caching for avoiding duplicate calls);
- what you said.
If you read the update of my recent post, one of the causes for the slow sort is the memory pressure. Also the number of comparisons increases faster than O(N), therefore caching the compared keys is a must for larger lists.
- dobrichev
- 2016 Supporter
- Posts: 1863
- Joined: 24 May 2010
7 posts
• Page 1 of 1
