Performance: Ziehen ohne Zurücklegen (große Datenmenge)

[pocketom]

Hi.

Ich habe mal wieder ein Performance Problem. Und zwar möchte ich ein Array in zwei Teile splitten. Das soll zufällig geschehen. Es ist also "Ziehen ohne Zurücklegen" angesagt. Das funktioniert bis zu einer Arraygröße von 100.000 ganz gut, darüber wird es dann aber immer haariger. Aktuell muss ich ca. 5 Mio. Zellen in zwei Teile splitten.



Die Größe des ersten Teils wird angegeben (0-100%), der zweite Teil ist komplementär.

/**
	 * splits an array into two parts by drawing random values
	 * 
	 * @param data the input 2D array of doubles
	 * @param part1percentage the percentage to put into the first 2D array,
	 * the rest is put into the second array
	 * 
	 * @return a list containing the two splitted parts (List(0) = training, List(1) = validation)
	 */
	public static List<double[][]> splitArrayRandomly(double[][] data, double part1percentage)
	{		
		if(part1percentage > 1)
			part1percentage = 1.0;
		else if(part1percentage < 0)
			part1percentage = 0.0;
				
		int tcount = (int)(data.length * part1percentage);
		int vcount = data.length -tcount;
		
		double[][] tpatterns = new double[tcount][data[0].length];
		double[][] vpatterns = new double[vcount][data[0].length];
			
    	ArrayList<Integer> availablepatterns = new ArrayList<Integer>();   	
    	for(int i=0; i<data.length; i++)
    		availablepatterns.add(i);    	
	
    	
    	Random randomizer = new Random(System.nanoTime());   	
    	int available,r,rpattern = 0;  	
    	
    	// fetch the first part
    	int count = 1;
    	for(int i=0; i<tpatterns.length; i++)
    	{	
    		if(count%100==0)
    			System.out.print(count+"\t");
    		
    		if(count%1000==0)
    			System.out.println();
    		
    		available = availablepatterns.size();
    		r = randomizer.nextInt(available);   		
    		rpattern = availablepatterns.get(r);  		   		
    		availablepatterns.remove(r);
    		
    		for (int j = 0; j < data[0].length; j++)		
    			tpatterns[i][j] = data[rpattern][j];
    		
    		count++;
    	}   
    	
    	// fetch the second part
    	count = 1;
    	for(int i=0; i<vpatterns.length; i++)
    	{	
    		if(count%100==0)
    			System.out.print(count+"\t");
    		
    		if(count%1000==0)
    			System.out.println();
    		
    		available = availablepatterns.size();
    		r = randomizer.nextInt(available);
    		rpattern = availablepatterns.get(r);
    		availablepatterns.remove(r);
    		
    		for (int j = 0; j < data[0].length; j++)		
    			vpatterns[i][j] = data[rpattern][j];
    		
    		count++;
    	} 
    	
    	ArrayList<double[][]> result = new ArrayList<double[][]>();
    	
    	result.add(tpatterns);
    	result.add(vpatterns);   	
    	
    	return result;
	}

Habe es mit hashen auch probiert, das geht am Anfang dann schnell und zum Ende hin immer langsamer, also genau umgekehrt weil zum Ende hin immer öfter "ins Leere" gegriffen wird. Mir fällt einfach nichts mehr ein. Habt ihr eine pfiffige Idee? Oder geht es einfach nicht schneller???

Viele Grüße, Tom

 

[Gast]

Wenn das "ins Leere greifen" das Problem ist dann würde ich an deiner Stelle keine Arrays mehr verwenden sondern auf ArrayLists. Wird zwar kompliziert da du schon eine hast aber ist meiner Meinung nach doch die einfachste Lösung.
Obwohl ArrayList<ArrayList<ArrayList>>> schon sehr übel aussieht. Da muss man dann echt aufpassen

 

[Gast]

Mein natürlich ArrayList<ArrayList<ArrayList<Double>>>

 

[Guest]

Hi,

hier eine etwas optimierte Beispielimplementierung mit ArrayLists. Die Haupteigenschaften sind:

- Nutzt einen effizienteren Zufallszahlengenerator (https://uncommons-maths.dev.java.net/)
- Die prozentuale Verteilung auf die beiden Arrays ist nur statistisch korrekt und nicht exakt, wie in der ursprünglichen Implementierung
- Reduziert den Algorithmus auf einen Schleifendurchlauf und benutzt durchgängig ArrayLists um unperformantes Array kopieren zu vemeiden
- Es ist wirklich nur eine Beispielimplementierung!! Bitte nicht direkt so einsetzen, sondern nur als Vorlage für eine eigene Implementierung nehmen

Hoffe es hilft
-Tim

    public static List<ArrayList<double[]>> splitArrayRandomly2(ArrayList<double[]> data, double part1percentage)
    {
        List<ArrayList<double[]>> result = new ArrayList<ArrayList<double[]>>( 2 );

        // map percentage to 0.0 - 1.0 range
        if( part1percentage > 1 )
        {
            part1percentage = 1.0;
        }
        else if (part1percentage < 0)
        {
            part1percentage = 0.0;
        }

        // special case 1.0
        if( part1percentage == 1.0 )
        {
            result.add( data );
            result.add( new ArrayList<double[]>() );
            return result;
        }

        // special case 0.0
        if( part1percentage == 0.0 )
        {
            result.add( new ArrayList<double[]>() );
            result.add( data );
            return result;
        }

        // else, do the real work
        BinomialGenerator generator = null;

        try
        {
            // genarates random numbers between 0 and 1 with a statistical percentage of part1percentage 1'ns
            generator = new BinomialGenerator(1, part1percentage, new CellularAutomatonRNG( DefaultSeedGenerator.getInstance() ) );
        }
        catch ( SeedException e )
        {
            e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
        }

        // create the two array we sort to, with a safety-buffer of one percent
        int tcount = (int)(data.size() * part1percentage) + (int)(data.size() * 0.01);
        int vcount = (int)(data.size() * (1.0 - part1percentage) ) + (int)(data.size() * 0.01);

        ArrayList<double[]> tpatterns = new ArrayList<double[]>(tcount);
        ArrayList<double[]> vpatterns = new ArrayList<double[]>(vcount);

        for ( double[] curElement : data )
        {
            if ( generator.nextValue() == 1 )
            {
                tpatterns.add( curElement );
            }
            else
            {
                vpatterns.add( curElement );
            }
        }

        result.add( tpatterns );
        result.add( vpatterns );
        return result;
    }

 

[Guest]

Hi,

hier eine etwas aufgeräumtere Version, die jetzt wirklich nur noch ArrayLists benutzt:

    public static List<ArrayList<ArrayList<Double>>> splitArrayRandomly2(ArrayList<ArrayList<Double>> data, double part1percentage)
    {
        List<ArrayList<ArrayList<Double>>> result = new ArrayList<ArrayList<ArrayList<Double>>>( 2 );

        // special case 1.0
        if( part1percentage >= 1.0 )
        {
            result.add( data ); result.add( new ArrayList<ArrayList<Double>>() );
        }
        // special case 0.0
        else if (part1percentage <= 0.0 )
        {
            result.add( new ArrayList<ArrayList<Double>>() ); result.add( data );
        }
        // else, do the real work
        else
        {
            BinomialGenerator generator = null;

            try
            {
                // genarates random numbers between 0 and 1 with a statistical percentage of part1percentage 1'ns
                generator = new BinomialGenerator(1, part1percentage, new CellularAutomatonRNG( DefaultSeedGenerator.getInstance() ) );
            }
            catch ( SeedException e )
            {
                e.printStackTrace();  //Todo: Do something usefull here
            }

            // create the two arrays we sort to, with a safety-buffer of one percent
            int tcount = (int)(data.size() * part1percentage) + (int)(data.size() * 0.01);
            int vcount = (int)(data.size() * (1.0 - part1percentage) ) + (int)(data.size() * 0.01);

            ArrayList<ArrayList<Double>> tpatterns = new ArrayList<ArrayList<Double>>(tcount);
            ArrayList<ArrayList<Double>> vpatterns = new ArrayList<ArrayList<Double>>(vcount);

            for ( ArrayList<Double> curElement : data )
            {
                if ( generator.nextValue() == 1 )
                    tpatterns.add( curElement );
                else
                    vpatterns.add( curElement );
            }

            result.add( tpatterns ); result.add( vpatterns );
        }

        return result;
    }

Bei einem einfachen Test mit einem Array von [500000][8] komme ich auf eine ungefähre Laufzeit von 400 bis 500 Millisekunden; sollte also deutlich schneller laufen als die ursprüngliche Implementierung.

-Tim

 

[pocketom]

Hi!

Erstmal danke für deine Antwort. Sieht auf den ersten Blick kompliziert aus, hab aber verstanden wie es funzt. Liest sich nur etwas ungewohnt. Ich werde es mal probieren und die Performance mit meiner aktuellen Lösung vergleichen. Jetzt wo dus sagst, eine exakte Lösung brauche ich eigentlich eh nicht, das Teil splittet die Daten für ein neuronales Netz, dem dürfte das wurst sein. Was es allerdings tun muss, es muss immer mischen. Auch wenn man 0% oder 100% als Anteil1 verwendet.


Habe natürlich nicht locker lassen können und mir die ganze Nacht um die Ohren geschlagen *räusper*

*gähn*


Habe das jetzt mal so implementiert:

/**
	 * splits an array into two parts by drawing random values
	 * 
	 * @param data the input 2D array of doubles
	 * @param part1percentage the percentage to put into the first 2D array,
	 * the rest is put into the second array
	 * 
	 * @return a list containing the two splitted parts (List(0) = training, List(1) = validation)
	 */
	public static List<double[][]> splitArrayRandomly(double[][] data, double part1percentage)
	{		
		if(part1percentage > 1)
			part1percentage = 1.0;
		else if(part1percentage < 0)
			part1percentage = 0.0;
				
		int tcount = (int)(data.length * part1percentage);
		int vcount = data.length -tcount;
		int total = tcount + vcount;
				    	
    	// fetch the training patterns
		System.out.println("Drawing training pattern pool("+tcount+" total).");    	
    	double[][] tpatterns = new double[tcount][data[0].length];
    	int[] t_positions = getUniqueRandomInts(tcount, total);    	
    	for (int i = 0; i < t_positions.length; i++)
			tpatterns[i] = data[t_positions[i]];

    	System.out.println();
    	// fetch the validation patterns
    	System.out.println();
    	System.out.println("Drawing validation pattern pool("+vcount+" total).");    	
    	double[][] vpatterns = new double[vcount][data[0].length];
    	int[] v_positions = getUniqueRandomInts(vcount, total, t_positions);
    	for (int i = 0; i < v_positions.length; i++)
			vpatterns[i] = data[v_positions[i]];    	
    	
    	ArrayList<double[][]> result = new ArrayList<double[][]>();
    	
    	result.add(tpatterns);
    	result.add(vpatterns);   	
    	
    	return result;
	}


/**
     * create an array with unique, random drawn integers
     * from 0 - max.
     * 
     * @param size the number of integers to draw
     * @param max the highest integer that should be drawn
     * 
     * @return array with the random integers
     */
    private static int[] getUniqueRandomInts(int size, int max)
    {			
    	return getUniqueRandomInts(size, max, new int[0]);
    }    
    
    /**
     * create an array with unique, random drawn integers
     * from 0 - max.
     * 
     * @param size the number of integers to draw
     * @param max the highest integer that should be drawn
     * @param exclude an array of integers that should not be contained in the
     * result, for example because they have been already drawn.
     * 
     * @return array with the random integers
     */
    private static int[] getUniqueRandomInts(int size, int max, int[] exclude)
    {	
		Stack<Integer> st 	= new Stack<Integer>();
		HashSet<Integer> hs = new HashSet<Integer>();
		
		for (int i = 0; i < exclude.length; i++) 
			hs.add(exclude[i]);
		
    	Random randomizer = new Random(System.nanoTime());
    	int r;
    	
    	
    	int count = 1; 
    	String len = String.valueOf(size);
    	String zeros = "";
    	for(int i=0;i<len.length();i++)
    		zeros+="0";
    	DecimalFormat formater = new DecimalFormat(zeros);
    	while(st.size() < size)
    	{
    		r = randomizer.nextInt(max);  
    		
    		if(!hs.contains(r))
    		{
    			hs.add(r);
    			st.push(r);
    			
    			if(count%100000 == 0)
    				System.out.print( formater.format((((int)(hs.size()/100000))*100000))+"  ");
    			if(count%1000000 == 0)
    				System.out.println();
    			
    			count++;
    		}   		
    	}
    	
    	int[] result = new int[st.size()];
    	
    	for(int i=0; i<result.length; i++)
    		result[i] = st.pop();    		
    	
    	return result;
    }

Ist wirklich sehr sehr schnell (zumindest im Vergleich zu vorher). Für 11 Millionen Arraypositionen braucht er bei mir so ca. 3-4 Minuten. Vorher hab ichs nicht mehr ausgehalten bei 5 Mio. und nach ner Stunde abgebrochen... Braucht nur RAM ohne Ende, 10-12 GB futtert es bei 11 Mio. auf. Überlege grad wie ich es jetzt noch parallelisieren kann, habe noch etliche Kerne die kalt sind. Denke um den Faktor 4-8 kann man noch was rausholen (ist zwar nicht zwingend nötig aber macht irgendwie Fun).

So funkt das jetzt: Zum checken das Hashset nutzen, contains() hat O(1), und zum aufnehmen den Stack mit ebenfalls O(1) dank push(). Generieren des Ergebnisses auch O(1) dank pop(). Und einfach und intuitiv bedienbar dank des 2-Phasen Konzepts.

Den von dir vorgeschlagenen BinomialGenerator werd ich gleich mal ausprobieren, ist der irgendwie schneller als der original Randomizer (bzw. gibts da generell nen großen Unterschied bei Drittanbieter-Randomizern)?

Ach ja, und es ist natürlich die exakte Lösung.

 

[Guest]

Hi!

...
Was es allerdings tun muss, es muss immer mischen. Auch wenn man 0% oder 100% als Anteil1 verwendet.

Ok, das hatte ich übersehen.

...
Den von dir vorgeschlagenen BinomialGenerator werd ich gleich mal ausprobieren, ist der irgendwie schneller als der original Randomizer (bzw. gibts da generell nen großen Unterschied bei Drittanbieter-Randomizern)?
...

Der eigentliche Zufallszahlengenerator ist der CellularAutomatonRNG (erweitert Randomizer, ist also ein DropIn Ersatz); und der ist sehr schnell. Der BinomialGenerator sorgt nur dafür, dass die Gewichtung der erzeugten 1sen und 0en stimmt. Einen guten Blog Beitrag zu Java und Zufallszahlen gibt es hier [1], mehr zur Binomialverteilung gibts in der Wikipedia [2] und hier [3] gibt es eine sehr gute Java Bibliothek für wissenschaftliche Anwendungen, unter anderem auch mit einem Zufallszahlengenerator.

-Tim

[1] http://blog.uncommons.org/2008/04/0...-random-numbers-part-1-beyond-javautilrandom/
[2] http://de.wikipedia.org/wiki/Binomialverteilung
[3] http://www.ee.ucl.ac.uk/~mflanaga/java/

 

[Guest]

Hi,

nochmal etwas überarbeitet:

- jetzt mit Shuffle
- Benutzt zusätzlich commons-math (http://commons.apache.org/math/)

Braucht nach Warmup ca. 3 Sekunden für 6 Millionen Einträge; allerdings wieder kein exakter Split.

-Tim

    public static List<ArrayList<ArrayList<Double>>> splitArrayRandomly2(ArrayList<ArrayList<Double>> data, double part1percentage)
    {
        List<ArrayList<ArrayList<Double>>> result = new ArrayList<ArrayList<ArrayList<Double>>>( 2 );

        BinomialGenerator generator = null;
        int[] indexPermutation;

        if( part1percentage > 1.0 )
        {
            part1percentage = 1.0;
        }
        else if (part1percentage < 0.0 )
        {
            part1percentage = 0.0;
        }

        indexPermutation = new RandomDataImpl().nextPermutation( data.size(), data.size() );

        try
        {
            // genarates random numbers between 0 and 1 with a statistical percentage of part1percentage 1'ns
            generator = new BinomialGenerator(1, part1percentage, new CellularAutomatonRNG( DefaultSeedGenerator.getInstance() ) );
        }
        catch ( SeedException e )
        {
            e.printStackTrace();  //Todo: Do something usefull here
        }

        // create the two arrays we sort to, with a safety-buffer of one percent
        int tcount = (int)(data.size() * part1percentage) + (int)(data.size() * 0.01);
        int vcount = (int)(data.size() * (1.0 - part1percentage) ) + (int)(data.size() * 0.01);

        ArrayList<ArrayList<Double>> tpatterns = new ArrayList<ArrayList<Double>>(tcount);
        ArrayList<ArrayList<Double>> vpatterns = new ArrayList<ArrayList<Double>>(vcount);

        for ( int i : indexPermutation )
        {
            if ( getNextRandomNumber(generator, part1percentage) == 1 )
                tpatterns.add( data.get( i ) );
            else
                vpatterns.add( data.get( i ) );
        }

        result.add( tpatterns ); result.add( vpatterns );

        return result;
    }

    /**
     * Returns a random sequence on ones and zeros with the given stochastic propability of ones.
     *
     */
    private static int getNextRandomNumber( BinomialGenerator generator, double propbability )
    {
        if ( propbability == 1.0 )
        {
            return 1;
        }
        else if ( propbability == 0.0 )
        {
            return 0;
        }
        else
        {
            return generator.nextValue();
        }
    }

 

[Marco13]

Hm :? was spricht jetzt gegen sowas? (3.9 Sekunden für 10 Millionen Einträge bei exaktem split - und 7 Zeilen code...)

import java.util.*;

class RandomSplitTest
{
    public static void main(String args[])
    {
        int size = 10000000;
        List<double[]> data = new ArrayList<double[]>(size);
        for (int i=0; i<size; i++)
        {
            double d[] = new double[2];
            for (int j=0; j<d.length; j++)
            {
                d[j] = Math.random();
            }
            data.add(d);
        }

        System.out.println("Splitting...");
        long before = System.nanoTime();
        List<List<double[]>> result = splitArrayRandomly(data, 0.2);
        long after = System.nanoTime();
        long requiredMs = (after-before) / 1000000;
        System.out.println("Required "+requiredMs+" ms");


        //print(result.get(0));
        //print(result.get(1));
    }


    private static void print(List<double[]> list)
    {
        System.out.println("Number of elements: "+list.size());
        for (int i=0; i<list.size(); i++)
        {
            System.out.println(Arrays.toString(list.get(i)));
        }
    }



    public static List<List<double[]>> splitArrayRandomly(List<double[]> data, double part1percentage)
    {
        List<double[]> input = new ArrayList<double[]>(data);
        Collections.shuffle(input);
        int split = (int)(input.size() * part1percentage);
        List<List<double[]>> result = new ArrayList<List<double[]>>();
        result.add(input.subList(0, split));
        result.add(input.subList(split, input.size()));
        return result;
    }


}

 

[Marco13]

Korrigiere: 3 Zeilen

    public static List<List<double[]>> splitArrayRandomly2(List<double[]> data, double p)
    {
        List<double[]> i = new ArrayList<double[]>(data);
        Collections.shuffle(i);
        return new ArrayList<List<double[]>>(Arrays.asList(i.subList(0, (int)(i.size() * p)), i.subList((int)(i.size() * p), i.size())));
    }

( )

(Jaja.... :roll: )

 

[pocketom]

Hey, danke!

Das ist natürlich eine simple und sehr effective Methode. Ich habe wohl ein wenig zu komplizert gedacht. Wobei die 3 Zeilenvaraiante ich natürlich auf zwei verkürzen liesse wenn man data gleich direkt shufflen würde ;-)

Ich bevorzuge dann aber doch eher die 7 Zeilen, das ist übersichtlicher.