✅ Optimizing number matching algorithm for a logical game
Hey, I'm trying to optimize one function from my solver thats is the most performance critical area.
The idea is that I have a grid x by y of numbers 1-9 (0 is an empty cell).
Numbers must be next to each other horizontally, vertically, or diagonally. There can't be any number between them. Distance between the cells has no limit. Find all valid pairs.
I have 2 approaches
1.https://pastecode.io/s/11vo1bcs - this approach first pre-processes the grid to find and store the locations of every number. After this phase, it iterates thru each number's stored positions and checks every possible pair to see if they can be connected. A separate function verifies if the path between two positions is valid.
2. https://pastecode.io/s/gmp701ig checks every cell in the grid. For each cell containing a number, it does a linear search in specific directions (right, down, and two diagonals) to find a matching number. The search stops if a match is found or if the path is blocked by a non-zero number
I compared these 2 approaches on 3 different grids (10 rows, 9 cells)
I've attached image showing the results.
Original_ stands for the first approach and Optimized_ for the second one. Looks like my optimized approach isn't really faster which kinda makes no sense for me cuz it should make less checks, but anyway. Which approach should I choose? Are there better ways to do that? What low level optimizations can I do? I'm trying to push this as far as I can.
Thanks in advance!
45 Replies
I'm trying to work out how your code actually works. What does
Solve return?
(The fact that you've used cryptically short variable names everywhere, and there are no comments, really doesn't help)does your solve function return duplicate pair?
it returns row and column of numbers that can be connected and what number it is
let me rename variables to more human readable
sorry for that, that's how I code when I don't intend to share my code with anyone ;v
"Connected" means that two cells in the same row/column contain the same number, and all the cells between them are empty?
in the same row/column or diagonally
yes
btw a way guarantee O(# of row x # of col) is to use two pointers for scanning
but you would end up with three nested loops
I've updated my code, check new links in the original post
but I'm using two pointers for scanning
Right, I see
Yeah I don't see how the "optimised" version really removes any of the cost. You've just moved the cost around a bit
Is there a limit on the max number of rows/cols?
well, the game that I'm trying to "solve" has 9 cols and infinite rows.
I guess I can write some specific optimizations for that but I also want it to work on any grid
can't decide on that. But I think we can focus on 9 cols and inifnite rows to make it easier I guess
I wonder if there's a way to do this with a single pass through the board
E.g. scan along a row. Whenever you encounter a number, that becomes the "current" number. If you encounter a differetn number, the "current" number changes, if you encounter the same number then that number gets marked as being connected
I can't see how to avoid testing each row/col/diagonal individually there. Maybe there's a smart way
yep, I bet that there is some smart way to do this in O(n), that's why I came here to ask ;p
this is only to find pairs in a given row right?
Actually yeah. If you have an array of the current number for each column, then when you scan along a row, you can update the "current" for each column as you go
Same for diagonals
That should give you O(rows*cols)
yes, so thats why i say you would end up with three nested loops
Argh fucking lab.razor.fyi froze on me
Here we go. This looks like it works for rows and columns: https://paste.mod.gg/sqckmjurfrpq/0
BlazeBin - sqckmjurfrpq
A tool for sharing your source code with the world!
looks compact, I will benchmark this in a sec
Diagonals are doable, just a tad more fiddly. Give me a min
sure thing
there is one more check that I will need to implement later, but for now I'm skipping it
cuz you can also pair the last number of one row with the first number of the next row
you can connect
3 here
but ye, its not important for nowyou can still solve it by two pointers by iterate row by row and pair the first to last or last to first
4 nested loops rn
I've got 2 nested loops
You can do the whole thing in 1 pass
With diagonal support: https://paste.mod.gg/kiggbxhpnpvu/0
BlazeBin - kiggbxhpnpvu
A tool for sharing your source code with the world!
alright, thanks, lets test it
Oops, fixed a bug: https://paste.mod.gg/arlezvqiogcs/0
BlazeBin - arlezvqiogcs
A tool for sharing your source code with the world!
Can you do the same for columns, and for diagonals?
nope, only rows
Heh, that's really easy to support
yep, I just wanted to simplify the problem for now
BlazeBin - ralfnnjwdved
A tool for sharing your source code with the world!
oh u are fast haha
ur approach is faster in all grids
the biggest difference is in super dense grids
(u are A2)
Tbh I'm surprised the difference is that small with the sparse grids
I'd expect the biggest difference in dense grids: that's when you're doing a lot of looping, as you go off searching every time you encounter a number
I have some other small ideas that can optimize it, will test them and see if I can improve
benchamarking takes 4 minutes :OhNo:
Ooh?
[MethodImpl(MethodImplOptions.AggressiveInlining)] on UpdateCurrent
pre-allocate var result = new List<Result>(numRows * numCols);
making Current non-nullablewell, AggressiveInlining doesn't change much
A1 is without it and A2 is with it
Yeah I wouldn't necessarily expect inlining to help much there
numRows * numCols is a fairly arbitrary initial size for result? And I'd expect the cost of adding to result to be completely amortised
Making Current non-nullable could help though, if the number of rows/cols/diagonals is struggling to fit into a cache lineit didnt help, maybe my implementation is stupid
but anyway, I think that its already fast enough. Time to implement the rest of the solver
thanks for help :)
Cool, that was a fun little challenge!
Advent of code teaser
I always like to approach those assuming it can be done in O(n). So you're forced to imagine walking through the grid cell-by-cell, and the question becomes "what information do I need about this cell right now, because I'm not going to be coming back to it?"
Actually I have one more question about time complexity
O(n), n means the number of cells right?
Then isnt O(x * y) the same here?
x - grid width
y - grid height
Yeah, I was taking
n there to be the number of cells
(Actually, I was being very lax, and just using "O(n)" to mean "linear time complexity")
(There's no way that you can solve this without visiting each cell. So searching for anything sub-linear is pointless. So there's nothing n could usefully be which isn't the number of cells)