directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel Lecharny <elecha...@gmail.com>
Subject Re: Long comparisons
Date Wed, 23 Jan 2008 13:55:28 GMT
Ok, I did some experiments with the long comparisons. Here are the results.

What I did is that I created 4 methods, comparing long using different 
algorithms :

compare1 : splits longs into two ins (low and high), and then compares 
the ints transformed to long.
compare2 : uses 'if ( Math.abs( comp ) == comp )'
compare3 : uses 'if ( x - y > 0 )'
compare4 : uses David's algorithm ( 4 comparisons, depending on the 
longs' sign)

I did a test with X and Y, two arrays of longs, with those values :

        long[] X = new long[]{Long.MIN_VALUE, -500, -1, 0, 1, 500, 
Long.MAX_VALUE};
        long[] Y = new long[]{Long.MIN_VALUE, -501, -500, -499, -1, 0, 
1, 499, 500, 501, Long.MAX_VALUE};

Then I compare the results of those 4 compare methods. If they all have 
the same result, then I print nothing. If there is some difference, than 
I dump all the results.

Here is what I get :


x - y [-1, 499] = -500
Compare1 [-1, 499] => x > y
Compare4 [-1, 499] => x > y
Compare2 [-1, 499] => x < y
Compare3 [-1, 499] => x < y
-----------------------------------------------------------------

x - y [-1, 500] = -501
Compare1 [-1, 500] => x > y
Compare4 [-1, 500] => x > y
Compare2 [-1, 500] => x < y
Compare3 [-1, 500] => x < y
-----------------------------------------------------------------

x - y [-1, 501] = -502
Compare1 [-1, 501] => x > y
Compare4 [-1, 501] => x > y
Compare2 [-1, 501] => x < y
Compare3 [-1, 501] => x < y
-----------------------------------------------------------------

x - y [-1, 9223372036854775807] = -9223372036854775808
Compare1 [-1, 9223372036854775807] => x > y
Compare4 [-1, 9223372036854775807] => x > y
Compare2 [-1, 9223372036854775807] => x > y
Compare3 [-1, 9223372036854775807] => x < y
-----------------------------------------------------------------

x - y [0, -9223372036854775808] = -9223372036854775808
Compare1 [0, -9223372036854775808] => x < y
Compare4 [0, -9223372036854775808] => x < y
Compare2 [0, -9223372036854775808] => x > y
Compare3 [0, -9223372036854775808] => x < y
-----------------------------------------------------------------

x - y [0, -501] = 501
Compare1 [0, -501] => x < y
Compare4 [0, -501] => x < y
Compare2 [0, -501] => x > y
Compare3 [0, -501] => x > y
-----------------------------------------------------------------

x - y [0, -500] = 500
Compare1 [0, -500] => x < y
Compare4 [0, -500] => x < y
Compare2 [0, -500] => x > y
Compare3 [0, -500] => x > y
-----------------------------------------------------------------

x - y [0, -499] = 499
Compare1 [0, -499] => x < y
Compare4 [0, -499] => x < y
Compare2 [0, -499] => x > y
Compare3 [0, -499] => x > y
-----------------------------------------------------------------

x - y [0, -1] = 1
Compare1 [0, -1] => x < y
Compare4 [0, -1] => x < y
Compare2 [0, -1] => x > y
Compare3 [0, -1] => x > y
-----------------------------------------------------------------

x - y [1, -501] = 502
Compare1 [1, -501] => x < y
Compare4 [1, -501] => x < y
Compare2 [1, -501] => x > y
Compare3 [1, -501] => x > y
-----------------------------------------------------------------

x - y [1, -500] = 501
Compare1 [1, -500] => x < y
Compare4 [1, -500] => x < y
Compare2 [1, -500] => x > y
Compare3 [1, -500] => x > y
-----------------------------------------------------------------

x - y [1, -499] = 500
Compare1 [1, -499] => x < y
Compare4 [1, -499] => x < y
Compare2 [1, -499] => x > y
Compare3 [1, -499] => x > y
-----------------------------------------------------------------

x - y [1, -1] = 2
Compare1 [1, -1] => x < y
Compare4 [1, -1] => x < y
Compare2 [1, -1] => x > y
Compare3 [1, -1] => x > y
-----------------------------------------------------------------

x - y [500, -501] = 1001
Compare1 [500, -501] => x < y
Compare4 [500, -501] => x < y
Compare2 [500, -501] => x > y
Compare3 [500, -501] => x > y
-----------------------------------------------------------------

x - y [500, -500] = 1000
Compare1 [500, -500] => x < y
Compare4 [500, -500] => x < y
Compare2 [500, -500] => x > y
Compare3 [500, -500] => x > y
-----------------------------------------------------------------

x - y [500, -499] = 999
Compare1 [500, -499] => x < y
Compare4 [500, -499] => x < y
Compare2 [500, -499] => x > y
Compare3 [500, -499] => x > y
-----------------------------------------------------------------

x - y [500, -1] = 501
Compare1 [500, -1] => x < y
Compare4 [500, -1] => x < y
Compare2 [500, -1] => x > y
Compare3 [500, -1] => x > y
-----------------------------------------------------------------

x - y [9223372036854775807, -1] = -9223372036854775808
Compare1 [9223372036854775807, -1] => x < y
Compare4 [9223372036854775807, -1] => x < y
Compare2 [9223372036854775807, -1] => x > y
Compare3 [9223372036854775807, -1] => x < y
*********************************************************


As you can see, only methods 1 and 4 are correct. Which one should we use ?

I run the very same tests million of times, and measured the time it cost :

Delta compare 1 = 12621ms
Delta compare 2 = 12522 ms
Delta compare 3 = 10086 ms
Delta compare 4 = 7098 ms

Clearly, David's method is the best. So be it...

Thanks David !

PS: The code ...



public class TestCompareLong
{
   
    private static int compare1( long l1, long l )
    {
        long l1l = l1 & 0x00000000FFFFFFFFL;
        long l1h = (l1 >> 32) & 0x00000000FFFFFFFFL;

        long lll = l & 0x00000000FFFFFFFFL;
        long llh = (l >> 32) & 0x00000000FFFFFFFFL;

        if ( l1h < llh )
        {
            return -1;
        }
        else if ( l1h > llh )
        {
            return 1;
        }
        else
        {
            if ( l1l < lll )
            {
                return -1;
            }
            else if ( l1l > lll )
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
    }

    private static int compare2( long l1, long l )
    {
        if ( l1 == l )
        {
            return 0;
        }
       
        long comp = l1 - l;
       
        if ( Math.abs( comp ) == comp )
        {
            return 1;
        }
        else
        {
            return -1;
        }
    }

    private static int compare3( long l1, long l )
    {
        if ( l1 == l )
        {
            return 0;
        }
       
        if ( l1 - l > 0 )
        {
            return 1;
        }
        else
        {
            return -1;
        }
    }

    private static int compare4( long l1, long l2 )
    {
        if ( l1 == l2 )
        {
            return 0;
        }
       
        if ( l1 >= 0 )
        {
            if ( l2 >= 0 )
            {
                return ( l1 > l2 ) ? 1 : -1;
            }
            else
            {
                return -1;
            }
        }
        else if ( l2 >= 0 )
        {
            return 1;
        }
        else
        {
            return ( l1 < l2 ) ? -1 : 1;
        }
    }


    private static void test( long l1 )
    {
        long[] LL = new long[]{Long.MIN_VALUE, -500, -1, 0, 1, 500, 
Long.MAX_VALUE};

        System.out.println( "================================\n" );
       
        for ( long l:LL )
        {
            if ( compare1( l1, l ) == -1 )
            {
                System.out.println( l1 + " > " + l );
            }
            else if ( compare1( l1, l ) == 1 )
            {
                System.out.println( l1 + " > " + l );
            }
            else
            {
               System.out.println( l1 + " = " + l );
            }
        }
    }
   
    private static String printResult( int value )
    {
        if ( value == 1 )
        {
            return "x > y";
        }
        else if ( value == -1 )
        {
            return "x < y";
        }
        else
        {
            return "x = y";
        }
    }
   
    private static void test2()
    {
        long[] X = new long[]{Long.MIN_VALUE, -500, -1, 0, 1, 500, 
Long.MAX_VALUE};
        long[] Y = new long[]{Long.MIN_VALUE, -501, -500, -499, -1, 0, 
1, 499, 500, 501, Long.MAX_VALUE};

        System.out.println( "================================\n" );
        for ( long x:X )
        {
            for ( long y:Y )
            {
                int res1 = compare1( x, y );
                int res2 = compare2( x, y );
                int res3 = compare3( x,y );
                int res4 = compare4( x,y );
               
                if ( ( res1 != res2 ) || ( res1 != res3 )|| ( res1 != 
res4 ) )
                {
                    System.out.println( 
"-----------------------------------------------------------------\n" );
                    System.out.println( "x - y [" + x + ", " + y +"] = " 
+ ( x - y ) );
                    System.out.println( "Compare1 [" + x + ", " + y +"] 
=> " + printResult( res1 ) );
                    System.out.println( "Compare4 [" + x + ", " + y +"] 
=> " + printResult( res4 ) );
                    System.out.println( "Compare2 [" + x + ", " + y +"] 
=> " + printResult( res2 ) );
                    System.out.println( "Compare3 [" + x + ", " + y +"] 
=> " + printResult( res3 ) );
                }
            }
        }
    }

   
    /**
     */
    public static void main( String[] args )
    {
        test2();
       
        System.out.println( 
"*********************************************************\n" );

        test( Long.MIN_VALUE );
        test( -100L );
        test( -1L );
        test( 0L );
        test( 1L );
        test( 100L );
        test( Long.MAX_VALUE );
       
        int res = 0;
        long t0 = System.currentTimeMillis();
       
        for ( long i = 0; i < 2000000000L; i++ )
        {
            res = compare1( Long.MIN_VALUE, i );
        }
       
        long t1 = System.currentTimeMillis();

        if ( res != 1 )
        {
            System.out.println( "Error" );
        }
        System.out.println( "Delta compare 1 = " + ( t1 - t0 ) );

   
        t0 = System.currentTimeMillis();
       
        for ( long i = 0; i < 2000000000L; i++ )
        {
            res = compare2( Long.MIN_VALUE, i );
        }
       
        t1 = System.currentTimeMillis();

        if ( res != 1 )
        {
            System.out.println( "Error" );
        }
        System.out.println( "Delta compare 2 = " + ( t1 - t0 ) );

   
        t0 = System.currentTimeMillis();
       
        for ( long i = 0; i < 2000000000L; i++ )
        {
            res = compare3( Long.MIN_VALUE, i );
        }
       
        t1 = System.currentTimeMillis();

        if ( res != 1 )
        {
            System.out.println( "Error" );
        }
        System.out.println( "Delta compare 3 = " + ( t1 - t0 ) );

        t0 = System.currentTimeMillis();
       
        for ( long i = 0; i < 2000000000L; i++ )
        {
            res = compare4( Long.MIN_VALUE, i );
        }
       
        t1 = System.currentTimeMillis();

        if ( res != 1 )
        {
            System.out.println( "Error" );
        }
        System.out.println( "Delta compare 4 = " + ( t1 - t0 ) );
    }

}

-- 
--
cordialement, regards,
Emmanuel L├ęcharny
www.iktek.com
directory.apache.org



Mime
View raw message