Friday, 27 April 2007
hashtable
Hashtables(哈希表)在计算机领域中已不是一个新概念了。它们是用来加快计算机的处理速度的,用当今的标准来处理,速度非常慢,而它们可以让你在查询许多数据条目时,很快地找到一个特殊的条目。尽管现代的机器速度已快了几千倍,但是为了得到应用程序的最佳性能,hashtables仍然是个很有用的方法。
设想一下,你有一个包含约一千条记录的数据文件,比如一个小企业的客户记录,还有一个程序,它把记录读到内存中进行处理。每个记录包含一个唯一的五位数的客户ID号、客户名字、地址、帐户结余等等。假设记录不是按客户ID号顺序分类的,所以,如果程序要将客户ID号作为“key” 来查找一个特殊的客户记录,唯一的查找方法就是连续地搜索每个记录。有时侯,它会很快找到你需要的记录;但有时侯,在程序找到你需要的记录前,它几乎已搜索到了最后一条记录。如果要在1,000条记录中搜索,那么查找任何一条记录都需要程序平均查核500.5 ((1000 + 1 )/2)条记录。如果你常需要查找数据,你应该需要一个更快的方法来找到一条记录。
一种加快搜索的方法就是把记录分成几段,这样,你就不用搜索一个很大的列表了,而是搜索几个短的列表。对于我们数字式的客户ID号,你可以建10个列表,以0开头的ID号组成一个列表,以1开头的ID号组成一个列表,依此类推。那么要查找客户ID号38016,你只需要搜索以3开头的列表就行了。如果有1,000条记录,每个列表的平均长度为100(1,000条记录被分成10个列表),那么搜索一条记录的平均比较次数就降到了约50(见图1)。
当然,如果约十分之一的客户号是以0开头的,另外十分之一是以1开头的,等等,那么这种方法会很适合。如果90%的客户号以0开头,那么那个列表就会有900条记录,每次查找平均需要进行450次比较。另外,程序需要执行的搜索有90%都是针对以0开头的号码的。因此,平均比较数就大大超过简单数学运算的范围了。
如果我们可以按这样一种方式在我们的列表中分配记录,情况就会好一些,即每个列表约有相同条目的记录,而不管键值中数字的分布。我们需要一种方法能够把客户号码混合到一起并更好地分布结果。例如,我们可以取号码中的每位数,乘以某个大的数(随着数字位置的不同而不同), 然后将结果相加产生一个总数,把这个数除以10,并将余数作为索引值(index)(除数相同的分到一组)。当读入记录时,程序在客户号码上运行这个哈希(hash) 函数来确定记录属于哪个列表。当用户需要查询时,将同一个哈希函数作为一个“key”用于客户号码,这样就可以搜索正确的列表了。 像这样的一个数据结构就称为一个哈希表(hashtable)。
Java中的Hashtables
Java包含两个类,java.util.Hashtable 和java.util.HashMap,它们提供了一个多种用途的hashtable机制。这两个类很相似,通常提供相同的公有接口。但它们的确有一些重要的不同点,我在后面会讲到。
Hashtable和HashMap对象可以让你把一个key和一个value结合起来,并用put() 方法把这对key/value输入到表中。然后你可以通过调用get()方法,把key作为参数来得到这个value(值)。只要满足两个基本的要求,key和value可以是任何对象。注意,因为key和value必须是对象,所以原始类型(primitive types)必须通过运用诸如Integer(int)的方法转换成对象。
为了将一个特定类的对象用做一个key,这个类必须提供两个方法,equals() 和 hashCode()。这两个方法在java.lang.Object中,所以所有的类都可以继承这两个方法;但是,这两个方法在Object类中的实现一般没什么用,所以你通常需要自己重载这两个方法。Equals()方法把它的对象同另一个对象进行比较,如果这两个对象代表相同的信息,则返回true。该方法也查看并确保这两个对象属于相同的类。如果两个参照对象是完全一样的对象,Object.equals()返回true,这就说明了为什么这个方法通常不是很适合的原因。在大多数情况下,你需要一个方法来一个字段一个字段地进行比较,所以我们认为代表相同数据的不同对象是相等的。
HashCode()方法通过运用对象的内容执行一个哈希函数来生成一个int值。Hashtable和HashMap用这个值来算出一对key/value位于哪个bucket(哈希元)(或列表)中。作为例子,我们可以查看一下String 类,因为它有自己的方法来实现这两个方法。String.equals()对两个String对象一个字符一个字符地进行比较,如果字符串是相同的,则返回true:
String myName = "Einstein";
// The following test is
// always true
if ( myName.equals("Einstein") )
{ ...
String.hashCode()在一个字符串上运行哈希函数。字符串中每个字符的数字代码都乘以31,结果取决于字符串中字符的位置。然后将这些计算的结果相加,得到一个总数。这个过程似乎很复杂,但是它确保能够更好地分布值。它也证明了你在开发你自己的hashCode()方法时,能够走多远,确信结果是唯一的。
例如,假设我要用一个hashtable来实现一个书的目录,把书的ISBN号码作为搜索键来进行搜索。我可以用String类来承载细节,并准备好了equals()和hashCode()方法。我们可以用put()方法添加成对的key/value到hashtable中。
Put()方法接受两个参数,它们都属于Object类型。第一个参数是key;第二个参数是value。Put()方法调用key的hashCode()方法,用表中的列表数来除这个结果。把余数作为索引值来确定该条记录添加到哪个列表中。注意,key在表中是唯一的;如果你用一个已经存在的key来调用put(),匹配的条目就被修改了,因此它参照的是一个新的值,而旧的值被返回了(当key在表中不存在时,put()返回空值)。要读取表中的一个值,我们把搜索键用于get()方法。它返回一个转换到正确类型的Object参照:
BookRecord br =(BookRecord)isbnTable.get("0-345-40946-9");
System.out.println("Author: " + br.author+ " Title: " + br.title);
另一个有用的方法是remove(),其用法同get()几乎一样,它把条目从表中删除,并返回给调用程序。
你自己的类
如果你想把一个原始类型用做一个key,你必须创建一个同等类型的对象。例如,如果你想用一个整数key,你应该用构造器Integer(int)从整数中生成一个对象。所有的封装类如Integer、Float和Boolean都把原始值看做是对象,它们重载了equals()和hashCode()方法,因此,它们可以被用做key。JDK中提供的许多其它的类也是这样的(甚至Hashtable和HashMap类都实现它们自己的equals()和hashCode()方法),但你把任何类的对象用做hashtable keys前,应该查看文件。查看类的来源,看看equals()和hashCode()是如何实现的,也很有必要。例如,Byte、Character、Short和Integer都返回所代表的整数值作为哈希码。这可能适合,也可能不适合你的需求。
如果你想创建一个hashtable,这个hashtable运用你自己定义的一个类的对象作为key,那么你应该确信这个类的equals()和hashCode()方法提供有用的值。首先查看你扩展的类,确定它的实现是否满足你的需求。如果没有,你应该重载方法。
任何equals()方法的基本设计约束是,如果传递给它的对象属于同一个类,而且它的数据字段设定为表示同样数据的值,那么它就应该返回true。你也应该确信,如果传递一个空的参数给该方法,那么你的代码返回false:
public boolean equals(Object o){
if ( (o == null)|| !(o instanceof myClass)){
return false;
}
// Now compare data fields...
另外,在设计一个hashCode()方法时,应该记住一些规则。首先,该方法必须为一个特定的对象返回相同的值,而不管这个方法被调用了多少次(当然,只要对象的内容在调用之间没有改变,在将一个对象用做一个hashtable的key时,应该避免这一点)。第二,如果由你的equals()方法定义的两个对象是相等的,那么它们也必须生成相同的哈希码。第三,这更像是一个方针,而不是一个原则,你应该设法设计方法,使它为不同的对象内容生成不同的结果。如果偶尔不同的对象正好生成了相同的哈希码,这也不要紧。但是,如果该方法只能返回范围在1到10的值,那么只能用10个列表,而不管在hashtable中有多少个列表。
在设计equals()和hashCode()时,另一个要记住的因素是性能问题。每次调用put()或get(),都包括调用hashCode()来查找正确的列表,当get()扫描列表来查找key时,它为列表中的每个元素调用equals()。实现这些方法使它们尽可能快而有效地运行,尤其当你打算使你的类公开可用时,因为其它的用户可能想在执行速度很重要的情况下,在高性能的应用程序中运用你的类。
Hashtable性能
影响hashtable功效的主要因素就是表中列表的平均长度,因为平均搜索时间与这个平均长度直接相关。很显然,要减小平均长度,你必须增加hashtable中列表的数量;如果列表数量非常大,以至于大多数列表或所有列表只包含一条记录,你就会获得最佳的搜索效率。然而,这样做可能太过分了。如果你的hashtable的列表数远远多于数据条目,那你就没有必要做这样的内存花费了,而在一些情况下,人们也不可能接受这样的做法。
在我们前面的例子中,我们预先知道我们有多少条记录1,000。知道这点后,我们就可以决定我们的hashtable应该包含多少个列表,以便达成搜索速度和内存使用效率之间最好的折衷方式。然而,在许多情况下,你预先不知道你要处理多少条记录;数据被读取的文件可能会不断扩大,或者记录的数量可能一天一天地发生很大的变化。
随着条目的增加,Hashtable和HashMap类通过动态地扩展表来处理这个问题。这两个类都有接受表中列表最初数量的构造器,和一个作为参数的负载系数(load factor):
public Hashtable(int initialCapacity,float loadFactor)
public HashMap(int initialCapacity,float loadFactor)
将这两个数相乘计算出一个临界值。每次给哈希表添加一个新的条目时,计数就被更新,当计数超过临界值时,表被重新设置(rehash)。(列表数量增加到以前数量的两倍加1,所有的条目转移到正确的列表中。)缺省的构造器设定最初的容量为11,负载系数是0.75,所以临界值是8。当第九条记录被添加到表中时,就重新调整哈希表,使其有23个列表,新的临界值将是17(23*0.75的整数部分)。你可以看到,负载系数是哈希表中平均列表数量的上限,这就意味着,在缺省情况下,哈希表很少会有许多包含不只一条记录的列表。比较我们最初的例子,在那个例子中,我们有1,000条记录,分布在10个列表中。如果我们用缺省值,这个表将会扩展到含有1,500多个列表。但你可以控制这点。如果用负载系数相乘的列表数量大于你处理的条目数,那么表永远不会重制,所以我们可以仿效下面的例子:// Table will not rehash until it
// has 1,100 entries (10*110):
Hashtable myHashTable = new Hashtable(10, 110.0F);
你可能不想这么做,除非你没有为空的列表节省内存,而且不介意额外的搜索时间,这可能在嵌入系统中会出现这种情况。然而,这种方法可能很有用,因为重新设置很占用计算时间,而这种方法可以保证永远不会发生重新设置这种情况。注意,虽然调用put()可以使表增大(列表数量增加),调用remove()不会有相反的结果。所以,如果你有一个大的表,而且从中删除了大部分条目,结果你会有一个大的但是大部分是空的表。
Hashtable和HashMap
Hashtable和HashMap类有三个重要的不同之处。第一个不同主要是历史原因。Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现。
也许最重要的不同是Hashtable的方法是同步的,而HashMapu方法不是。这就意味着,虽然你可以不用采取任何特殊的行为就可以在一个多线程的应用程序中用一个Hashtable,但你必须同样地为一个HashMap提供外同步。一个方便的方法就是利用Collections类的静态的synchronizedMap()方法,它创建一个线程安全的Map对象,并把它作为一个封装的对象来返回。这个对象的方法可以让你同步访问潜在的HashMap。这么做的结果就是当你不需要同步时,你不能切断Hashtable中的同步(比如在一个单线程的应用程序中),而且同步增加了很多处理费用。第三点不同是,只有HashMap可以让你将空值作为一个表的条目的key或value。HashMap中只有一条记录可以是一个空的key,但任意数量的条目可以是空的value。这就是说,如果在表中没有发现搜索键,或者如果发现了搜索键,但它是一个空的值,那么get()将返回null。如果有必要,用containKey()方法来区别这两种情况。
一些资料建议,当需要同步时,用Hashtable,反之用HashMap。但是,因为在需要时,HashMap可以被同步,HashMap的功能比Hashtable的功能更多,而且它不是基于一个陈旧的类的,所以有人认为,在各种情况下,HashMap都优先于Hashtable。
关于Properties
有时侯,你可能想用一个hashtable来映射key的字符串到value的字符串。DOS、Windows和Unix中的环境字符串就有一些例子,如key的字符串PATH被映射到value的字符串C:\WINDOWS;C:\WINDOWS\SYSTEM。Hashtables是表示这些的一个简单的方法,但Java提供了另外一种方法。
Java.util.Properties类是Hashtable的一个子类,设计用于String keys和values。Properties对象的用法同Hashtable的用法相象,但是类增加了两个节省时间的方法,你应该知道。Store()方法把一个Properties对象的内容以一种可读的形式保存到一个文件中。Load()方法正好相反,用来读取文件,并设定Properties对象来包含keys和values。注意,因为Properties扩展了Hashtable,你可以用超类的put()方法来添加不是String对象的keys和values。这是不可取的。另外,如果你将store()用于一个不包含String对象的Properties对象,store()将失败。作为put()和get()的替代,你应该用setProperty()和getProperty(),它们用String参数。好了,我希望你现在可以知道如何用hashtables来加速你的处理了。
关于作者:
Pete Ford已经做了20多年的软件开发工作了,他主要在嵌入系统和turnkey system方面进行研究。他生活并工作于德克萨斯州的达拉斯。你可以通过p_ford@mindspring.com联系他
哈希表是一种重要的存储方式,也是一种常见的检索方法。其基本思想是将关系码的值作为自变量,通过一定的函数关系计算出对应的函数值,把这个数值解释为结点的存储地址,将结点存入计算得到存储地址所对应的存储单元。检索时采用检索关键码的方法。现在哈希表有一套完整的算法来进行插入、删除和解决冲突。在Java中哈希表用于存储对象,实现快速检索。
Java.util.Hashtable提供了种方法让用户使用哈希表,而不需要考虑其哈希表真正如何工作。
哈希表类中提供了三种构造方法,分别是:
public Hashtable()
public Hashtable(int initialcapacity)
public Hashtable(int initialCapacity,float loadFactor)
参数initialCapacity是Hashtable的初始容量,它的值应大于0。loadFactor又称装载因子,是一个0.0到0.1之间的float型的浮点数。它是一个百分比,表明了哈希表何时需要扩充,例如,有一哈希表,容量为100,而装载因子为0.9,那么当哈希表90%的容量已被使用时,此哈希表会自动扩充成一个更大的哈希表。如果用户不赋这些参数,系统会自动进行处理,而不需要用户操心。
Hashtable提供了基本的插入、检索等方法。
■插入
public synchronized void put(Object key,Object value)
给对象value设定一关键字key,并将其加到Hashtable中。若此关键字已经存在,则将此关键字对应的旧对象更新为新的对象Value。这表明在哈希表中相同的关键字不可能对应不同的对象(从哈希表的基本思想来看,这也是显而易见的)。
■检索
public synchronized Object get(Object key)
根据给定关键字key获取相对应的对象。
public synchronized boolean containsKey(Object key)
判断哈希表中是否包含关键字key。
public synchronized boolean contains(Object value)
判断value是否是哈希表中的一个元素。
■删除
public synchronized object remove(object key)
从哈希表中删除关键字key所对应的对象。
public synchronized void clear()
清除哈希表
另外,Hashtalbe还提供方法获取相对应的枚举集合:
public synchronized Enumeration keys()
返回关键字对应的枚举对象。
public synchronized Enumeration elements()
返回元素对应的枚举对象。
例8.5 Hashtable.java给出了使用Hashtable的例子。
例8.5 Hashtalbe.java。
//import java.lang.*;
import java.util.Hashtable;
import java.util.Enumeration;
public class HashApp{
public static void main(String args[]){
Hashtable hash=new Hashtable(2,(float)0.8);
//创建了一个哈希表的对象hash,初始容量为2,装载因子为0.8
hash.put("Jiangsu","Nanjing");
//将字符串对象“Jiangsu”给定一关键字“Nanjing”,并将它加入hash
hash.put("Beijing","Beijing");
hash.put("Zhejiang","Hangzhou");
System.out.println("The hashtable hash1 is: "+hash);
System.out.println("The size of this hash table is "+hash.size());
//打印hash的内容和大小
Enumeration enum1=hash.elements();
System.out.print("The element of hash is: ");
while(enum1.hasMoreElements())
System.out.print(enum1.nextElement()+" ");
System.out.println();
//依次打印hash中的内容
if(hash.containsKey("Jiangsu"))
System.out.println("The capatial of Jiangsu is "+hash.get("Jiangsu"));
hash.remove("Beijing");
//删除关键字Beijing对应对象
System.out.println("The hashtable hash2 is: "+hash);
System.out.println("The size of this hash table is "+hash.size());
}
}
运行结果:
The hashtable hash1 is: {Beijing=Beijing, Zhejiang=Hangzhou, Jiangsu=Nanjing}
The size of this hash table is 3
The element of hash is: Beijing Hangzhou Nanjing
The capatial of Jiangsu is Nanjing
The hashtable hash2 is: {Zhejiang=Hangzhou, Jiangsu=Nanjing}
The size of this hash table is 2
Hashtable是Dictionary(字典)类的子类。在字典类中就把关键字对应到数据值。字典类是一个抽象类。在java.util中还有一个类Properties,它是Hashtable的子类。用它可以进行与对象属性相关的操作
http://www.skyabove.cn/article.asp?id=32
enum
In the Java programming language, you define an enum type by using the enum keyword. For example, you would specify a days-of-the-week enum type as:
public enum Day {
SUNDAY, MONDAY, TUESDAY, WEDNESDAY,
THURSDAY, FRIDAY, SATURDAY
}
Java programming language enum types are much more powerful than their counterparts in other languages. The enum declaration defines a class (called an enum type). The enum class body can include methods and other fields. The compiler automatically adds some special methods when it creates an enum. For example, they have a static values method that returns an array containing all of the values of the enum in the order they are declared. This method is commonly used in combination with the for-each construct to iterate over the values of an enum type. For example, this code from the Planet class example below iterates over all the planets in the solar system.
for (Planet p : Planet.values()) {
System.out.printf("Your weight on %s is %f%n",
p, p.surfaceWeight(mass));
}
Note: All enums implicitly extend java.lang.Enum. Since Java does not support multiple inheritance, an enum cannot extend anything else.
Each enum constant is declared with values for the mass and radius parameters. These values are passed to the constructor when the constant is created. Java requires that the constants be defined first, prior to any fields or methods. Also, when there are fields and methods, the list of enum constants must end with a semicolon.
Note: The constructor for an enum type must be package-private or private access. It automatically creates the constants that are defined at the beginning of the enum body. You cannot invoke an enum constructor yourself.
ref:
Enum Types
掌握JDK1.5枚举类型
体验JAVA 5的新增语言特性
enum
In the Java programming language, you define an enum type by using the enum keyword. For example, you would specify a days-of-the-week enum type as:
public enum Day {
SUNDAY, MONDAY, TUESDAY, WEDNESDAY,
THURSDAY, FRIDAY, SATURDAY
}
Java programming language enum types are much more powerful than their counterparts in other languages. The enum declaration defines a class (called an enum type). The enum class body can include methods and other fields. The compiler automatically adds some special methods when it creates an enum. For example, they have a static values method that returns an array containing all of the values of the enum in the order they are declared. This method is commonly used in combination with the for-each construct to iterate over the values of an enum type. For example, this code from the Planet class example below iterates over all the planets in the solar system.
for (Planet p : Planet.values()) {
System.out.printf("Your weight on %s is %f%n",
p, p.surfaceWeight(mass));
}
Note: All enums implicitly extend java.lang.Enum. Since Java does not support multiple inheritance, an enum cannot extend anything else.
Each enum constant is declared with values for the mass and radius parameters. These values are passed to the constructor when the constant is created. Java requires that the constants be defined first, prior to any fields or methods. Also, when there are fields and methods, the list of enum constants must end with a semicolon.
Note: The constructor for an enum type must be package-private or private access. It automatically creates the constants that are defined at the beginning of the enum body. You cannot invoke an enum constructor yourself.
ref:
Enum Types
掌握JDK1.5枚举类型
Wednesday, 25 April 2007
lecture 7;8;9
lecture 6
Memory-Mapped Input and Output
Within SPIM: console and keyboard are using by CPU to communicate with external devices.
Some MIPS addresses are actually device registers
- Console I/O in SPIM
- SPIM emulates MMIO
- Must select ‘Mapped I/O’ in PCSpim settings
- Receiver – keyboard
- Transmitter – display
- Can still use syscalls
Keyboard Input
- Receiver control (at FFFF000016) consists of 2 bits
- Bit 0 is the ‘ready’ bit – unread input from keyboard
- Receiver data (at FFFF000416) contains last pressed key
- Reading data register resets ‘ready’ bit
- Read from control register
- AND off the ‘ready’ bit
- If zero, no keypress
- Keep waiting
- Else read data register
- li $t0, 0xffff0000
- rd poll:
- lw $v0, 0($t0)
- andi $v0, $v0, 0x01
- beq $v0, $zero, rd poll
- lw $v0, 4($t0)
- # last key code in $v0
Character Display
- Transmitter control (at FFFF000816) consists of 2 bits
- Bit 0 is the ‘ready’ bit – display accepting new character
- Transmitter data (at FFFF000C16) takes ASCII character
- Writing data register resets ‘ready’ bit
- Read from control register
- AND off the ‘ready’ bit
- If zero, not ready
- Keep waiting
- Else send to data register
- # character in $a0
- li $t0, 0xffff0008
- wr poll:
- lw $v0, 0($t0)
- andi $v0, $v0, 0x01
- beq $v0, $zero, wr poll
- sw $a0, 4($t0)
half-adder
- S = A &B
- C = A ^ B
Full-Adder
- S = A &B& Cin
- Cout = (A^B)&(B^Cin)&(A^Cin)
Ripple Carry Adder
- A chain of full-adders can sum as many bits as needed
- The Cout of each adder is wired to the Cin of the next
- Present the nth bit of inputs A and B to the nth adder
- Set C0 to 0; carry out C4 indicates overflow
- Calculates S = A + B, where Sn is the nth bit of S. . .
- The carry bits ripples across the full adders
- Simplest, but not the fastest (c.f. carry look-ahead)
Representing Negative Numbers
- Sign and Magnitude :What we use in decimal notation: +/− and 0, 1, 2, · · ·, becide the sign bit, other bits are same for a pair of positive and negative number.
- Ones’ Complement : Represent −x by its bitwise inverse (NOT). the bits are revise between positve and negative number, +0 and -0 are special.
- Excess-n :Zero represented by binary n: 02 is thus −n
- Two’s Complement :For an n-bit number, represent −x by 2n − x
Method of Complements :Subtract each digit of x from b − 1, then add 1 to result
Two’s Complements :In base 2 with n bits, represent −x using 2n − x
But there’s a quicker way to calculate 2n − x:
- Take the bitwise inverse (NOT) of x, then add 1 to result
- Addition as for unsigned numbers; just ignore carry bit
- Conventionally we take the MSB to represent the sign 0 for positive, 1 for negative
Thus n bits can represent from −2n−1 up to 2n−1 − 1
All modern processors primarily use two’s complement
lecture 7
Sign Extension :For a signed byte, copy the MSB (bit 7) 24 times:
lb and lh performs sign extension;
However, add and addi also check for overflow
Overflow when result exceeds −231 _ x <>On overflow, trigger an error exception Try
- li $t0, 0x7fffffff
- addi $t0, $t0, 1
- Checking for Overflow
- addu $s0, $s1, $s2
- xor $t0, $s1, $s2
- blt $t0, $zero, no overflow
- xor $t0, $s0, $s1
- bge $t0, $zero, no overflow
- # we have overflow!
- no overflow: # rest of program
Multiplication Product of m- and n-digit numbers requires m + n digits
n-Bit Binary Multiplication
Slow compared to e.g. addition; takes many cycles Would stall the next instructions in the pipeline Independent unit (from main ALU) for muln and divn Source operands come from the usual register file Results written to two special registers HI and LO
lecture 8
Shifting the Point What is 0.110 in binary? 0.110 = 0.0001001001 . . .2 Digits repeat forever – no exact finite representation!
Use binary scaling: e.g.
- let one increment represent 1/16th Hence,
- 0000.00012 = 1 _= 1/16 = 0.0625
- 0001.10002 = 24 _= 24/16 = 1.5 Fixed Point Arithmetic
Fixed position for binary point Addition same as integers: a/c + b/c = (a + b)/c
Multiplication mostly unchanged, but must scale after
a b
- * - =(a × b)/c
c c
e.g. 1.5 × 2.5 = 3.75
0001.10002 × 0010.10002 = 0011.1100 00002
Scientific Notation
- General form ±m × be where
- The mantissa contains a decimal point
- The exponent is an integer e 2 Z
- The base can be any positive integer b 2 N_
- A number is normalised when 1 _ m < 0016 =" 0" 6=" 0" ff16 =" 0" 6=" 0"> largest representable number
- Alternative is to give a wrong value, or raise an exception
- Overflow gives ±1 (underflow gives denormalised)
- In long computations, only a few results may be wrong
- Raising exceptions would abort entire process
- Giving a misleading result is just plain dangerous
- Infinities and NaN propagate through calculations, e.g. 1 + (1 ÷ 0) = 1 +1 = 1 ; (0 ÷ 0) + 1 = NaN + 1 = NaN
lecture 9
Floating Point Addition
- Suppose f0 = m0 × 2e0 and f1 = m1 × 2e1
- Then f0 × f1 = m0 × m1 × 2e0+e1
- Shift the smaller number right until exponents match
- Add/subtract the mantissas, depending on sign
- Normalise the sum by adjusting exponent
- Check for overflow
- Round to available bits
- Result may need further normalisation; if so, goto step 3
- 1 Add the exponents (be careful, excess-n encoding!)
- 2 Multiply the mantissas, setting the sign of the product
- 3 Normalise the product by adjusting exponent
- 4 Check for overflow
- 5 Round to available bits
- 6 Result may need further normalisation; if so, goto step 3
IEEE 754 Rounding
Hardware needs two extra bits (round, guard) for rounding
IEEE 754 defines four rounding modes
- Round Up Always toward +1 Round Down Always toward −1 Towards Zero Round
- down if positive, up if negative
- Round to Even Rounds to nearest even value: in a tie, pick the closest ‘even’ number: e.g. 1.5 rounds to 2.0, but 4.5 rounds to 4.0
Here be Dragons
Cannot rely on e.g. (a + b) + c = a + (b + c)
e.g. calculate 1 + 1020 − 1020 on a computer
Absolute and Relative Error
- We wish to represent some given some number m
- Its IEEE 754 representation is n – an approximation
- The absolute error is defined to be
- a = |m − n|
- The relative error is defined as
- r = |m − n|/n
- m The true value of n lies within the ranges
- n ± a = [n − a, n + a], or
- n(1 ± r ) = [n(1 − r ), n(1 + r )]
Error Propagation
- Addition or subtraction sums absolute error of operands (x ± ax ) + (y ± ay ) = (x + y) ± (ax + ay )
- When x _ −y, the error can be as large as the result
- Multiplication or division sums relative error of operands : x(1 ± rx ) × y(1 ± ry ) = (x × y)(1 ± (rx + ry ) ± rx*ry ) We can ignore the much smaller rx*ry term
Example: given the relative error of x, y and z,
- what is the absolute error in the expression y2 − 4xz?
- y2(1 ± 2ry ) − 4xz(1 ± (rx + rz )) = (y2 − 4xz) ± (2y2ry + 4xz(rx + rz ))
Monday, 23 April 2007
square_root
Square Root Approximation Library
Successive Approximation Algorithm
Successive approximation is an iterative algorithm for approximating the square root of a number. The algorithm is based on the following observations:
If x is the square root of N then,
(1) (N/x) = x so
(2) (x + (N/x)) / 2 = x.
It can be shown that if y is an approximation of the square root of N then,
(3) (y + (N/y)) / 2 is a better approximation.
Using equation (3) repeatedly allows an approximation for the square root of N to be continuously refined. The refinement of the approximation may be stopped once the difference between successive approximations is less than some threshold.
Bisection Algorithm
Bisection is another iterative process used to approximate the square root of number. The algorithm works by repeatedly reducing the range of values which the square root of a value is known to exist in. Given an initial value N and an approximate square root guess of x, the bisection algorithm is implemented using the following steps:
Step 1. Set the square root upper bound to N.
Step 2. Set the square root lower bound to 1.*
Step 3. If (x)2 is close enough to N, x is the square root. Exit.
Step 4a. If (x)2 <> N, set the upper bound to x, and let x be half way between the lower bound and the old x.
Step 5. Go to Step 3.
*NOTE: For N between 0 and 1, set the lower bound to 0 and the upper bound to 1
other reference:
Ancient Square Roots
Square root
example_Structure
College Application Essays Help Lesson Three: Example Essay Structures
which is quite good, it gives some points and support a real example.
How Do I Write an Example/Illustration Essay?
illustrate the general structure including what every parts should be.
mips_arithmetic
CHAPTER 8 — Binary Addition and Two's Complement
Here are some details:
usually the operands and the result have a fixed number of bits (usually 8, 16, 32, or 64). These are the sizes that processors use to represent integers.
1. to keep the result the same size as the operands, you may have to include zero bits in some of the leftmost columns.
2. compute the carry-out of the leftmost column, but don't write it as part of the answer (because there is no room if you have a fixed number of bits.)
3. when the operands are represented using the unsigned binary scheme (the base two representation scheme discussed in the last two chapters) a carry-out of 1 from the leftmost column means the sum does not fit into the fixed number of bits. This is called Overflow.
4. when the operands are represented using the two's complement scheme (which will be described at the end of this chapter), then a carry-out of 1 from the leftmost column is not necessarily overflow.
Overflow Detection
The electronic circuits of a computer can easily detect overflow by checking if the carry-out of the leftmost column is a zero or a one. A program might branch to an error handling routine when overflow is detected.
when the "Binary Addition Algorithm" is used with unsigned binary integer representation:The result is CORRECT only if the CARRY OUT of the high order column is ZERO.
Sign-Magnitude Representation
It uses one bit (usually the leftmost) to indicate the sign. "0" indicates a positive integer, and "1" indicates a negative integer. The rest of the bits are used for the magnitude of the number
One pattern corresponds to "minus zero", 1000 0000. Another corresponds to "plus zero", 0000 0000.
This is what is wrong with Roman Numerals: they can represent any positive integer you want, but they are very, very poor when used in computation.
Two's Complement
Start with an N-bit representation of an integer.
To calculate the N-bit representation of the negative integer:
1. Reflect each bit of the bit pattern (change 0 to 1, and 1 to 0).
2. Add one.
here is what is going on: When each bit of a pattern is reflected then the two patterns added together make all 1's.
adding one to this pattern creates a pattern of all zero's:
Three patterns added together result in a zero. If one pattern represents an integer, then the sum of the other two patterns represents the negative of the integer.
pattern + pattern reflected + one = all zeros
pattern + (pattern reflected + one ) = all zeros
pattern + (two's complement of pattern) = all zeros
it looks like +128 and - 128 are represented by the same pattern. This is not good. A non-zero integer and its negative can't both be represented by the same pattern. So +128 can not be represented in eight bits. The maximum positive integer that can be represented in eight bits is 12710. The negative integers -1 .. -12710 also can be represented.Eight bits can represent the numbers
-12810 ... 0 ... +12710.
it is by happy coincidence that the high order bit of a two's complement integer is 0 for positive and 1 for negative. But, to create the two's complement representation of the negative of a number you must "reflect, add one".
to convert N bits of two's complement representation into decimal representation:
1. If the integer is negative, complement it to get a positive integer.
2. Convert (positive) integer to decimal (as usual).
3. If the integer was originally negative, put "-" in front of the decimal representation.
with two's complement representation the result of addition is correct if the carry into the high order column is the same as the carry out of the high order column. The carry can be one or zero. Overflow is detected by comparing two bits, an easy thing to do with electronics
CHAPTER 9 — First SPIM Program
1. Register Display: This shows the contents (bit patterns in hex) of all 32 general purpose registers, the floating point registers, and a few others.
2. Text Display: This shows the assembly language program source, the machine instructions (bit patterns in hex) they correspond to, and the addresses of their memory locations.
3. Data and Stack Display: This shows the sections of MIPS memory that hold ordinary data and data which has been pushed onto a stack.
4. SPIM Messages: This shows messages from the simulator (often error messages).
Text is the name for machine language bit patterns intended for eventual execution. The word "program" is often ambiguous, so "text" is used. "Text" is a machine language program waiting to become part of an executing process.
Character output from the simulated computer is in the SPIM console window, shown as an icon in the picture.
.text is a directive. A directive is a statement that tells the assembler something about what the programmer wants, but does not itself result in any machine instructions. This directive tells the assembler that the following lines are ".text" -- source code for the program.
.globl main is another directive. It says that the identifier main will be used outside of this source file (that is, used "globally") as the label of a particular location in main memory.
The line main: defines a symbolic address (sometimes called a statement label). A symbolic address is a symbol (an identifier) that is the source code name for a location in memory. In this program, main stands for the address of the first machine instruction (which turns out to be 0x00400000). Using a symbolic address is much easier than using a numerical address. With a symbolic address, the programmer refers to memory locations by name and lets the assembler figure out the numerical address.
CHAPTER 10 — A MIPS Programming Model
Memory Model
modern computer systems nearly always use cache and virtual. But our abstract view of memory does not include them. The purpose of virtual memory is to make it appear as if a program has the full address space available. So our programming model has the full address space. The purpose of cache is to transparently speed up memory access. So our programming model does not include cache. Memory in the programming model is as follows:
data:
MIPS memory is an array of 232 bytes. Each byte has a 32-bit address. Each byte can hold an 8-bit pattern, one of the 256 possible 8-bit patterns. The addresses of MIPS main memory range from 0x00000000 to 0xFFFFFFFF.
However, user programs and data are restricted to the first 231 bytes. The last half of the address space is used for the operating system and for specialized purposes.
operation:
The processor chip contains registers, which are electronic components that can store bit patterns. The processor interacts with memory by moving bit patterns between memory and its registers.
• Load: a bit pattern starting at a designated address in memory is copied into a register inside the processor.
• Store: a bit pattern is copied from a processor register to memory at a designated address.
Bit patterns are copied between the memory and the processor in groups of one, two, four, or eight contiguous bytes. When several bytes of memory are used in an operation, only the address of the first byte of the group is specified.
Memory Layout
though the address space is 32 bits, the top addresses from 0x80000000 to 0xFFFFFFFF are not available to user programs. They are used for the operating system and for ROM. When a MIPS chip is used in an embedded controller the control program exists in ROM in this upper half of the address space.
The parts of address space accessible to a user program are divided as follows:
Text Segment: Thisholds the machine language of the user program (the text).
Data Segment: This holds the data that the program operates on. Part of the data is static. This is data that is allocated by the assembler and whose size does not change as a program executes. Values in it do change; "static" means the size in bytes does not change during execution. On top of the static data is the dynamic data. This is data that is allocated and deallocated as the program executes. In "C" dynamic allocation and deallocation is done with malloc() and free().
Stack Segment: At the top of user address space is the stack. With high level languages, local variables and parameters are pushed and popped on the stack as procedures are activated and deactivated.
Registers:
often data consist of several contiguous bytes. Each computer manufacturer has its own idea of what to call groupings larger than a byte. The following is used for MIPS chips.
• byte — eight bits.
• word — four bytes, 32 bits.
• double word — eight bytes, 64 bits.
A block of contiguous memory is referred to by the address of its first byte (ie. the byte with the lowest address.) Most MIPS instructions involve a fixed number of bytes.
Often you need a number of bits other than one of the standard amounts. Use the next largest standard amount, and remember to be careful. Attempting to use the very minimum number of bits is more complicated than it is worth and is a rich source of errors in assembly language programming.
register is a part of the processor that can hold a bit pattern. On the MIPS, a register holds 32 bits. There are many registers in the processor, but only some of them are visible in assembly language. The others are used by the processor in carrying out its operations.
• A load operation copies a bit pattern from memory into a register.
• A store operation copies a bit pattern from a register into memory.
The registers that are visible in assembly language are called general purpose registers and floating point registers. There are 32 general purpose registers. Each general purpose register holds a 32 bit pattern. In assembly language, these registers are named $0, $1, $2, ... , $31. There are 32 floating point registers. These are discussed in a later chapter.
One of the general purpose registers is hard-wired to always contain the value 0x00000000 (all zero bits).
the arithmetic/logic unit (ALU) of a processor performs integer arithmetic and logical operations. For example, one of its operations is to add two 32-bit integers. An integer used as input to an operation is called an operand. One operand for the ALU is always contained in a register. The other operand may be in a register or may be part of the machine instruction itself. The result of the operation is put into a general purpose register.
Machine instructions that use the ALU specify four things:
As execution proceeds through a list of instructions, a special register, the program counter, points at the instruction that is next in line to execute.
Fetch the next Instruction. The program counter contains the address of the next machine instruction. The instruction is fetched from memory.
Increment the PC. The address in the program counter is incremented by four.
Execute the Instruction. The machine operation specified by the instruction is performed.
CHAPTER 11 — Immediate Operands and Bitwise Logic
General OR Immediate Instruction
here is a description of the ori instruction used as a bitwise OR instruction:
ori d,s,const # register d <-- bitwise OR of const
# with the contents of register $s
# const is 16-bits, so
# 0x0000 ... const ... 0xFFFF
The parts of the instruction must appear in the correct order, and const must be within the specified range. If the immediate operand in the assembly language shows less than 16 bits (as does 0x2 in the previous example) then the assembler expands it to the required sixteen bits. If the assembly language specifies more than sixteen bits, then the assembler writes an error
message.
CHAPTER 12 — Shift Instructions and Logic Instructions
Shifting in Place
hen an ALU operation is performed: (1) data is copied from the register(s) into the ALU. Then (2), the ALU does the operation. Next (3) the result is written to the designated result register. There is no problem when an operand register is also the result register because the operand data was transferred to the ALU in the first step, leaving the register open to receive the result.
No-Op
A machine instruction that does nothing is called (in official computer science jargon) a no-op. The no operation instruction is surprisingly useful, especially for MIPS.
CHAPTER 14 — Integer Multiplication, Division and Arithmetic Shift Instructions
he product of two N-place decimal integers may need 2N places. This is true for numbers expressed in any base. In particular, the product of two integers expressed with N-bit binary may need 2N bits.
MIPS Multiply Unit
he multiply unit of MIPS contains two 32-bit registers called hi and lo. These are not general purpose registers. When two 32-bit operands are multiplied, hi and lo hold the 64 bits of the result. Bits 32 through 63 are in hi and bits 0 through 31 are in lo.
mult s,t # hilo <-- $s * $t. two's comp operands multu s,t # hilo <-- $s * $t. unsigned operands add and addu perform the same operation. The "u" means "don't trap overflow". With mult and multu, different operations are carried out. Neither instruction ever causes a trap.
The significant bits in a positive or unsigned number represented in binary are the most significant 1 bit (the leftmost 1 bit) and all bits to the right of it. For example, the following has 23 significant bits: 0000 0000 0100 0011 0101 0110 1101 1110
The significant bits in a negative number represented in two's complement are the most significant 0 bit (the leftmost 0 bit) and all bits to the right of it. For example, the following has 23 significant bits: 1111 1111 1011 1100 1010 1001 0010 0010
To ensure that a product has no more than 32 significant bits, ensure that the sum of the number of significant bits in each operand is 32 or less. For the programming in this course you will not need to be careful about this.
The mfhi and mflo Instructions
here are two instructions that move the result of a multiplication into a general purpose register: mfhi d # d <-- hi. Move From Hi mflo d # d <-- lo. Move From Lo The hi and lo registers cannot be used with any of the other arithmetic or logic instructions. If you want to do something with a product, it must first be moved to a general purpose register. However there is a further complication on MIPS hardware:
Rule: Do not use a multiply or a divide instruction within two instructions after mflo or mfhi. The reason for this involves the way the MIPS pipeline works. On the SPIM simulator this rule does not matter.
The div and the divu Instructions
ith N-digit integer division there are two results, an N-digit quotient and an N-digit remainder. With 32-bit operands there will be (in general) two 32-bit results. MIPS uses the hi and lo registers for the results:
The sra Instruction
Sometimes you need to divide by two. This instruction is faster and more convenient than the div instruction.
CHAPTER 15 — Memory Access Instructions
he operands for all arithmetic and logic operations are contained in registers. To operate on data in main memory, the data is first copied into registers. A load operation copies data from main memory into a register. A store operation copies data from a register into main memory .
When a word (4-bytes) is loaded or stored the memory address must be a multiple of four. This is called an alignment restriction. Addresses that are a multiple of four are called word aligned. This restriction makes the hardware simpler and faster.
Big Endian and Little Endian
load word or store word instruction uses only one memory address. The lowest address of the four bytes is used for the address of a block of four contiguous bytes.
Big Endian Byte Order: The most significant byte (the "big end") of the data is placed at the byte with the lowest address. The rest of the data is placed in order in the next three bytes in memory.
Little Endian Byte Order: The least significant byte (the "little end") of the data is placed at the byte with the lowest address. The rest of the data is placed in order in the next three bytes in memory.
Intel 80x86: little-endian.
Macintosh: big-endian.
MIPS Addresses
An instruction that refers to memory uses a base register and an offset. The base register is a general purpose register that contains a 32-bit address. The offset is a 16-bit signed integer contained in the instruction. The sum of the address in the base register with the (sign-extended) offset forms the memory address.
CHAPTER 16 — More Memory Access
CHAPTER 29 — Binary Fractions
Limited Precision
The important point of all this is that on the number line from zero to 15.9375 not all real numbers can be represented. This is called a limit in precision. Floating point representation has the same problem.
Converting Representation from Decimal to Binary
To convert a decimal fraction to Base 2: Repeatedly multiply the decimal fraction by two. After each multiplication, copy the bit (0 or 1) that moves into the one's place (the place just left of the radix point) to the right of the binary fraction, then erase it from the decimal fraction. Stop when the decimal fraction is zero. (Note: if this never happens, stop when you have enough bits in the binary fraction.)
CHAPTER 30 — IEEE 754 Floating Point
Scientific Notation
10+n means move the decimal point n places right.
10-n means move the decimal point n places left.
IEEE 754 Floating Point
Bits 0 through 22 are for the mantissa; bits 23 through 30 are for the exponent; and bit 31 is the sign bit. The mantissa and exponent fields work like the similar parts in scientific notation (details follow). The sign bit gives the sign of the entire expression: a 0 bit means positive and a 1 bit means negative.
Very tricky: The mantissa represents the 23-bit binary fraction part of a 24-bit number that starts with a "1". The 20 place (the one's place) is presumed to contain a 1 and is not present in the mantissa. This trick gives us 24 bits of precision with only 23 bits.
The Exponent
The exponent is expressed using a biased integer. The true exponent is added to +12710 resulting in an unsigned binary integer. The biased integer is encoded using 8-bit unsigned binary.
A biased exponent of +127 represents the actual exponent 0.
A biased exponent of +128 represents the actual exponent 1.
A biased exponent of +126 represents the actual exponent -1.
Exceptions: (1) A floating point value of 0.0 is represented with a mantissa of 23 zero bits and an exponent of 8 zero bits. It is not legal to have an exponent of zero with a non-zero mantissa. (2) The exponent 25510 (1111 1111) is used to signal various problems, such as division by zero.
Float Formula
ere is a formula that summarizes the past several pages. In it, s is the sign bit (0 or 1), M is the mantissa (000...000 to 1111...111) and E is the biased exponent. value = (-1)s × 1.M × 2E-127
To convert a paper-and-pencil number into IEEE floating point, fill in each piece of the picture. Let us represent 1.0 as a 32-bit IEEE 754 float.
CHAPTER 31 — Floating Point Arithmetic on MIPS
MIPS Floating Point
Floating point on MIPS was originally done in a separate chip called coprocessor 1 (also called the FPA for Floating Point Accelerator). Modern MIPS chips include floating point operations on the main processor chip. But the instructions sometimes act as if there were still a separate chip.
MIPS has 32 single precision (32 bit) floating point registers.
The registers are named $f0 – $f31
$f0 is not special (it can hold any bit pattern, not just zero).
Single precision floating point load, store, arithmetic, and other instructions work with these registers.
Because floating point zero has the same representation as integer zero, 32 zero-bits. Register $0 works as a floating point zero as well as an integer zero.
Double Precision
MIPS also has hardware for double precision (64 bit) floating point operations. For this, it uses pairs of single precision registers to hold operands. There are 16 pairs, named $f0, $f2, — $f30. Only the even numbered register is specified in a double precision instruction; the odd numbered register of the pair is included automatically.
Some MIPS processors allow only even-numbered registers ($f0, $f2,...) for single precision instructions. However SPIM allows all 32 registers in single precision instructions. These notes follow that usage.
Full-Word Aligned
However, if you want to perform floating point arithmetic, then the floating point number must be in a floating point register
Floating Point Services
To print a floating point value to the SPIM monitor, use service 2 (for single precision) or service 3 (for double precision). To read a floating point value from the user, use service 6 (for single precision) or service 7 (for double precision). These notes deal mostly with single precision.
Compilers that keep track of the data types of values and that make sure that the correct types are used as arguments do strong type checking. Java is strongly typed. In assembly language type checking is largely absent.
Data Movement
CHAPTER 32 — Floating Point Comparison Instructions
Comparison Instructions
Testing if two floating point numbers are exactly equal is sometimes NOT a good idea. Floating point calculations are not exact. Sometimes values are not equal even though mathematically they should be. It is best to use "less than" or "less than or equal" instead of testing for exact equality. Here are some MIPS comparison instructions for single precision floating point:
Branch Instructions
The floating point branch instructions inspect the condition bit in the coprocessor. The bc1t instruction takes the branch if the bit is true (==1). The bc1f instruction takes the branch if the bit is false (==0). These are the only two floating point branch instructions.
The branch instructions have a one instruction branch delay. Hardware requires a nop instruction after each branch instruction. For this chapter, let us not bother with this. When running the programs with SPIM, disable branch delays in the settings menu
Newton's Method
Newton's method is a common way to compute the square root of a number. Say that n is the number and that x is an approximation to the square root of n. Then: x' =(1/2)(x + n/x)
x' is an even better approximation to the square root. The reasons for this are buried in your calculus book (which you, perhaps, have buried in the darkest corner of your basement). But, to make the formula plausible, look what happens if the approximation x happens to be exactly the square root. In other words, what if x = n0.5. Then: x' = (1/2)(x + n/x) = (1/2)( n0.5 + n/n0.5 )
= (1/2)(n0.5 + n0.5) = n0.5
If x gets the exact value, it stays fixed at that value.
Ending Test
But, due to the lack of precision with floating point, the best we can hope for is to calculate an x such that: 0.999999 <>The left and the right bound in the above have 6 decimal digits of precision. If 1.00000 is subtracted from this value the result is: -0.000001 <>To be safe, terminate the loop when: n/x*x - 1 <>
Sunday, 22 April 2007
closer
lyric:
I've had enough, of this parade.
I'm thinking of, the words to say.
We open up, unfinished parts,
Broken up, its so mellow.
And when I see you then I know it will be next to me
And when I need you then I know you will be there with me
Ill never leave you...
Just need to get closer, closer,
Lean on me now,
Lean on me now,
closer, closer,
Lean on me now,
Lean on me now.
Keep waking up (waking up), without you here (without you here).
Another day (another day), another year (another year).
I seek the truth (seek the truth), we set apart (we set apart)
Thinking of a second chance (a second chance).
And when I see you then I know it will be next to me
And when I need you then I know you will be there with me
Ill never leave you...
Just need to get closer, closer,
Lean on me now,
Lean on me now,
closer, closer,
Lean on me now,
Lean on me now (lean on me now).
And when I see you then I know it will be next to me
And when I need you then I know you will be there with me
Ill never leave you...
Just need to be closer, closer,
Lean on me now,
Lean on me now,
closer, closer,
Lean on me now,
Lean on me now (lean of me now).
closer, closer... closer, closer.
I ll Be A Virgin I ll Be A Mountain
I ll Be A Virgin I ll Be A Mountain
all linked lyric and his official web
Snow White
And I lied in your arms
You dreamed of all our children
Playing in the sun
I hope, I hope that you're alright
No More Lies To Reach You
No more lies around
I tried hard to see you
I tried hard to sound
No more lies to sound
I tried hard to see you
And I tried hard to sound
No more vows around
I tried hard to fool you
And hard to lose the ground
No more vows to sound
I tried hard to fool you
And hard to lose the ground
No more lies in my head
Your Stammering Kisses
In a room of empty walls?
With your vacant stare
And gloomy thoughts of sorrow?
Flown to America?
Oh, but all that I recall
Your stammering kisses is all that I need
Your stammering kisses is all that I have
Your stammering kisses is all that I'll get
Did you break your wings in a rage?
Are you flying now
And still it feels like falling?
Flown to America?
Oh, but all that I recall
Velvet Son
As you fought all the sounds in me
At the time of escapades up in the mountains
The sound of the bells embraced me
As you taught all the kids to shoot
At the time of escapades down in the valley
You fired a velvet gun
My warehouse legs, my Arabian chimes
Should I leave them by your gun?
Or, long-faced Lady, should I run?
And to dive in your open sea
At the time of escapades out in the desert
You cradled our velvet son
Silly Lily, Funny Bunny
Head over heels built up house
I scream and I lean in vain tonight
Remember the words that I said
As you're silly, Lily
I keep on knocking at your door with my head
As you're funny, bunny
Tasting like drops of cold rain
I'll drink and I'll drown and ruin the whole world
So think of the words that I said
I'll Be A Virgin, I'll Be A Mountain
My love is growing
My dreams have ended
And my soul is stranded
I'll swim to you
I'll leave my prison
To swim to you
When I reach you
I'll be a mountain
When I touch you
Wilted Flower
Were sumptuous rainfalls
Dreary whispering of how you love
Sun-baked objects
And I still hear your withered talk
I am blooming
Without you
You're a wilted flower
How could I now miss your face
As I'm watered in a shower?
And I still hear your withered talking
Messed-up Girl
Staying up all night and losing our pearl?
Why are you lying?
Why are you sighing, my love?
Your cheeks are all red
It's hard for you to hide that you betrayed me in his bed
But still you don't leave me
Still you don't leave, oh my love
What keeps you from falling prey to his charms?
Is it your love?
Oh, do you still love me, my dear?
But I'll be your moon
Brightening your night, but fading too soon
Brightening your path with my borrowed light, oh my love
Silver lining
Noble sweetness
Always shining
How can you do this?
Oh, how can you do this to me?
Staying up all night and losing our pearl?
Why are you lying?
Why are you sighing, my love?
The Saviour
And ruin my kingdom
Force me to break down
Take my pride
Plunder my homeland
Leave me down on the ground
And abduct my brothers
Pilfer my treasures
Waste my fields
That's what I deserve
For redeeming all mournful souls
With my splendour
I'll shine until I fall
I'll shine until I fall, my father
I'll shine until I fall
There's nothing in the world to save my life
You Came To Me When I Was Born
You came to me when I was torn
You came to me when I was strung out
You came to me when I was born
You came to me when I was mad
You came to me when I was lying
You came to me when I was sad
You came to me when I was passed
You came to me when I was longing
You came to me when I was lost
You came to me when I was caught
You came to me when I was crying
You came to me when I was fought
Feel Like Children
My heart is quiet
No tomorrow
No more sorrow
This winter's night
Heals my wounds
Stops my everlasting sighs
But I am yours
Together we could
Together we could
Fall asleep
And drift away
Cry in peace
Feel like children
Grey
I lose my daydreamsI lose my colours
I lose my longing
I find myself
CEP_Essay
question:
Question 4: How successfully can fiscal policy be used to combat (a) recessions and (b) 'overheating' in the economy? Use examples and evidence to support your arguments.
- Offer clear and concise definitions in the introduction ( Fiscal Policy, recession, overheating, business cycle etc)
- Discuss how fiscal policy operates and its types
- Discuss its affect on AD/AS
- Discuss the effectiveness and limitations of fiscal policy
- Illustrate the above with specific evidence
Please through the following articles and the relevant chapters in your textbook before you think about constructing an essay plan.
Survey: The unfinished recession The Economist.
Why
Interest rates: what the economists say: Thursday February 8, 2007
Guardian Unlimited
http://business.guardian.co.uk/story/0,,2008562,00.html
Notes
总需求:
(PE_p729)经济波动的基本模型:
短期经济模型集中在两个变量上:
- 用实际GDP衡量的经济物品和劳务产量
- 用CPI或GDP平减指数衡量的物价总水平
(P508)实际GDP回答了一个假设的问题,如果我们已过去某一年的价格来评价物品和劳务,今年生产的物品与劳务的价值是多少 。 实际GDP说明了经济的整体物品与劳务生产的变动。实际GDP是按照不变的价格衡量的物品与劳务的生产。 总之, 名义GDP使用当年的价格来评价经济中的物品与劳务的生产的价值。 实际 GDP是用不变的基年价格来评价经济中物品与劳务生产的 价值 。他反映了经济满足人们需要与欲望的能力。衡量了经济福利。
GDP平减指数:反映了物品与劳务的价格, 不反映生产量。等于名义GDP/实际GDP
总需求和总供给模型(model of aggreatedemand and aggreate supply):
- 总需求曲线(aggregate-demand curve):表示在每一种物价水平时,家庭,企业和政府想购买的物品和劳务总量。
- 总供给曲线(aggregate-supply curve):表示在每一种物价水平时,企业生产并销售的物品与劳务的总量。
为什么总需求曲线向右下方倾斜:
GDP:Y=C+I+G+NX
假设政府支出由政策决定,则其他三部分的组成取决于经济状况,特别是取决于物价水平。这里的假设也就是说总货币量的供给在一段时间内是相同的。
- 物价水平与消费:财富效应。钱包与银行账户上所持有的货币的名义值是固定的,但实际值不固定。当物价水平下降时,美元更值钱,可以买到更多的物品和劳务。 物价水平下降时消费者更富裕,鼓励他们更多的支出,消费支出增加意味着物品与劳务的需求更大。
- 物价水平与投资:利率效应。(第30章)提到,物价水平是货币需求量的一个决定因素。物价水平低,则购买相同物品和劳务所需要持有的货币就少,就有更多面额的货币转化成了有利息的资产。银行业就有了将以前更充分的资金作为贷款,所以利率会下降,而降低的利率又促进了借款。所以较低的物价水平降低了利率,鼓励了更多的支出与投资物品,从而增加了物品和劳务的需求量。
- 物价水平与净出口:汇率效应。物价水平低会带来利率低,,于是更多的投资转向国外市场?????????,于是增加了外汇市场上本国货币的供给。,从而使本国货币相对于其他通货而贬值。 外国物品相对于国内物品就变得昂贵了。这种实际汇率(国内与国外物品的相对价格) 的变动,减少了进口,所以净出口增加。所以,当美国物价水平下降引起美国利率下降,实际汇率贬值,刺激了美国的进出口,从而增加了物品与劳务的总需求。
- 消费引起的移动:任何一个改变人们的一种物价水平时想消费多少的时间都会使总需求曲线移动。例如,股市上涨,税收水平。减税时候,鼓励人们更多的支出,总需求曲线向右移动,反之亦然。
- 投资引起的移动:投资税收优惠(减免与企业的投资支出相关的税收)增加企业在利率为一定时需求的投资数量,所以投资税收优惠是总需求曲线向右移动。短期中货币供给增加会降低利率,抑制投资。 许多经济学家认为,整个美国历史上的货币政策的变动是总需求移动的一个重要来源。
- 政府购买引起的移动:驱策这移动总需求曲线的最之间的方法是政府购买。直接增加总需求的量的多少。
- 净出口引起的移动:
- 短期中,总需求移动引起经济中物品与劳务产量的波动。
- 长期中,总需求移动影响物价总水平,但不影响总产量。
(PE-747)2001年的衰退,三大冲击,网络泡沫,恐怖袭击和财务丑闻。在总统的要求下,国会在2001年通过了减税法案,包括直接的退税。减税的一个亩苗就是吃几消费者的支出,在恐怖主义者袭击之后,国会增加了从简纽约的资金和帮组有困难的民航业的政府支出。这些财政政策的目的就是是总需求曲线的向右移动,抵消经济经历的三次紧缩性的冲击。美联储叶通过实施扩张性的货币政策来帮组合扩大总需求。货币增长加速,利率下降。
总供给移动的影响:
总共给曲线的移动会引起stagflation-衰退(产量减少)和通货膨胀(物价上涨)的结合那些能影响总需求的决策者不能同时抵消着两种不利的影响,通常是抵消总供给曲线的移动,将其维持在自然产量率上,因为,他们允许用成本增加来影响长期物价水平。
总需求和总共给的来源:凯恩斯的《就业,利息和货币通论》。主要观点,衰退和萧条之所以会发生,是因为对物品与劳务的总需求不足。
difinition of fiscal police in wiki_pedia http://en.wikipedia.org/wiki/Fiscal_policy:
Fiscal policy is the economic term that defines the set of principles and decisions of a government in setting the level of public expenditure and how that expenditure is funded. Fiscal policy and monetary policy are the macroeconomic tools that governments have at their disposal to manage the economy. Fiscal policy is the deliberate and thought out change in government spending, government borrowing or taxes to stimulate or slow down the economy, also known as the contractionary policy. It contrasts with monetary policy, which describes the policies about the supply of money to the economy.
Fiscal policy is described as being either neutral, expansionary, or contractionary. An expansionary fiscal policy occurs when the government lowers taxes and increases spending; thus expanding output (national income). An increase in government spending or a cut in taxes shifts the aggregate demand curve to the right. An expansionary fiscal policy will expand the economy's growth. A contractionary fiscal policy occurs when the government raises taxes and lowers spending; thus lowering output (national income). A decrease in government purchases or an increase in taxes shifts the aggregate demand curve to the left. A contractionary fiscal policy will constrict the economy's growth.
(PE_p765) 财政如何影响中需求:
财政政策是指政府对政府购买或税收总水平的选择(PE_765)。财政政策主要影响物品与劳务的总需求。
政府购买的变动:政府改变其物品与劳务的购买,可以直接是总需求曲线移动。
乘数效应:政府购买,增加了企业的就业和利润,随着工人收入增加和企业所有者的利润增加,促进了对消费品的支出。同时也促进的别的企业的需求。所以政府支出的每一美元可以在全社会所带动增加的物品与劳务的总需求大于一美元。所以叫multiplier effect。这种产生于消费支出反映的乘数效应由于投资对更高水平需求的反应而得到了加强。在这种情况下,较高的政府需求刺激了较高的投资品需求。这种来自于投资需求的正的反馈有时候被称为投资加速器。乘数=1/(1-x)。 乘数的大小取决于边际消费倾向。因为更高的收入会引起更大的消费支出。
挤出效应:当政府购买增加了物品与劳务的总需求时,利率也会随之升高,较高的利率会减少投资支出,阻止总需求增加。称为crowding-out effect。 企业的收入增加,家庭计划购买更多的物品与劳务,于是选择更多的以流动形势持有自己的财富。也就是说财政扩张的收入增加提高了货币需求。由于货币供给的垂直曲线是固定的。 为了保持货币供应平衡,利率必然会上升????????????。利率上升减少了物品与劳务的需求量。,特别是对住房和企业投资品的需求减少了。 也就是说,当政府购买增加提高了物品与劳务的需求时,他也会挤出投资。从而影响了社会的总需求。
总之,当物品与劳务总需求的增加与政府购买的需求, 取决于乘数效应和挤出效应的强弱。
税收变动:
税收变动:
减税增加了消费,使总需求曲线向右移动。
税收变动引起的总需求移动的幅度也受乘数和挤出效应的影响。所以总需求曲线的移动可以大于或小于引起他的税收变动。
还有一个重要因素巨鼎税收引起的总需求移动幅度:家庭对税收变动的持久的还是暂时的感觉。
大多数经济学家认为,财政政策的短期宏观经济效应主要是通过总需求发生作用的。但财政政策也会潜在的影响物品与劳务的供给量。一些供给学派经济学家认为,减税的影响如此之大,以致降低税率实际将通过提高工人努力程度来增加税收收入。政府购买变动也会潜在的影响总供给,例如政府投资公路建设,则可以提高企业的作业效率。但这种投资更趋向于是一种长期的投资。
运用政策来稳定经济:
政府要尽量避免成为经济波动的原因。凯恩斯强调在总需求看来不足以维持充分就业水平的生产时,政府应该积极的刺激总需求。
消费信心指数?????
财政政策也有相当大的时滞,主要是由于政治过程。在美国,大多数政府支出与税收的变动必须经过参众两院的国会委员会,等等,完成过程需要几个月,甚至是几年。到财政政策的变动通过并实施时,经济状况可能已经改变了。
原因是因为经济预测既不稳定。但是衰退和萧条实际上是在没有任何预兆的情况下发生的。最好的决策者也只能在衰退和萧条发生的时候对经济变动做出变动。
为了避免了时滞,automatic stabilizers 是在经济景如衰退使决策者不用采取有益的行动就可以刺激总需求的财政政策变动。其中最重要的是税制度,根据情况收扩税收。 政府支出也可以作稳定器。特别是在社会福利这一方面
经济萧条和经济过热的定义
在一些年份,并没有出现正常的经济增长。企业无法把他们提供的所有物品与劳务都卖出去,因此,他们削减生产,解雇工人,失业增加,而且工厂被限制,由于经济生产的物品和劳务少了,实际GDP和其他的收入指标下降。 如果这种收入减少和失业增加较为缓和, 这种时期就被称为衰退,如果较为严重,就称为萧条(depression)。
经济波动的三个事实:
- 经济波动是无规律的和无法预测的。
- 大多数宏观经济数量同时波动。
- 随着产量减少,失业增加。
The main reading for this lecture is: Mankiw: Chapters 33 & 34
Additional reading:
-Begg and Ward : Chapter 11
- BFD: chapter 19 " Introduction to macroeconomics", chapter 20 "Output
and aggregate demand" and chapter 21 "Fiscal policy and foreign trade",
- Griffiths & Wall: chapters 16 - 19.
- Parkin, Powell & Matthews: chapters 21 - 24.
- Sloman: chapter 17.
Friday, 20 April 2007
regular_expression
- * metacharacter means any srtings of zero or more characters, eg *.*,
- ? matches any single character
- [] matches any of the eclosed charcter. [a-z] or [!abc]
- ` substitutes the output of a command.
Avoiding Shell Expansion: The character needs to be quoted or escaped
quoted:
- "" everything between " and " is taken literally, except for : $ ` ' " .
- '' everything between ' and ' is taken literally except for ' . we can embed another ' within a pare of ' using escaping.
Escaped: using \
- The character following a backslash \ is taken literally.
- Use \ within ″ ″ or ’ ’ to escape ″, $, and ′ when necessary.
p11
shell_script
- [zliybsj2@unnc-cslinux ~]$ echo $PATH
- /usr/kerberos/bin:/usr/local/bin:
- /bin:/usr/bin:/usr/X11R6/bin:/opt/SUNWappserver/jdk/bin/:
- /usr/NX/bin:/home/domain/zliybsj2/bi
- [zliybsj2@unnc-cslinux ~]$ echo $TERM
- xterm
- [zliybsj2@unnc-cslinux ~]$ echo $HOME
- /home/domain/zliybsj2
- [zliybsj2@unnc-cslinux ~]$ echo $PS1
- [\u@\h \W]\$
- using all capitals,
- using echo to get the value of a variable.
- variables are expanded by the shell before he command is executed.
- environment variables can be used by any program.
- variables change is only visible in the current shell.child process don't automatically inherit the environmrnt variables from their parent. using export to let proecessed get the changed value, eg export VAR=value, then $VAR in child process is value, or stay same. using : to add somthing to PATH, eg, export PATH=$PATH:new stuff
PATH:
- it tells UNIX where to look for executables
- when you type the name of a program, the shell will look for it in your PATH
- ecah directory seperated by a colon
- changed PATH can only live in current widow.
shell script:
- the shell is a command interpreter
- shell script is a text file contains all command you want to group, which is executed in a sub shell.
- first line is a specially comment: #!/bin/sh tell program which kind of shell will be using to execut this shell.
chomd :
- chmod o-r coursework
- chmod u+x shellscript
- chmod a+x shellscript
- chmod +x directory
input and output:
- echo works like Java's println.
- argument: $0, $1, $2,...... $#
conditionals:
- if ...
- then ...
- else if ...
- else ...
- fi
read: to get input to interacte with users
can have more than one argument. will bind the first word of input to the first variable and bind the rest to the second. this acts like a list or array, so can be used with for.
controlling input:
- using <<>
- using <>
Thursday, 19 April 2007
SMB/CIFS
SMB协议已经被发展成为可以运行于DOS操作系统,因此字节顺序将会和网络顺序相反。
SMB可以运行在TCP/IP,NetBEUI,DECnet和IPX/SPX协议之上。如果SMB执行于TCP/IP,DECnet或则是NetBEUI之上,那么NETBIOS名字必须被使用。
NETBIOS名字用来在网络上鉴别一台计算机。
SMB域名是用来鉴别一个SMB服务器上的一组资源的(用户,打印机,文件……)。
让我们假设一个这样的环境:一个客户端希望访问一台服务器上的特定资源。
1 - 开始于客户端向服务器请求一个NETBIOS会话。客户端发送它的已编码的NETBIOS名字到SMB服务器(它们在139端口监听连接请求)。服务器接收到NETBIOS名字后回复一个NETBIOS会话数据报给有效的会话连接。客户端在建立了连接之后才能进入访问。
2 - 客户端发送一个SMB negprot请求数据报(negprot是磋商协议“negotiate protocol”的简写)。客户端列出了它所支持的所有SMB协议版本。
3 - 通过磋商之后,客户端进程向服务器发起一个用户或共享的认证。(下一章中我们将会看到共享认证和用户认证之间的不同)。
这个过程是通过发送SesssetupX(SesssetupX是会话建立和X“Session setup and X”的简称)请求数据报实现的。客户端发送一对登录名/密码或一个简单密码到服务器,然后服务器通过发送一个SesssetupX应答数据报来允许或拒绝本次连接。
4 - 好了,在客户端完成了磋商和认证之后,它会发送一个TconX数据报并列出它想访问的特定网络资源的名称,之后服务器会发送一个TconX应答数据报以表示此次连接是否接受或拒绝。
SMB的安全等级
第一种是“共享”级的安全模式。这种安全模式需要一个访问网络上共享资源的密码。用户通过这个正确的密码来访问网络资源(IPC,磁盘,打印机)。他可以是网络上任何一个知道共享资源服务器名字的用户。
第二种是“用户”级的安全模式。这是在第一种模式上的增强版。它坚持使用一对登录名/密码来访问共享资源。所以如果一个用户想访问这种类型的共享资源,就必须同时提供登录名和密码。这种
密码
在SMB协议中,如果你想进行一次在服务器上的请求认证,你的密码可以以原码或加密后的形式发送到服务器端。如果服务器支持加密属性,客户端必须发送一个应答信号。在negprot应答数据报中,服务器会给客户端发送一个密钥。然后,客户端将密码加密并通过SesssetupX请求数据报发送到服务器端。服务器将会核查密码的有效性,并由此允许或拒绝客户端的访问。
你必须知道一个SMB密码(未加密)的最大长度是14位。密钥的长度一般为8位,加密过后的口令长度为24位。在ANSI密码中,密码中的所有位都转换成大写的形式然后再加密。
密码是以DEC编码方式进行加密的。
几种SMB数据报的描述
SMB数据报的常规特征
通常情况下,SMB运行于TCP/IP协议组之上。那么我们就假设SMB运行在TCP层之上。在TCP层上面,你常常会发现NETBIOS(NBT)头部。在NBT上面,有SMB基础报文头部。在SMB基础报文头部之上,就是另一种依赖于特定请求命令的头部。
----------------------
│ TCP Header │
----------------------
│ NETBIOS Header │
----------------------
│ SMB Base Header │----------------------
│ SMB Command Header │----------------------
│ DATA │----------------------
“SMB Base header”包含了几种信息,像接收缓冲区的长度,允许的最大连接数目……它也包含了一个鉴别请求命令的数字。
“SMB Command header”包含了所有的请求命令的参数(像磋商协议版本命令……)。
“DATA”容纳了请求命令的数据。
我们把“SMB packet”看成:NETBIOS Header + SMB Base Header + SMB Command Header+ DATA。
注意:我将使用这个定义:
typedef unsigned char UCHAR; // 8 unsigned bitstypedef unsigned short USHORT; // 16 unsigned bitstypedef unsigned long ULONG; // 32 unsigned bits
而STRING被定义为以空字符结束的ASCII字符串。
NETBIOS与SMB
NETBIOS(NETwork Basic Input and Output System)在微软的网络系统中被广泛使用。它是一个软件接口和命名系统。每台主机都有一个长度为15个字符的NETBIOS名字,且第十六个字符用来标志主机的类型(域名服务器,工作站……)。
第十六个字符的选择:
0x00 基础电脑,工作站。0x20 资源共享服务器。
这还有一些其他的值可选,不过我们对这两个最感兴趣。第一个(0x00)鉴定一台工作站,第二个(0x20)鉴定服务器。
在一个SMB数据报中,NETBIOS头部对应NETBIOS会话头部。
定义如下:
UCHAR Type; // Type of the packetUCHAR Flags; // FlagsUSHORT Length; // Count of data bytes (netbios header not included)
“Flags”域的值总是被置为0。
“Type”域有几种可能的选择:
0x81 对应一个NETBIOS会话请求。这个代码在客户端发送它的NETBIOS名字到服务器是使用。
0x82 对应一个NETBIOS会话应答。这个代码在服务器向客户端批准NETBIOS会话时使用。
0x00 对应一个会话消息。这个代码总是在SMB会话中被使用。
“Length”域包含了数据字节的长度(NETBIOS头部没有被包含在内)。数据包含在NETBIOS头部以上的所有部分(它可能是 SMB Base Header + SMB Command Header + DATA 或 NETBIOS名字)。
NETBIOS名字与编码。
NETBIOS编码名字的长度为32字节。
NETBIOS名字总是以大写的形式存在的。
编码一个NETBIOS名字非常的简单。例如我的计算机的NETBIOS名字是“BILL”,它是一个工作站,所以它的第十六个字符为“0x00”。
首先,如果一个NETBIOS名字比15字节短,就会在右边补填上空格。
“BILL “
十六进制为: 0x42 0x49 0x4c 0x4c 0x20 0x20 ......0x00
每个字节都分裂为4位一组:
0x4 0x2 0x4 0x9 0x4 0xc 0x4 0xc 0x2 0x0 .......
而且每个4位都要添加ASCII码‘A’的值(0x41)。
0x4 + 0x41 = 0x45 -> ASCII value = E0x2 + 0x41 = 0x43 -> ASCII value = C……
最后NETBIOS名字被编码为32字节长。
注意:
SMB可以直接运行于TCP之上而无须NBT(在Windows 2k和XP上它们使用455端口)。此时,NETBIOS名字没有被限制在15字符以内
STDIN
first is that, I can write script to using STDIN instand of type in by hand. for example, there is a command: smb -U username password servicename. it can lead us into the windows share dirve on Linux service platform. however, when we get into this sharedrive, we need to type command into this program, which means we are in this program. but how can I use script to execute command in sequence? using STDIN. there are two ways, first is like this to write in script:
- smb -U zliybsj2 $1 //10.2.1.21/Central_Application_Center <<>
- ls
- exit
- EOF
first, script will using $1 as possward to login Central_Application_Center, then input ls, run it and exit, run again and finish to goto the next command. here EOF is a labell.
another way to write is creating another file, such as com1, we write what we want to do after we get into Central_Application_Center. so, as follow:
- smb -U zliybsj2 $1 //10.2.1.21/Central_Application_Center <>
in com1:
- ls
- exit
There is another way to test when a script or program is runing well by using returning number. as follow:
- succ=0
- smb -U zliybsj2 $1 //10.2.1.21/Central_Application_Center <>
- if [ succ -ed $? ]; then
- echo running_well
- else
- echo some_mistakes_happened
- fi
here, $? stands for the retunring number of last program. so if we can complete the left part, such as however to create a pasward, the do this loop to guess, this is the most stupid way to decrypt, if for us time is not a problem. just a joking.
awk
- deal with text file which is thought of as being made up of records and fields. we can write programing by awk to do anything we want.
- we can:execute UNIX command from within a script; process the output from UNIX commands; work with multiple input streams; define functions.
- we can combined with sed and shell scripting. compared: shell is very easy and quick to write, but lacks functionality. sed, awk, and shell are designed to be integrated.
invoke:
- awk [options] 'script' var=value file(s)
- awk [options] -f scriptfile var=value file(s) : we can have more than one -f scriptfile.
- a literal: awk -f scriptFile count=5
- a shell variable: awk -f scriptFile count=$count
- A command substitution: awk -f scriptFile count=`who wc-l`
set filed seperator:
- using -F
- one line can be sperated into different filed and can be refered by variables $1, $2 etc. $0 means the whole record.
awk script consist of patterns and procedure:
- a pattern can be : /regular expression/, eg /^...:/ or relational expression, eg $1=="gdm". ~ means match, !~ means don't match, eg awk -F: '$1 ~ /.dm.*/ {print $0}' /etc/passwd. BEGIN specifies procedure to take place before the first input line is processed, END as well, eg awk ‘BEGIN {print “Version 1.0”}’ dataFile. pattern missing, the procedure applies all lines
- procedure is arround by {} and seperated by newlines or semi-colons. can be: commands, functions and veriable assignment. procedure missing, printed all lines matched by pattern.
commands used with procedures: 5 types
- Assignments of variables or arrays
- Commands that print
- Built-in functions
- Control-flow commands
- User-defined functions (in nawk only)
awk Built-in Variables:
- FILENAME - current filename
- FS - Field separator
- NF - Number of fields in current record
- NR - Number of current record
- RS - Record separator
- $0 - Entire input record
- $n - nth field in current record
awk operators: $_++_ --_ +_-_!_*_/_%_<_<=_>=_>_!=_==_~_!~_in_$$__?:_=_+=_-+_*=_/=_%=
two ways to usingarrays in awk:
- in an assignment statement: myArray[i]++
- split() function : n=splict(input,words," ") : splict this input by " "(whitespace) into words.
functions in awk: works in the same way as java: calling a function, no sapce between function name and left bracket.
Wednesday, 18 April 2007
Graphical User Interface Programming
Introduction to GUI Programming
Event-driven Programming: program responds to these events. The order of the events is determined by the user, not the program. This is similar to going to a hardware store to get components for your home improvement project. Most of the components you need already exist. All you need to do is to install them.
Java GUI Programming:A user interacts with a GUI application by causing events. The application must respond to events in the order they arrive.
Three Parts of a GUI Program:
- Graphical Components make up the Graphical User Interface.
- Listener methods receive the events and respond to them.
- Application methods do useful work for the user.
The graphical components are Swing objects. You may use them without change or may extend them to make your own classes. Listener methods and application methods are Java methods that you write. Listener methods respond to events by calling application methods. Application methods are ordinary Java methods that perform useful computations. They receive data from the GUI and send data to the GUI to be displayed, but are not usually themselves concerned with the user interface.
To write a GUI application, keep these three types of software separated (while keeping the big picture in mind). In a big software project an entire team of programmers is assigned to each of the tasks.
Container Classes: A GUI program consists of a collection of graphical components that are all placed inside one or more windows. A container is an object that can hold other GUI components. In Java terminology, a window (such as the browser window you are looking at) is a container. The buttons, sliders, icons and other GUI components are contained (by the container).
AWT Hierarchy: Some of the AWT classes derived from Component are Button, Canvas, and Container. The JComponent class is derived from Container and is one of the base classes of Swing. The JFrame class is derived from the AWT Frame class. It is usually the main container for a GUI application.
JComponent class: Objects of classes based on Container have common characteristics. They can contain components, they themselves can be placed inside containers, they can be displayed on the monitor, they generate events, they register event listeners, and so on. Since all Swing classes have Container as an ancestor, all Swing objects have these characteristics.
Swing JFrames:
Frames: In Java, a frame is a window that has nice borders, various buttons along the top border, and other features. What you usually call a "window" Java calls a "frame". A frame is a container object, so GUI components can be placed in it. a frame object is actually a section of main memory that holds information and methods. With the help of the operating system and the graphics board.
Small GUI Program
First a JFrame is created by invoking its constuctor. The argument to the constructor sets the title of the frame. The setSize(200,100) method call makes the rectangular area 200 pixels wide by 100 pixels high.
The setVisible(true) method call makes the frame appear on the screen. If you forget to do this, the frame object will exist as an object in memory, but no picture will appear on the screen. A call to setVisible(false) makes the frame invisible, but does not destroy the software object.
It is easy to forget to include setVisible(true). If you run your GUI program, and nothing happens, check that you have called this method.
The setDefaultCloseOperation() method picks the action to perform when the "close" button of the frame is clicked. This is the little button usually at the top right of the frame. If you forget to call this method with the appropriate constant, clicks on the close button will be ignored.
Running the GUI Program:
The usual way of writing a GUI is to define your own class by extending the JFrame class.
The drawString() method: When the Java system needs to paint a MyFrame object it first draws most of the picture and then calls paint() in the MyFrame object to do whatever extra the programmer wants. The first part of the work is vital. It involves interacting with the graphics of the computer system and controling the graphics board. The parameter g is a reference to a Graphics object. The Graphics object represents the part of the frame that you can draw on. When the system calls paint(), the system provides a value for this parameter. One of the methods of Graphics is drawString(String st, int X, int Y) which draws a string on the graphics area at location starting X pixels from the left and Y pixels from the top.
Buttons and Actions
JButton->AbstractButton->JComponent->Container->Component->Onject
To construct a JButton object, use new. Then add the button to the frame's content pane. The content pane is a container that represents the main rectangle of the frame. To get a reference to the content pane, use the getContentPane() method of the frame. The add method of a content pane puts a JButton (or other component) into the frame.
The ButtonFrame class does not to define a paint() method because everything in the frame is a Swing component. The system will automatically paint all components in a container when it needs to. If special processing is needed, (as with drawString() in the previous chapter), then you need to override paint().
The program in the previous chapter did not define a constructor because the constructor it inherited from its parent class JFrame was enough to do the job. ButtonFrame adds a components, and this should be done in a constructor.
Layout Manager:
When you add() buttons (and other components) to a content pane, a layout manager automatically decides what size they will be and where they will go. This is convenient, because you can add components without worrying about the details. The layout manager is like a little artist inside the computer. You say what components you want and the layout manager lays them out in the picture.
The layout manager sometimes makes odd choices. However, there are several kinds of layout managers. Each layout manager has a different style of positioning components. Usually there is a layout manager that will do the job you want. If you don't specify otherwise, a default layout manager is used.
Our program will look better if it uses the FlowLayout manager. The FlowLayout manager puts components into the frame row by row in the order they are added.
Event Listener Object
For a program to respond to an event there must be an event listener object for it. The event listener object contains listener methods for various types of events
Event Object
An event listener is an object that "listens" for events from a GUI component, like a button. An event is represented as an object. When the user generates an event, the system creates an event object, which is then sent to the listener that has been registered for the GUI component.
To be able to respond to events, a program must first:
Create an event listener object for the type of event.
Register the listener object with the GUI component that generates the event (or with a component that contains it).
ActionListener
A button listener class must implement the ActionListener interface. ActionListener is an interface (not a class) that contains the single method: public void actionPerformed( ActionEvent evt) ;
The ActionEvent parameter is an Event object that represents an event (a button click). It contains information that can be used in responding to the event. Since ActionListener is an interface, you use it with a class that will implement the actionPerformed() method. It is common to implement the interface in the same class that contains the button(s):
For the ActionListener interface, there is only one method: actionPerformed().
The repaint() method called in actionPerformed()tells the system to repaint the screen sometime soon because we have changed something. The system will do this when it is ready. Don't call paint().
The frame will be the listener for the button.
button's life in a frame:
- JButton newButton=new JButton(***) ; //create a new JButton object and assign to newButton
- newButton.addActionListener(this);//addactionlistener
- getContentPane().add(newButton);//add into JRame
- public void actionPerformed(ActionEven e){***}//action performeed. everytime, when a even happened, such as mouce moved, if such kind of event has been registed, than a even object is created and have certain action performeed, after performed, then program executes next statement or event, or this performemt will not stop. so we can see is a button is released on show which means relevant actionPerformed has been successed done. if this even is not registed, system just ingnore them.
Buttons and Action Events
setActionCommand() and getActionCommand() method refer to different action, it will pass or return String to distingish different button event. which can help us to deal with different event in actionPerformed() method.
Swing Text Fields and Labels:
A Swing Component: JTextField
A JTextField is a box that contains text. The user can type text into the box and the program can get it and then use it as data. The program can write the results of a calculation to a JTextField.
To enter text into the field you must first click the mouse pointer inside of it. This gives the field the keyboard focus (usually just called focus). When a component has focus, characters from the keyboard are directed to that component. A component gets focus by various means. The user might click it, or the program might give it focus.
JTextArea+JTextField+JEditorPane -> JTextComponent->JComponent->Container->Component->Object
The JLabel Class
In a typical application with a graphical interface, about 40% of the code manages the user interface. The rest of the code is for the application--the reason the program was written. Usually the application code is kept separate from the code that manages the interface. In a big application it would be confusing to mix the two together.
The GUI components from Swing can be used by applets.
It is a good idea to keep the GUI code and the application code in separate modules to help in debugging and understanding the program. This is also helpful if you later need to make changes to the program, say changing it from an application to an applet. The application code can be carried over without change.
The user can type into a JTextField even if it does not have a listener. getText() will still work
JPanel and BoxLayout
Each panel uses its own layout manager for the components it contains. The default layout manager of JPanel is flow layout, which is often ideal. But you may use another layout manager if appropriate.
BoxLayout Layout Manager
BoxLayout. This layout manager aligns components either horizontally or vertically within a pane. BoxLayout(Container box, int axis)
box: the container this layout manager is for axis: BoxLayout.X_AXIS -- for left to right alignment BoxLayout.Y_AXIS -- for top to bottom alignment . box is a reference to the container which will be managed by this layout manager. Often the container is a content pane.
This idea of nesting panels is a powerful one. It may look complicated and tedious, but it is much less so than laying out a design on graph paper and specifying the exact size and location of all the components. Such a design has no flexibility. What happens if you want to add or delete a component? Everything must change. With Java's layout managers everything is dynamically adjusted.
Radio Buttons, BorderLayout, and Glue
Radio Buttons
Usually radio buttons are placed in (1) a panel, to control how they are displayed, and (2) a button group, to control which buttons may be active simultaneously. A button group is an object which must be constructed. Radio buttons are then added to it.
Radio buttons generate action events which require a registered action listener. Do this as with JButtons. Use setActionCommand() to assign a command string to each button. Use addActionListener() to register a listener for each button, usually the same listener for all the buttons in a group. Use getActionCommand() in the action listener to determine which button was pushed.
BorderLayout
BorderLayout.is a frequently used layout manager. The container it manages corresponds to a rectangle on the screen. That rectangle is divided up into five regions:
- BorderLayout.NORTH,
- BorderLayout.SOUTH,
- BorderLayout.EAST,
- BorderLayout.WEST,
- BorderLayout.CENTER.
Each region may hold only one component, although that component may be a panel (and usually is). The panel may contain several components. The layout manager adjusts the size of the regions depending on what is in them. You don't have to put a component in each region. If a region has no component in it, it shrinks to a small area.
Class Box
Layout managers sometimes jam components together in a way that makes the layout look cramped. The class Box can help in this situation. A Box object is a container similar to a panel, but lacking some features. The default layout manager of Box is BoxLayout. However, the most useful features of class Box are its methods that create invisible components. These components correspond to rectangular areas of the screen. They are used as spacers to separate the visible components. If you have ever set type you know how useful spacers are in creating an attractive page. To create a fixed-sized invisible component use the method: Box.createRigidArea( new Dimension( int width, int height ) )
The parameter to createRigidArea()is a Dimension object, which does little more than hold a width and a height.
All GUI components have a getSize() method that is used to determine the dimensions of the component. The dimensions may change as a program executes, so this is a useful method. To determine the current size of a frame, use: Dimension JFrame.getSize()
Then it can look at the height and width fields of the Dimension object. Using this data it can create a rigid area of appropriate size. If this is too complicated, then use glue.
The glue component is another invisible component that class Box creates. Think of glue as stretchy caulking between components. It keeps them separated, but expands or shrinks as needed.
To create glue use one of the following:
- Box.createHorizontalGlue()
- Box.createVerticalGlue()
Class JSlider
JSlider( int orientation, int min, int max, int init )
orientation: SwingConstants.HORIZONTAL or SwingConstants.VERTICAL
min: the minimum value. The value when the slider is at the extreme left (or very bottom) of its range.
max: the maximum value. The value when the slider is at the extreme right (or very top) of its range.
init: the initial value of the slider
- JSlide silderV=new JSlide(SwingConstants.HORIZONTAL, 0, 100, 79)
- slideV.setMajorTickSpacing(10);
- slideV.setMinorTickSpacing(10);
- sliderV.setPaintTicks(true);
- sliderV.setPaintLabels(true);
- sliderV.setSnapToTicks(true);
setPreferredSize()
The layout managers have control over the size of components, but often do their job better if you indicate a preferred size. This is done with setPreferredSize( new Dimension( int width, int height )
If this is not used, the graphical representation of a slider often has its labels and tick marks crowded together
A listener for a slider implements the ChangeListener interface. This interfaces has a single method: public void stateChanged(ChangeEvent evt)
An object that implements the interface must be registered with the slider in order to receive events: slider.addChangeListener( ChangeListener lstn )
There may be several sliders in your user interface. They all generate change events. If one change listener listens to all these events it is convenient to give the sliders names so that the events can be sorted out correctly. (Another way is to register its own listener with each slider). A name is a string that can be assigned to any object that inherits from class Component. Assign it using: component.setName( String name )
Of course you must make sure that components that share the same listener have unique names.
The Object getSource() Method
An event object contains a reference to the component that generated the event. To extract that reference from the event object use: Object getSource()
Since the return type of getSource() is Object you typically use a type cast with it: // listener method
public void stateChanged( ChangeEvent evt )
{
JSlider source;
source = (JSlider)evt.getSource();
. . . .
}
Now that you have a reference to whichever slider caused the event you can use any of the slider's methods.
Assume that the slider has a name you have set using setName(). The name of the slider is a string that is stored as part of its data. To ask the slider for its name use: String getName()
Then, to get the value of the slider use int getValue()
The value is an int between the minimum and maximum value of the slider.
In the previous application the number in the text box changes continuously as the knob is moved. Usually this is desirable. But sometimes the application calls for a great deal of work and you don't want to do it for each change event. There are (potentially) hundreds of change events generated in moving the knob from one value to the next. While the value is still changing the listener should discard the event. boolean getValueIsAdjusting()
This method returns true while the knob is still moving.