Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

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

Re: Is there a better way to group and sort objects?

Show all headers | View raw

On Wed, 08 Aug 2018 07:45:13 -0400, Eric Sosman wrote:

> On 8/8/2018 7:22 AM, Martin Gregorie wrote:
>> On Wed, 08 Aug 2018 06:57:33 -0400, Eric Sosman wrote:
>> 
>>> On 8/8/2018 4:20 AM, Martin Gregorie wrote:
>>>> On Tue, 07 Aug 2018 06:00:19 -0700, Eric Douglas wrote:
>>>>
>>>>> I want to combine and sort objects by key properties and merge their
>>>>> secondary properties.  Is there a better way?  This is what I came
>>>>> up with..
>>>>>
>>>> Given your ..and sort... requirement, I'd use a TreeMap rather than a
>>>> HashMap because storing items in key sequence is implicit. In
>>>> addition,
>>>> its search efficiency rises as the tree gets bigger; if the treemap
>>>> contains 2**23 entries a worst case search only does 23 key
>>>> comparisons.
>>>
>>>       ... except that he sorts on a field of the mapped values,
>>> not on the map keys.  Specifically, if he has two instances with
>>> `var1' values of 2 and 10 they will sort in that order, but their map
>>> keys will sort in the order "10" followed by "2".
>> 
>> Another thought, seeing that Eric wants to use an integer key, why not
>> store the key value in an Integer, which is already Comparable, rather
>> than making the class containing the int key Comparable?
>> 
>> This is effectively what I do when manipulating a TreeMap of objects
>> with String values as keys. A scan of the class definitions shows that
>> the same idea should work for a HashMap.
> 
>      As an extreme case, he might use the object itself as both the
> key and value in a Map<TestClass,TestClass>.  I sometimes find this a
> useful substitute for a Set<TestClass>, because the Set will tell me
> whether an equal item is or isn't present, but will not deliver the
> pre-existing item.
> 
>      If he were to do this, though, it would be a *very* good idea to
> make his `var1' field `final'.  (As things stand it's not required, but
> even so: Massive confusion would ensue were it to change.)
> 
>      To a related matter, I'm not convinced TreeMap is more efficient
> than HashMap-and-sort-afterwards in a situation where the ordering is
> needed only after all items have been added.  If anything, I'd imagine
> TreeMap would be somewhat less efficient because it expends effort in
> keeping itself "always sorted" even while the order is unimportant: it
> carefully computes {3} and {1,3} and {1,2,3} and ... {1,2,3,...,N} even
> though only the last of these results is required.  I'd save TreeMap for
> occasions when the intermediate orderings are to be used or when
> "closest match" (as opposed to "present/absent") searches are needed.

Actually, red-black trees (which is the tree variant TreeMap uses) is 
surprisingly efficient both for searches and insertions. Some time back 
(1999) I built an implementation (C, not Java) that hit 25,000 lookups[*] 
a second running on a single core Alphaserver chip with half a million 
nodes in the tree and in production was still managing 35,000 lookups a 
second with 100,000,000 nodes in the tree when running on the full holy-
schmoly multicore Alphaserver. 

Nodes were simple: a 13 character string and a 1000 entry bitlist. It 
stored 19 digit international phone numbers, compressing them by storing 
the first 13 digits as a string and using the bitlist position to 
represent the last 3 digits, thus theoretically reducing the actual node 
count by a factor of 1000. This was based on the assumption that the last 
three digits of a phone number are fully used though the rest of the 
number may form a sparse array. Assumption checked with and agreed by 
experts in the field, but proved incorrect in practise - the last three 
digits were also sparse in reality, but still dense enough for this 
representation to save memory space. 

[*] 'Lookup in this application meant "check if the key is present and, 
if not add a new node" Nodes 

The only thing that was slow was startup if the trees had to be rebuilt 
from scratch: that could take 40 minutes. Solved by periodically 
snapshotting the tree's memory space to disk and at shutdown. Starting up 
was now much faster since the trees could be reloaded from disk rather 
than rebuilt from a database.

So, in short, yes I agree that many tree map implementations are slow, 
especially if the input data is in a pathological order, but this does 
not affect to red-black trees, which are self-balancing.
 

-- 
Martin    | martin at
Gregorie  | gregorie dot org

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

Thread

Is there a better way to group and sort objects? Eric Douglas <e.d.programmer@gmail.com> - 2018-08-07 06:00 -0700
  Re: Is there a better way to group and sort objects? Eric Sosman <esosman@comcast-dot-net.invalid> - 2018-08-07 09:44 -0400
    Re: Is there a better way to group and sort objects? Eric Sosman <esosman@comcast-dot-net.invalid> - 2018-08-07 11:33 -0400
    Re: Is there a better way to group and sort objects? Eric Douglas <e.d.programmer@gmail.com> - 2018-08-07 10:22 -0700
      Re: Is there a better way to group and sort objects? Eric Sosman <esosman@comcast-dot-net.invalid> - 2018-08-07 14:16 -0400
        Re: Is there a better way to group and sort objects? Eric Sosman <esosman@comcast-dot-net.invalid> - 2018-08-07 14:36 -0400
        Re: Is there a better way to group and sort objects? Eric Douglas <e.d.programmer@gmail.com> - 2018-08-07 12:13 -0700
          Re: Is there a better way to group and sort objects? Eric Sosman <esosman@comcast-dot-net.invalid> - 2018-08-07 16:00 -0400
  Re: Is there a better way to group and sort objects? Martin Gregorie <martin@mydomain.invalid> - 2018-08-08 08:20 +0000
    Re: Is there a better way to group and sort objects? Eric Sosman <esosman@comcast-dot-net.invalid> - 2018-08-08 06:57 -0400
      Re: Is there a better way to group and sort objects? Martin Gregorie <martin@mydomain.invalid> - 2018-08-08 11:08 +0000
      Re: Is there a better way to group and sort objects? Martin Gregorie <martin@mydomain.invalid> - 2018-08-08 11:22 +0000
        Re: Is there a better way to group and sort objects? Eric Sosman <esosman@comcast-dot-net.invalid> - 2018-08-08 07:45 -0400
          Re: Is there a better way to group and sort objects? Martin Gregorie <martin@mydomain.invalid> - 2018-08-08 14:12 +0000
        Re: Is there a better way to group and sort objects? Eric Douglas <e.d.programmer@gmail.com> - 2018-08-08 05:50 -0700
          Re: Is there a better way to group and sort objects? Eric Sosman <esosman@comcast-dot-net.invalid> - 2018-08-08 09:23 -0400
            Re: Is there a better way to group and sort objects? Eric Douglas <e.d.programmer@gmail.com> - 2018-08-08 06:47 -0700
              Re: Is there a better way to group and sort objects? Eric Sosman <esosman@comcast-dot-net.invalid> - 2018-08-08 10:31 -0400
                Re: Is there a better way to group and sort objects? Eric Douglas <e.d.programmer@gmail.com> - 2018-08-08 08:24 -0700
          Re: Is there a better way to group and sort objects? Robert Klemme <shortcutter@googlemail.com> - 2018-08-14 14:06 +0200
            Re: Is there a better way to group and sort objects? Eric Douglas <e.d.programmer@gmail.com> - 2018-08-14 05:49 -0700
  Re: Is there a better way to group and sort objects? Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2018-08-09 16:06 +0200
    Re: Is there a better way to group and sort objects? Eric Douglas <e.d.programmer@gmail.com> - 2018-08-14 05:47 -0700

csiph-web