怎样实现从一个数据有序的文件中比较快速的查找？

本文转载自 a3 查看原文 2005/05/28 10 数据/ 比较/ 文件/ 查找/ 快速/ 实现

33 个解决方案

#1

这是一个查找问题了

我想用折半法应该不错

#2

能具体说一下怎样在文件中进行折半查找？

#3

通过对关键字进行查找

#4

Keyword：BinarySearch

#5

文件中怎样用关键字，又怎样进行折半？用语言描述一下吧

#6

折半查找：
折半查找（binary search）也称二分法查找，使用于顺序存储结构并且数据元素已经按照关键字大小排序的线性表。

基本思想是这样的：
假定线性表的数据元素是按照升序排列的，对于给定值k，从线性表的中间位置开始比较，如果当前数据元素的关键字等于k，则查找成功。否则，若k小于当前数据元素的关键字，则在线性表的前半部继续查找；反之，则在线性表的后半部分继续查找。依次重复进行，直至获得查找成功或不成功的结果。

建议楼主好好打基础，好好看看java数据结构

#7

大哥，我当然知道折半的算法，我要问的是怎么在文件中实现！！

#8

刚吃完饭，过来再顶一下

#9

仔细说一下，我的文件的数据项有两部分组成，一项是key，整型；另一项是数据，也是整型。文件只进行读操作，怎么二分？对文件操作好像没有指针。

#10

看你是什么文件了，如果是xml...

#11

txt

#12

没人知道吗？

#13

如果每个记录的长度相同，尝试使用mark() reset() 方法来定位来二分法的上下界

#14

怎样跳到比较值那里？文件不是只能顺序读取吗？

#15

可以第一次遍历时建立一个索引
把这个索引保存起来好了
以后直接查找这个索引

#16

顶上去

#17

你可以使用java.io.RandomAccessFile来做折半

#18

二当家，我还是不明白啊。详细说一下怎样建索引吧

#19

建索引只是我的一个思路
如果有多个文件
在读入文件时取得它的key
然后建立一个链表
每个节点的内容如下
class node {
int key,//该文件的关键字值
String fileName;//该文件的名字
}
然后每个文件名对应它的关键字值好了

不知能否解决你的问题

#20

只有一个文件，但是有7000个纪录

#21

现在问题是文件不是从头读起，而是从中间读，怎么办？

#22

ding

#23

建议对文件分段，检索时先确认待查记录在哪一段，之后再把该段全部读到内存，然后二分查找；
如果不想分段可以用skip，不过文档里说性能不好，不推荐（这个函数是顺序读取文件到字节数组，之后不做任何处理扔掉），目前J2ME里没有可以随机移动文件指针的函数。

#24

例：分段文件为0.dat,1.dat,2.dat，各文件首记录key分别为11，22,33
则可以开数组
int key[3]={11,22,33}
String fileName[3]={"0.dat","1.dat","2.dat"}
如果待查key为15，则通过对key[]的查找知道它在文件fileName[0]中，将fileName[0]整个读入内存，之后做二分查找。
文件分段可以写一个拆分器，好解决。

#25

我的文件有7000个纪录，每个纪录有两个整数构成，拆多少个文件合适？
dataoutputstream.read(byte[],off,len)这个函数可以进行跳跃读取吗？

#26

既然是有序的文件,使用折半是比较好的办法

#27

我不知道怎样在文件中跳跃查询，文件不是没有指针么？

#28

建议用二分法（也就是折半法）做查找比较合适！

#29

你既然有KEY，那么就用KEY查找。

用把你的文件内容分批读到map结构数组中，比如数组大小是500，每读一次，用KEY去找对应的值。找到了就停止，没有就再读500个。

至于IO和MAP的用法，你自己看书把，一两句话说不清。

#30

airhand(暴风雨) 这样速度会不会太慢？

#31

ding

#32

难道没有人会吗？

#33

key  value
1     109
2     290
3     3837
4     10
5     4748

楼主的文件是这样的结构吗？

有序排列的是key还是value啊？

DataOutputStream.read(byte[],off,len)可以实现从指定的地方读取。
如果这真的如楼主所说的那样的数据结构的话，
使用这个方法是一个很好的选择。

注意！

本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。

猜您在找

SQLite 如何实现从一个数据库的某个表的记录复制到另一个数据库中请教：在oracle中怎么实现从一个排好序的结果集中查出指定的第n行到第n+m行数据哪位大哥能给小弟一个实现从一个文件读取数据的Filter的例子。 KEIL 中无法实现从一个C文件中查找头文件中定义的函数 C#怎么实现从一个文件的指定行开始读取数据