9 个解决方案
#1
hash
#2
那要看你这10万条记录怎么存放的了,如果能用hash当然hash最快了,不过要选择一个合适的hash函数也不是个容易的事情.选好了O(1)的时间复杂度,选不好比你折半还慢.
#3
10万条记录的规模不算太大的，二分法（或者叫折半查找）能得到足够的效率
如果你的记录是定长记录的话，处理很方便，如果是变长记录，则要事先
构造一个索引
如果你的记录是定长记录的话，处理很方便，如果是变长记录，则要事先
构造一个索引
#4
数据库。
#5
100k的纪录应用折半查找最多需要约18次的比较，很显然，做18次比较不需要5s这么长的时间，但是lz的方法确实花了5s的时间，原因可能如下
1. lz直接在文件上应用折半查找，耗时的磁盘操作消耗了大部分时间
2. lz将其直接将数据读到内存里面，这可能需要大量的内存空间，但你的进程得不到这么多空间，于是几次缺页耗费了大量时间
所以，瓶颈在于磁盘操作，而不是算法本身。对于大量数据的查找，无非是建立一个相对较小的索引，将索引读到内存，然后在索引上进行查找，之后再直接定位到数据项上。对于lz的case，直接用线性表来描述索引就可以了，这样大概需要100k*sizeof(索引项)的空间。更大的数据，可以考虑使用B或者B+树。当然，对大量数据的处理并没有说得那么容易，要不然也不会发展出数据库这个领域了
1. lz直接在文件上应用折半查找，耗时的磁盘操作消耗了大部分时间
2. lz将其直接将数据读到内存里面，这可能需要大量的内存空间，但你的进程得不到这么多空间，于是几次缺页耗费了大量时间
所以，瓶颈在于磁盘操作，而不是算法本身。对于大量数据的查找，无非是建立一个相对较小的索引，将索引读到内存，然后在索引上进行查找，之后再直接定位到数据项上。对于lz的case，直接用线性表来描述索引就可以了，这样大概需要100k*sizeof(索引项)的空间。更大的数据，可以考虑使用B或者B+树。当然，对大量数据的处理并没有说得那么容易，要不然也不会发展出数据库这个领域了
#6
最好再多给出一些信息啦.比如记录格式是怎样的,查找哪种数据类型,等等.
#7
10W条很少了
#8
如果是相似度比较高的,比如全是电话号码,就可以用位操作来做
#9
查找可以使用hash配合KMP来匹配
不过kmp应该修改一下使用
不过kmp应该修改一下使用
#1
hash
#2
那要看你这10万条记录怎么存放的了,如果能用hash当然hash最快了,不过要选择一个合适的hash函数也不是个容易的事情.选好了O(1)的时间复杂度,选不好比你折半还慢.
#3
10万条记录的规模不算太大的，二分法（或者叫折半查找）能得到足够的效率
如果你的记录是定长记录的话，处理很方便，如果是变长记录，则要事先
构造一个索引
如果你的记录是定长记录的话，处理很方便，如果是变长记录，则要事先
构造一个索引
#4
数据库。
#5
100k的纪录应用折半查找最多需要约18次的比较，很显然，做18次比较不需要5s这么长的时间，但是lz的方法确实花了5s的时间，原因可能如下
1. lz直接在文件上应用折半查找，耗时的磁盘操作消耗了大部分时间
2. lz将其直接将数据读到内存里面，这可能需要大量的内存空间，但你的进程得不到这么多空间，于是几次缺页耗费了大量时间
所以，瓶颈在于磁盘操作，而不是算法本身。对于大量数据的查找，无非是建立一个相对较小的索引，将索引读到内存，然后在索引上进行查找，之后再直接定位到数据项上。对于lz的case，直接用线性表来描述索引就可以了，这样大概需要100k*sizeof(索引项)的空间。更大的数据，可以考虑使用B或者B+树。当然，对大量数据的处理并没有说得那么容易，要不然也不会发展出数据库这个领域了
1. lz直接在文件上应用折半查找，耗时的磁盘操作消耗了大部分时间
2. lz将其直接将数据读到内存里面，这可能需要大量的内存空间，但你的进程得不到这么多空间，于是几次缺页耗费了大量时间
所以，瓶颈在于磁盘操作，而不是算法本身。对于大量数据的查找，无非是建立一个相对较小的索引，将索引读到内存，然后在索引上进行查找，之后再直接定位到数据项上。对于lz的case，直接用线性表来描述索引就可以了，这样大概需要100k*sizeof(索引项)的空间。更大的数据，可以考虑使用B或者B+树。当然，对大量数据的处理并没有说得那么容易，要不然也不会发展出数据库这个领域了
#6
最好再多给出一些信息啦.比如记录格式是怎样的,查找哪种数据类型,等等.
#7
10W条很少了
#8
如果是相似度比较高的,比如全是电话号码,就可以用位操作来做
#9
查找可以使用hash配合KMP来匹配
不过kmp应该修改一下使用
不过kmp应该修改一下使用