How do I efficiently read random lines from a TXT or CSV file?

Question

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.

Answer 1

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.

Answer 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.