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

Groups > comp.lang.java.programmer > #36682 > unrolled thread

How to parse an array?

Back to article view | Back to comp.lang.java.programmer

Contents

  How to parse an array? Eric Douglas <e.d.programmer@gmail.com> - 2017-06-20 12:18 -0700
    Re: How to parse an array? Knute Johnson <nospam@rabbitbrush.frazmtn.com> - 2017-06-20 14:49 -0500
    Re: How to parse an array? Arne Vajhøj <arne@vajhoej.dk> - 2017-06-20 16:15 -0400
    Re: How to parse an array? Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-06-20 16:23 -0400
    Re: How to parse an array? Robert Klemme <shortcutter@googlemail.com> - 2017-06-24 12:02 +0200
      Re: How to parse an array? Eric Douglas <e.d.programmer@gmail.com> - 2017-06-26 05:10 -0700
        Re: How to parse an array? Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-06-26 09:36 -0400
          Re: How to parse an array? Eric Douglas <e.d.programmer@gmail.com> - 2017-06-26 07:47 -0700
            Re: How to parse an array? Martin Gregorie <martin@address-in-sig.invalid> - 2017-06-26 15:47 +0000
          Re: How to parse an array? Arne Vajhøj <arne@vajhoej.dk> - 2017-06-26 20:37 -0400
        Re: How to parse an array? lewbloch@gmail.com - 2017-06-27 12:29 -0700
          Re: How to parse an array? Eric Douglas <e.d.programmer@gmail.com> - 2017-06-27 12:50 -0700
            Re: How to parse an array? Martin Gregorie <martin@address-in-sig.invalid> - 2017-06-27 20:05 +0000
              Re: How to parse an array? Eric Douglas <e.d.programmer@gmail.com> - 2017-06-27 14:01 -0700
                Re: How to parse an array? Martin Gregorie <martin@address-in-sig.invalid> - 2017-06-27 22:34 +0000
                  Re: How to parse an array? Eric Douglas <e.d.programmer@gmail.com> - 2017-06-28 05:10 -0700
                    Re: How to parse an array? Martin Gregorie <martin@address-in-sig.invalid> - 2017-06-28 19:09 +0000
                      Re: How to parse an array? Eric Douglas <e.d.programmer@gmail.com> - 2017-06-28 13:02 -0700
                        Re: How to parse an array? Martin Gregorie <martin@address-in-sig.invalid> - 2017-06-28 21:55 +0000
                          Re: How to parse an array? Eric Douglas <e.d.programmer@gmail.com> - 2017-06-30 06:10 -0700
                            Re: How to parse an array? Martin Gregorie <martin@address-in-sig.invalid> - 2017-06-30 16:52 +0000
    Re: How to parse an array? Jerry Stuckle <jstucklex@attglobal.net> - 2017-06-24 16:34 -0400
      Re: How to parse an array? Martin Gregorie <martin@address-in-sig.invalid> - 2017-06-24 22:42 +0000
        Re: How to parse an array? Jerry Stuckle <jstucklex@attglobal.net> - 2017-06-24 20:05 -0400
        Re: How to parse an array? Robert Klemme <shortcutter@googlemail.com> - 2017-06-25 12:20 +0200

Page 1 of 2  [1] 2  Next page →

#36682 — How to parse an array?

I'm writing a method to take 2 arrays and return the subset of the first array.  Is there a more efficient way than creating a new array and iterating?

ArrayList<String> list1 = new ArrayList();
list1.add("AA");
list1.add("CC");
list1.add("DD");
list1.add("BB");
list1.add("EE");
ArrayList<Integer> list2 = new ArrayList();
list2.add(1);
list2.add(3);
ArrayList<String> retval = new ArrayList();
for (int i : list2) {
     retval.add(list1.get(i));
}
Collections.sort(retval);
System.out.println(retval);

[toc] | [next] | [standalone]

#36684

On 6/20/2017 14:18, Eric Douglas wrote:
> I'm writing a method to take 2 arrays and return the subset of the first array.  Is there a more efficient way than creating a new array and iterating?
> 
> ArrayList<String> list1 = new ArrayList();
> list1.add("AA");
> list1.add("CC");
> list1.add("DD");
> list1.add("BB");
> list1.add("EE");
> ArrayList<Integer> list2 = new ArrayList();
> list2.add(1);
> list2.add(3);
> ArrayList<String> retval = new ArrayList();
> for (int i : list2) {
>       retval.add(list1.get(i));
> }
> Collections.sort(retval);
> System.out.println(retval);
> 

I have no idea if it is efficient or not:

import java.util.*;
import java.util.stream.*;
import static java.util.stream.Collectors.*;

public class test4 {
     public static void main(String... args) {
         List<String> list1 = Arrays.asList("AA","CC","DD","BB","EE");
         List<Integer> list2 = Arrays.asList(1,3);

         List<String> list = list2.stream().
          map(i -> list1.get(i)).sorted().
          collect(toList());
         System.out.println(list);
     }
}



-- 

Knute Johnson

[toc] | [prev] | [next] | [standalone]

#36685

On 6/20/2017 3:18 PM, Eric Douglas wrote:
> I'm writing a method to take 2 arrays and return the subset of the first array.
> Is there a more efficient way than creating a new array and iterating?
> 
> ArrayList<String> list1 = new ArrayList();
> list1.add("AA");
> list1.add("CC");
> list1.add("DD");
> list1.add("BB");
> list1.add("EE");
> ArrayList<Integer> list2 = new ArrayList();
> list2.add(1);
> list2.add(3);
> ArrayList<String> retval = new ArrayList();
> for (int i : list2) {
>       retval.add(list1.get(i));
> }
> Collections.sort(retval);
> System.out.println(retval);

The problems must be O(n) in both list sizes.

Your code is O(n).

And your code is easy to read.

I don't see any urgent need to do it differently.

Arne

[toc] | [prev] | [next] | [standalone]

#36686

On 6/20/2017 3:18 PM, Eric Douglas wrote:
> I'm writing a method to take 2 arrays and return the subset of the first array.  Is there a more efficient way than creating a new array and iterating?

     It would remove some few obstacles to understanding if you
were to stop treating `ArrayList' and `array' as synonyms.  In
return, I will forswear using `4' to mean `for'.  Deal?

> ArrayList<String> list1 = new ArrayList(); > list1.add("AA");
> list1.add("CC");
> list1.add("DD");
> list1.add("BB");
> list1.add("EE");
> ArrayList<Integer> list2 = new ArrayList();
> list2.add(1);
> list2.add(3);
> ArrayList<String> retval = new ArrayList();

     `new ArrayList<>(list2.size())' might be a bit more efficient,
as it uses the minimum memory and avoids any expansions of too-short
intermediate lists.

> for (int i : list2) {
>       retval.add(list1.get(i));

     Aside: This might throw IndexOutOfBoundsException.  If you
"know things" about the length of `list1' and the contents of
`list2', that might not be a concern.

> }
> Collections.sort(retval);

     Aside: You could get a NullPointerException during the sort
if `list1' contains any nulls that are selected by the contents
of `list2'.  Again, this may not be a concern if you have
sufficient prior knowledge.

> System.out.println(retval);

     There are certainly other ways to write this -- as a stream
pipeline, for example.  Whether the alternatives would be more or
less efficient is something you'd need to measure for yourself.
My guess (*no* hard evidence, mind you) is that "manual" methods
would win if `list2' is short, streams would win if it's Really
Long (because you could parallelize), and there'd probably be a
rather wide intermediate range of lengths where differences might
be difficult to measure.

     And, of course, you could always use arrays instead.

-- 
esosman@comcast-dot-net.invalid
Thirteen hundred ten days to go.

[toc] | [prev] | [next] | [standalone]

#36710

On 20.06.2017 21:29, Stefan Ram wrote:
> Eric Douglas <e.d.programmer@gmail.com> writes:
>> I'm writing a method to take 2 arrays and return the subset of the first array.
> 
>    »The subset of the first array« makes no sense in English,
>    because
> 
>    1.) an array is not a set, so it does not have subsets, and
> 
>    2.) a set might have multiple subsets, it's not clear which
>        subset you would like to return.

Plus, there are neither arrays nor parsing involved.  From the code it 
seems he wants to use a data structure as index into the first one.  The 
thing is, we do not know where the index numbers come from.  Maybe they 
could be stored in a static array because they never change.  Without 
context the code does not make much sense to me.

Cheers

	robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

[toc] | [prev] | [next] | [standalone]

#36727

On Saturday, June 24, 2017 at 6:03:03 AM UTC-4, Robert Klemme wrote:
> Plus, there are neither arrays nor parsing involved.  From the code it 
> seems he wants to use a data structure as index into the first one.  The 
> thing is, we do not know where the index numbers come from.  Maybe they 
> could be stored in a static array because they never change.  Without 
> context the code does not make much sense to me.

ArrayList is the simplest way to do it that I'm aware of.
Both arrays could be anything, from String[] to LinkedList, but they just need to be maintained in simple order and they need to be dynamic.  I believe ArrayList<String> is simpler than String[] when you need to be able to insert and remove elements.  The numbers are the indexes of the elements to be returned so yes they will always be valid indexes and yes they will change.

[toc] | [prev] | [next] | [standalone]

#36729

On 6/26/2017 8:10 AM, Eric Douglas wrote:
> On Saturday, June 24, 2017 at 6:03:03 AM UTC-4, Robert Klemme wrote:
>> Plus, there are neither arrays nor parsing involved.  From the code it
>> seems he wants to use a data structure as index into the first one.  The
>> thing is, we do not know where the index numbers come from.  Maybe they
>> could be stored in a static array because they never change.  Without
>> context the code does not make much sense to me.
> 
> ArrayList is the simplest way to do it that I'm aware of.
> Both arrays could be anything, from String[] to LinkedList, but they just need to be maintained in simple order and they need to be dynamic.  I believe ArrayList<String> is simpler than String[] when you need to be able to insert and remove elements.  The numbers are the indexes of the elements to be returned so yes they will always be valid indexes and yes they will change.

     It's true that dynamic insertions and deletions are simpler to write
with an ArrayList<Thing> than with a Thing[].  But your original post
didn't mention simplicity as a goal; rather, you asked for "a more
efficient way."

     Open-coded Thing[] will be no less efficient than ArrayList<Thing>
(barring silly mistakes in the open code), and stands a good chance of
being more efficient.  By how much remains an open question.

-- 
esosman@comcast-dot-net.invalid
Thirteen hundred four days to go.

[toc] | [prev] | [next] | [standalone]

#36731

On Monday, June 26, 2017 at 9:37:16 AM UTC-4, Eric Sosman wrote:
>      It's true that dynamic insertions and deletions are simpler to write
> with an ArrayList<Thing> than with a Thing[].  But your original post
> didn't mention simplicity as a goal; rather, you asked for "a more
> efficient way."
> 
>      Open-coded Thing[] will be no less efficient than ArrayList<Thing>
> (barring silly mistakes in the open code), and stands a good chance of
> being more efficient.  By how much remains an open question.

Now if you're saying it would be more efficient to use String[] instead of the ArrayList<String> and int[] instead of the ArrayList<Integer>, the first question is how much more and do I end up copying all the code from the ArrayList class when I need to remove or insert elements.  The second question is how do you manage an array of arrays.

Consider list1 is actually ArrayList<String[]>.  Now list2 passes in the integer list of indexes to return and a second parameter passes in a second list of the element order to return.  So each index now returns a String[] set, all sets having the same number of elements, now you want them sorted based on say their second element.

The Oracle Java does this automatically in DefaultRowSorter.sort() but it does take several seconds for each call with a relatively large table as they completely rebuild arrays, while the filtering without sorting appears instant.

[toc] | [prev] | [next] | [standalone]

#36733

On Mon, 26 Jun 2017 07:47:19 -0700, Eric Douglas wrote:

> On Monday, June 26, 2017 at 9:37:16 AM UTC-4, Eric Sosman wrote:
>>      It's true that dynamic insertions and deletions are simpler to
>>      write
>> with an ArrayList<Thing> than with a Thing[].  But your original post
>> didn't mention simplicity as a goal; rather, you asked for "a more
>> efficient way."
>> 
>>      Open-coded Thing[] will be no less efficient than ArrayList<Thing>
>> (barring silly mistakes in the open code), and stands a good chance of
>> being more efficient.  By how much remains an open question.
> 
> Now if you're saying it would be more efficient to use String[] instead
> of the ArrayList<String> and int[] instead of the ArrayList<Integer>,
> the first question is how much more and do I end up copying all the code
> from the ArrayList class when I need to remove or insert elements.  The
> second question is how do you manage an array of arrays.
> 
> Consider list1 is actually ArrayList<String[]>.  Now list2 passes in the
> integer list of indexes to return and a second parameter passes in a
> second list of the element order to return.  So each index now returns a
> String[] set, all sets having the same number of elements, now you want
> them sorted based on say their second element.
> 
> The Oracle Java does this automatically in DefaultRowSorter.sort() but
> it does take several seconds for each call with a relatively large table
> as they completely rebuild arrays, while the filtering without sorting
> appears instant.

If I need an ordered list, and particularly if the list will be 
constructed once and read at least twice, I'll probably use a TreeMap.

TreeMaps are implemented as red-black binary trees, so stepping through a 
one is generally fairly efficient and so are searches since they only 
need to look at one node in each level of the tree: a red-black tree with 
4 million elements has 23 levels [1].  So far I haven't had any 
performance issues doing it this way, and I've used this approach for 
trees that big. However, it may be an inefficient approach for tiny trees 
due to the per-node overheads when adding or removing nodes.

[1] Red-black binary trees are always balanced because they rebalance as 
nodes are added and are not sensitive to the order in which nodes are 
added. This is not the case for simple binary trees, which do not self-
balance and in the extreme case, adding nodes in key sequence, will 
degenerate into an ordered linked list.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#36739

On 6/26/2017 9:36 AM, Eric Sosman wrote:
> On 6/26/2017 8:10 AM, Eric Douglas wrote:
>> On Saturday, June 24, 2017 at 6:03:03 AM UTC-4, Robert Klemme wrote:
>>> Plus, there are neither arrays nor parsing involved.  From the code it
>>> seems he wants to use a data structure as index into the first one.  The
>>> thing is, we do not know where the index numbers come from.  Maybe they
>>> could be stored in a static array because they never change.  Without
>>> context the code does not make much sense to me.
>>
>> ArrayList is the simplest way to do it that I'm aware of.
>> Both arrays could be anything, from String[] to LinkedList, but they 
>> just need to be maintained in simple order and they need to be 
>> dynamic.  I believe ArrayList<String> is simpler than String[] when 
>> you need to be able to insert and remove elements.  The numbers are 
>> the indexes of the elements to be returned so yes they will always be 
>> valid indexes and yes they will change.
> 
>      It's true that dynamic insertions and deletions are simpler to write
> with an ArrayList<Thing> than with a Thing[].  But your original post
> didn't mention simplicity as a goal; rather, you asked for "a more
> efficient way."
> 
>      Open-coded Thing[] will be no less efficient than ArrayList<Thing>
> (barring silly mistakes in the open code), and stands a good chance of
> being more efficient.

I think the most likely for a real world application is that there will
not be a measurable performance difference.

Which of course sort of favor ArrayList<Thing>.

Arne

[toc] | [prev] | [next] | [standalone]

#36740

Eric Douglas wrote:
> Both arrays could be anything, from String[] to LinkedList

Except that they can't, because `LinkedList` is not an array.

What do you mean by "efficient"? Is it "efficient" if you take six months to write a program that runs 0.000001% faster? What if the changes to make it "efficient" require 80 hours per month to maintain? Is that "efficient"?

I suspect that you are asking the wrong question.

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#36742

On Tuesday, June 27, 2017 at 3:30:08 PM UTC-4, lewb...@gmail.com wrote:
> What do you mean by "efficient"? Is it "efficient" if you take six months to write a program that runs 0.000001% faster? What if the changes to make it "efficient" require 80 hours per month to maintain? Is that "efficient"?
> 

Efficient means I have a searchable JTable using Lucene to index, tied to a KeyListener on a JTextComponent.  If I type a key it instantly updates the view with matching rows.  If I try to sort any of the columns I'm just going through DefaultRowSorter which currently adds about a 3 second delay on every keypress (on my machine, other machines would be slower), would like to see that stay as close to instant as possible.

Since our tables are normally smaller and searchable tables don't necessarily have to be sortable, I'm just leaving the default sort logic in for now, as you say it's not worth my time right now.  A 3 second delay per keypress is worth a few hours of developer time if end users do want more rows in at one time and you have a lot of users waiting 3 seconds at a time many times per day.

[toc] | [prev] | [next] | [standalone]

#36743

On Tue, 27 Jun 2017 12:50:15 -0700, Eric Douglas wrote:

> On Tuesday, June 27, 2017 at 3:30:08 PM UTC-4, lewb...@gmail.com wrote:
>> What do you mean by "efficient"? Is it "efficient" if you take six
>> months to write a program that runs 0.000001% faster? What if the
>> changes to make it "efficient" require 80 hours per month to maintain?
>> Is that "efficient"?
>> 
>> 
> Efficient means I have a searchable JTable using Lucene to index, tied
> to a KeyListener on a JTextComponent.  If I type a key it instantly
> updates the view with matching rows.  If I try to sort any of the
> columns I'm just going through DefaultRowSorter which currently adds
> about a 3 second delay on every keypress (on my machine, other machines
> would be slower), would like to see that stay as close to instant as
> possible.
> 
> Since our tables are normally smaller and searchable tables don't
> necessarily have to be sortable, I'm just leaving the default sort logic
> in for now, as you say it's not worth my time right now.  A 3 second
> delay per keypress is worth a few hours of developer time if end users
> do want more rows in at one time and you have a lot of users waiting 3
> seconds at a time many times per day.

Are you using the DefaultTable or have you extended AbstractTableModel 
and if the latter, what are you using as the underlying table storage 
method? 

Whats a 'usual' size in terms of row and column counts?
  

-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#36745

On Tuesday, June 27, 2017 at 4:09:25 PM UTC-4, Martin Gregorie wrote:
> 
> Are you using the DefaultTable or have you extended AbstractTableModel 
> and if the latter, what are you using as the underlying table storage 
> method? 
> 

Yes my table model extends AbstractTableModel.  I have each cell value in a custom object that handles getting and setting values by String or numeric for different cell styles.  The model data is in an ArrayList.  Each element of the ArrayList is an array [] of that cell class.

> Whats a 'usual' size in terms of row and column counts?
>   

Currently within the application a typical table may contain around 10 columns and a few hundred rows.  I populated the table in some test programs with full query results of over 70,000 rows of 24 columns to test the search capability.  It populates very quickly until I try to sort a column.

[toc] | [prev] | [next] | [standalone]

#36746

On Tue, 27 Jun 2017 14:01:20 -0700, Eric Douglas wrote:

> Yes my table model extends AbstractTableModel.  I have each cell value
> in a custom object that handles getting and setting values by String or
> numeric for different cell styles.  The model data is in an ArrayList. 
> Each element of the ArrayList is an array [] of that cell class.
>
Sounds good, though as the row is a fixed size I'm curious why it isn't a 
class instead, since that, given a getter/setter for each data element 
would seem to be functionally very similar.
 
>> Whats a 'usual' size in terms of row and column counts?
>>   
>>   
> Currently within the application a typical table may contain around 10
> columns and a few hundred rows.  I populated the table in some test
> programs with full query results of over 70,000 rows of 24 columns to
> test the search capability.
>
Understood. Thats a significant amount of data regardless of the size of 
the 'average column' so your performance stats should be good.

> It populates very quickly until I try to sort a column.
>
Do you know what sorting algorithm is being used? 

Its worth finding out and considering their strengths and weaknesses, 
which are not always obvious. 

For instance, quicksort is generally considered to be the bee's knees, 
but I discovered a weakness: its has an unstated optimisation (at least 
in my books) because they assume that moving sorted items into sequence 
will always be more expensive than key comparisons. This is not always 
the case.

Years back I implemented all the sort routines in 'Software Tools in 
Pascal' using a very small, somewhat C-like language (PL/9 which was 
effectively an implementation of PL/M in the 6809 MPU). In doing this I 
stored the input records as a heap of strings and added theit address 
pointers to an address array. This made swaps very fast because I never 
moved anything in record heap and reordered records by exchanging their 
pointer positions in the array. When I'd implemented multi-key sorts and 
lexicographic ordering, the key comparisons could become quite expensive 
to execute. In the course of experimenting with this I found that 
quicksort got much slower as the key comparisons got more complex but, 
surprisingly, the more lowly shellsort overtook quicksort as I made the 
key comparisons more and more complex.

This point may not affect you, but do bear it in mind when looking at 
comparisons of sorting algorithms, especially as the analyses often don't 
consider the relative costs of key comparisons vs swapping sorted items.

It might also be worthwhile seeing if different ways of storing the data 
speeds things up. Try using a TreeMap which should be good, if by 
'sorting' you mean changing the key of a row and having it jump to a new 
position determined by key comparison. It may also speed things up if the 
entire table gets resorted because you've changed the sort key from 
column A to column B and rebuilding the TreeMap. I think you'll find that 
rebuilding a TreeMap in this way leaves the arrays (or objects if you go 
that way) in their old positions in the heap while creating a new TreeMap 
instance in which each element contains the key and reference to the 
corresponding array/object, in which case building a new TreeMap and 
scrapping the old one should be a pretty fast operation.  

You might also consider the sort of indirection I mentioned above: that 
should make a big difference too if the current sort method involves 
swapping row positions in the ArrayList.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#36748

On Tuesday, June 27, 2017 at 6:38:53 PM UTC-4, Martin Gregorie wrote:
> On Tue, 27 Jun 2017 14:01:20 -0700, Eric Douglas wrote:
> 
> > Yes my table model extends AbstractTableModel.  I have each cell value
> > in a custom object that handles getting and setting values by String or
> > numeric for different cell styles.  The model data is in an ArrayList. 
> > Each element of the ArrayList is an array [] of that cell class.
> >
> Sounds good, though as the row is a fixed size I'm curious why it isn't a 
> class instead, since that, given a getter/setter for each data element 
> would seem to be functionally very similar.
>  

So the long part is the DefaultRowSorter, trying to build an array of cells from scratch every time you change the sort order of columns or the filter clause.  So maybe I just need another level.  My table cell class is Comparable.  Now if I put them in a table row class that is Comparable then it can ask what order the columns go in and just sort themselves.

Now, the searchable table holds an ArrayList, indices are view row numbers, values are model row numbers.  This is where my question came in.  Even if the rows can sort themselves, isn't it more efficient to make a set of rows that match the filter (view) before I sort them, and how best to grab those row elements from the table model array.

[toc] | [prev] | [next] | [standalone]

#36756

On Wed, 28 Jun 2017 05:10:16 -0700, Eric Douglas wrote:

> On Tuesday, June 27, 2017 at 6:38:53 PM UTC-4, Martin Gregorie wrote:
>> On Tue, 27 Jun 2017 14:01:20 -0700, Eric Douglas wrote:
>> 
>> > Yes my table model extends AbstractTableModel.  I have each cell
>> > value in a custom object that handles getting and setting values by
>> > String or numeric for different cell styles.  The model data is in an
>> > ArrayList. Each element of the ArrayList is an array [] of that cell
>> > class.
>> >
>> Sounds good, though as the row is a fixed size I'm curious why it isn't
>> a class instead, since that, given a getter/setter for each data
>> element would seem to be functionally very similar.
>>  
>>  
> So the long part is the DefaultRowSorter, trying to build an array of
> cells from scratch every time you change the sort order of columns or
> the filter clause.  So maybe I just need another level.  My table cell
> class is Comparable.  Now if I put them in a table row class that is
> Comparable then it can ask what order the columns go in and just sort
> themselves.
> 
> Now, the searchable table holds an ArrayList, indices are view row
> numbers, values are model row numbers.  This is where my question came
> in.  Even if the rows can sort themselves, isn't it more efficient to
> make a set of rows that match the filter (view) before I sort them, and
> how best to grab those row elements from the table model array.
>
What you need is to change the ordering without reconstructing everything 
and especially without moving any items stored in an array or ArrayList. 
I hope the following clarifies one way of doing that.

If your rows are held in an ArayList (and it doesn't matter whether a row 
is an object[] array or a single RowContent object) then, as you say, you 
have to sort it when its loaded and:

- if you change the key in any row, you can either:
  - find the row containing the original key
  - remove it from the row ArrayList leaving a gap
  - work out where to put it back in the arraylist
  - move part of the array list up or down to fill the gap and leave
    a gap where the new key should go
  - put the modified row into the gap
  OR
  - change the key in situ
  - re-sort the row list

  OR (if you store all rows, regardless of order in an immutable
     ArrayList array and use a TreeMap as the sorting mechanism) 
  - rowNo = TreeMap.get(oldKey);
  - TreeMap.remove(oldKey);
  - row = rowList.get(rowNo); row.setKeyVal(newKey);
  - TreeMap.put(newKey, rowNo)
 
  which will almost certainly be the fastest of the three, even if you
  have to map an Iterator onto it for the JTable to use when refreshing
  the display, because no matter what the key value changes are, they
  only affect a very small part of the red-black tree used to implement
  a TreeMap. 

- if you switch ordering to another row in the table, you can either
  - re-sort the entire table if your rows are in an ArrayList whose
    order determines the display sequence
  OR (if you store all rows, regardless of order in an immutable
     ArrayList array and use a TreeMap as the sorting mechanism)
  -treemap = new TreeMap(); 
  - for all rows in the immutable array
    - row = rowList.get(i);
    - TreeMap.add(row.getKey(), i)

  which will probably be faster than sorting an ArrayList since it will
  probably do fewer key comparisons than a comparable sort and will not
  have to re-order any ArrayLists.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#36757

On Wednesday, June 28, 2017 at 3:13:48 PM UTC-4, Martin Gregorie wrote:
> If your rows are held in an ArayList (and it doesn't matter whether a row 
> is an object[] array or a single RowContent object) then, as you say, you 
> have to sort it when its loaded and:
> 
> - if you change the key in any row, you can either:

I'm not quite sure you're describing my problem but I think we may have a solution here.

So I have my simple table class with a table model which extends AbstractTableModel, which currently stores cell data in a ArrayList<MyCustomCellData[]> type structure.  MyCustomCellData class implements Comparable and Serializable, so the cells know how to sort themselves.

Now if I change that to an ArrayList<MyCustomRowData>, the rows will know how to sort themselves.  I just need to make MyCustomRowData Comparable and link it to the SortKeys.

Now the problem is the fancy view.  I have a fancy sortable table which extends my simple table class, which adds search() methods which call lucene to check the cell values.  This currently puts the lucene row results into an ArrayList<Integer> where the keys are the view row indices and the values are the model row indices.  So if I change that to a tree type (TreeMap? TreeSet?) so it can automatically sort itself, and the values link the MyCustomRowData objects, then it's automatically rebuilt to filter and sort as fast as possible.

Now, I have a TreeMap where the indices are MyCustomRowData objects and the values are the model indices?  How do I write the row sorter methods convertRowIndexToView, convertRowIndexToModel when the tree classes have no indexOf method?  I keep the ArrayList<Integer> translator and just update it with a clear() and an addAll(myTreeMap.values()) in the sort() and search() methods?

[toc] | [prev] | [next] | [standalone]

#36759

On Wed, 28 Jun 2017 13:02:38 -0700, Eric Douglas wrote:

> Now the problem is the fancy view.  I have a fancy sortable table which
> extends my simple table class, which adds search() methods which call
> lucene to check the cell values.  This currently puts the lucene row
> results into an ArrayList<Integer> where the keys are the view row
> indices and the values are the model row indices.
>
OK, thats the information I was missing and explains  why using a custom 
class instead of an ArrayList to hold the row is a bad idea.

> So if I change that to a tree type (TreeMap? TreeSet?) so it can
> automatically sort itself
>
Here's a restatement of what I was suggesting. You'd leave the ArrayList 
of ArrayLists alone, exactly as Lucene returned them and never modify or 
recreate them unless/until Lucene replaces its content with new data.

Instead, the TableModel would be based on a Collection that was sorted as 
the TreeMap it is derived from was being built. The Treemap's key fields 
are the contents of whatever column you want to sort on and its values 
are references to the ArrayList containing the corresponding row. Setting 
up the TreeMap would be something like:

for (int i = 0; i < rowList.size(); i++)
{
  ArrayList row = rowList.get(i);
  treemap.put(row.get(keyIndex), row);
}

Collection<ArrayList> sortedList = treeMap.values();

and you'd use the Collection as the basis of your TableModel subclass 
rather than the ArrayList you currently use and which I've referred to as 
rowList.

The effect is that the TreeMap should act as a self-sorting list. I think 
it would be faster than whatever sort is currently being used since 
building a TreeMap only looks at a subset of the keys already in it when 
adding a new item: I'd certainly expect it to be get relatively faster as 
the number of rows in the table increases.

> and the values link the MyCustomRowData objects, then it's automatically
> rebuilt to filter and sort as fast as possible.
>
Yes.
 
> Now, I have a TreeMap where the indices are MyCustomRowData objects and
> the values are the model indices?
>
The treemap keys are the values from the column you're sorting on and the 
values are references to the ArrayLists that form the rows.

> How do I write the row sorter methods convertRowIndexToView,
> convertRowIndexToModel when the tree classes have
> no indexOf method?
>
If those methods really need to use a row index, i.e. can't easily be 
made to work on each row as forEach() returns it, then calling 
Collection.toArray() will return the collection as a sorted ArrayList[]. 
But if it comes down to that the game would appear to be somewhat lost, 
unless it runs significantly faster than your current code.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#36776

On Wednesday, June 28, 2017 at 6:00:02 PM UTC-4, Martin Gregorie wrote:
> OK, thats the information I was missing and explains  why using a custom 
> class instead of an ArrayList to hold the row is a bad idea.
> 
> > So if I change that to a tree type (TreeMap? TreeSet?) so it can
> > automatically sort itself
> >
> Here's a restatement of what I was suggesting. You'd leave the ArrayList 
> of ArrayLists alone, exactly as Lucene returned them and never modify or 
> recreate them unless/until Lucene replaces its content with new data.
> 
> Instead, the TableModel would be based on a Collection that was sorted as 
> the TreeMap it is derived from was being built. The Treemap's key fields 
> are the contents of whatever column you want to sort on and its values 
> are references to the ArrayList containing the corresponding row. Setting 
> up the TreeMap would be something like:
> 
> for (int i = 0; i < rowList.size(); i++)
> {
>   ArrayList row = rowList.get(i);
>   treemap.put(row.get(keyIndex), row);
> }
> 
> Collection<ArrayList> sortedList = treeMap.values();
> 
> and you'd use the Collection as the basis of your TableModel subclass 
> rather than the ArrayList you currently use and which I've referred to as 
> rowList.
> 
> The effect is that the TreeMap should act as a self-sorting list. I think 
> it would be faster than whatever sort is currently being used since 
> building a TreeMap only looks at a subset of the keys already in it when 
> adding a new item: I'd certainly expect it to be get relatively faster as 
> the number of rows in the table increases.
> 
> > and the values link the MyCustomRowData objects, then it's automatically
> > rebuilt to filter and sort as fast as possible.
> >
> Yes.
>  
> > Now, I have a TreeMap where the indices are MyCustomRowData objects and
> > the values are the model indices?
> >
> The treemap keys are the values from the column you're sorting on and the 
> values are references to the ArrayLists that form the rows.
> 
> > How do I write the row sorter methods convertRowIndexToView,
> > convertRowIndexToModel when the tree classes have
> > no indexOf method?
> >
> If those methods really need to use a row index, i.e. can't easily be 
> made to work on each row as forEach() returns it, then calling 
> Collection.toArray() will return the collection as a sorted ArrayList[]. 
> But if it comes down to that the game would appear to be somewhat lost, 
> unless it runs significantly faster than your current code.
> 

Nice, I'm not sure I did exactly everything you were suggesting but it seems I get barely a 1 second delay now on clicking a column header to sort the table.  That is on a full table, tested 74,707 rows, 24 columns, totaling 1,792,968 cells.

That is with the full sort processing, I can click one column to be ascending or descending, then a second column with duplicate values which remain sorted on the first column as secondary.

That is with full search capability.  I have 2 JTextComponent controls with key listeners that update the table search, each linked to list buttons where I can select to search on any specific column or all columns.  All cells indexed, with wildcards.

That includes mixed cell styles.  Some cells are just text, some are masked numbers, some are masked dates, some are list buttons.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.java.programmer

csiph-web