Determine index from array reference?

[Lew]

So you vote for looping through the array until a match is found?

But ArrayList.indexOf() *does* loop through the array until a match is found!

The only difference is that it does it for you, saving you the trouble of
hand-coding the loop.

- Lew

 

[Knute Johnson]

It's faster because lookups into a HashMap are O(1) and lookups into an
ArrayList are O(n) on the size of the collection. Plus you skip the code
to derive an index then use it to do the lookup in the parallel list.


It can use less memory when there are two or more lists coordinated in
parallel, which was the condition under which I suggested using a Map
would be worthwhile.


Given that you were looking up an index with a JTextField as the key,
then using the index to find a SomeOtherThing, you already have the key
- the JTextField - so there is no lookup of the key, only of the
SomeOtherThing associated with the key.

The suggestion of a Map is predicated on the notion that you are doing
that kind of parallel lookup.


By preventing any bugs caused by independent Lists falling out of
synchrony with each other. With two Lists, the orders or lengths might
differ. (This type of thing has been a question on these newsgroups
before.) With a Map, if the key is in there, so is the value (which
might be null). No chance of the order or length differing, hence less
opportunity for bugs.

- Lew

Then we are talking about two different things. I only have one list.

 

[Knute Johnson]

Winner! Keeping parallel lists or arrays, and searching one to find the index
in another is error-prone, hard-to-understand, and makes you look like a
non-OO neanderthal programmer. The first two are actually good reasons to
consider alternatives, and the third is a gratuitous epithet which may provide
a bit of motivation to change, or to explain things well enough to know why
it doesn't apply in this case.

I don't think that saves me anything over the original scheme and just
makes it more complicated.

how is
OtherType thing = fieldMap.get(thisField)
more complicated than
OtherType thing = secondArray[Arrays.asList(firstArray).indexOf(thisField)]

It's just more sane to use actual data structures that do what you need than
to sling around pairs of arrays that your code happens to know are in sync.

It's also faster, if these lists get to be of any significant size.
ArrayList.indexOf() is a linear search of the list. HashMap.get() is
constant-time.

You guys are obviously not listening to this neanderthal programmer. I
only have one list. I can't use a Map because you can't get to the key
with the value. I could use a Map to a Map but that would have the
dreaded two lists.

 

[Knute Johnson]

But ArrayList.indexOf() *does* loop through the array until a match is
found!

The only difference is that it does it for you, saving you the trouble
of hand-coding the loop.

- Lew

I understand how it works. I was just confirming that Chris likes the
other method better and in the special case of a large array. So we
have three methods and one vote for each. I'd say it is hardly a consensus.

Thanks everybody for your insights.

 

[Patricia Shanahan]

Lew wrote:
If you plan to use the result of your "indexOf()" to locate another
object, rather than just println() it, you might consider using a
Map <JTextField, OtherType>. That would have the benefit of constant
time lookup (if you use HashMap) instead of O(n). You also avoid
bugs caused by "parallel" Lists going non-Euclidean.

Winner! Keeping parallel lists or arrays, and searching one to find
the index
in another is error-prone, hard-to-understand, and makes you look like a
non-OO neanderthal programmer. The first two are actually good
reasons to
consider alternatives, and the third is a gratuitous epithet which may
provide
a bit of motivation to change, or to explain things well enough to
know why
it doesn't apply in this case.

I don't think that saves me anything over the original scheme and
just makes it more complicated.

how is
OtherType thing = fieldMap.get(thisField)
more complicated than
OtherType thing =
secondArray[Arrays.asList(firstArray).indexOf(thisField)]

It's just more sane to use actual data structures that do what you
need than
to sling around pairs of arrays that your code happens to know are in
sync.

It's also faster, if these lists get to be of any significant size.
ArrayList.indexOf() is a linear search of the list. HashMap.get() is
constant-time.

You guys are obviously not listening to this neanderthal programmer. I
only have one list. I can't use a Map because you can't get to the key
with the value. I could use a Map to a Map but that would have the
dreaded two lists.

I'm still very unclear about what the actual accesses are. Why do you
want the index? Presumably, there is some bigger operation involved that
uses the index.

Generally, if you find yourself thinking in terms of "you can't get to
the key with the value" it means you have the map the wrong way round.
However, without knowing what the index is for, it is impossible to say.

Patricia

 

[Knute Johnson]

I'm still very unclear about what the actual accesses are. Why do you
want the index? Presumably, there is some bigger operation involved that
uses the index.

Generally, if you find yourself thinking in terms of "you can't get to
the key with the value" it means you have the map the wrong way round.
However, without knowing what the index is for, it is impossible to say.

Patricia

Patricia:

I'm sorry you must have missed my reply to your earlier message. I've
got an array of JTextFields. These JTextFields have ActionListeners
attached. In the actionPerformed() I need to get the index of the
JTextField that fired the action to set some values in another array.
In other parts of my code I also need to access the JTextField[] by
index. So the dreaded Vector/ArrayList suggestions were good ones
because they did solve the problem. Then somehow we got onto the
multiple list/Map tangent which I don't really have and doesn't work
because of the 'you can't get the key from the value' problem. Chris
suggested just looping through the array. I asked but haven't gotten an
answer if he thought that was still a good solution for very large
arrays. In my case however the array only has 16 elements.

There is one note if agreement in all of this, everybody dislikes my
solution.

 

[Patricia Shanahan]

Patricia:

I'm sorry you must have missed my reply to your earlier message. I've
got an array of JTextFields. These JTextFields have ActionListeners
attached. In the actionPerformed() I need to get the index of the
JTextField that fired the action to set some values in another array.

Now I'm really confused: "You guys are obviously not listening to this
neanderthal programmer. I only have one list"

1. The array of JTextField references.

2. The "another array" in which you are going to set some values.

I decided I had misunderstood what was going on, and had no idea what
the index was used for, after reading the comment about "only one list".

Why not have a map, indexed by JTextField, with the object you need to
update on actionPerformed as value?

Patricia

 

[Knute Johnson]

Now I'm really confused: "You guys are obviously not listening to this
neanderthal programmer. I only have one list"

1. The array of JTextField references.

2. The "another array" in which you are going to set some values.

I decided I had misunderstood what was going on, and had no idea what
the index was used for, after reading the comment about "only one list".

Why not have a map, indexed by JTextField, with the object you need to
update on actionPerformed as value?

Patricia

Patricia:

Sorry for the confusion. I have an array of objects. I have an array
of JTextFields to collect data to update elements of the first object
array. Both arrays need to be accessed by their index in other code.

In the ActionListener I can easily get a reference to the JTextField.
What I was looking for was simpler way of finding the index into the
JTextField array.

After your question I think I see what Lew meant by two lists. What I
thought he meant was my indexes.

In any case, my method is orders of magnitude faster than an ArrayList.

The tests below require 400mb of heap. Just make the array smaller if
you don't have that much.

import java.awt.*;
import java.awt.event.*;
import java.util.*;
import javax.swing.*;

public class test4 {
public static void main(String[] args) {
final int LEN = 100000;

ArrayList<JTextField> array = new ArrayList<JTextField>(LEN);
JTextField[] tf = new JTextField[LEN];
long start = 0;

for (int i=0; i<LEN; i++) {
tf = new JTextField("",4);
array.add(tf);
}

System.out.println("Start");
start = System.currentTimeMillis();

for (int i=0; i<LEN; i++) {
int index = array.indexOf(tf);
}

System.out.println(System.currentTimeMillis() - start);
}
}

import java.awt.*;
import java.awt.event.*;
import java.util.*;
import javax.swing.*;

public class test5 {
public static void main(String[] args) {
final int LEN = 100000;
long start = 0;

class ITextField extends JTextField {
int n;

public ITextField(String text, int columns, int index) {
super(text,columns);

n = index;
}

public int getIndex() {
return n;
}
}
ITextField[] tf = new ITextField[LEN];

for (int i=0; i<LEN; i++) {
tf = new ITextField("",4,i);
}

System.out.println("Start");
start = System.currentTimeMillis();

for (int i=0; i<LEN; i++) {
int index = tf.getIndex();
}

System.out.println(System.currentTimeMillis() - start);
}
}

 

[Mark Rafn]

I've got an array of JTextFields. These JTextFields have ActionListeners
attached. In the actionPerformed() I need to get the index of the
JTextField that fired the action to set some values in another array.

We're saying not to do that. Instead of having an array of JTextFields and an
array of values in another array, have a map of JTextField to otherValue.
This replaces BOTH arrays. If you need to preserve order (and you probably
do), a LinkedHashMap is perfect.

In other parts of my code I also need to access the JTextField[] by
index.

It all depends, of course, on what your overall app is, but it seems quite
believeable that these indexed uses of the JTextField[] could be replaced by
faster clearer use of a different data structure.

So the dreaded Vector/ArrayList suggestions were good ones
because they did solve the problem. Then somehow we got onto the
multiple list/Map tangent which I don't really have and doesn't work
because of the 'you can't get the key from the value' problem.

Yet another requirement. Which likely leads to writing a real data object
that contains both directions of mapping if you need. Then you can be free to
change the implementation to one that fits best.

Instead of two arrays, or an array and an ArrayList, have a TextFieldInfo
class, with an addField(JTextField, OtherThing), a getFoo(JTextField), and a
getTextField(OtherThing), and any other mechanisms you need. Inside that,
keep two hashes, one for each direction. Or some other mechanism if that
makes more sense.

Chris suggested just looping through the array. I asked but haven't gotten
an answer if he thought that was still a good solution for very large
arrays. In my case however the array only has 16 elements.

Looping through the array is exactly the same work done by the indexOf()
method of most List implementations.

 

[Knute Johnson]

I've got an array of JTextFields. These JTextFields have ActionListeners
attached. In the actionPerformed() I need to get the index of the
JTextField that fired the action to set some values in another array.

We're saying not to do that. Instead of having an array of JTextFields and an
array of values in another array, have a map of JTextField to otherValue.
This replaces BOTH arrays. If you need to preserve order (and you probably
do), a LinkedHashMap is perfect.

In other parts of my code I also need to access the JTextField[] by
index.

It all depends, of course, on what your overall app is, but it seems quite
believeable that these indexed uses of the JTextField[] could be replaced by
faster clearer use of a different data structure.

So the dreaded Vector/ArrayList suggestions were good ones
because they did solve the problem. Then somehow we got onto the
multiple list/Map tangent which I don't really have and doesn't work
because of the 'you can't get the key from the value' problem.

Yet another requirement. Which likely leads to writing a real data object
that contains both directions of mapping if you need. Then you can be free to
change the implementation to one that fits best.

Instead of two arrays, or an array and an ArrayList, have a TextFieldInfo
class, with an addField(JTextField, OtherThing), a getFoo(JTextField), and a
getTextField(OtherThing), and any other mechanisms you need. Inside that,
keep two hashes, one for each direction. Or some other mechanism if that
makes more sense.

Chris suggested just looping through the array. I asked but haven't gotten
an answer if he thought that was still a good solution for very large
arrays. In my case however the array only has 16 elements.

Looping through the array is exactly the same work done by the indexOf()
method of most List implementations.

Mark:

I appreciate the suggestions but I don't think that is simpler than what
I already have. I'm going to stick with the neanderthal approach.

 

[Mark Rafn]

I appreciate the suggestions but I don't think that is simpler than what
I already have.

Righto - it's your code and you're the final judge.

I'm going to stick with the neanderthal approach.

I have to admit, that "fire" invention has been handy. I hope this works out
as as well as that did!

 

[Chris Uppal]

So you vote for looping through the array until a match is found?

In this case, yes, that's what I would probably do.

I can't see a need for a higher-performance solution here. If there was a need
then I might use some sort of Map to find the indexes faster. Alternatively I
might try re-design so as to remove the need to link things via an indirect
index in the first place.

-- chris