1

I have large list of strings. Each string is of different length, just like sentence in text. Average length is below 255 chars. Please, propose file structure on disk to enable fast picking of random sentence. This means I need fast: * read total count * read N-th string. There's no requirements of writing time. It's better if structure would be simple and waste of disk space is minimum.

I come with following format: 

<N, number of strings>
<S1, fixed size first chunk of string 1,
    right padded with zeroes if size of chunk is less than size of string>
...
<SN, string N chunk, ends with index of next string N chunk,
    if string N dont fits in single chunk>
<SN+1, string N additional chunk 1>
<SN+2, string N additional chunk 2>

Additional chunks of the same string I can put together to minimize seek and reads. This way I pick every string with equal probability and read it with minimum of 1 seek and 1 read and at most 2 seek and 2 reads. I can pick average string length as size of a chunk.

Improve this question
3
  • I don't have time to write an answer, but the solution is to use a directory: an array of offsets into the rest of the data. That way you don't need to have fixed-size chunks.
    – kdgregory
    Apr 25, 2017 at 12:33
  • Maybe just store count, then store offset+length for each entry (2 bytes for length, 4 bytes for offset or something like that). Then you read count, generate random number up to count, use it to get offset+length of given sentence, then read sentence itself. So after you read count that will be just 2 lookups - fast enough.
    – Evk
    Apr 25, 2017 at 12:52
  • Thanks @kdgregory and Evk, I think it's most speed+space efficient solution, there's even no need for lengths: N+1-th offset is where N-th string ends.
    – Dmitry Teslenko
    Apr 25, 2017 at 14:52

2 Answers 2

Reset to default
1

This looks like homework to me, but I'll try to give my best answer here.

Storing to search/seek any value in disk is a solved problem. DBMSs do this all the time, and the one thing that DBMS do better than most programs is I/O.

That being said, go for the same structure they use for storing indexes B Trees or B+ Trees.

If you're really into something fast for querying and has great hash skills, you could create some sort of Hash table based index.

Improve this answer
0

This process can only be quick if you have fixed length records, allowing you to skip through the file to a particular record based on its index value (and the record length).

Question: Why does this need to be in a single file?

  • Store each sentence in a separate, numbered, file in a single directory.
  • Store the number of files in another, "count" file.
  • Read the count file.
  • Generate the random number based on the count.
  • Read the appropriate file.
Improve this answer
3
  • each file takes up at least a single 4k block on disk on many filesystems so having an index into the strings (where the indexes are fixed length and point to the offset of the actual string or remaining part of a string) will be less wastefull.
    – ratchet freak
    Apr 25, 2017 at 10:51
  • Also I dont want to hit file number limit in single directory. I can make directory structure of cause, but this would make it more complex and waste even more disk space on directory filesystem records.
    – Dmitry Teslenko
    Apr 25, 2017 at 11:02
  • @Phill W. fixed size chunks is the point
    – Dmitry Teslenko
    Apr 25, 2017 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.