5 Replies - 950 Views - Last Post: 14 September 2010 - 06:43 PM Rate Topic: -----

#1 sh1n3  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 24
  • View blog
  • Posts: 164
  • Joined: 22-April 10

Search char array

Posted 13 September 2010 - 07:08 AM

Hey this program is something similar to a search using character arrays. Static import used for my convenience...remove it if you like! But how do I make this kind of search more efficient? It takes 50,000 tries to find "000" , I know that it is so because '0' is the last character in the array. But still can I bring this number down?

import static java.lang.System.out;
class Pass {
    String p=null;
    char[] charset={'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 't', 'w', 'x', 'y', 'z', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0'};
    public static void main(String[] args) {
        Pass pas=new Pass();
        pas.p=args[0];
        pas.check();
    }
    public void check() {
        int count=0;
        outer:
        for (int a=0;a<charset.length;a++) {
            for (int b=0;b<charset.length;b++) {
                for (int c=0;c<charset.length;c++) {
                    count++;
                    String t=charset[a]+""+charset[b]+""+charset[c];
                    if (p.equalsIgnoreCase(t)) {
                        out.println("Match Found after "+count+" tries!");
                        break outer;
                    }
                }
            }
        }
    }
}



Is This A Good Question/Topic? 0
  • +

Replies To: Search char array

#2 cfoley  Icon User is online

  • Cabbage
  • member icon

Reputation: 1949
  • View blog
  • Posts: 4,048
  • Joined: 11-December 07

Re: Search char array

Posted 13 September 2010 - 07:14 AM

Take each char of p in turn.
See if it is in the charSet.
If they are all in charTet you have a match.

Worst case is 3 * charSet.length instead of charSet.length ^ 3.
Was This Post Helpful? 1
  • +
  • -

#3 sh1n3  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 24
  • View blog
  • Posts: 164
  • Joined: 22-April 10

Re: Search char array

Posted 13 September 2010 - 07:19 AM

Yeah you're absolutely right about that! :) But can it be improved further?
I have been thinking about this since I learnt about nested for loops!

This post has been edited by sh1n3: 13 September 2010 - 07:20 AM

Was This Post Helpful? 0
  • +
  • -

#4 cfoley  Icon User is online

  • Cabbage
  • member icon

Reputation: 1949
  • View blog
  • Posts: 4,048
  • Joined: 11-December 07

Re: Search char array

Posted 13 September 2010 - 07:36 AM

Of course it can. :)

Right now you are looking up something in a lits of n items. Worst case, it takes n comparisons.

You can change this to log(n) comparisons by doing a binary search. For this you have to begin with a sorted char array of your charset. You start at the middle one then because it's sorted you can rule out half the list. Jump to the middle of what's left and rule half of that out too. Continue until you find what you're after or you run out of options.

You can improve this further and look up in guaranteed constant time. For this you need a hash table to store your charset. You'll need to look that up for a proper description but the essence is this:

When storing a value, compute the value's hash. This is its location in the array. To see if a value is in the array, compute the hash and look up only at that value. If the hash function is fast, it takes you right to where the value should be. Writing hash functions and designing hashtables can get pretty in depth but that's the 101 on how they work. Luckily, Java has a Hashtable and (my favourite) a HashMap class ready to use.

Now, just because you've gone from 30 comparisons to 1 doesn't make it faster. For a very short array, running through it will be the fastest. A binary search might be a bit faster for yours but the extra code probably isn't worth your while.

Your array would have to get quite a bit bigger for a hashtable to speed things up. It'll work about as fast for any size of list... but the current approach will be faster for small charsets like yours.

Hope that helps!
Was This Post Helpful? 0
  • +
  • -

#5 sh1n3  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 24
  • View blog
  • Posts: 164
  • Joined: 22-April 10

Re: Search char array

Posted 14 September 2010 - 06:17 PM

Yeah exactly thanks, what I'm planning to do is like a secret code encoder / decoder that doesn't use the normal a-z 0-9 charset...it is going to use a more local charset which probably contains 150+ chars. I'll look into hash tables and maps! :)
Was This Post Helpful? 0
  • +
  • -

#6 cfoley  Icon User is online

  • Cabbage
  • member icon

Reputation: 1949
  • View blog
  • Posts: 4,048
  • Joined: 11-December 07

Re: Search char array

Posted 14 September 2010 - 06:43 PM

A HashMap sounds exactly like what you're looking for. :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1