private Iterable < Key > getSplitKey ( List < Key > keys , int numSplits ) { // If the number of keys is less than the number of splits, we are limited in the number of // splits we can make. if ( keys . size ( ) < numSplits - 1 ) { return keys ; } // Calculate the number of keys per split. This should be KEYS_PER_SPLIT, but may // be less if there are not KEYS_PER_SPLIT * (numSplits - 1) scatter entities. // // Consider the following dataset, where - represents an entity and * represents an entity // that is returned as a scatter entity: // ||---*-----*----*-----*-----*------*----*----|| // If we want 4 splits in this data, the optimal split would look like: // ||---*-----*----*-----*-----*------*----*----|| // | | | // The scatter keys in the last region are not useful to us, so we never request them: // ||---*-----*----*-----*-----*------*---------|| // | | | // With 6 scatter keys we want to set scatter points at indexes: 1, 3, 5. // // We keep this as a double so that any "fractional" keys per split get distributed throughout // the splits and don't make the last split significantly larger than the rest. double numKeysPerSplit = Math . max ( 1.0 , ( ( double ) keys . size ( ) ) / ( numSplits - 1 ) ) ; List < Key > keysList = new ArrayList < Key > ( numSplits - 1 ) ; // Grab the last sample for each split, otherwise the first split will be too small. for ( int i = 1 ; i < numSplits ; i ++ ) { int splitIndex = ( int ) Math . round ( i * numKeysPerSplit ) - 1 ; keysList . add ( keys . get ( splitIndex ) ) ; } return keysList ; }
Given a list of keys and a number of splits find the keys to split on .