搜索数组中的数据(列表)

Question

我有一个ArrayList包含Attributes

class Attribute{
  private int id;
  public string getID(){
    return this.id;
  }

  private string value;
  public string getValue(){
    return this.value;
  }

  //... more properties here...
}

好吧,我用数百个属性填充了ArrayList.我想找到具有已定义ID的属性.我想做这样的事情:

ArrayList<Attribute> arr = new ArrayList<Attribute>();
fillList(arr); //Method that puts a lot of these Attributes in the list
arr.find(234); //Find the attribute with the ID 234;

循环遍历ArrayList是唯一的解决方案.

Answer 1

好吧,有些东西必须循环遍历数组列表,是的.有各种方法可以做到这一点,不同的图书馆等.

如果以有序的方式填充数组(例如,低ID始终位于高ID之前),则可以在O(log N)时间内执行二进制搜索.否则,它将是O(N).

但是,如果你要通过ID进行大量搜索,为什么不创建一个Map<Integer, Attribute>开始 - 例如a HashMap,或者LinkedHashMap如果你想保留排序？

但是,如果你只是要搜索一个ID(或几个),那么这几乎肯定是不值得的 - 毕竟哈希有成本; 填充地图将比填充列表更昂贵,并且差异可能大于查找几个ID所节省的时间.

您是否已经确定这是性能瓶颈？如果是这样,通过使用地图(或只是带有二分搜索的排序列表),这是一个容易改进的地方.如果没有,我不会打扰你的代码,如果它更自然地使用列表而不是地图 - 但你当然应该检查它是否是一个瓶颈.