再帰を使わない code が net を探しても以外にないので、ここに書いておくことにした。(Dawn
主要 code:
private static AbstractList<String> GCP2(AbstractList<char[]> token_data_list, int max_size) { AbstractList<String> resultList = Utility.CreateList(max_size); char[] holder = new char[token_data_list.size()]; GCP2(holder, resultList, token_data_list, max_size); return resultList; } private static void GCP2( char[] holder, AbstractList<String> resultList, AbstractList<char[]> token_tables, int max_size ) { int[] slot_index = new int[holder.length]; int token_tab_index_max = token_tables.size() - 1; int add_count = 0; int current_depth = 0; A: while (true) { char[] tokens = token_tables.get(current_depth); int slot_offset = slot_index[current_depth]; for ( ;slot_offset < tokens.length;) { holder[current_depth] = tokens[ slot_offset++ ]; if ( current_depth >= token_tab_index_max ) { resultList.add( new String(holder) ); if (++add_count >= max_size) break A; } else { slot_index[current_depth++] = slot_offset; continue A; } } slot_index[current_depth--] = 0; } } /** * <pre>CreateRandomTokenTableEx の再帰を使用しない version. *performance up が期待されたが, 以外にも再帰を使っている CreateRandomTokenTableEx より少し劣るという結果に終わった... *</pre> * <pre style="width: 70%; background-color: white; border: solid 1px gray; padding: 5px"> * CreateRandomTokenTableNoRecursive(char_table, 4, 0, true); * token size=59969536, time spent=35001.143374ms * token size=59969536, time spent=25154.862951ms * token size=59969536, time spent=26027.361446ms * token size=59969536, time spent=28732.167771ms * token size=59969536, time spent=29026.178012ms * token size=59969536, time spent=27629.538253ms * * CreateRandomTokenTableEx(char_table, 4, 0, true); * token size=59969536, time spent=32314.025ms * token size=59969536, time spent=26509.068976ms * token size=59969536, time spent=25851.00512ms * token size=59969536, time spent=27271.664457ms * token size=59969536, time spent=27561.225602ms *</pre> *<pre> * この method は, 単一の char table から depth 数を取り出した場合の組み合わせ抽出します.(重複を許容 * max_size を 0 にすると全て, 2000 などの値を指定した場合, その値の数だけ抽出します.(組み合わせが max_size 以上 * * see CombinationsTest.testGetCombinationsNoRecursiveLoop * shuffle を適用しても実行速度への影響は無視できる level. * </pre> * @param token_data token 作成に使用する char table. * @param depth token の長さ. * @param max_size サイズを制限する場合指定.全て取得するなら 0. * @param shuffle true にすると抽出結果に Collections.shuffle を適用. * @return random token table * @since 2015/10/24 */ public static AbstractList<String> CreateRandomTokenTableNoRecursive(char[] token_data, int depth, int max_size, boolean shuffle) { AbstractList<char[]> sourceList = Utility.CreateList(depth); for (int i = 0; i < depth; i++) { sourceList.add( shuffle? Shuffle(token_data): token_data ); } int combination = (int)Math.pow(token_data.length, depth); if (max_size > 0 && combination > max_size) combination = max_size; StopWatch sw = new StopWatch(); sw.startNano(); AbstractList<String> resultList = GCP2(sourceList, combination); sw.stopNano(); AfxLogger.info("token size={}, time spent={}ms", resultList.size(), sw.getTimeSpentAsMillis()); if (shuffle) Collections.shuffle(resultList); return resultList; }
test method:
@SuppressWarnings("static-method") @Test public void testGetCombinationsNoRecursiveLoop() { int count = LOOP; final char[] char_table = "$%&'()*+,-./0123456789;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_`abcdefghijklmnopqrstuvwxyz{|}~".toCharArray(); // length=88 while (count-- > 0) { CreateRandomTokenTableNoRecursive(char_table, 4, 0, true); } }