написание компаратора для составного объекта для двоичного поиска
-
16-09-2019 - |
Вопрос
У меня есть класс и список экземпляров, которые выглядят примерно так (имена полей изменены для защиты невинных / проприетарных):
public class Bloat
{
public long timeInMilliseconds;
public long spaceInBytes;
public long costInPennies;
}
public class BloatProducer
{
final private List<Bloat> bloatList = new ArrayList<Bloat>();
final private Random random = new Random();
public void produceMoreBloat()
{
int n = bloatList.size();
Bloat previousBloat = (n == 0) ? new Bloat() : bloatList.get(n-1);
Bloat newBloat = new Bloat();
newBloat.timeInMilliseconds =
previousBloat.timeInMilliseconds + random.nextInt(10) + 1;
newBloat.spaceInBytes =
previousBloat.spaceInBytes + random.nextInt(10) + 1;
newBloat.costInPennies =
previousBloat.costInPennies + random.nextInt(10) + 1;
bloatList.add(newBloat);
}
/* other fields/methods */
public boolean testMonotonicity()
{
Bloat previousBloat = null;
for (Bloat thisBloat : bloatList)
{
if (previousBloat != null)
{
if ((previousBloat.timeInMilliseconds
>= thisBloat.timeInMilliseconds)
|| (previousBloat.spaceInBytes
>= thisBloat.spaceInBytes)
|| (previousBloat.costInPennies
>= thisBloat.costInPennies))
return false;
}
previousBloat = thisBloat;
}
return true;
}
BloatProducer bloatProducer;
Список bloatList
хранится внутри с помощью BloatProducer
и поддерживается таким образом, что он только добавляет новые Bloat
записи, не изменяет ни одно из старых, и каждое из полей монотонно увеличивается, например bloatProducer.testMonotonicity()
всегда возвращался бы true
.
Я хотел бы использовать Collections.binarySearch(list,key,comparator)
для поиска Bloat
записывайте с помощью полей timeInMilliseconds, spaceInBytes или costInPennies.(и если число находится между двумя записями, я хочу найти предыдущую запись)
Какой самый простой способ написать серию из 3 классов компаратора, чтобы заставить это работать?Должен ли я использовать ключ, который является раздувающимся объектом с фиктивными полями для тех, которые я не ищу?
Решение
Вам нужно будет написать отдельный компаратор для каждого поля, по которому вы хотите провести сравнение:
public class BloatTimeComparator implements Comparator<Bloat> {
public int compare(Bloat bloat1, Bloat bloat2) {
if (bloat1.timeInMilliseconds > bloat2.timeInMilliseconds) {
return 1;
} else if (bloat1.timeInMilliseconds < bloat2.timeInMilliseconds) {
return -1;
} else {
return 0;
}
}
}
И так далее для каждого свойства в Bloat
вы хотите провести сравнение дальше (вам нужно будет создать класс компаратора для каждого).Затем используйте вспомогательный метод Collections:
Collections.binarySearch(bloatList, bloatObjectToFind,
new BloatTimeComparator());
Из Документация Java для метода BinarySearch возвращаемое значение будет:
индекс поискового ключа, если он содержится в списке;в противном случае, (-(точка вставки) - 1).Точка вставки определяется как точка, в которой ключ будет вставлен в список:индекс первого элемента больше ключа, или list.size(), если все элементы в списке меньше указанного ключа.Обратите внимание, что это гарантирует, что возвращаемое значение будет >= 0 тогда и только тогда, когда ключ найден.
Который является указанным вами индексом, который вы хотели.
Другие советы
Вам нужно будет иметь 3 отдельных Comparator
s, если вы хотите выполнить поиск по каждому из 3-х свойств.
Более чистым вариантом было бы иметь общий Comparator
который получает параметр, указывающий ему, по какому полю сравнивать.
Базовый универсальный компаратор должен выглядеть примерно так:
public class BloatComparator implements Comparator<Bloat>
{
CompareByEnum field;
public BloatComparator(CompareByEnum field) {
this.field = field;
}
@Override
public int compare(Bloat arg0, Bloat arg1) {
if (this.field == CompareByEnum.TIME){
// compare by field time
}
else if (this.field == CompareByEnum.SPACE) {
// compare by field space
}
else {
// compare by field cost
}
}
}
Вот основанный на тестировании подход к написанию первого компаратора:
public class BloatTest extends TestCase{
public class Bloat {
public long timeInMilliseconds;
public long spaceInBytes;
public long costInPennies;
public Bloat(long timeInMilliseconds, long spaceInBytes, long costInPennies) {
this.timeInMilliseconds = timeInMilliseconds;
this.spaceInBytes = spaceInBytes;
this.costInPennies = costInPennies;
}
}
public void testMillisecondComparator() throws Exception {
Bloat a = new Bloat(5, 10, 10);
Bloat b = new Bloat(3, 12, 12);
Bloat c = new Bloat(5, 12, 12);
Comparator<Bloat> comparator = new MillisecondComparator();
assertTrue(comparator.compare(a, b) > 0);
assertTrue(comparator.compare(b, a) < 0);
assertEquals(0, comparator.compare(a, c));
}
private static class MillisecondComparator implements Comparator<Bloat> {
public int compare(Bloat a, Bloat b) {
Long aTime = a.timeInMilliseconds;
return aTime.compareTo(b.timeInMilliseconds);
}
}
}
Если вы хотите использовать двоичный поиск для всех трех свойств, вам необходимо создать для них компараторы и иметь дополнительные списки или наборы деревьев, отсортированные по этим компараторам.
тестовая программа (MultiBinarySearch.java
) чтобы увидеть, работают ли эти идеи должным образом (похоже, что они):
package com.example.test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
class Bloat
{
final public long timeInMilliseconds;
final public long spaceInBytes;
final public long costInPennies;
static final private int N = 100;
public Bloat(long l1, long l2, long l3) {
timeInMilliseconds = l1;
spaceInBytes = l2;
costInPennies = l3;
}
public Bloat() { this(0,0,0); }
public Bloat moreBloat(Random r)
{
return new Bloat(
timeInMilliseconds + r.nextInt(N) + 1,
spaceInBytes + r.nextInt(N) + 1,
costInPennies + r.nextInt(N) + 1
);
}
public String toString() {
return "[bloat: time="+timeInMilliseconds
+", space="+spaceInBytes
+", cost="+costInPennies
+"]";
}
static int compareLong(long l1, long l2)
{
if (l2 > l1)
return -1;
else if (l1 > l2)
return 1;
else
return 0;
}
public static class TimeComparator implements Comparator<Bloat> {
public int compare(Bloat bloat1, Bloat bloat2) {
return compareLong(bloat1.timeInMilliseconds, bloat2.timeInMilliseconds);
}
}
public static class SpaceComparator implements Comparator<Bloat> {
public int compare(Bloat bloat1, Bloat bloat2) {
return compareLong(bloat1.spaceInBytes, bloat2.spaceInBytes);
}
}
public static class CostComparator implements Comparator<Bloat> {
public int compare(Bloat bloat1, Bloat bloat2) {
return compareLong(bloat1.costInPennies, bloat2.costInPennies);
}
}
enum Type {
TIME(new TimeComparator()),
SPACE(new SpaceComparator()),
COST(new CostComparator());
public Comparator<Bloat> comparator;
Type(Comparator<Bloat> c) { this.comparator = c; }
}
}
class BloatProducer
{
final private List<Bloat> bloatList = new ArrayList<Bloat>();
final private Random random = new Random();
public void produceMoreBloat()
{
int n = bloatList.size();
Bloat newBloat =
(n == 0) ? new Bloat() : bloatList.get(n-1).moreBloat(random);
bloatList.add(newBloat);
}
/* other fields/methods */
public boolean testMonotonicity()
{
Bloat previousBloat = null;
for (Bloat thisBloat : bloatList)
{
if (previousBloat != null)
{
if ((previousBloat.timeInMilliseconds
>= thisBloat.timeInMilliseconds)
|| (previousBloat.spaceInBytes
>= thisBloat.spaceInBytes)
|| (previousBloat.costInPennies
>= thisBloat.costInPennies))
return false;
}
previousBloat = thisBloat;
}
return true;
}
public int searchBy(Bloat.Type t, Bloat key)
{
return Collections.binarySearch(bloatList, key, t.comparator);
}
public void showSearch(Bloat.Type t, Bloat key)
{
System.out.println("Search by "+t+": ");
System.out.println(key);
int i = searchBy(t,key);
if (i >= 0)
{
System.out.println("matches");
System.out.println(bloatList.get(i));
}
else
{
System.out.println("is between");
i = -i-1;
Bloat b1 = (i == 0) ? null : bloatList.get(i-1);
System.out.println(b1);
Bloat b2 = (i >= bloatList.size()) ? null : bloatList.get(i);
System.out.println("and");
System.out.println(b2);
}
}
}
public class MultiBinarySearch {
private static int N = 1000;
public static void main(String[] args)
{
BloatProducer bloatProducer = new BloatProducer();
for (int i = 0; i < N; ++i)
{
bloatProducer.produceMoreBloat();
}
System.out.println("testMonotonicity() returns "+
bloatProducer.testMonotonicity());
Bloat key;
key = new Bloat(10*N, 20*N, 30*N);
bloatProducer.showSearch(Bloat.Type.COST, key);
bloatProducer.showSearch(Bloat.Type.SPACE, key);
bloatProducer.showSearch(Bloat.Type.TIME, key);
key = new Bloat(-10000, 0, 1000*N);
bloatProducer.showSearch(Bloat.Type.COST, key);
bloatProducer.showSearch(Bloat.Type.SPACE, key);
bloatProducer.showSearch(Bloat.Type.TIME, key);
}
}