论坛首页 Java企业应用论坛

写了个递归算法,欢迎大家来拍砖

浏览 2388 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2011-10-12  
	/**
	 * 一个递归算法,将一个PropertyDO(地域)的列表merge成一个PropertyDO
	 * @author hemaodong
	 * @param propertyDO1
	 * @param propertyDO2
	 * @return propertyDO1
	 */
	private static PropertyDO mergeArea(List<PropertyDO> propertyDOs) {

		if (null != propertyDOs && propertyDOs.size() == 1) {
			return propertyDOs.get(0);
		}
		int i = propertyDOs.size();
		PropertyDO propertyDO1 = propertyDOs.get(i-2);
		PropertyDO propertyDO2 = propertyDOs.get(i-1);
		// 将propertyDO2转化成MAP,便于检索,如果propertyDO2中存在propertyDO1的值,
		// 则将propertyDO2中的该值移除,若循环检索完后propertyDO2中还有值,则将
		// propertyDO2中的值循环添加至propertyDO1中并返回,至此就完成了地域的merge
		Map<Long, EnumDO> map = convert2Map(propertyDO2);

		for (EnumDO enumDO : propertyDO1.getValuesAsList()) {
			if (null != map.get(enumDO.getId())) {
				map.remove(enumDO.getId());
			}
		}

		if (map != null && map.size() != 0) {
			for (Long key : map.keySet()) {
				propertyDO1.getValuesAsList().add(map.get(key));
			}
		}
		PropertyDO temp = propertyDO1;
		propertyDOs.remove(propertyDO1);
		propertyDOs.remove(propertyDO2);
		propertyDOs.add(temp);
		mergeArea(propertyDOs);
		return propertyDOs.get(0);
	}

	/**
	 * @author hemaodong
	 * @param propertyDO2
	 * @return
	 */
	private static Map<Long, EnumDO> convert2Map(PropertyDO propertyDO) {
		Map<Long, EnumDO> map = new HashMap<Long, EnumDO>();
		for (EnumDO enumDO : propertyDO.getValuesAsList()) {
			map.put(enumDO.getId(), enumDO);
		}
		return map;
	}

	@SuppressWarnings("serial")
	public static void main(String args[]) {

		final PropertyDO do1 = new PropertyDO();
		List<EnumDO> enumDOlist1 = new ArrayList<EnumDO>(){
			{
				EnumDO enumDO1 = new EnumDO(1l, "1");
				EnumDO enumDO2 = new EnumDO(2l, "2");
				EnumDO enumDO3 = new EnumDO(3l, "3");
				add(enumDO1);
				add(enumDO2);
				add(enumDO3);
			}
		};
		do1.setValuesAsList(enumDOlist1);

		final PropertyDO do2 = new PropertyDO();
		List<EnumDO> enumDOlist2 = new ArrayList<EnumDO>(){
			{
				EnumDO enumDO3 = new EnumDO(3l, "3");
				EnumDO enumDO4 = new EnumDO(4l, "4");
				EnumDO enumDO5 = new EnumDO(5l, "5");
				add(enumDO3);
				add(enumDO4);
				add(enumDO5);
			}
		};
		do2.setValuesAsList(enumDOlist2);

		final PropertyDO do3 = new PropertyDO();
		List<EnumDO> enumDOlist3 = new ArrayList<EnumDO>(){
			{
				EnumDO enumDO3 = new EnumDO(3l, "3");
				EnumDO enumDO4 = new EnumDO(4l, "4");
				EnumDO enumDO5 = new EnumDO(5l, "5");
				add(enumDO3);
				add(enumDO4);
				add(enumDO5);
			}
		};
		do3.setValuesAsList(enumDOlist3);

		final PropertyDO do4 = new PropertyDO();
		List<EnumDO> enumDOlist4 = new ArrayList<EnumDO>(){
			{
				EnumDO enumDO3 = new EnumDO(7l, "7");
				EnumDO enumDO4 = new EnumDO(8l, "8");
				EnumDO enumDO5 = new EnumDO(9l, "9");
				add(enumDO3);
				add(enumDO4);
				add(enumDO5);
			}
		};
		do4.setValuesAsList(enumDOlist4);
		List<PropertyDO> propertyDOs = new ArrayList<PropertyDO>(){
			{
				add(do1);
				add(do2);
				add(do3);
				add(do4);
			}
		};
		System.out.println(mergeArea(propertyDOs).getValuesAsList().size());
	}

 欢迎大家提供更好的算法

   发表时间:2011-10-13  
不推荐使用递归,不太容易懂。
以下是我的代码,我不知道你的EnumDO和PropertyDO是什么样的。
我只是根据调用的方法建立一个简单的数据类。
package model.test;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TEST {
	/**
	 * 不使用递归以减少内存开销,亦使得程序易于理解
	 */
	private static PropertyDO mergeArea(List<PropertyDO> propertyDOs) {
		if (null == propertyDOs)
			return null;// 判断数组是否为空,你原先的判断是有漏洞的。
		// 使用map来去重。
		Map<Long, EnumDO> enumDOs = new HashMap<Long, EnumDO>();
		for (PropertyDO propertyDO : propertyDOs) {
			for (EnumDO enumDO : propertyDO.getValuesAsList()) {
				enumDOs.put(enumDO.getId(), enumDO);
			}
		}
		return new PropertyDO(enumDOs.values());
	}

	@SuppressWarnings("serial")
	public static void main(String args[]) {
		final PropertyDO do1 = new PropertyDO(new ArrayList<EnumDO>() {
			{
				add(new EnumDO(1l, "1"));
				add(new EnumDO(2l, "2"));
				add(new EnumDO(3l, "3"));
			}
		});
		final PropertyDO do2 = new PropertyDO(new ArrayList<EnumDO>() {
			{
				add(new EnumDO(3l, "3"));
				add(new EnumDO(4l, "4"));
				add(new EnumDO(5l, "5"));
			}
		});
		final PropertyDO do3 = new PropertyDO(new ArrayList<EnumDO>() {
			{
				add(new EnumDO(3l, "3"));
				add(new EnumDO(4l, "4"));
				add(new EnumDO(5l, "5"));
			}
		});
		final PropertyDO do4 = new PropertyDO(new ArrayList<EnumDO>() {
			{
				add(new EnumDO(7l, "7"));
				add(new EnumDO(8l, "8"));
				add(new EnumDO(9l, "9"));
			}
		});
		List<PropertyDO> propertyDOs = new ArrayList<PropertyDO>();
		Collections.addAll(propertyDOs, do1,do2,do3,do4);
		System.out.println(mergeArea(propertyDOs).getValuesAsList().size());
	}
}

class EnumDO {
	long id;
	String name;

	public EnumDO(long l, String string) {
		this.id = l;
		this.name = string;
	}

	public Long getId() {
		return this.id;
	}
}

class PropertyDO {
	List<EnumDO> list;

	public PropertyDO(Collection<EnumDO> enumDOs) {
		this.list = new ArrayList<EnumDO>(enumDOs);
	}

	public List<EnumDO> getValuesAsList() {
		return list;
	}
}
0 请登录后投票
   发表时间:2011-10-14   最后修改:2011-10-14
给你做个code review。。。

1.
private static PropertyDO mergeArea(List<PropertyDO> propertyDOs) {  
  
    if (null != propertyDOs && propertyDOs.size() == 1) {  
        return propertyDOs.get(0);  
    }
    。。。
    mergeArea(propertyDOs);  
    return propertyDOs.get(0);  
}  

最后两行明明就可以直接写成
    return mergeArea(propertyDOs);

然后一眼就看出是个尾递归。尾递归通常都能很方便地转换为使用循环的非递归实现,有些语言都能自动帮你优化,不过java不行,所以其实应该尽量用改用循环实现。

2. 既然你有
null != propertyDOs && propertyDOs.size() == 1

这样的判断,说明你认为propertyDOs可能为null。然后你跟着就来一行
int i = propertyDOs.size();  

这里直接就抛NPE了。

3. 这个convert2Map是个私有方法,对于当前的类来说是可控代码。它明明不可能返回null,后面为什么要做非null判断呢。而且foreach循环(或者下面第4点的修改)已经处理了map.size()==0的情况,所以 if (map != null && map.size() != 0) 这个判断纯属多余。

4.
        for (Long key : map.keySet()) {  
            propertyDO1.getValuesAsList().add(map.get(key));  
        }  

为什么不
for (EnumDO v : map.values()) {
    ...add(v);
}

或者直接
propertyDO1.getValuesAsList().addAll(map.values());


5. 你明明已经拿着propertyDO1的引用,干嘛要先把它赋值给temp,List.remove又不会干掉这个propertyDO1。
0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics