使用 Javascript 在文本文件中进行二分查找
有没有办法在 Javascript 中对文本文件中的特定键进行基于磁盘的二进制搜索？ 文本文件太大，无法加载到内存中，只能按键值排序。 特别是我正在寻找一种在 Javascript 中模仿 Perl 的 Search::Dict 功能的方法。
例如，如果我有一个文件 foo.txt：
a 1
b 10
c 5
z 4
look(c,foo.txt) 应该通过进行二分搜索而不是遍历来返回行 'c 5'文件呈线性。
Is there a way to do a disk-based binary search for a particular key in a text file in Javascript? The text file is too big to be loaded into memory, but sorted by the key values. In particular I am looking for a way to mimic Perl's Search::Dict functionality in Javascript.
For e.g. If I have a file foo.txt:
a 1
b 10
c 5
z 4
look(c,foo.txt) should return the line 'c 5', by doing a binary search and not traversing the file linearly.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我不知道Javascript，但是如果你可以进行随机查找，你可以通过查找当前块的中点（以字节为单位）来进行二分搜索，然后向前前进，直到你消耗掉一个换行符，只要你“知道”你的密钥是针对换行符的。
不过，在某些情况下，您需要向后前进，因此您可能会在了解文件缓冲的情况下进行搜索，这样后退步骤的成本就不会很高。
我想如果您不处理 ASCII 文件，这可能会有点麻烦。
I don't know Javascript, but can if you can do random seeks, you can do a binary search by seeking to the midpoint of your current block (in bytes) and then march forward until you've consumed a newline, as long as you "know" that your key is against a newline.
There will be cases where you need to march backward, though, so you might do your seeks with knowledge of the file buffering so that back-steps are not expensive.
I suppose this could be a bit hairier if you're not dealing with ASCII files.
事实并非如此，只有当您可以识别记录开头时，二分搜索才真正可行。 您似乎有可变长度记录，因此，除非您创建行起始偏移量数组，否则它不会起作用。
正如 Nikhil 在评论中正确指出的那样，一种方法是根据文件大小对文件进行二进制划分，然后找到从那里开始的最接近的行。 这仍然是相对有效的（即，比顺序搜索更好）。
Not really, binary searches are really only possible when you can identify the record beginnings. You appear to have variable length records so, unless you create an array of line start offsets, it's not going to work.
As Nikhil rightly points out in a comment, one method would be to binary divide the file based on file size and then find the closest line beginning from there. That would still be relatively efficient (i.e., much better than a sequential search).