Sort Double Double HashMap Java/Processing

Grad_student

I have this Hashmap of floats and I want to get the top 5 largest values from it:

import java.util.Map;


HashMap<Float,Float> hm = new HashMap<Float,Float>();

// Putting key-value pairs in the HashMap
for (int i = 0; i < 100; i++) {

  float pos = random(-50, 50);
  float time = random(0, 50);
  hm.put(time, pos);

}
// Using an enhanced loop to interate over each entry
for (Map.Entry me : hm.entrySet()) {
  print("key is " + me.getKey());
  println(" value is " + me.getValue());
}

I assume I would need to sort it first. Question is, how to sort it and will the keys still remain the same after the sort? When I say "same" I mean will the sorted values still have the original key identifier? This is crucial for what I am trying to accomplish.

I posted this question is stackoverflow and someone suggested:

___If it is possible, replace HashMap by an implementation of NavigableMap, such as TreeMap. The iteration order of a HashMap is undefined.

With a NavigableMap you can sort it from higher to lower values by means of;

---

    for (Map.Entry me : tm.descendingMap().entrySet() ()) {
      System.out.print("key is " + me.getKey());
      System.out.println(" value is " + me.getValue());
    }

It is worth noting that descendingMap() does not actually sort the contents of the map (because the TreeMap is already sorted), but just return a reverse view of the original map

Not sure if this is possible or if it makes since I am not a java expert (I barely know processing!). I have even less experience with these map data structures.

Please SOS.

GoToLoop

I've got a similar example saved here. Later gonna try to adapt it to work w/ Map<Float, Float>: :-\"

/** 
 * Remove Duplicate + Original PVector IV (v4.11)
 * by  PhiLho (2013/Dec)
 * mod GoToLoop
 * 
 * forum.processing.org/two/discussion/1752/
 * removing-equal-number-from-arraylist
 */

import java.util.Map.Entry;

final ArrayList<PVector> vecs = new ArrayList();

vecs.add( new PVector(7, 6.8) );
vecs.add( new PVector(10, -5) );
vecs.add( new PVector(45, -5) );
vecs.add( new PVector(1., -1) );
vecs.add( new PVector(10, -5) );
vecs.add( new PVector(10, -5) );
vecs.add( new PVector(45, -5) );
vecs.add( new PVector(3.2, 9) );
vecs.add( new PVector(-8, 39) );

// All PVector objects within ArrayList:
for (PVector p: vecs)   println(p);
println();

final HashMap<PVector, Boolean> freq = new HashMap();

// Identify and remove duplicates:
int i = vecs.size();
while (i-- != 0) {
  final PVector p = vecs.get(i);
  freq.put(p, freq.containsKey(p)? vecs.remove(i) == p : false);
}

// All unique PVector objects:
for (PVector p: vecs)   println(p);
println();

// Remove by object original leftovers which ever had duplicates:
for (Entry<PVector, Boolean> e: freq.entrySet())
  if (e.getValue())   vecs.remove(e.getKey());

// Only PVector objects which never had dups now:
for (PVector p: vecs)   println(p);

exit();

Grad_student

@GoToLoop

Ohhh....looks...uhhhh...fun...yeah....good luck with that......lol

GoToLoop

As said, found a solution! Although a not-so-perfect lazy 1 w/ String keys and float values: :ar!
http://processing.org/reference/FloatDict.html

Well, you can convert a String to its float value later w/:
http://processing.org/reference/floatconvert_.html

So here it is: :P
UPDATED: List 5 highest values in order!

// forum.processing.org/two/discussion/2241/
// sort-double-double-hashmap-javaprocessing

import java.util.Iterator;

final int NUM = 10, RANGE = 50, SAMPLE = 5;
final FloatDict values = new FloatDict(NUM);

for (int i = 0; i != NUM; ++i)
  values.set(str(random(-RANGE, RANGE)), random(RANGE));

println(values);

values.sortValues();
println();
println(values);

values.sortValuesReverse();
println();
println(values);

final Iterator<String> entries = values.keys().iterator();
println();

for (int i = 0; i != SAMPLE; ++i)
  print(values.get(entries.next()) + "\t");

exit();

Grad_student

this could work...

Grad_student

I'd just have to transform my key to a float before inserting it and then after I pull it out I guess

GoToLoop

AFAIK, to insert a key, gotta covert it to String w/ str(). And to access it, you might need to convert it to float() again!

Grad_student

@GoToLoop

How do you get the key and value at the same time here:

final Iterator<String> entries = values.keys().iterator();
println();

for (int i = 0; i != SAMPLE; ++i)
  print(values.get(entries.next()) + "\t");

I need the key associated with the top 5 largest values as well. I actually have no idea of how this Iterator thing works....

Grad_student

Also, why do you use "final?" It basically makes a variable constant. Any particular reason you do this here?

Grad_student

What is the purpose of the NUM here:

final FloatDict values = new FloatDict(NUM);

GoToLoop

Newer version w/ the 5 highest values stored in an array too: (~~)

/** 
 * Sorted Floats (v2.12)
 * by GoToLoop (2014/Jan)
 *
 * forum.processing.org/two/discussion/2241
 * /sort-double-double-hashmap-javaprocessing
 */

final int NUM = 10, RANGE = 50, SAMPLE = 5;
final FloatDict numbers = new FloatDict(NUM);
final float[] highers = new float[SAMPLE];

int i = 0;
while (i++ != NUM)
  numbers.set(str(random(-RANGE, RANGE)), random(RANGE));

println(numbers);

numbers.sortValuesReverse();
println();
println(numbers);
println();

i = 0;
for (String k: numbers.keys()) {
  final float entry = float(k), value = numbers.get(k);
  println("Key: " + entry + "\tValue: " + (highers[i] = value));
  if (++i == SAMPLE)  break;
}

println();
println(highers);

exit();

GoToLoop

How do you get the key and value at the same time here:

Modified 1st version to make it more explicit:

/** 
 * Sorted Floats (v1.5)
 * by GoToLoop (2014/Jan)
 *
 * forum.processing.org/two/discussion/2241
 * /sort-double-double-hashmap-javaprocessing
 */

import java.util.Iterator;

final int NUM = 10, RANGE = 50, SAMPLE = 5;
final FloatDict values = new FloatDict(NUM);

for (int i = 0; i != NUM; ++i)
  values.set(str(random(-RANGE, RANGE)), random(RANGE));

println(values);

values.sortValuesReverse();
println();
println(values);

final Iterator<String> entries = values.keys().iterator();
println();

for (int i = 0; i != SAMPLE; ++i) {
  final String entry = entries.next();
  final float  value = values.get(entry);
  println("Key: " + entry + "\tValue: " + value);
}

exit();

I actually have no idea of how this Iterator thing works...

My 2nd version doesn't explicitly use it anymore! The "enhanced/foreach" for loop does it instead!
Nevertheless, lookie below to learn about it :
docs.oracle.com/javase/7/docs/api/java/util/Iterator.html

GoToLoop

Also, why do you use "final?" It basically makes a variable constant. Any particular reason you do this here?

Mostly I use it as an annotation for any1 looking at the code to rest assured that variable won't be re-assigned! =:)

And for primitive & String field variables, as an additional performance boost too! $-)

GoToLoop

What is the purpose of the NUM here: final FloatDict values = new FloatDict(NUM);

Just an initial capacity value. Since we already know there won't be more than NUM entries in that data structure anyways! ;;)

Grad_student

So NUM limits the size? What would happen if you didn't know how big the dictionary may be? My application will be loading data 200 per second into the values!

Grad_student

Im collecting these values in real time

Grad_student

Check out this post to see exactly what I am trying to do with this data structure: http://forum.processing.org/two/discussion/2036/find-5-largest-values-in-a-linked-list-in-processingjava#Item_3

GoToLoop

So NUM limits the size? What would happen if you didn't know how big the dictionary may be? My application will be loading data 200 per second into the values!

In your original sample you used this following loop -> for (int i = 0; i < 100; i++) {
I've just replaced value 100 w/ a constant NUM. And made it 10 in order for it to be displayed.

Of course you gotta adapt my & your samples to your exactly particular needs! :(|)

Remember that such data structures can have as many entries as you like/need!
Merely keep issuing either set() or put() to add more of them! :-@

Grad_student

oh ok. Yeah I forgot that my original example had 100. While in reality it will have much, much, much more. You dont think I will run into performance issues?

GoToLoop

Well, every time a sortValuesReverse() method is issued, the bigger the # of entries, the longer will take to sort them all out! [..]

PhiLho

The TreeMap suggestion was good, one advantage it has is that it won't do a sort on each new key, it just insert the key in the right order when adding it.

Here is an example of implementation, using frameCount as time value. I could have used millis() or something else.

import java.util.*;
import java.util.Map.Entry; // Workaround of a Processing pre-processor bug

NavigableMap<Float, Integer> values = new TreeMap<Float, Integer>();
final int TO_DISPLAY = 5;

void setup()
{
  size(500, 800);
  fill(0);
  textSize(24);
}

void draw()
{
  background(255);
  if (frameCount % 17 == 0) // Simulates data coming at a slower rate
  {
    values.put(random(-50, 50), frameCount);
  }

  int c = 0;
  for (Entry<Float, Integer> me : values.descendingMap().entrySet())
  {
    if (c > TO_DISPLAY)
      break;

    text(
        nf(me.getValue().intValue(), 2, 0) + "   " + 
        nf(me.getKey().floatValue(), 2, 3),
       10, 30 + c * 30); 
    c++;
  }
}