Results 1 to 13 of 13
  1. #1
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default Efficiency of Searching

    I am taking a data structures course, and could use a little help with the concept of searching efficiency. So far, we have studied how having an indexed array can be used when searching a file, but one of the questions is confusing me. It asks:

    Compare the efficiency of searching an ordered sequential table of size b and searching an un-ordered table of the same size for the key key:

    - If no record with 'key key' is present

    I have not been able to get in contact with the instructor, but im guessing 'key key' is not a typo. Can someone help clarify what this is asking? I would guess that its saying if we have 2 tables, one ordered, and one unordered, is the searching efficiency effected by having a 'key key'. I'm just a little confused, any help would be greatly appreciated.

  2. #2
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    How would you search something that's unordered manually? Would you check each element, or check random elements? How would you find page x in some book? Would you use any sort of method to get there as quickly as possible? Or would you check each page to see if it is page x? Looking up linear search, and binary search will be helpful as well.

  3. #3
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    If its unordered and no 'key key', I would guess that you would try to do it almost like a dictionary search, where you grab a handful of 'pages' and if you go too far, back up, if you pass it, go forward, etc, but I'm not sure how to articulate that. Im guessing were comparing the big oh notation for the efficiency, so with no key key for an unordered table it would be O(n^2).
    Last edited by fam2315; 08-03-2011 at 01:32 AM.

  4. #4
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    If you are given an unordered dictionary, how would you know if you've gone past the key? Unordered implies not in alphabetic order. So you could have the word Apple, followed by Zebra, followed by Orange. So what would you do to find some randomly given word? Would you be able to devise any 'smart' approach? Or would you have to use a brute force approach?

    Now an ordered dictionary may have a different approach. Since you know for a fact that Apple comes before orange, and orange comes before zebra, you can think up a 'smart' approach.

  5. #5
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    I see,

    So for an unordered table, since there is no key for the file, we would have to perform n searches to find the record we want, where n is the number of records, so its a linear search.

    If it is ordered, I think the average was n/2 comparisons.

    I guess i'm more confused because when we talk about searching a 'table' I don't know what data structure in java that would be. A 2d array?
    Last edited by fam2315; 08-03-2011 at 01:40 AM.

  6. #6
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    You are right on the unordered list, it will be O(n), but I don't believe you are correct on the next part. When you search a dictionary, and think like a computer, you don't know that if you are looking for a z word to start near the back, a computer would start at exactly halfway. You would test the page exactly halfway through the dictionary and either three things can happen. The word can be on the halfway page, the word can be less than the halfway page, or it will be past the halfway page. You can repeat this successive halving and checking approach and guarantee that you will eventually find the key(if it exists).

  7. #7
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    For ordered lists, once we go beyond the point where the item should be, we can stop, because (assuming the data is ordered), the key is not there. So after we perform k searches, and k is greater or lower (depending on the order of data, ascending or descending), we know the key is not present in the list.
    Last edited by fam2315; 08-03-2011 at 01:54 AM.

  8. #8
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    Not so in an ordered list. If you have a dictionary, let's say the halfway word happens to be Mango, and the key is zebra(and let's say this dictionary doesn't know what a zebra is), would you ever be checking any page before Mango? Is it possible that a word that starts with a Z can ever be found in the A section, or b, c, d,... ?

    Try this, take an ordered list of 1-100, and don't specify a key, but write on paper the successive halfs. I'll even start you out:
    100->50->75->...

    Finish this, at each halfway point you can choose whether you want to go up or down, but this will eventually terminate. Once it does terminate, count how many steps you took and see how quickly(or slowly) it terminated and use this to try to hypothesize what the big o notation will be.

  9. #9
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    I have one more question:

    Suppose you have a file of data of approximately 10,000 personnel records using Social Security numbers as primary key. You have decided to store the file as an indexed sequential structure.

    How should the index be accessed?

    What is meant by accessing the index?

  10. #10
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    What kind of data structure do you think should be used? Do you know of any data structures that can be indexed into? Which ones are sequential?(meaning to find the nth item you must first check the 1st, 2nd,...,n-1,nth)

  11. #11
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    a LinkedList is sequential but an array can be indexed.

  12. #12
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    Check the linked list API to see if it has any methods to get index i.

  13. #13
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,656
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by fam2315 View Post
    Compare the efficiency of searching an ordered sequential table of size b and searching an un-ordered table of the same size for the key key:
    Does the term 'sequential' imply that you can only traverse the table one record by one record? Or can you hop through the table at will? If it is the first an ordered table takes b/2 steps on average, an unordered table takes b steps. If you can hop through the table(s) randomly an ordererd table takes 2log(b) steps to conclude that a record is not in the table.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Efficiency of searching a list
    By fam2315 in forum New To Java
    Replies: 9
    Last Post: 06-29-2011, 03:34 AM
  2. Cryptography Efficiency
    By joshdgreen in forum Advanced Java
    Replies: 22
    Last Post: 10-29-2010, 09:16 AM
  3. URLConnection Efficiency
    By Lil_Aziz1 in forum New To Java
    Replies: 22
    Last Post: 08-19-2010, 06:27 PM
  4. An Efficiency Question
    By Revenna in forum Java 2D
    Replies: 0
    Last Post: 06-25-2010, 07:22 AM
  5. method efficiency
    By TheWave in forum Advanced Java
    Replies: 0
    Last Post: 02-13-2008, 04:11 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •