среда, 3 ноября 2010 г.

Поиск по ключу входящему в числовой диапазон.

Дана таблица по которой, в зависимости от опыта игрока, определяется его уровень:

  Диапазон опыта     Уровень

0 < exp <= 12 1
12 < exp <= 30 2
30 < exp <= 67 3
... ...
231 < exp <= 300 10

Задача: реализовать алгоритм поиска уровня.

Для решения задачи я задействую класс java.util.TreeMap. Почему этот класс? Все просто, он реализует важный интерфейс - java.util.NavigableMap, появившийся с версии Java 1.6. Его метод

Map.Entry<K,V> ceilingEntry(K key)

как раз позволяет найти запись в map-е удовлетворяющую условию K(n) < key <= K(n+1) и при этом будет содержать значение по ключу K(n+1). Таким образом, остается составить map-у из записей: ключ - макс. значение опыта на уровне, значение - уровень. Код решения:

Для наглядности я захардкодил map-у в коде, на деле же она создается из xml.

7 комментариев:

BegemoT комментирует...

Интерфейс интересный, не обращал на него внимания. Но в данном случае, казалось бы, простой массив верхних границ уровней, + binarySearch по нему будет иметь ту же асимптотику, но меньший коэффициент, и экономнее по памяти -- нет?

Никита Кокшаров комментирует...

Таблица уровней в приложении существует лишь в одном экземпляре, потому я особо не беспокоюсь о памяти. А вот по поводу использования массива не могли бы привести пример?

Bura комментирует...

Коллеги, вот пример:

public class Test{

private static final NavigableMap lMap = new TreeMap();

private static final Integer[] array = {
12, 30, 67, 100, 129, 148, 174, 200, 240, 300
};

static {
lMap.put(12, 1);
lMap.put(30, 2);
lMap.put(67, 3);
lMap.put(100, 4);
lMap.put(129, 5);
lMap.put(148, 6);
lMap.put(174, 7);
lMap.put(200, 8);
lMap.put(240, 9);
lMap.put(300, 10);
}

public static Integer findLevel1(Integer exp) {
return lMap.ceilingEntry(exp).getValue();
}

public static Integer findLevel2(Integer exp) {
for (int i = 0; i < array.length; i++) {
if (array[i] >= exp) {
return i + 1;
}
}

return array.length;
}

public static void main(String[] args) {
Integer[] testArr = {
3, 130, 180, 290, 300
};
for (Integer n : testArr) {
long start = System.nanoTime();
System.out.println("first: score=" + n
+ "; level=" + findLevel1(n)
+ "; time=" + (System.nanoTime() - start));
}
for (Integer n : testArr) {
long start = System.nanoTime();
System.out.println("second: score=" + n
+ "; level=" + findLevel1(n)
+ "; time=" + (System.nanoTime() - start));
}
}

}

Надеюсь с форматированием разберетесь :)

и мой стектрейс:

first: score=3; level=1; time=388038
first: score=130; level=6; time=20114
first: score=180; level=8; time=24863
first: score=290; level=10; time=18438
first: score=300; level=10; time=18438
second: score=3; level=1; time=25981
second: score=130; level=6; time=17600
second: score=180; level=8; time=17880
second: score=290; level=10; time=22629
second: score=300; level=10; time=18438

Вот такой вот интересный результат.

И еще, у варианта 1 есть недостаток: Если значение привесит максимально допустимое, то в результате мы получим NullPointerException.. со вторым вариантом такого не произойдет.

Никита Кокшаров комментирует...

Я вижу использовали уровни как индекс в массиве, но что если вместо индекса будет объект? В своем посте я хотел показать именно пример поиска.

NPE можно избежать, если добавить
lMap.put(Integer.MAX_VALUE, 10);

В моем приложении такое произойти не может, т.к. опыт не может быть больше границы 300.

Bura комментирует...

"но что если вместо индекса будет объект?"
Можно, например, использовать вот такую конструкцию:
Object[][] array = {
{new Integer(10), любой объект},
...
}

Bura комментирует...

Но на самом деле, лучше использовать стандартные реализации (если они уже есть) и не изобретать своих велосипедов. Как известно.. свой код JIT оптимизирует лучше чем чужой.

Анонимный комментирует...

Bura, а ты используй чужой JIT компилятор,тогда все будет ок! Проверено!