Groups > comp.lang.java.programmer > #5910

Re: StringBuilder Difficulties

From	blmblm@myrealbox.com <blmblm.myrealbox@gmail.com>
Newsgroups	comp.lang.java.programmer
Subject	Re: StringBuilder Difficulties
Date	2011-07-06 16:59 +0000
Organization	None
Message-ID	<97jiioFr6pU2@mid.individual.net> (permalink)
References	<c4tk07dv1pq7u8k32qd6b7o1brc2rj8r30@4ax.com> <jsu6171vmasu6jfvsbroa052n8u7ukarr3@4ax.com> <97hd9sFa1jU2@mid.individual.net> <rma717948c79cs9nnupdqjrhuu965bag76@4ax.com>

Show all headers | View raw

In article <rma717948c79cs9nnupdqjrhuu965bag76@4ax.com>,
Gene Wirchenko  <genew@ocis.net> wrote:
> On 5 Jul 2011 21:16:44 GMT, blmblm@myrealbox.com
> <blmblm.myrealbox@gmail.com> wrote:
> 
> >In article <jsu6171vmasu6jfvsbroa052n8u7ukarr3@4ax.com>,
> >Gene Wirchenko  <genew@ocis.net> wrote:
> >> On 5 Jul 2011 19:12:39 GMT, blmblm@myrealbox.com
> >> <blmblm.myrealbox@gmail.com> wrote:
> >> 
> >> [snip]
> >> 
> >> >What I found is that HashSet was noticeably faster on all the
> >> >systems where I ran the benchmarks.  Unless you need for the set
> >> >to be sorted (and it's not apparent from your code that you do),
> >> >why not .... ?  (I'm curious too about why you chose TreeSet in
> >> >the first place.  ? )
> >> 
> >>   1) I can output the set in order without having to do anything else.
> >> My real program has a lot of debugging info dumping.  (Read as "checks
> >> that I have not done something wrong".)
> >
> >
> >Ah.  Well, yes, then you probably do need a SortedSet, though
> >considering that you initially build the set from a string that's in
> >order, maybe you could use that (the string) instead.  Just sayin',
> >maybe.
> 
>      I set the string value that way so that the binary search would
> work.

Ah, okay.  

> >>   2) When I read "hash", I think "collision", and I get nervous.
> >> Nothing I read reassured me that that could not happen.
> 
> >Why would that make you nervous?  If you're worried about
> >correctness, um, as far as I know hash tables are supposed to
> >deal with collisions in some way that preserves the overall "map"
> >semantics.  Performance may suffer if there are a lot of collisions,
> >but -- benchmark on the system(s) of interest and check?
> 
>      I would need to know what the behaviour is supposed to be.  

Maybe there's something I'm not understanding, but as far as I
know hash tables (including the Java HashMap class that, according
to the API, is used by HashSet) are required to do something that
allows storing multiple distinct keys that have the same hash code
("collisions").  The implementation that comes to mind is one that
has some sort of list for each possible hashcode value.  Obviously(?)
performance suffers if very many of these lists have more than one
or a few elements, but correctness (in the sense of considering
keys to be equal based only on what equals() returns and not on 
what hashCode() returns) is preserved.

I don't think I'm explaining this very well.  Maybe the following
short test program will do better -- it's a totally contrived example
of using a HashSet to store elements that are distinct but have the
same hash code:

import java.util.*;

public class HashSetTest {

    public static class Foo {
        public final int n;

        public Foo(int n) {
            this.n = n;
        }

        @Override
        public int hashCode() {
            return 0;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj instanceof Foo) {
                return n == ((Foo) obj).n;
            }
            else {
                return false;
            }
        }
    }

    public static void main(String[] args) {
        Set<Foo> s = new HashSet<Foo>();
        // add what should be ten distinct elements
        for (int i = 0; i < 10; ++i) {
            s.add(new Foo(i));
        }
        // add what should be duplicate elements
        for (int i = 0; i < 10; ++i) {
            s.add(new Foo(i));
        }
        // iterate over all elements of s -- this "foreach" syntax
        // is possible AFAIK with all classes that implement Collection
        for (Foo foo : s) {
            // note use of C-like printf
            System.out.printf("foo with value %d, hashcode %d\n",
                    foo.n, foo.hashCode());
        }
    }
}

When I run this I get 10 lines of output, indicating to me that 
whether two elements are considered duplicates depends on equality
as determined by the equals() method rather than on hashcode.

Or maybe I'm once again totally misunderstanding you, and your actual
concern is something else ....

> I
> have something that works for now.  Optimisation comes after getting
> it working.

Well, yeah, sure, but this rather seems at odds with your having
done benchmarking of various ways of looking up a character in a
set of characters.

Anyway if at some point it seems that performance of your lookup 
isn't good enough, it might be worthwhile to explore HashSet, if
you can think of some way to get the debugging information you need
that doesn't depend on being able to retrieve elements from the set
in sorted order.  (E.g., maybe you could do a one-time operation 
that retrieves all the elements, sorts them, and saves the result.)

Or, as supercali* suggests in another post, you could use a
LinkedHashSet.  Replace HashSet with LinkedHashSet in the above test
program to see the difference.  This would require you to build your
set from elements in the right order, but assuming building the set
is a one-time thing, it should be easy enough to sort the elements
before adding them, or so I would think.  

> >>   3) I had to pick something.  If it works, I can change it later.  If
> >> it does not, I have not solved my problem yet.  The former is safer.
> 
> >Sure.  Then again, if you were only concerned about getting something
> >that works, why try various alternatives ....  <shrug>
> 
>      1) Just in case there was a BIG difference.  

In my experiments HashSet was about twice as fast as TreeSet.  Of
course if you needed the sortedness, HashSet is off the table, but
LinkedHashSet (which I did not know about!) seems like it would do
what you need and is about as fast as HashSet on the systems where
I tried it.

The code using java.util.regex.* wasn't as fast on the old system
where I did my initial experiments, but on a newer system it seems
to give performance comparable to (Linked)HashSet.

Just sayin'.

> 2) To learn more
> about Java.  At some point though, I have to do something useful with
> it.

Sure.  I'm dimly aware that I'm probably flogging a horse that has long
since shuffled off this mortal coil.

>      My preprocessor is shaping up nicely.  I have to write the symbol
> define command code, handle the include command, and handle output to
> a file.  That is about it.  Which means that there are probably only
> about three other things that I will come up.

And then you can go back to coding in a language you like better?  :-)

-- 
B. L. Massingill
ObDisclaimer:  I don't speak for my employers; they return the favor.

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-28 17:54 -0700
  Re: StringBuilder Difficulties Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-28 21:29 -0400
    Re: StringBuilder Difficulties Lew <noone@lewscanon.com> - 2011-06-29 00:48 -0400
      Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-29 12:19 -0700
    Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-29 12:11 -0700
      Re: StringBuilder Difficulties Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-29 22:06 -0400
  Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-06-29 20:17 +0000
    Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-29 18:55 -0700
      Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-06-30 20:30 +0000
        Re: StringBuilder Difficulties Patricia Shanahan <pats@acm.org> - 2011-06-30 14:17 -0700
          Re: StringBuilder Difficulties Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-30 21:36 -0400
            Re: StringBuilder Difficulties "John B. Matthews" <nospam@nospam.invalid> - 2011-07-01 01:41 -0400
        Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-30 14:26 -0700
          Re: StringBuilder Difficulties Steve Sobol <sjsobol@JustThe.net> - 2011-06-30 17:33 -0700
          Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-01 20:47 +0000
            Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-01 17:29 -0700
              Re: StringBuilder Difficulties rossum <rossum48@coldmail.com> - 2011-07-02 11:36 +0100
              Re: StringBuilder Difficulties Robert Klemme <shortcutter@googlemail.com> - 2011-07-02 12:58 +0200
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-04 07:52 -0700
                Re: StringBuilder Difficulties Robert Klemme <shortcutter@googlemail.com> - 2011-07-04 21:45 +0200
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-05 02:06 -0400
                Re: StringBuilder Difficulties markspace <-@.> - 2011-07-05 09:32 -0700
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-05 14:13 -0400
                Re: StringBuilder Difficulties markspace <-@.> - 2011-07-05 12:51 -0700
                Re: StringBuilder Difficulties Silvio <silvio@moc.com> - 2011-07-05 23:16 +0200
                Re: StringBuilder Difficulties markspace <-@.> - 2011-07-05 15:08 -0700
                Re: StringBuilder Difficulties Silvio <silvio@moc.com> - 2011-07-06 09:41 +0200
                Re: StringBuilder Difficulties "eye" <eye@mocka.com> - 2011-07-06 09:55 +0000
                Re: StringBuilder Difficulties thoolen <thoolen@tholenbot.thorium> - 2011-07-06 05:37 -0400
                Re: StringBuilder Difficulties "thoolen" <thoolen@tholenbot.thorium> - 2011-07-06 08:43 -0400
                Re: StringBuilder Difficulties thoolen <thoolen@tholenbot.thorium> - 2011-07-06 22:30 -0400
                Re: StringBuilder Difficulties "Stefan Robacki" <noemail@noemail.foobar> - 2011-07-06 00:04 -0400
                Re: StringBuilder Difficulties thoolen <thoolen@tholenbot.thorium> - 2011-07-06 05:45 -0400
                Re: StringBuilder Difficulties thoolen <thoolen@tholenbot.thorium> - 2011-07-06 08:26 -0400
                Re: StringBuilder Difficulties thoolen <thoolen@tholenbot.thorium> - 2011-07-06 22:36 -0400
                Re: StringBuilder Difficulties "tholen@antispam.ham" <tholen@ifa.hawaii.edu> - 2011-07-06 06:09 -0700
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 22:40 -0400
                Re: StringBuilder Difficulties John Doe <jdoe@usenetlove.invalid> - 2011-07-14 06:50 +0000
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-14 02:58 -0400
                Re: StringBuilder Difficulties Jane Doe <jdoe@love.in.d.jungle.invalid> - 2011-07-14 10:20 -0400
                Re: StringBuilder Difficulties thoolen <tholen01@gmail.com> - 2011-07-14 07:33 -0700
                Re: StringBuilder Difficulties Stanimir Stamenkov <s7an10@netscape.net> - 2011-07-05 23:44 +0300
                Re: StringBuilder Difficulties markspace <-@.> - 2011-07-05 14:08 -0700
              Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-02 18:33 +0000
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-02 16:56 -0400
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-03 01:34 +0000
                Re: StringBuilder Difficulties Patricia Shanahan <pats@acm.org> - 2011-07-02 19:55 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-04 03:32 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-04 08:04 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-05 19:12 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-05 14:06 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-05 21:16 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-05 17:29 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-06 16:59 +0000
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 19:52 -0400
                Re: StringBuilder Difficulties Patricia Shanahan <pats@acm.org> - 2011-07-06 16:58 -0700
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 19:52 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 21:54 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 22:18 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 22:41 -0400
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-08 17:45 +0000
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 05:48 -0400
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-06 16:59 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-06 10:56 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-08 17:44 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-08 11:51 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-10 19:08 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-11 07:54 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-11 22:37 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-11 15:52 -0700
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 08:25 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 19:41 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 19:58 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 21:57 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 22:17 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 22:44 -0400
                Re: StringBuilder Difficulties Steve Erwin <trollHunter@Usenet.4.usenetizens.org.invalid> - 2011-07-07 12:51 +1000
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 23:02 -0400
                Re: StringBuilder Difficulties John Doe <jdoe@usenetlove.invalid> - 2011-07-14 06:32 +0000
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-14 02:57 -0400
                Re: StringBuilder Difficulties Jane Doe <jdoe@love.in.d.jungle.invalid> - 2011-07-14 10:07 -0400
                Re: StringBuilder Difficulties thoolen <tholen01@gmail.com> - 2011-07-14 07:24 -0700
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-04 07:58 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-05 19:09 +0000
                Re: StringBuilder Difficulties KitKat <kitkat_11697@gmail.example.com> - 2011-07-05 15:15 -0400
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-05 20:03 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-05 14:11 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-06 16:55 +0000
      Re: StringBuilder Difficulties lewbloch <lewbloch@gmail.com> - 2011-07-03 00:08 -0700
        Re: StringBuilder Difficulties Robert Klemme <shortcutter@googlemail.com> - 2011-07-03 12:35 +0200
          Re: StringBuilder Difficulties lewbloch <lewbloch@gmail.com> - 2011-07-04 04:07 -0700
  Re: StringBuilder Difficulties Patricia Shanahan <pats@acm.org> - 2011-06-29 14:38 -0700
    Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-29 15:00 -0700
      Re: StringBuilder Difficulties Patricia Shanahan <pats@acm.org> - 2011-06-29 15:52 -0700
        Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-29 18:58 -0700
          Re: StringBuilder Difficulties Patricia Shanahan <pats@acm.org> - 2011-06-29 19:26 -0700
          Re: StringBuilder Difficulties lewbloch <lewbloch@gmail.com> - 2011-07-03 00:11 -0700
  Re: StringBuilder Difficulties Roedy Green <see_website@mindprod.com.invalid> - 2011-06-29 18:32 -0700

csiph-web