• Post Reply Bookmark Topic Watch Topic
  • New Topic

Array Shuffling

 
Samuel Wolfe
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Let's say I need to represent a chess position in an array and search it for the best move in the least time. Would I lose significant performance by using an ASCII representation, as opposed to something purely numeric? Is there something better than an array for this?

 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, it will be interesting to see what sort of performance you can get for this - I suspect this is one of the tougher things you could try to do in Java. But doubtless a worthwhile learning experience. First off, whatever the internal representation you use, I'd wrap it in a BoardPosition class which abstracts the details away, allowing you to change internal representations later as needed. This very abstraction will introduce some performance overhead, but hopefully it's small, and the flexibility should be worth it. It can also go a long way toward making the code readable.
Anyway, for the internal representation - offhand I'd say go with a byte[64], and use a unique numeric code for each piece type. Alternately you could try a byte[8][8] - my gut says this will be slightly slower, but who knows? I suspect you'd get the same results with int instead of byte, as the JVM probably uses 32 bits to store each value anyway - but try it either way. Good luck.
 
Samuel Wolfe
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Perhaps I should add that this will likely be a recursive function, so even minor improvements in speed would bring exponential dividends. If that changes anything, anyway...
 
Peter Tran
Bartender
Posts: 783
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

If I had to represent a chess boards, I would use an internal single dimensional array of ints. I then would provide public accessor methods that uses an offset to the position into the board. For example, row 2 and col 5 would be calculated (2 * 8) + 5 = 21 offset into the array. I would also use a look up table to represent the pieces.
An int[] is faster than int[][] because JAVA checks boundary conditions. There's less to check with one [].
-Peter
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Samuel - Don't get too bogged down in saving every little bit of speed early on. The big gains in performance of your program will likely come from changes in algorithms, which will be a lot easier for you to write with a few levels of abstraction between you and the underlying data. Most of the optimizations you might make early on won't matter nearly as much as you might think - if your program is spending 90% of its time in methodA(), doubling the speed of methodB() won't help you much at all. Deferring a lot of the optimization until later (when you know where the bottlenecks are) will probably save you a lot of needless work. Even if overall performance probably is the biggest challenge of this project.
Which is not to say that you shouldn't consider the data structure carefully for how it may impact your speed - it almost certainly will be important. But don't think that every little performance improvement will give you exponential gains.
Having said that though, I can't resist observing that since most of your multiplications and divisions will be by 8, you may find that right and left shifts are faster than multiplication and division. (E.g. 2 << 3 + 5, rather than 2 * 8 + 5.) I really doubt that will matter much in Java, but it could.
 
Samuel Wolfe
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, this would be the 'flagship' algorithm. As far time spent in the code would go, this is likely the biggest bottleneck since it wil be repeated so many times. Most other places in the code wouldn't be as likely to be so time-critical. But, as you said, that challenge is for later, and it may not be as much of an issue once other parts of the code are in place. Besides, I suspect that optimization would not be the biggest problem facing me in such a project...

Thanks for the input.

 
Marius Holm
Ranch Hand
Posts: 84
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Samuel,
Probably you will make the recursive calls as small as possible, since recursion in itself usually impairs performance a lot. That way it should be possible both to modularize your code, adding a bit of overhead, while the recursion takes place on lower levels. I'm quite certain that bitshifting by 3 in your code will work faster than dividing by 8.
Good luck,
Marius
 
Paul Bailey
Ranch Hand
Posts: 91
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Marius, why do you say, " [...] recursion in itself usually impairs performance a lot. "?
PB
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!