0

My file consists of logs. In which, every line is a log with starting column as time. All the lines in file are sorted according to the timestamp. I have to find out where the given timestamp occurs in the given file, file size could be of around 10gb. I can sequentially check line by line. Is there any way this can be done in optimized way to find the required?

Edit: I'm thinking of applying binary search. But what would be the approach I should go with to apply binary search on file? Can I use randomAccessFile class and use pointers? If so, How can I spot starting of a specific line where my pointer lands to get the timestamp of that log, thanks.

Sample log in the file: 2020-01-31T20:12:38.1234Z,field1,field2,etc,.....\n

9
  • If the lines are not of equal length, you cannot determine the line number with binary search, only the file offset.
    – Armali
    Jul 15, 2020 at 13:27
  • Does this answer your question? Binary search in a sorted (memory-mapped ?) file in Java
    – Joe
    Jul 15, 2020 at 13:32
  • Hey, are all of the lines represented as Long values?
    – Jason
    Jul 15, 2020 at 15:25
  • @Jason No, actually they're all text lines. Jul 15, 2020 at 18:12
  • 1
    @Joe Thanks for that. Not the main answer, but second answer of that thread gave me solution. Jul 16, 2020 at 10:00

1 Answer 1

0

Option 1 (fastest):

If possible, create another file that acts as an index for the file when generating the input. This could represent what index in the byte array each line exists at as well as the length of the line in bytes. You could even break this up into multiple index files.

// 1 is line id, 0 is byte start index, 12 is end index 
1 0 12 

Option 2:

A good solution would be a binary search implementation. This would likely be significantly faster than a linear search. The idea is that if what you're seeking is unequal to the middle element (line) then you're going to use the left half of the file byte array, otherwise the right half of the byte array.

11
  • I definitely second that. But How can i apply binary search with line numbers. how can i access specific line of file using line number? Jul 15, 2020 at 13:21
  • How to do this without loading 10gb into memory? I don't think OP has 15-20 GB RAM (10gb file+object headers+...)
    – JCWasmx86
    Jul 15, 2020 at 13:22
  • You could easily load chunks of the file at a time instead of the entire file @JCWasmx86.
    – Jason
    Jul 15, 2020 at 13:23
  • 1
    The byte array likely uses the value 10 which is \n also known as new line. You can assume the middle based on file size / 2 (roughly) and seek until \n is found in the array and find the given line and parse.
    – Jason
    Jul 15, 2020 at 13:25
  • @suryaphaniteja Updated to provide another option.
    – Jason
    Jul 15, 2020 at 13:27

Your Answer

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

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