6

Context of the problem:

  1. I have made chess GUI (Java)
  2. The GUI is capable of loading chess puzzles/problems to solve
  3. Of said puzzles, I have gotten my hands on a database which is just shy of a million entries

The problem/question: How does one most efficiently go about getting a random puzzle from this database?

Obviously keeping the database in memory is not an option, despite it already being compressed. Stripped all data that isn't needed from it and in the end converted it into byte-arrays. All to no avail. The full database always ends up taking up somewhere between 100 and 200 MB of memory. A tenth of that would be acceptable (for my purposes).

Even worse: When processing the entire database (in attempts to keep it all in memory), the process file->memory took upwards of 700 MB memory.

Let's say I have the following:

  • The database as either a txt or csv file
  • The amount of lines in said file (which is equal to the amount of puzzles)

Am I with that, in some way, capable of grabbing either a random or specific puzzle from the file (albeit async, that doesn't matter) without having to load the entire database into memory?

/edit:

Some additional context: The chess GUI i have created is running in Bukkit/Spigot adaption of the Minecraft server software. This means that players are able to interact with 3D chess boards and start/play chess games to their hearts content.

The puzzles come in as an additional feature that's supposed to give players the ability to practice finding the best moves.

The amounts of memory consumed in the process i originally described are a problem, because i intend to make this chess game available to all minecraft servers that desire to have it - and each server will have an unknown amount of RAM available attached to it. It may be that they're running on a low total of 1-2 GB, which isn't too uncommon, or that they're equipped with 16-32 GB.

Of course, i could just attach an instructional "help"-file that explains that in order to launch this chess game without causing OutOfMemory execptions, they need to have a certain amount of RAM on boot time, but that just seems like lazy & bad practice; "In order to start this plugin you must have ~1GB spare RAM at boot time, but after that you don't need it anymore".

As for the randomness, it really just needs to be a (targeted) random line from the database. The puzzles come with thematic-tags attached to them, but i have generated additional TXT-files that sort these puzzles by theme. For instance:

  • Player requests a random mate-in-2-theme puzzle
  • File "MATE_IN_2.txt" contains all puzzle line numbers that are mate-in-2 puzzles and returns one of those lines randomly
  • The puzzle is retrieved from the txt file that contains all the puzzle data via the line number
  • Mind you, that puzzles may have multiple themes so sorting them like this is necessary

/edit: Solution The marked reply is the way to go. Here's how i solved it:

int length = line.getBytes().length;
System.out.println("Line offset/length: " + byteOffset + "/" + length);
indices.add(byteOffset);
byteOffset += length;
byteOffset++;

^ This code is ran while initially iterating through the database. "indices" may be a collection or list. "byteOffset" is initialized with "0", because the first line starts at 0.

randomAccessFile.seek(offset);
StringBuilder stringBuilder = new StringBuilder();
while (true) {
    int b = randomAccessFile.read();
    char c = (char) ((byte) b);
    if (c == '\n') {
            break;
        } else {
            stringBuilder.append(c);
        }
    }
System.out.println("Line at offset " + offset + ": \"" + stringBuilder.toString() + "\"");

^ This retrieves the line using RandomAccessFile, "offset" being a value from the prior "indices"

final edit: For those stumbling over this in the future: i benchmarked this and can confirm that reading through files like this extremely RAM friendly.

5
  • 2
    Try opening the file and reading from a random location until you get a complete line. – Erik Eidt Jan 16 at 16:24
  • 6
    Scan the database once to create an index of entries, in particular noting the byte offsets where the entries start. The index will fit into memory. Scanning can be performed in chunks and doesn't need to fit the entire database into memory. The index is sufficient to find the offset of an entry, you can then seek() to the correct position in the database file. You can have all of this for free by using an actual database engine, e.g. embedding HSQLDB in Java. – amon Jan 16 at 16:31
  • 2
    Indexing. (One-word comments are not allowed, but really the only word you need is "indexing".) – Kilian Foth Jan 16 at 17:38
  • Your problem is underspecified. What do you mean be efficient? More importantly, what is the access pattern: just one random entry here and there from random sources, or many, many in a series, based off of unchanging data? You refer to grabbing a single random puzzle, but in context is that really the case? Do you need to know the case number of the random test? Is the case number encoded in the text file, or can that only be found by knowing the ordered record number? Beyond these, why is 700MB an unworkably large amount of RAM these days? – Erik Eidt Jan 17 at 1:54
  • @ErikEidt I have attached some additional context to my post; hope it helps! – jaylawl Jan 17 at 8:27
5

CSV files and many other text based formats encode information in a potentially variable size. Due to the variable record size, there is no way to directly jump to a random record if you don’t know its precise position in the file.

To get some randomness in your app, you could imagine to go to a random offset in the file and move forward or backward to the next record by looking for a line separator. However, you will not know which record it is. Moreover, if you use the CSV variant defined in RFC4180, this will not work, because line separators can be part of a field if it is enclosed between quotes, and you wouldn’t know if there wasn’t such an unclosed opening quote before. The only way is then to read the file from the start and parse it record after record.

What you need to do is to construct an index. , as suggested by Killian and Amon in the comments. For example:

  • at start of your programme by parsing your data file, and build in memory an array with the starting position of the record in the file.
  • or, use a separate indexer that parses the file, and created an index file. Each index record is of fixed size and indicates the position of the next record in the main data file. Since the size of index record is fixed, you can locate easily any random record n by going to position n*sizeOfRecord in the index file, read the position of where to find the record in the data file, and start reading the data at this offset.

Remark: this indexing approach works with any variable length encoding. It could be multiline files, or even complex formats such as json or xml, provided that the indexer can parse the expected format to identify the boundaries of each record.

3
  • Thanks for the detailed reply (this goes for the comment section, too). I believe i understand the concept. However how would this be applied practically? As i am not quite sure how to implement this. The data is already sorted via line breaks (e.g. each line is its own puzzle). By index, do you mean i save the byte at the beginning of the line - and if so: how would i use that to go back to that specific point in the data set? – jaylawl Jan 16 at 21:40
  • 2
    @jaylawl Does this and this help? – Christophe Jan 16 at 21:56
  • At first glance i believe it does. I will study these links, thanks again! – jaylawl Jan 17 at 8:42
2

While Christophe's answer addresses the actual question about the random reading of the text files, I think there is a XY problem here.

You have a set of chess puzzles structures in a form of a text file. And so you're asking how to read a random line from this file. Your actual question should instead be how to load a random chess puzzle, given that currently, the puzzles are stored in a given format.

The answer then involves two stages.

The first stage is to find what's the correct format to store the puzzles in the first place. For your needs, the text format is not a correct one. It doesn't allow it easily to load a random puzzle, and it possibly wastes too much disk space anyway. Instead, one may use a relational database. If the data needs to be distributed with your application (i.e. to work in offline mode), SQLite could be a great option. It will handle all the storage details for you, so you would be able to retrieve a puzzle in just one line of code.

NoSQL databases may also be considered, in order to store the puzzle in a very readable (such as JSON), but also very efficient (i.e. compressed) way. This could further simply the code, in your application, which would convert the data received from the database to the actual object in the application itself.

The second stage then is to export the data from the text file, and actually import it to the database.

2
  • 1
    > r5k/2p1pp/pp4p/1q1r/5P/2QP2R/PP/1K4R1 b - - 0 32,d5h5 g3g6 f7g6 g1g6 g8f7 c3g7 f7e8 g7g8 e8d7 g8e6 d7d8 g6g8,8 16 42 48 Seperated by the "," characters, this is: FEN position, forced moves, theme-tag-id-bytes This is the current format i am storing the puzzles in and i have already spent many, many hours to getting them this small. The original database i acquired was 158 MB in size; my edited one i down to 79 MB. The only way known to me that could compress this any further is using something like Huffman coding, which is way unfortunately is "above my paygrade". – jaylawl Jan 17 at 8:58
  • 2
    Simple. “r5k/2p1pp...” is text. ASCII. This text format doesn't take in account that “d5h5” means something, while “z_M%” is just meaningless garbage. In other words, you take a 3-bit value, and store it as 8-bit (or slightly more depending on the encoding of your text file). Additionally, some databases (not SQLite, if I remember well) are very capable when it comes to file-level compression. While you can actually compress your file, it won't play well with random access then. – Arseni Mourzenko Jan 17 at 9:22

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.