I&C SCI 46 Lecture Notes - Lecture 7: Complexity Class, Equivalence Class, Instance Variable

• School: UC-Irvine
• Department: Information and Computer Science
• Course: I&C SCI 46
• Professor: Richard Pattis

Document Summary

small efficiency improvement for hash equivalence (for 200,000 items) In this lecture we will move away from looking at complexity classes for the equivalence class and focus on various way to improved (the constant for) performance: i timed the standard compress_to_root algorithm in my solution 5 times. 1. 287; 1. 283; 1. 282; 1. 282; 1. 282 : average = 1. 283: next, i pre-allocate compress_set as private instance variable. In this way its constructor/destructor is called just once -when the equivalence is constructed- and not once each time compress_to_root is called. But not it must be cleared before return, so that the next time compress_to_root is called it is empty. Hashequivalence::hashequivalence (int (*ahash)(const t& element)) : hash(ahash), parent(ahash), root_size(ahash), compress_set(ahash) { compress_set. clear(); You will find the average size of this set in quiz #8. Hashequivalence::hashequivalence (int (*ahash)(const t& element)) : hash(ahash), parent(ahash), root_size(ahash), compress_set() { Note, i left the name as compress_set even though i should rename it compress_queue.