Эффективная сортировка деревьев

Question

Я не очень доволен своими методами построения древовидной структуры в моем приложении J2ME. Кто-нибудь может указать в более производительном направлении? Если вам нужно больше кода, чтобы понять мои фрагменты, просто прокомментируйте ниже. Версия Java 1.4.

Большое спасибо,
Rayt

if(companyList != null) {
    companyList.setNodeStructure(null);

    Hashtable nodes = new Hashtable();
    for(Enumeration e = companyList.elements(); e.hasMoreElements();) {
        Company temp_comp = (Company)e.nextElement();
        if(temp_comp.getParentCompanyId() == 0 && temp_comp.getCompanyId() > 0) {
            getSubTree(temp_comp.getCompanyId(), companyList, nodes); 
        }
    }   
    companyList.setNodeStructure(nodes);

Методы

private void getSubTree(int CompanyId, CompanyList _companyList, Hashtable nodes) {
    Vector children = getChildren(CompanyId, _companyList);
    if(children.size() > 0) {
        nodes.put(new Integer(CompanyId), children);
        for(Enumeration e = children.elements(); e.hasMoreElements();) {
            Company temp_comp = (Company)e.nextElement();
            getSubTree(temp_comp.getCompanyId(), _companyList, nodes);
        }
    }
}

private Vector getChildren(int CompanyId, CompanyList _companyList) {
    Vector temp = new Vector();
    for(Enumeration e = _companyList.elements(); e.hasMoreElements();) {
        Company temp_comp = (Company)e.nextElement();
            if(temp_comp.getParentCompanyId() == CompanyId) {
                temp.addElement(temp_comp);
            }
        }
    temp.trimToSize();
    return temp;
}

Answer 1

getChildren () может быть гораздо более эффективным. Похоже, что каждый раз, когда вы вызываете его, вы перебираете весь CompanyList, чтобы найти тех, чей родитель соответствует указанному CompanyId. Это просто кричит о Hashtable, заполненном векторами. Ключами Hashtable будут родительский идентификатор, а не исходный идентификатор; значениями будут векторы, которые содержат компанию, чей родительский идентификатор соответствует данному родительскому идентификатору Тогда у вас есть:

private Vector getChildren(int CompanyId, Hashtable companyParentLoookup) {
    return (Vector) companyParentLookup.get(CompanyId);
}

Конечно, похоже, что ваша цель при написании getSubTree - создать Hashtable, который я только что описал. Проблема здесь в том, что вы пытаетесь создать его по идентификатору компании, а не по компании. Вы можете попробовать это вместо этого, чтобы построить companyParentLookup:

private Hashtable calcLookupTable(CompanyList _companyList) {
    Hashtable retval = new Hashtable();
    for (Enumeration e = _companyList.elements(); e.hasMoreElements();) {
        Company temp_comp = (Company) e.nextElement();
        Integer parent_id = temp_comp.getParentCompanyID();

        if (retval.containsKey(parent_id) == false) {
            retval.put(parent_id, new Vector());
        }
        retval.get(parent_id).add(temp_comp);
    }
    return retval;
}

После этого вы можете вставить структуру companyParentLookup непосредственно в nodeLuctru.comList.

РЕДАКТИРОВАТЬ: Важным моментом здесь является то, что вы можете лениво инициализировать векторные записи Hashtable по мере необходимости; каждый раз, когда вы можете просто проверить, есть ли в Hashtable нужная запись, а если нет, просто добавьте ее. Это то, что позволяет создавать Hashtable, итерируя компании как дети, а не как их родители , Если вы действительно не можете использовать ничего, кроме Hashtables и Vectors, то это не плохой способ реализовать дерево; это примерно эквивалентно сохранению структуры данных графа с использованием списков смежности. На самом деле я написал что-то очень похожее на структуру данных графа, хотя и с HashMaps.

Э-э, это помогает?