Дана таблица по которой, в зависимости от опыта игрока, определяется его уровень:
Диапазон опыта Уровень
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.
Интерфейс интересный, не обращал на него внимания. Но в данном случае, казалось бы, простой массив верхних границ уровней, + binarySearch по нему будет иметь ту же асимптотику, но меньший коэффициент, и экономнее по памяти -- нет?
ОтветитьУдалитьТаблица уровней в приложении существует лишь в одном экземпляре, потому я особо не беспокоюсь о памяти. А вот по поводу использования массива не могли бы привести пример?
ОтветитьУдалитьКоллеги, вот пример:
ОтветитьУдалить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.
"но что если вместо индекса будет объект?"
ОтветитьУдалитьМожно, например, использовать вот такую конструкцию:
Object[][] array = {
{new Integer(10), любой объект},
...
}
Но на самом деле, лучше использовать стандартные реализации (если они уже есть) и не изобретать своих велосипедов. Как известно.. свой код JIT оптимизирует лучше чем чужой.
ОтветитьУдалитьBura, а ты используй чужой JIT компилятор,тогда все будет ок! Проверено!
ОтветитьУдалить