- wrap an outer scope variables in object and define a method
- use Lambda functions
Surprisingly 1st method became almost 2x more performant:
member
final public class BinaryGap { public BinaryGap( long value ){ val = value; } public final static int maxGapCount( final long value ) { final BinaryGap vo = new BinaryGap(value); vo.skipBits(0 ); for( int max0 = 0; vo.val !=0 ; ) { vo.skipBits(1 ); int z = vo.skipBits(0 ); if( z == 0 ) return max0; if( z > max0 ) max0 = z; } return 0; } long val; final int skipBits( final int bit0 ) { int ret = 0; do { if( val == 0 || (val&1) != bit0 ) return ret; val = val >> 1; ret++; }while( val != 0 ); return ret; } }
Lambda
public final static int maxGapCountLambda( long value ) { class Wrap{ long v; } final Wrap w = new Wrap(); w.v = value; IntSupplier skip0 = ()-> { int count=0; long L = w.v; for( ; L!=0 && (L&1) == 0; count++ ) // skip 0 L = L>>1; w.v = L; return count; }; IntSupplier skip1 = ()-> { long L = w.v; while( L!=0 && (L&1) == 1 ) // skip 1 L = L>>1; w.v = L; return 0; }; skip0.getAsInt(); int maxCount =0; while( w.v != 0 ) { skip1.getAsInt(); int count =skip0.getAsInt(); if( count > maxCount ) maxCount = count; } return maxCount; }
Tests
Test | Duration | Result |
---|---|---|
maxGapCount | 0s | passed |
maxGapCountInlineLoad | 0.126s Of course inline is fastest, but not as much readable. |
passed |
maxGapCountLambdaLoad | 0.226s | passed |
maxGapCountLoad | 0.141s | passed |
skipBits | 0s | passed |
Full sources
package codily.lesson1; import java.util.function.IntSupplier; import java.util.function.LongPredicate; import java.util.function.LongToIntFunction; /** * https://app.codility.com/programmers/lessons/1-iterations/binary_gap/ */ final public class BinaryGap { long val; public BinaryGap( long value ){ val = value; } public final static int maxGapCount( final long value ) { final BinaryGap vo = new BinaryGap(value); vo.skipBits(0 ); for( int max0 = 0; vo.val !=0 ; ) { vo.skipBits(1 ); int z = vo.skipBits(0 ); if( z == 0 ) return max0; if( z > max0 ) max0 = z; } return 0; } public final static int maxGapCountInline( long value ) { while( value!=0 && (value&1) == 0 ) // skip 0 value = value>>1; int maxCount =0; while( value !=0 ) { while( value!=0 && (value&1) == 1 ) // skip 1 value = value>>1; int count =0; while( value!=0 && (value&1) == 0 ) // skip 0 { count ++; value = value >> 1; } if( count > maxCount ) maxCount = count; } return maxCount; } public final static int maxGapCountLambda( long value ) { class Wrap{ long v; } final Wrap w = new Wrap(); w.v = value; IntSupplier skip0 = ()-> { int count=0; long L = w.v; for( ; L!=0 && (L&1) == 0; count++ ) // skip 0 L = L>>1; w.v = L; return count; }; IntSupplier skip1 = ()-> { long L = w.v; while( L!=0 && (L&1) == 1 ) // skip 1 L = L>>1; w.v = L; return 0; }; skip0.getAsInt(); int maxCount =0; while( w.v != 0 ) { skip1.getAsInt(); int count =skip0.getAsInt(); if( count > maxCount ) maxCount = count; } return maxCount; } final int skipBits( final int bit0 ) { int ret = 0; do { if( val == 0 || (val&1) != bit0 ) return ret; val = val >> 1; ret++; }while( val != 0 ); return ret; } }
package codily.lesson1; import org.junit.Test; import static org.junit.Assert.*; public class BinaryGapTest { public final long [] exp = { 00, 00, 00, 00, 00, 00, 01, 02, 03, 30 }; public final long [] inp = { 0b0000_0000_0000_0000_0000_0000_0000_0000L , 0b1111_1111_1111_1111_1111_1111_1111_1111L , 0b0000_0000_0000_0000_0000_0000_0000_0001L , 0b0000_0000_0000_0000_0000_0000_0000_0011L , 0b0000_0000_0000_0000_0000_0000_0000_0010L , 0b0000_0000_0000_0000_0000_0000_0000_0100L , 0b0000_0000_0000_0000_0000_0000_0000_0101L , 0b0000_0000_0000_0000_0000_0000_0000_1001L , 0b0000_0000_0000_0000_0000_0000_1000_1001L , 0b1000_0000_0000_0000_0000_0000_0000_0001L }; long [] act= new long[inp.length]; @Test public void maxGapCount() { assertEquals(00, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_0000L ) ); assertEquals(00, BinaryGap.maxGapCount( 0b1111_1111_1111_1111_1111_1111_1111_1111L ) ); assertEquals(00, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_0001L ) ); assertEquals(00, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_0011L ) ); assertEquals(00, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_0010L ) ); assertEquals(00, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_0100L ) ); assertEquals(01, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_0101L ) ); assertEquals(02, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_1001L ) ); assertEquals(03, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_1000_1001L ) ); assertEquals(30, BinaryGap.maxGapCount( 0b1000_0000_0000_0000_0000_0000_0000_0001L ) ); } final int REPEAT_COUNT = 1000_000; @Test public void maxGapCountLoad() { for( int k=0; k < REPEAT_COUNT; k++ ) // timer count for( int i=0; i<exp.length; i++ ) act[i] = BinaryGap.maxGapCount( inp[i] ); assertArrayEquals( act, exp ); } @Test public void maxGapCountInlineLoad() { for( int k=0; k < REPEAT_COUNT; k++ ) // timer count for( int i=0; i<exp.length; i++ ) act[i] = BinaryGap.maxGapCountInline( inp[i] ); assertArrayEquals( act, exp ); } @Test public void maxGapCountLambdaLoad() { for( int k=0; k < REPEAT_COUNT; k++ ) // timer count for( int i=0; i<exp.length; i++ ) act[i] = BinaryGap.maxGapCountLambda( inp[i] ); assertArrayEquals( act, exp ); } @Test public void skipBits() { BinaryGap bg = new BinaryGap( 0L ); assertEquals( "zero", bg.skipBits(0), 0 ); assertEquals( "zero", bg.skipBits(0), 0 ); assertEquals( "zero", bg.skipBits(1), 0 ); bg = new BinaryGap( 0b1111_1111_1111_1111_1111_1111_1111_1111L ); assertEquals( "zero", bg.skipBits(0), 0 ); assertEquals( "zero", bg.skipBits(1), 32 ); assertEquals( "zero", bg.skipBits(1), 0 ); assertEquals( "zero", bg.skipBits(0), 0 ); } }
No comments:
Post a Comment