列表中列表的查找算法優於O（n2）複雜性

Question

我正在使用java 1.6。 我有一組項目，每個項目都有一個名稱和一組組件。每個組件也有一個名稱。

Set<Item> 

Class Item 
    String name 
    Set<Component> 

Class Component 
    String name 

我現在的任務是編寫一個輸入：項目名稱+組件名稱和輸出的方法：該對是否存在於項目列表中。

public boolean hasItemComponentPair(String itemName, String componentName) 
{ 
    for(Item item : getItems()) 
    { 
     if (item.getName() == itemName) 
     { 
      for(Component component : item.getComponents()) 
      { 
       if (component.getName() == componentName) 
       { 
        return true; 
       } 
      } 
     } 
    } 

    return false; 
} 

最簡單的方法是簡單地逐個查看集合中的元素，如果找到匹配則斷開。這種方法適用於小集合。

我的物品組通常在5到20個物品之間，並且組件集合大致相同。所以有25到400個獨特的項目組件對。這種數量的配對似乎太大，以至於天真算法效率不高，特別是如果該方法被多次調用。但是我也認爲分而治之的技巧對於給定數量的元素來說太冗長了。

對於這個問題，通常使用哪些數據結構和算法，記住給定集的大小？

Answer 1

如果你可以改變你的項目類，你可以那樣做：

class Item { 
    String name; 
    Map<String, Component> components; 
} 

在上面鍵映射爲組件的名稱。

比你的代碼更改爲：

public boolean hasItemComponentPair(String itemName, String componentName) 
{ 
    for(Item item : getItems()) 
    { 
     if (item.getName().equals(itemName)) 
     { 
      return item.getComponents().containsKey(componentName); 
     } 
    } 

    return false; 
} 

現在你需要遍歷只有一個集合。

Answer 2

1）對列表進行排序並對其進行二分搜索。

2）建立索引（通常作爲散列表）。

Answer 3

覆蓋在你的項目的equals和hashCode方法和組件類，如下列：

// Item.java 
import java.util.Set; 

public class Item 
{ 
    private String name; 
    private Set<Component> components; 

    public Item(String name) 
    { 
    this.name = name; 
    } 

    @Override 
    public int hashCode() 
    { 
    return name.hashCode(); 
    } 

    @Override 
    public boolean equals(Object obj) 
    { 
    if (obj instanceof Item) 
    { 
     Item item = (Item) obj; 
     if (item.name != null && this.name != null) 
     return item.name.equals(this.name); 
    } 
    return false; 
    } 

    public Set<Component> getComponents() 
    { 
    return components; 
    } 

    public void setComponents(Set<Component> components) 
    { 
    this.components = components; 
    } 
} 

// Component.java 
public class Component 
{ 
    private String name; 

    public Component(String name) 
    { 
    this.name = name; 
    } 

    @Override 
    public int hashCode() 
    { 
    return name.hashCode(); 
    } 

    @Override 
    public boolean equals(Object obj) 
    { 
    if (obj instanceof Component) 
    { 
     Component component = (Component) obj; 
     if (component.name != null && name != null) 
     return component.name.equals(this.name); 
    } 
    return false; 
    } 
} 

這會給你一定的時間查找。所以你可以在固定的時間搜索元素。

以下是一個演示：

import java.util.HashSet; 

public class SearchDemo 
{ 
    public static void main(String[] args) 
    { 
    Item item1 = new Item("Item 1"); 
    item1.setComponents(new HashSet<Component>()); 
    item1.getComponents().add(new Component("Component A")); 
    item1.getComponents().add(new Component("Component B")); 
    item1.getComponents().add(new Component("Component C")); 

    Item item2 = new Item("Item 2"); 
    item2.setComponents(new HashSet<Component>()); 
    item2.getComponents().add(new Component("Component X")); 
    item2.getComponents().add(new Component("Component Y")); 
    item2.getComponents().add(new Component("Component Z")); 

    HashSet<Item> items = new HashSet<>(); 
    items.add(item1); 
    items.add(item2); 

    // Input from user 
    String inputItem = "Item 2"; 
    String inputComponent = "Component Y"; 

    // Cast it to item and component 
    Item searchItem = new Item(inputItem); 
    Component searchComponent = new Component(inputComponent); 

    if (items.contains(searchItem)) // Constant time search 
    { 
     System.out.println("Contains Item"); 
     for (Item item : items) 
     { 
     if (item.equals(searchItem)) 
     { 
      if (item.getComponents().contains(searchComponent)) // Constant time search 
      { 
      System.out.println("Contains even the component"); 
      } 
     } 
     } 
    } 
    } 
} 

唯一的問題是在上面查找循環。 可以在固定時間內搜索該項目，但必須在該集合中再次搜索該項目（如果它確實存在），因爲我有點愚蠢地認爲該程序相信searchItem等於該集合中的item。一旦該物品被真正找到並且其組件組被提取出來，它就會持續搜索componentItem。 如果您在Item類有Component個HashMap，而不是Set，並在每個HashMap關鍵是component的name，然後從用戶的輸入可以搜索在一定的時間！