Programming Pearls Clmn 13
Search where to write a blog? Haha!
How many ways to do a search?
- use library
- linear structure: linear search and binary search
- binary search tree (BST): SBT, Splay Tree, AVL Tree, Treap and RBT
- Bins
We have see a lot about linear and binary search using linear structure. We should pay attention to those we are not familiar with.
Tree
I suggest that one should know all these tree structures and can write at least 2 of them immediately. That’s the way of study tree structures.
Maybe write some ACM problems in the searching category. Use multiple solutions to solve one classic question. ^_^
Bin
I want to admit that bin is a tricky structure. I made a easy question for my OIer mate. It is a structure-oriented question. There will be a lot of duplicated number in a list. All of the numbers are not greater than 100000, maybe. And you need to solve the list first and then make some decision. The list is not available to be sorted using quick-sort within the limited time. So, our best choice is bin, or you can also use a simple array — one number keep one slot.
One bad thing is that, I could now see any wide use of bins in other application situations. It could because that I know too little. Anyway, still, bin is a good choice when you want to do searching.
Library
Hmm, library is good. Library is necessary.
But I insist not using these powerful libraries during learning. You use TreeMap, you use HashMap, but you know neither.
I suggestion learner should go through C programming language and then go to read Pointer on C and then learn algorithm and data structure using C or C++. That’s the way of learning. Definitely not using Java — Learn Java syntax, learn how to read Java doc. Then you are powerful enough by using thousands of libraries and an IDE…
Another way is that you know Lisp, Scheme or Haskell and then go to read Structure and Interpretation of Computer Programs. I admit that I do not know this book much. But I will read it may be during next semester. Not too far later.
I write this review after quite a long time after I finished this book. Because I went back home……T_T
I have to say: Home, Sweet home, You made me do not want to study at all!!!
