`

Hash VS. BinarySearch

阅读更多
cqy:

有一大表,记录最终大约能到200万条记录,另有10万行的文本数据。表中有个字段(该表的聚合索引)和文本中每行的数据相对应。

要找到两者所有共同的记录,如何才能性能最优呢?

1、遍历文件,取每行数据对大表做select count(*) ...

2、遍历文件,每1千行数据对大表作select * from ... where ... in (记录1,记录2,...,记录1000)

3、将文件数据插入临时表,和大表做关联查询。

...

三种方案都是只出汗水不出智慧,因已有索引,所以假设每条记录的平均比较次数是5次,则10万行数据要进行50万次比较。


需求背景:
1、用户定期从文本导入一批币类卡号到数据库的币类实时表,但由于人为失误,可能会存在文本中的卡号已经在实时表或历史表中了。
2、要求在正式导入前,检查实时表和历史表,确认文本中没有和数据库中相同的卡号。
3、要求能打印出重复的卡号,协助用户调整导入文件。


zg:

10万行数据,最少比较多少次?

起码也是10万次,这个应该是避免不开的吧。

能减少的,也就是n*m的那个m

可能可优化的空间并不多:)

cqy:
确实,优化的空间不多.有时定个方案,面临的选择真让人踌躇: 
人为失误的可能性是比较小的,为了这个概率比较小的失误,每次都要大动干戈,觉得不值.但如果不做这个,一旦失误导入了重复的卡号,则有可能导致用户申请币成功后无法消费,用户极有可能投诉.

zg:
我这样看

1:这个操作是个校对工作,很重要,要做

2:但也正由于是校对工作,因此对时间不敏感,不需要很快完成

3:因此,可以慢一点来(所谓慢一点,就是不要对数据库操作太大压力),保证最终质量即可

正由于太慢,因此要给用户一个选择

是否先进行数据校对? 是  否 (默认为是)

说明:数据校对需要耗费一定时间,但我们仍旧建议先进行数据校对,因为.....。(这里说明不校对的严重性,但校不校对给用户一个选择权比较好)

每次操作,要有记录,以防后面出现问题,我们可以查看是否用户选择了不校对。

cqy:
我原先的考虑是将数据校对从导入功能中剥离开,另外专门做一个导入数据校对的界面。

你的方式更好,在导入时就可以给用户以明显的警示。

lwj:
把两种方法测试了一下,测试结果如下:
1、遍历文件,取每行数据对大表做select count(*) ...
测试一:
文本记录条数为:70000
文本校对共花时间为:610028
没有重复的记录!
测试二:
文本记录条数为:120000
文本校对共花时间为:1203999
重复的记录如下:
1247010990
1247010990
1247010990
1246699687
1247372542
1272267392
1389770716
1716469803
1984701859
1145419315
1806052289
1849935038
1600328218

2、遍历文件,每1千行数据对大表作select * from ... where ... in (记录1,记录2,...,记录1000)
所得resultList会把重复的记录合并

测试一:
文本记录条数为:70000(修改了测试一的文本文件)
文本校对共花时间为:297505
重复的记录如下:
100105777551R0340629
1100006598
11002326
1100241930
1100275543
测试二:
文本记录条数为:120000
文本校对共花时间为:517384
重复的记录如下:
1246699687
1247010990
1247372542
1272267392
1389770716
1716469803
1984701859
1145419315
1806052289
1849935038
1600328218


cqy:
请用第二种方式,再测试一下2000,3000,4000,5000四种情况。只要测试12万那个样本。

lwj:
测试一:
批处理记录数:2000
文本记录条数为:120000
文本校对共花时间为:517739
重复的记录如下:
1246699687
1247010990
1247372542
1272267392
1389770716
1716469803
1984701859
1145419315
1806052289
1849935038
1600328218
测试二:
批处理记录数:3000
文本记录条数为:120000
文本校对共花时间为:517659
重复的记录如下:
1246699687
1247010990
1247372542
1272267392
1389770716
1716469803
1984701859
1145419315
1806052289
1849935038
1600328218
测试三:
批处理记录数:4000
文本记录条数为:120000
文本校对共花时间为:579531
重复的记录如下:
1246699687
1247010990
1247372542
1272267392
1389770716
1716469803
1145419315
1806052289
1984701859
1849935038
1600328218
测试四:
批处理记录数:5000
文本记录条数为:120000
文本校对共花时间为:520637
重复的记录如下:
1246699687
1247010990
1247372542
1272267392
1389770716
1716469803
1145419315
1806052289
1984701859
1849935038
1600328218


cqy:
数据库方案的结果出来了,大概最好的方式是5分钟左右,但操作期间数据库的其它操作响应缓慢——这个让人没法接受。

上午tzc建议采用非数据库的方式,类似方案之前和tde也有讨论,上午请lwj再做一下测试,并给出测试结果。

算法步骤:

1、创建一个视图,对应库存表和历史库存表的卡号纪录。

2、将纪录bcp到文件。

3、将文件中的卡号读入内存,以HashMap为存储结构,(key:卡号,value:固定为1)。假设共有100万纪录,估计需要15M左右的空间,是可以接受的。

4、将导入文件读入内存,以List为存储结构。

5、遍历导入文件的List,每个卡号对HashMap做contranerKey操作,将true的卡号存入结果List。

6、将bcp文件删除。

上述的操作只有第2步会影响到数据库,但很小了。

衍生方案:

对于第3步,不知道jdk的散列函数怎么样,100万的key会有多大的冲突。因此,将第三步改一下:

3、将文件中的卡号读入内存,以List为存储结构,并作排序。

4、将导入文件读入内存,以List为存储结构。

5、遍历导入文件的List,每个卡号对卡号List做二分查找,将找到卡号存入结果List。


tzc:
3、将文件中的卡号读入内存,以LinkedHashSet为存储结构,(key:卡号,value:固定为1)。假设共有100万纪录,估计需要15M左右的空间,是可以接受的。

4、将导入文件读入内存,以LinkedList<String[]{cardnum,标准=0}>为存储结构。

5、遍历导入文件的List,每个卡号对LinkedHashSet做contains操作,将true的卡号标志设置为1。


保存打数据量的结果集合,尽量采用Linked的结构,这样子减少内存的拷贝,或者如果你能估算有多少记录可以这样子生成对象:List list = new ArrayList(初始容量);  这样子性能会更加好。


cqy:
OK,请lwj采用linked类型的存储结构。

呵呵,老实讲,我到不太担心这个的影响。我担心的是100万的纪录,java的Hash表会有多大的冲突,如果冲突太多,Hash表查找将退化成线性表顺序查找。

两种方案都试试吧!:)


lwj:
测试一:linkList存储
277655 rows copied.
bcp成功277655条记录.
Clock Time (ms.): total = 2203  Avg = 0 (126034.95 rows per sec.)
[MPS_XY2_STOCK]:bcpout所花时间共为:2281,共bcpout 277655条记录
F:\temp\bcp\temp.txt装入set开始~~~
F:\temp\bcp\temp.txt装入set完成,共花时间641
set.size=277655
比较开始~~~
F:\temp\coin_10_70000\test1.txt比较结束,共比较120000条记录,共花时间94
导入文件与实时库及历史库重复记录如下:
2100005220
2100015899
2100022897
2100027656
210018760
2100005220
2100005220
2100005220
2100015899
2100005220
2100005220
2100005220
2100005220
测试二:二分查找
277655 rows copied.
bcp成功277655条记录.
Clock Time (ms.): total = 1562  Avg = 0 (177756.08 rows per sec.)
[MPS_XY2_STOCK]:bcpout所花时间共为:1640,共bcpout 277655条记录
F:\temp\bcp1\temp.txt装入list开始~~~
F:\temp\bcp1\temp.txt装入list且排序完成,共花时间313
比较开始~~~
F:\temp\coin_10_70000\test1.txt二分查找结束,共比较120000条记录,共花时间141
导入文件与实时库及历史库重复记录如下:
2100005220
2100015899
2100022897
2100027656
210018760
2100005220
2100005220
2100005220
2100015899
2100005220
2100005220
2100005220
2100005220


cqy:
那么测试一的时间就是:
bcp时间:2281ms
装入hashset时间:641ms
比较时间:94ms
共计:2281 + 641 + 94 = 3016ms = 3.016s

测试二的时间就是:
bcp时间:1640ms,公平起见,此处定为2281
装入list和排序的时间:313ms
比较时间:141ms
共计:2281+ 313 + 141 = 2939ms =2735s

哈,都只需要3秒左右。二分查找的快一点,主要是装入list比装入hashset要开一倍时间。

那么我们基本定这种方案了,这个测试只是测试了27万纪录,请再测试100万纪录的。


lwj:
1000264条数据库数据测试结果:
测试一:二分查找
1000264 rows copied.
bcp成功1000264条记录.
Clock Time (ms.): total = 7859  Avg = 0 (127276.24 rows per sec.)
[MPS_QB_STOCK]:bcpout所花时间共为:8391,共bcpout 1000264条记录
F:\temp\bcp1\temp.txt装入list开始~~~
F:\temp\bcp1\temp.txt装入list且排序完成,共花时间1187
listBcpFile.size=1000264
二分查找开始~~~
F:\temp\coin_10_70000\test1.txt二分查找结束,共比较120000条记录,共花时间1782
导入文件与实时库及历史库重复记录如下:
1719918650
1850631185
1591643820
1677294646
1506542891
1184630720
1661464630
测试二:linkList存储
1000264 rows copied.
bcp成功1000264条记录.
Clock Time (ms.): total = 8219  Avg = 0 (121701.42 rows per sec.)
[MPS_QB_STOCK]:bcpout所花时间共为:8297,共bcpout 1000264条记录
F:\temp\bcp\temp.txt装入set开始~~~
F:\temp\bcp\temp.txt装入set完成,共花时间5375
set.size=1000264
比较开始~~~
F:\temp\coin_10_70000\test1.txt比较结束,共比较120000条记录,共花时间281
导入文件与实时库及历史库重复记录如下:
1719918650
1850631185
1591643820
1677294646
1506542891
1184630720
1661464630



cqy:
100万规模的数据校验结果出来的,如下。从结果看,毕竟是随机访问,hashset的查找速度远胜二分法。但代价是它的装入太慢了,因此整体上,它比二分法方案慢了近3秒钟。
因此我们决定采用非数据库方式的二分查找法实现数据的校验,另外,请刘文娟将之前已经完成的检查导入文本自身重复卡号的算法和这个整合在一起,那么导入前的数据校验工作就完整了。

二分查找:
7859(bcp时间) + 1187(装入并排序) + 1782(查找) = 10828ms
hashset查找:
7859(bcp时间) + 5375(装入) + 281(查找) = 13515ms





分享到:
评论

相关推荐

    折半查找 binarySearch

    A binary search algorithm (or binary chop) is a technique for finding a particular value in a sorted list. It makes progressively better guesses, and closes in on the sought value, by comparing an ...

    Data.Structures.and.Algorithms.USING.C

    17. Binary Search 18. Interpolation Search 19. Hash Table SORTING TECHNIQUES 20. Sorting Algorithm 21. Bubble Sort Algorithm 22. Insertion Sort 23. Selection Sort 24. Merge Sort Algorithm 25. Shell ...

    java工具类-正则

    System.out.println(Arrays.binarySearch(arr, 5)); // 输出结果:2 System.out.println(Arrays.binarySearch(arr, 4)); // 输出结果:-3,表示没有找到该元素 ``` - **3. copyOfRange(int[] original, int from...

    算法第四版(algorithms),2011年新出版,算法设计力作

    3.2 Binary Search Trees 396 3.3 Balanced Search Trees 424 3.4 Hash Tables 458 3.5 Applications 486 CONTENTS vii 4 Graphs . . . . . . . . . . . . . . . . . . . . . . . 515 4.1 Undirected Graphs 518 4.2...

    c++数据结构与算法实现

    TestBinarySearchTree.cpp: Test program for binary search tree AvlTree.h: AVL tree TestAvlTree.cpp: Test program for AVL trees mapDemo.cpp: Map demos WordLadder.cpp: Word Ladder Program and Word ...

    leetcode博弈论-awesome-leetcode:在leetcode上练习

    hash(哈希) 数组、链表 82[M]. 138[M]. 142[M]. 143[M]. 148[M]. 328[M]. 430[M]. 817[M]. 跳表 字典树 208[M]. 211[M]. 位图(bitmap) 树 排序 179[M]. 查找 35[E]. 二分查找 852[E]. binary search 349[E]. binary ...

    hash_map的详解

    为了提高效率,我们可以考虑使用二叉搜索树(Binary Search Tree),它能够提供较快的查找速度。但在某些情况下,即使是O(log n)的查找时间也可能成为性能瓶颈,特别是在需要频繁访问大量数据的应用场景中。这就引出了...

    02. Dr Ahmed Khattab_hashtable_sortingAlgorithm_binarysearchtree

    Dr Ahmed Khattab_hashtable_sortingAlgorithm_binarysearchtree" 涉及的是数据结构和算法中的三个核心主题:哈希表(Hash Table)、排序算法(Sorting Algorithm)以及二叉搜索树(Binary Search Tree)。...

    浙江大学2018-19秋冬《数据结构基础》期末模拟练习21

    题目指出抛物线探测等同于双散列,但使用Hash(k) = k作为次要散列函数,这个说法是不正确的,因为抛物线探测通常涉及平方序列,而双散列需要两个不同的散列函数。 3. **二分查找** - 如果N个数字按递增顺序存储在...

    python3.6.5参考手册 chm

    PEP 456: Secure and Interchangeable Hash Algorithm PEP 436: Argument Clinic Other Build and C API Changes Other Improvements Significant Optimizations Deprecated Deprecations in the Python API ...

    浙江大学2018-19秋冬《数据结构基础》期末模拟练习1

    - 二次探测并不等同于使用Hash(k) = k作为次要哈希函数的双散列。二次探测是冲突解决策略,它通过在已占用位置的相邻位置进行探测,而双散列使用两个不同的哈希函数来确定新的探测位置。 9. **栈的操作序列**: -...

    Programming.Problems.in.Java.A.Primer.for.the.Technical.Interview.epub

    A complete primer for the technical programming interview. This book reviews the fundamentals of computer ...Chapter 7 Binary Search Chapter 8 Graphical Search Chapter 9 Selection Chapter 10 Sorting

    Go 零基础2000题 从入门到精通

    Binary Search Bit Manipulation Breadth First Search Depth First Search Dynamic Programming Hash Table Linked List Math Segment Tree Sliding Window Sort Stack String Tree Two Pointers Union Find 第三章...

    Learning.JavaScript.Data.Structures.and.Algorithms.1783554878

    Finally, we will round off by learning how to differentiate between various searching and sorting algorithms such as sequential search, binary search, quick sort, bubble sort, and so on, and how to ...

    Pass the SALT 2019PPT汇总(39份).zip

    .pdf', 'Reversing a Firmware uploader and others NFC stories.pdf', 'Scale Your Auditing Events.pdf', 'Syslog-ng:getting started, parsing messages, storing in Elasticsearch.pdf', 'Threat Hunting with ...

    leetcodepdfpython-hello-world:资料结构与演算法资料库-这是资料结构与演算法的程式码与演算法流程图及文字描述

    binary_search_tree_05170221.py: HW4 Hash Table 流程图,学习历程,Hash Table&Hash Function 原理最新版.ipynb: hash_table_05170221.py: HW5 BFS_05170221.py : BFS广度优先搜寻&DFS深度优先搜寻(1).ipynb: HW6 ...

    Hash查找、二分查找c语言关键字个数

    本项目主要涉及两种查找算法:哈希查找(Hash Search)和二分查找(Binary Search),并且应用在统计C语言源文件中的关键字个数。下面将详细阐述这两种查找算法以及它们在本项目中的具体应用。 哈希查找是一种高效...

    算法:python3中的算法实践

    binary search 1/25 binary search 1/26 binary search 1/26 binary search 2/1 bfs 2/1 dfs 2/2 hash table 2/3 hash table BaekJoon和程序员 资源 码 类别 链接 日本央行 SWEA SWEA SWEA SWEA ...

    每天学点C++(C++实例教程:教程+源码)常用查找算法.zip

    int binarySearch(int arr[], int l, int r, int x) { if (r &gt;= l) { int mid = l + (r - l) / 2; // 如果中间元素就是目标 if (arr[mid] == x) return mid; // 如果中间元素大于目标,那么目标只能在左半...

    Open Data Structures (in Java) Pat Morin

    binary search trees including treaps, scapegoat trees, and red-black trees; integer searching structures including binary tries, x-fast tries, and y-fast tries; heaps, including implicit binary heaps...

Global site tag (gtag.js) - Google Analytics