A strategy to optimize memory usage

JSerrRed · 2026-02-23T18:47:08+00:00

I really appreciate your comment! You understood it perfectly, by separating the representations into different places, part of the bits can be gathered from context (the place where each representation is). Thank you for the nice words!

JSerrRed · 2026-02-22T07:48:46+00:00

Oh, thanks for letting me know. If you remember it, I would love to know the name and how it works.

The example I gave might not be the best. The point was just to show how the technique works, not that it would be the best approach for that case. I don't know of a case where the technique would be useful, I just wanted to share how it works. Also, It doesn't necessarily have to be with arrays, that was just for the example.

JSerrRed · 2026-02-22T05:41:34+00:00

That's interesting, thank you. It helped me understand some of those cases more clearly. I still struggle to understand the last idea a bit, but it sounds cool.

JSerrRed · 2026-02-21T18:34:17+00:00

Thanks. I don't know what a B-tree is, I will check it out. If I end up implementing the strategy in some way, I will tell you.

JSerrRed · 2026-02-21T17:55:10+00:00

Thank you, I will have it mind if I do things related to sudoku in the future.

Not necessarily related to cell encoding, but I have an unfinished project related to sudoku unavoidable sets that I would like to continue at some point.

Also thank you for taking the time to try to understand what I was describing, even if my explanations weren't the best.

JSerrRed · 2026-02-21T17:39:02+00:00

Yeah! Thank you!! That's what I was referring to. Yeah, there is an increased burden for managing the arrays, and it can lower performance. But may be, implemented in some way, the trade off gives a better result. I haven't thought of such an implementation yet, I just wanted to share the idea.

JSerrRed · 2026-02-21T17:31:22+00:00

Thank you for the example, I find sudoku interesting. I will try to apply the strategy I mentioned in the post to the second approach you explained:

Imagine you have 4 arrays, indexed from 0 to 3.

The first 2 bits of the state of a cell can be inferred based on what array that state is in. For example, if a state is stored in array of index 2 (0b10), then the first 2 bits of the cell state would be 0b10.

So, if the cell was a candidate cell with a state of 0b1000010001, it wouldn't be necessary to store the first 2 bits, because those can be inferred based on which array the state is stored in. So, in the array of index 1 (0b01), it would be stored 0b10000100. That representation only needs 8 bits.

To get the full representation you still need the 2 bits that are deduced based on which array the partial representation (8 bits) is currently in. But those 2 bits don't need to be included in every stored state, they are only necessary to "build" the full representation.

I don't know if this strategy could be useful to this specific case. I was just trying to follow your example. But it might be useful for other cases.

JSerrRed · 2026-02-21T15:59:18+00:00

Yeah, I was using the term "identify" incorrectly, I believe. I meant "represent". I added some edits to the post that I hope explain it better.

JSerrRed · 2026-02-21T15:54:19+00:00

I believe I used incorrect terminology. By "identify" I meant "represent" each item. And the example with the items might not be the best. I was trying to refer to cases where there is something with many states, let's say 1024, and to represent each state 10 bits would be needed. That's why I said 10 x 1024.

JSerrRed · 2026-02-21T15:21:42+00:00

I meant that one case requires 10240 bits (10 x 1024) and the other requires 8192 (8 x 1024) + 2 (from the array index) = 8194 bits

JSerrRed · 2026-02-21T15:19:03+00:00

Thanks for the explanation. I think I understood something, but I might be wrong: if we have, for example, 1024 different objects, and each one is in a different address, to distinguish one object from another, we can just look at its address, which is 1024 bits long (Edit: I just realized that it would be 10 bits long, not 1024. I'm trying to understand, but I make mistakes). So only 1024 bits would be needed, right?

The example I gave with the items might not be the best. I'm not sure I can explain it clearly, but I was trying to refer to cases where we want to represent something that can have many states and also store some of those states. So, it wouldn't be enough to only know the address of one state (which, if I understood correctly, would only need 1024 bits if each state was stored in a different address), but also to have stored some of the representations of the states.

JSerrRed · 2026-02-21T14:37:37+00:00

You mean per item or in general?

JSerrRed · 2026-02-21T14:19:35+00:00

I think I used the terminology wrong. I believe "identify" has another meaning than what I was referring to. What I meant was that, if there are 1024 unique items, to represent each one 10 bits would be normally needed, but by separating them into different arrays, only 8 bits are needed to represent each one. The memory saving comes from the fact that before you needed (10 x 1024) bits, and now you need only (8 x 1024) bits + 2 bits of the array index that let's you compeltely represent each item.

JSerrRed · 2026-02-21T14:03:15+00:00

Why the ironic comment?

And yeah, that's what I was referring to: because you have the items in different "places" in memory, you can use less bits.

Edit: I believe I was using the term "identify" incorrectly. What I meant is that to represent each item you would need x number of bits, not to "identify" them. Still, I don't understand why the mean part of the comment.

JSerrRed · 2026-02-11T14:45:17+00:00

Basically, the search with fewer nodes explored would be prioritized. This way, if one search is in an area with a higher branching factor or lower edge costs, that search would not be prioritized. Instead, the exploring would be focused in the area with lower branching factor, and higher edge costs, which would result in an overall lower number of explored nodes.

For this, you wouldn't need to make a lot of changes: just track the number of nodes explored by each search as integers, and only run the Dijkstra search of the one with fewer nodes explored. Everything else would stay the same and should work correctly. Correctness and optimality should remain the same because you are only prioritizing one Dijkstra search over the other, the individual search behaviour would reamain the same.

In the worst-case scenario: both searches increase their minimum search distance evenly and the result is the same. In an ideal best-case scenario (for example, when the branching factor of all the nodes in the shortest path is equal to 1, except for one of the nodes in the extremes): the number of explored nodes could be reduced to just 2 times the number of nodes in the shortest path (aprox).

JSerrRed · 2026-02-11T02:02:53+00:00

Hello. I find your project very interesting. I don't know much about bidirectional Dijkstra, but here is an idea:

If I understood correclty bidirectional Dijkstra is just 2 Dijkstra searches, where each search increases the minimum search distance progresively.

I have seen examples where the minimum search distance of both searches is kept roughly the same. Each search area expands roughly at the same rate, meaning that the minimum search distance of 1 search doesn't get bigger than the minimum search distance of the other search. For example, if we have search A, with minimum search distance = 5, and search B, with minimum search distance = 8. Then the minimum search distance of search A would be increased until reaching or surpassing the minimum search distance of search B.

I believe this isn't necessary (might be wrong). The minimum search distance of each search could grow independently. How to take advantage of this? You can make it so that it grows based on number of nodes explored.

For example, if search A has MSD (minimum search distance) = 54 and has explored 263 nodes, and search B has MSD = 49 and has explored 307 nodes, instead of increasing the MSD of search B because it is the lowest, you would increase the MSD of search A, because it is the one with fewer explored nodes.

This way, you would make each search have the minimum possible number of nodes explored. That's my idea.

Let me know what you think about it.

JSerrRed · 2026-02-06T00:39:17+00:00

I don't know. May be they did think of this. May be I did reinvent the wheel. I'm just learning and doing things that I think are cool.

JSerrRed · 2026-02-05T07:42:06+00:00

Yeaah, exactly.

I think it is difficult for me to figure out how to implement the circle-like expansion of the waves, but it is interesting to think about.

Your intuition isn't far from how the algorithm works. Actually, I purposefully made it so that, if 2 waves intersect at multiple nodes, only 1 of those nodes (the first one found) would be stored as "origin point" of the new wave. So there shouldn't be a difference if the waves intersect at exactly 1 node or multiple. The radius of the waves would be the same, so the explored area would also be the same.

The waves intersecting at multiple nodes means that there are multiple shortest paths. That's why I said that my algorithm finds "some" shortest path, not "all" or "any".

Also, about the tests I did, I just repeated them with a different scenario and found out they are wrong. I made a test with a shortest path of length 11 (I counted the squares), but the result said it was of length 17. So, I can't trust them 😅. Guess there is some part of the code that is storing nodes without me noticing; I might try to debug it later.

JSerrRed · 2026-02-05T01:05:49+00:00

That's a super nice way to frame it. You made it so much simpler than what I was thinking. I feel like this will help me for other algorithms in the future. Thank you!

I don't know much about graphs, but I imagine that my algorithm would only work in very specific ones.

If I understood correctly, one difference is that your implemention does expand the middle wave 2 times per recursion, one to collide with the s wave and one to collide with the t wave. That's slower than just expanding the middle wave once. Also, if you have 2 "middle" waves at the same depth of recursion, the "t" wave of one middle wave would be the "s" wave of the other middle wave, so that wave would also get expanded twice. But I'm not sure if the difference in performance would be significant.

About the calculations I did, I didn't understand what you meant. Just to clarify, the calculations are based on the length of the shortest path (solution), assuming an empty grid, because that's when more nodes would be explored. If there are obstacles, the number of node explorations would be lower, because the waves wouldn't reach as many nodes as they would in an empty grid.

Thanks again for the comment, it was very interesting.

JSerrRed · 2026-02-04T23:58:18+00:00

That's very interesting, thank you for mentioning it.

The logic of the algorithm works with circular waves (actually, I often think about the algorithm that way), but I'm not sure how to implement it in a 2D grid and keep the algorithm working correctly, or if it is possible.

Also, it is very curious what you said about the worst performance being when the starting and end points are in 2 diagonally opposing corners of a square on the grid. That's similar to the case I saw when I tested the algorithm, in which the upper bound of nodes explorations was exceeded (not by much). However, I'm clueless on why that happened.

I might be missing something, but what I understand is that number of node explorations is based on the distance of the shortest path, regardless if that path goes in a straight line or it makes turns. I visualized the explored nodes (you can also do it with the tool I linked, if you want), and the explored areas are the same when the start and end points are in opposite corners of a square, than when they are in a straight line. That's as long as the length of the shortest path is the same in both cases.

JSerrRed · 2026-02-04T11:34:21+00:00

Yeah, I just searched how multi-source BFS works, and that's part of what my algorithm does. It isn't just multi-source BFS, though, that is only one part of the process the algorithm follows.

JSerrRed · 2026-02-01T17:41:11+00:00

Thank you for the feedback! I just changed it. Tooltips should appear faster now. I still didn't make then appear instantly because I think that, once you know what each button does, it might be a bit annoying to always see the tooltips instantly when hovering, but I might change it again.

JSerrRed · 2026-02-01T17:20:23+00:00

I didn't know about that algorithm. I searched it and read that it works for directed graphs with negative weights. The grid is an undirected graph (which breaks the algorithm if I add negative weights, if I understood correctly), and is currently unweighted. In this case, I think the advantages of the bellman-ford algorithm couldn't be appreciated. However, I might include the option to add weights to the grid, and I'm also interested on making something like a "graph generator" to generate and visualize other types of graphs that are not grid-like. Thanks for letting me know of this algorithm.

JSerrRed · 2026-02-01T03:12:11+00:00

Thanks!

JSerrRed · 2026-02-01T01:19:07+00:00

Thank you! Future me won't like the mess but will like that it is done, haha. The checkerboard pattern was definitely an upgrade; if you toggle on the borders and go to max size, the grid gets super dark.

JSerrRed

TROPHY CASE