7 ms·
Raymond’s selectRandomFromIterator algorithm requires iterating over all the files. It seems like querying the file system for the number of files in a director
by cpeterso 8d ago
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?
- orf 8d agoBecause counting the files is not an O(1) operation? It would be cool if it was, but that’s not reality?
- cpeterso 6d agoYou’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.