lotusyu
- 浏览: 34344 次
- 性别:
- 来自: 杭州
-
最新评论
-
hemowolf：
FEL(表达式语言)0.7版本发布（没有最快，只有更快） -
attend：
不好意思，看错了。 if (r < size & ...
堆结构的java实现 -
attend：
private void heapify(int i, ...
堆结构的java实现
文章列表
0.7版本更新：
1：加入取数组(array[i])和集合值(list[i]、set[i])的功能，并且支持多维数组和多维集合。
2：加入设置变量类型的功能。
3：调整FelContext接口，加入getVar和setVar方法。
3：优化语法分析功能。
4：对数值型的变量生成的编译代码进行调整。
参见：http://code.google.com/p/fast-el/
此版本主要觖负号和减号冲突的问题
需求：
1：对一个大数组进行求和。
2：需要使用多线程实现。
思路：
1：将大数组根据线程的数量进行拆分。
2：每个线程对数组的部分元素进行求和。
3：等待所有线程执行完毕，返回结果。
说明：
在论坛中看到有一个帖子是使用concurrent包实现的，我这个例子没有使用concurrent包，发现也挺简单。
代码如下所示：
/**
* 多线程求和
* @author Administrator
*
*/
public class ThreadsSum {
static public long sum(final int[] array) {
if (ar ...
Fel是轻量级的高效的表达式计算引擎。
Fel在源自于企业项目，设计目标是为了满足不断变化的功能需求和性能需求。
Fel是开放的，引擎执行中的多个模块都可以扩展或替换。Fel的执行主要是通过函数实现,运算符(+、-等都是Fel函数），所有这些函数都是可以替换的，扩展函数也非常简单。
Fel有双引擎，同时支持解释执行和编译执行。可以根据性能要求选择执行方式。编译执行就是将表达式编译成字节码（生成java代码和编译模块都是可以扩展和替换的）
Fel基于Java1.5开发，适用于Java1.5及以上版本。
特点：
易用性：API使用简单，语法简洁，和java语法很相似。
轻量级：整个包 ...
策略模式：定义了一系列的算法，并将每一个算法封装起来，而且使它们还可以相互替换。策略模式让算法独立于使用它的客户而独立变化。
在Fel中，使用的最多就是FelContext。FelContext就是一个策略，引擎执行时依赖于FelContext获取变量。FelContext只是定义了取变量的接口，取变量的策略由子类实现。这样引擎就可以专注于解析执行表达式，与变量相关的都交给FelContext了。
请看类图：
在FelContext中有一个最常用的实现类，就是MapContext。MapContext是使用Map来保存变量，需要时提供给引擎使用。当然也还有很多其他的实现类，如果有需要，也 ...
fast-el是表达式语言，实现简单，效率高，扩展性强。
有兴趣的朋友关注一下，帖子地址：http://www.iteye.com/topic/919382#1919146
合并排序采用了分治法的思路来设计排序算法。
主要步骤：
1：分解数组
2：排序子数组
3：合并排序好的子数组
其代码如下：
public interface Sort<T> {
/**
* 返回排序后的数组
* @return
*/
public T[] sort(T[] array);
}
import java.util.Arrays;
import java.util.Comparator;
public abstract class AbstractSort<T> implements Sort< ...
插入排序好比抓牌，一副牌是待排序的数组，拿一张牌，跟手里的牌从右到左一张张比较，插入到合适的位置。
优点：适应小数据量排序，空间消耗小。
缺点：当数据量比较大时，排序效率不高。
代码结构：
Sort:排序接口
AbstractSort：排序抽象类
InsertSort:排序算法。
Sort:
public interface Sort<T> {
/**
* 返回排序后的数组
* @return
*/
public T[] sort(T[] array);
public T[] sort();
}
AbstractSort:
...
通过统计元素的个数来达到排序的目的。
优点：
不需要对元素比较就能对元素进行排序（这个想法很巧妙）。
缺点：
1：只能对自然数进行排序。
2：自然数的数值不能太大（排序过程中需要创建一个计数数组，其长度要不能小于数组中的最大值）
实现代码：
import java.lang.reflect.Array;
public class CountSort<T extends Number> {
private T[] array;
public CountSort(T[] array) {
this.array = array;
}
publi ...
快速排序算法的思想来自于分治法（我的理解就是大事化小，小事化了）。
优点：速度快，内存占用小。
缺点：对于有序数组，耗时比较长（稳定性不够好）
实现步骤：
1：找出数组的最后位置的值（mid），不大于mid的，排在数组的前面，mid排在中间，比mid大的排在mid的后面（对应partition方法，返回mid的索引位置）。
2：将mid的前半部分做为子数组，递归调用步骤1；将mid的后半部分做为子数组，递归调用步骤1
实现代码：
import java.util.Comparator;
public class QuickSort<T> {
private T[] a ...
topn指的是从已经存在的数组中，找出最大（或最小）的前n个元素。
topn算法实现思路（找最大的n个元素）
1：取出数组的前n个元素，创建长度为n的最小堆。
2：从n开始循环数组的剩余元素，如果元素(a)比最小堆的根节点大，将a设置成最小堆的根节点，并让堆保持最小堆的特性。
3：循环完成后，最小堆中的所有元素就是需要找的最大的n个元素。
代码如下：
import java.util.Comparator;
/**
* 堆数据结构应用实例
*
* @author Administrator
*
*/
public class HeapApp {
pub ...
闲时写了一个heap的数据结构，支持最大堆，最小堆。
import java.util.Comparator;
/**
* 堆数据结构
*
* @author Administrator
*
*/
public class Heap<T> {
/**
* 以数组形式存储堆元素
*/
private T[] heap;
/**
* 用于比较堆中的元素。c.compare(根,叶子) > 0。
* 使用相反的Comparator可以创建最大堆、最小堆。
*/
private Compar ...
转自http://topic.csdn.net/u/20110518/09/6021fd63-3084-4fda-a4b6-da2fe58de367.html?seed=1655503227&r=73523235#r_73523235
对原贴的代码进行整理并做一些修改
import java.util.Comparator;
/**
* 将堆调整成最大堆
*
* @author Administrator
*
*/
public class Heap {
/**
* 返回值为i/2
* @param i
* @return
...
Fel使用说明
1:Fel简介
Fel是简单的、高效的、易扩展的开源项目，使用java开发的开源项目。
简单性：语法简单，与java表达式类似，支持中文变量和函数。其实现原理也非常简单，只要稍微有一些java基础就可以看懂源码。
高效性：不会比开源的脚本引擎慢。一些高级应用还可以大大高于其他脚本引擎。
易扩展：在执行表达式的主要环节（解析表达式、函数管理、操作符重载、引擎上下文、节点解释器）都有很高的可定制性。
Fel设计目标是面向最终用户和二次开发用户。它是功能灵活的、可以轻易掌控的和可定制的表达式语言。
2:快速入门
获取Fel
项目地 ...