blob: 77782f164d6d623d7ec20521e8961879373d0b78 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
<h5 style="text-align: center;" id="description">Description</h5>
<p>The search is pretty fast, but is it possible to come up with something even faster?</p>
<p>In the previous stage, you prepared the data using an algorithm with a complexity of <code class="java">O(n log n)</code> and found the data using an algorithm with a complexity of <code class="java">O(log n)</code>. At this stage, you will implement faster data preparation and a faster search. The preparation will have a complexity of <code class="java">O(n)</code>, and the search will have a complexity of <code class="java">O(1)</code>. A <strong>hash table</strong> will help you with this.</p>
<p>You need to add all the elements to the hash table and then find the necessary phone numbers, as in the previous stages. Since the hash table is filled once, you need to measure the hash table creation time separately (just like you did with sorting in the previous stage).</p>
<h5 style="text-align: center;" id="example">Example</h5>
<p>Output all four approaches one after another and see which one is faster. The output example is shown below. Note that you can get totally different sorting and searching times!</p>
<pre><code class="java">Start searching (linear search)...
Found 500 / 500 entries. Time taken: 1 min. 56 sec. 328 ms.
Start searching (bubble sort + jump search)...
Found 500 / 500 entries. Time taken: 9 min. 15 sec. 291 ms.
Sorting time: 8 min. 45 sec. 251 ms.
Searching time: 0 min. 30 sec. 40 ms.
Start searching (quick sort + binary search)...
Found 500 / 500 entries. Time taken: 1 min. 21 sec. 996 ms.
Sorting time: 1 min. 17 sec. 381 ms.
Searching time: 0 min. 4 sec. 615 ms.
Start searching (hash table)...
Found 500 / 500 entries. Time taken: 0 min. 4 sec. 256 ms.
Creating time: 0 min. 4 sec. 121 ms.
Searching time: 0 min. 0 sec. 135 ms.</code></pre>
|
