開発メモ

開発用のメモです。

三分木探査

ソース

package jp.mirageworld.algorithm.search;

import java.util.List;

public class TrinitySearch {

    public static <T extends Comparable<T>> boolean container(List<T> list, T target) {
        return container(list, target, 0, list.size());
    }

    public static <T extends Comparable<T>> boolean container(List<T> list, T target, int start, int end) {

        int len = end - start;
        int curr1 = start + (len / 3);
        int curr2 = end - (len / 3);
        if (len == 0)
            return false;
        T currObj1 = list.get(curr1);
        T currObj2 = list.get(curr2);
        int compare1 = target.compareTo(currObj1);
        int compare2 = target.compareTo(currObj2);

        //  1 or 0 or -1
        compare1 = compare1 < -1 ? -1 : compare1 > 1 ? 1 : compare1;
        compare2 = compare2 < -1 ? -1 : compare2 > 1 ? 1 : compare2;

        if (Math.abs(compare1 + compare2) == 1) {
            return true;
        } else if (compare1 + compare2 == -2) {
            return container(list, target, start, curr1);
        } else if (compare1 + compare2 == 0) {
            return container(list, target, curr1 + 1, curr2);
        }
        return container(list, target, curr2 + 1, end);

    }
}

テストケース

package jp.mirageworld.algorithm.search;

import static org.junit.Assert.*;

import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import jp.mirageworld.algorithm.search.BinarySearch;
import jp.mirageworld.algorithm.search.TrinitySearch;

import org.junit.Test;

public class TrinitySearchTest {

    @Test
    public void testContainer() {
        Set<Long> set = new HashSet<>();
        Long target = Math.round(Math.random() * 500);
        while (set.size() < 500000) {
            set.add(Math.round(Math.random() * 500000D));
        }
        List<Long> list = new LinkedList<>(set);
        target = list.get(target.intValue());

        Collections.sort(list);
        assertEquals(
                BinarySearch.container(list, target),
                TrinitySearch.container(list, target));

        long s = System.nanoTime();
        BinarySearch.container(list, target);
        long e = System.nanoTime();
        System.out.print(e - s);
        System.out.print(":" + target);
        System.out.println();

        s = System.nanoTime();
        TrinitySearch.container(list, target);
        e = System.nanoTime();
        System.out.print(e - s);
        System.out.print(":" + target);
        System.out.println();

    }

}
Twitter: @asahina_alice