10 - Algorithms 3 (Search) Flashcards
What is searching?
Searching for an item in a collection
Why may you want to search?
Want to know if an item is there at all
Want to know an item’s position
Name 3 applications of searching
Parsing strings
Database queries
Finding files on a disk
What is linear searching?
Going through all items and checking if any equal the key
What’s the worse case of linear searching?
Going through all elements
What is the work and step complexity of linear search?
O(n)
What does the performance of linear search depend on?
The data distribution
What do databases and other applications use to accelerate searching?
Sorted lists or B-trees
What is binary search?
A divide and conquer searching technique
What is the process of binary searching?
Recursively/iteratively check if the middle location contains the key, if not then discard one half which cannot contain the value, check the middle location of the remaining half and so on
What is the parallel search input split?
Divide input into p parts (number of processing elements) and run a serial search for each part
What are the effects of the input split?
A potential speed up of p times
But need to wait for all threads to finish
Some threads might need to perform the worst case scenario
Latency corresponding to the slowest search
What is the parallel search multiple keys?
Perform multiple searches at the same time
What are the effects of multiple keys searching?
A potential speed up of p times
Underutilisation if a number of searches is smaller than p - lots of idle threads
Early exit
Larger p makes it more likely that the worst case execution time will happen
How does a parallel binary search benefit from parallelism?
Parallel implementation using p PEs can perform p searches simultaneously
Discuss memory access in parallel search?
Binary parallel search cannot benefit from coalesced memory access
Linear parallel search might be faster for small arrays
In general, binary parallel search is preferable
What is the P-ary search?
A divide and conquer strategy on sorted arrays
What is the process of P-ary search?
Divide input into p parts, all p threads searching for the same key in a different part, each thread checks if the key can be in their part, the selected part is again assigned in equal shares to all threads, and the process is repeated until the search key is found
How does the p-ary search check for the key?
Assuming sorted arrays, each thread needs to look only at first and last elements of part of its subset to determine which part contains the search key
This part is again assigned in equal shares to all threads, and process is repeated until search key is found
What is the complexity of the p-ary search?
O(logpn)
What are search trees?
Another way of representing data in pre-ordered format
What are binary search trees?
Where each node can have two children
How do you traverse a binary search tree?
Compare out key with a node and select left child if its value is lower or right child if it is highter
What is the complexity of binary search tree?
O(log n)
What is a B-tree?
A generalisation of binary search trees where each node can have multiple children
When searching, more than two paths diverge from a single node
Very efficient when combined with p-ary parallel search
The binary search requires the input data to be sorted. What applications might justify that additional step?
Multiple searches, such as database queries. Searching performance depends on data distribution so its better if the key is more likely to be near the start of the collection.
What’s the totally rad thing about the step complexity of p-ary?
It scales with the increasing number of threads
