代码之家 › 专栏 › 技术社区 › levant pied

带密钥提取器的二进制搜索Java列表

java

levant pied · 技术社区 · 6 年前

假设我有:

class Item {
   int id;
   int type;
}

我可以这样做:

List<Item> items;
Item itemToFind;
Comparator<Item> itemComparator;
Collections.binarySearch(items, itemToFind, itemComparator);

type 对于上面的例子。假设列表是按该属性排序的,那么Java中是否有一个标准方法或某个已建立的库可以做到这一点:

List<Item> items;
Function<Item, Integer> typeExtractor = Item::getType;
int typeToFind;
Comparator<Integer> typeComparator = Integer::compare;
binarySearch(items, typeExtractor, typeToFind, typeComparator);

没有额外的开销(例如转换 List<Item> 到 List<Integer> 打电话 Collections.binarySearch

2 回复 | 直到 6 年前

Ervin Szilagyi 6 年前

你的问题是 Collection<T> java的二进制搜索实现只允许搜索类型为的项 T . 为了搜索另一个类型 T

把另一种包装在里面 ,在您的情况下,应该如下所示:

List<Item> items;
int typeToFind;

Item itemToFind = new Item(/* random value for id */ 0, typeToFind);
int index = binarySearch(items, itemToFind , (a, b) -> a.getType() - b.getType());

此处需要添加一些重要注意事项:

-项目的比较应该只依赖于并且只能依赖于“类型”,否则可能会导致一些讨厌的错误;

-项目列表应进行排序。排序应该只依赖于并且只依赖于“type”(基本上使用与以前相同的比较器)

List<Items> items;
int typeToFind

int index = binarySearch(items.stream.map(item -> item.getType()).collect(Collectors.toList()), itemToFind);

Juan 6 年前

比较器仍然是 Comparator<Item> . 您要更改的是comparator的实现,以根据类型而不是id进行计算。

Comparator<Item> comparator = new Comparator<Item>(){
    public int compare(Item a, Item b) 
    { 
        return a.getType() - b.getType(); 
    } 
}

项,则需要将类型的getter或属性公开。如果使用id也是一样。

不过,不知道你建议我怎么打电话

Item itemToFind = new Item();
itemToFind.setType(typeToFind);
Collections.binarySearch(items, itemToFind, comparator );

经过一番思考:

Item Comparator 项目 还有针具。

返回int值的接口:

 public interface Intgettable{
     public int getInt();
 }

必须实现此接口:

public class Item implements Intgettable{
     private int id;
     private int type;

     public void setId(int id){ 
         this.id = id;
     }
     public void setType(int type){ 
         this.type = type;
     }
     public int getId(){
         return id;
     }
     public int getType(){
         return type;
     }
     public int getInt(){
         return type;
     }
 }

搜索的关键是 Intgettable

1-使用扩展的类 .

public static class MyItemKey implements Intgettable{
     private int value;

     public MyItemKey(int v){
         this.value = v;
     }

     @Override
     public int getInt(){
         return value;
     }
}

MyItemKey typeToFind = new MyItemKey(6);

Intgettable typeTofind = new Intgettable(){
        private int value = 6;
        public int getInt(){
            return value;
        }
};

3-或使用lambda版本:

Intgettable typeTofind = ()->{return 6;};

比较器 将:

Comparator<Intgettable> comparator = new Comparator<Intgettable>(){
        public int compare(Intgettable a, Intgettable b){
            return a.getInt() - b.getInt();
        }
};

最后在二进制搜索中使用它:

Collections.binarySearch(items, typeToFind, comparator );