# How to count 900 million lines in a second

I always use wc-l command to count number of lines. But when my files(900 mill) are big, i have to wait at least 5 minutes to see the results. Any better ideas ?

-

## migrated from stackoverflow.comDec 25 '12 at 20:29

This question came from our site for professional and enthusiast programmers.

What is your exact use case? – scravy Dec 25 '12 at 16:50
Counting lines is a linear-time task, so I don't see any algorithmic trick to do it faster. Maybe you could create a tool yourself that splits the file into multiple chunks and thread it, but then again maybe that's already what `wc -l` does. – zneak Dec 25 '12 at 16:50
It's hard to say how wc-l works, I'd imagine the source is out there... But if it counts every character and checks it against the new line character then that would be inefficient. If that is the case you can cheat if you know more about the data set. If the lines are all the same length or close to it, you could only check every n bytes of a chunk for a newline and if it isn't, walk the next n bytes looking for new lines. Then you are checking an order of magnitude less bytes – Richthofen Dec 25 '12 at 17:08
The bottleneck is almost certainly the disk I/O, not the code doing the counting, unless the file is all cached in RAM. – Barmar Dec 25 '12 at 17:31

## 1 Answer

In theory you could take the first N lines (where N is a number you determine by experiment), average their length, then divide the filesize by the average length. This will give you a very crude approximation (which will be more accurate but slower the higher N is) of the actual number of lines.

-
Nice, guess we were thinking along the same lines :) – Richthofen Dec 25 '12 at 17:04
Take ~1500 lines starting from a truly random line, assuming the line length fits a normal distribution (which may not be a good assumption), then you have a 95% chance that the mean length of those lines represents the actual mean length. ~1500 would constitute statistically valid sample. So dividing (filesize /mean record length) would render pretty good estimate. This is way more trouble than wc -l. Your real problem is that your wc -l is I/O bound, and even with a 15000 rpm SATA drive or a really good SAN ~99% of elapsed time will be I/O wait. – jim mcnamara Dec 26 '12 at 1:56
I would imagine an SSD would fare better? What kind of performance would be you able to expect from one? – Niet the Dark Absol Dec 26 '12 at 2:08
"would be you"... right words, not necessarily the right order! – Niet the Dark Absol Dec 26 '12 at 2:08
SSD's are really expensive per GB of storage and are more effective in a SAN environment where software tiering is active. A hypothetical 900 million line file with 128 byte records (avg) would use 11.5GB, and a 128GB OCZ Vertex 4 costs \$US140 at newegg. Storing one file would use \$12.57 of storage, filesystem overhead excluded. That is crazy. IMO - creating gigantic files is frequently ill-advised, a poor use of a resource, and is always expensive. An SSD would provide at least a factor of 10 speed up on a full file read. – jim mcnamara Dec 26 '12 at 3:20