Hacker News Reader

Raymond’s selectRandomFromIterator algorithm requires iterating over all the files. It seems like querying the file system for the number of files in a directory should be an O(1) operation. Then you just select random number N between [1, number of files] and iterate to the Nth file.

Why does Raymond assume counting the files is an O(n) operation?

View on HN

Because counting the files is not an O(1) operation? It would be cool if it was, but that’s not reality?

You’re right. I looked it up: getting the number of files in a directory in FAT and FAT32 file systems is O(n). I had assumed the count would be recorded in an inode-like structure but instead the file system must scan a directory table to count the non-null entries.

Reply on news.ycombinator.com