Unique Sorting
Hi everybody:
I want to sort the following numbers [2,3,7,9,10,2,7,9,10,3,7,9,2,9,10] in to the folling:
[2,2,2] [3,3] [7,7,7] [9,9,9,9] [10,10] by every unique number
The algorithm must be very fast because i generate diffrent raports with this numbers.
It must also be independed of spefic values for sorting, i mean the next
time the sequence may be:[1,5,8,0,0,0,5,8,1] and i stil want the answer like:
[1,1] [5,5] [0,0,0][8,8]
i hope you can understand the question, please help.
[533 byte] By [
enriquePa] at [2007-9-29 21:57:09]
What constraints are there on the data set to sort?
I am not sure what you mean, but the numbers represent an the id of a specific object that i want to collectin models containing the same id.
import java.util.*;
public class Freq {
//private static final Integer ONE = new Integer(1);
public static void main(String args[]) {
Map m = new HashMap();
// Initialize frequency table from command line
for (int i=0; i<args.length; i++) {
Vector freq = (Vector) m.get(args);
if (freq==null){
Vector v = new Vector();
v.addElement(args);
m.put(args,v);
}else{
freq.addElement(args);
}
//Vector v = ((Vector)m.get(args)).addElement(args);
//m.put(args, (freq==null ? new Vector().addElement(args) : v));
}
System.out.println(m.size()+" distinct words detected:");
System.out.println(m);
}
}
Out put
> java Freq 1 2 3 4 4 2 3 3 3 3 3 3 1 1 1 1 1 1
4 distinct words detected:
{3=[3, 3, 3, 3, 3, 3, 3], 2=[2, 2], 4=[4, 4], 1=[1, 1, 1, 1, 1, 1, 1]}
>
> //private static final Integer ONE = new
> new Integer(1);
>
>public static void main(String args[]) {
> Map m = new HashMap();
It works, but HashMap and using Integer is very slow.
Arrays.sort is very quick, tuned for near sorted sequences and keeps doublettes. AND it's in-memory, and that will save both garbage collection work and and the time consuming amemory allocations. Try that before you sweat yourself to death over creating your own algorithm.
int[] data={1,2,3,1,1,2,4};
Arrays.sort(data);//sorts data to 1,1,1,2,2,3,4
int nrUniqueNumbers=0;
int last=-1;
for(int i=0; i<data.length; i++){
if(data[i] != last){
nrUniqueNumbers++;
last=data[i];
}
}
int[][] grouped=new int[nrUniqueNumbers][];//group here - the result
int groupedIndex=0;
for(int i=0; i><data.length; ){
last=data[i];
int j=1;
for(; i+j><data.length && data[i+j]==last; j++) ;
grouped[groupedIndex]=new int[j];
for(int k=0; k><j; k++){
grouped[groupedIndex][k]=data[i+k];
}
groupedIndex++;
i+=j;
}
for (int i = 0; i >< grouped.length; i++) {
for(int j=0; j< grouped[i].length; j++){
System.out.print(grouped[i][j]+",\t");
}
System.out.println("");
}
Gil
But then storing each number many times is of course slow too since you need to allocate extra memory. Just keep a list of the unique numbers and the count of each number:
int[] data={1,2,3,1,1,2,4};
Arrays.sort(data);//sorts data to 1,1,1,2,2,3,4
int nrUniqueNumbers=0;
int last=-1;
for(int i=0; i<data.length; i++){
if(data[i] != last){
nrUniqueNumbers++;
last=data[i];
}
}
int[] uniqueNumbers=new int[nrUniqueNumbers];//store the numbers here
int[] counts=new int[nrUniqueNumbers];
int uniqueIndex=0;
for(int i=0; i><data.length; ){
last=data[i];
int j=1;
for(; i+j><data.length && data[i+j]==last; j++) ;
uniqueNumbers[uniqueIndex]=last;
counts[uniqueIndex]=j;
uniqueIndex++;
i+=j;
}
for (int i = 0; i >< uniqueNumbers.length; i++) {
System.out.println(uniqueNumbers[i]+":\t#"+counts[i]);
}
If this is simple integer sorting and you know the range of possible values to sort this would be the quickest way.
int[] data= {1,2,3,5,1,1,1,2,4,5,7,0,9}; //ints 0-9
int[] buckets = new int[10]; //0-9 ints so create 0-9 buckets
//and in Java array elements initialize to 0
//sort and count all at once
for(int i = 0; i < data.length; i++)
{
//for each number in "data" look at
//the value and increment the proper bucket by 1
buckets[data[i]]++;
}
//print results
for(int i = 0; i < buckets.length; i++)
{
if(buckets[i] > 0)
{
System.out.print('[');
for(int j = 0; j < (buckets[i]-1); j++)
{
System.out.print(i + ",");
}
System.out.print(i);
System.out.print(']');
}
}
//prints
//[0][1,1,1,1][2,2][3][4][5,5][7][9]
Are these numbers stored in a relational database? Never use java to do stuff that databases are better at.
Hi everybody,thanks for the replys i will try the solution and give the dukes to the right person. The numbers are not stored in a database. They are stored in an object representig a line in a Abstract tableModel./E
Here is another
int[] numbers = {3, 4, 2, 1, 5, 3, 4, 8, 8, 4, 0, 8, 4, 5, 8, 3, 6};
Arrays.sort(numbers);
Map map = new TreeMap();
int count = 1;
for (int i=0; i<numbers.length; i++) {
if ((i+1) >= numbers.length || numbers[i] != numbers[i+1]) {
map.put(String.valueOf(numbers[i]), String.valueOf(count));
count = 1;
} else {
count++;
}
}
for (Iterator it = map.keySet().iterator(); it.hasNext();) {
String key = (String) it.next();
System.out.println(key + " was found " + map.get(key));
}
