Monday, August 31, 2015

String

在Java里,String是一个类(class)。这个类包含char数组(array),以及其他的字段(fields)和方法(methods)。

常用方法(Java):
toCharArray() //get char array of a String charAt(int x) //get a char at the specific index length() //string length length //array size 
indexOf(String s) // return the index of the substring s in string.
split(String pattern) // split the String with string pattern. substring(int beginIndex) substring(int beginIndex, int endIndex) Integer.valueOf()//string to integer String.valueOf()/integer to string Arrays.sort() //sort an array Arrays.toString(char[] a) //convert to string Arrays.copyOf(T[] original, int newLength) System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

注意事项(Java):
1. String is immutable. 也就是说string在被创建以后,在heap上不能被改变,任何的改变都会创建一个新的string object。
2. 如果想用可以改变的String,就需用StringBuffer或者StringBuilder。
3. String immutable的原因:
    1) Efficiency: Caching hashcode;
    2) Security: Security; thread safe; no violation for other objects (HashSet etc.)
4. 初始化String,用"" 还是 new String():
    主要在于interning,如果用"sss",那么会指向heap上已有的"sss",这样的话==是true。否则,会有两个"sss", equals()为true,但是==为false。
5. Array用length (length是Array object的一个final instance variable(不会变)). String用length(),是String这个class的一个method。
6. Varargs (Variable Arguments)
    As its definition indicates, varargs is useful when a method needs to deal with an arbitrary number of objects. One good example from Java SDK is String.format(String format, Object... args). The string can format any number of parameters, so varargs is used.
String.format("An integer: %d", i);
String.format("An integer: %d and a string: %s", i, s);


常见问题:
1. 转化一个char[] to String
public static void main(String[] args) {
  char[] myString = new char[] {'T', 'H', 'I', 'S', ' ',  'I', 'S', ' ', 'T', 'E', 'S', 'T'};
 
  String output1 = new String(myString);
  System.out.println("output1 : " + output1);
 
  String output2 = String.valueOf(myString);
  System.out.println("\noutput2 : " + output2);
 }

2. 转化String to char[]
toCharArray()

3. String to int
Integer.valueof(s);
or
Integer.parseInt(s);

4. String相关的问题,经常会用到char[],经常会遍历,用几个pointer标记位置的方法也是常用的。

5. for-each
char[] cArray = s.toCharArray();
for (char c : cArray)
这里c gets a copy of each value in cArray!

Friday, August 28, 2015

Java Heap Memory Size

Java Memory:
1. Java Heap Size
    Place to store objects created by your Java application, this is where Garbage Collection takes place, the memory used by your Java application.
    For a heavy Java process, insufficient Heap size will cause the popular java.lang.OutOfMemoryError: Java heap space.
    -Xms<size> - Set initial Java heap size
    -Xmx<size> - Set maximum Java heap size
    $ java -Xms512m -Xmx1024m JavaApp

2. Perm Gen Size
    Place to store your loaded class definition and metadata.
    If a large code-base project is loaded, the insufficient Perm Gen size will cause the popular Java.Lang.OutOfMemoryError: PermGen.
    -XX:PermSize<size> - Set initial PermGen Size.
    -XX:MaxPermSize<size> - Set the maximum PermGen Size.
    $ java -XX:PermSize=64m -XX:MaxPermSize=128m JavaApp

3. Java Stack Size
    Size of a Java thread. If a project has a lot of threads processing, try reduce this stack size to avoid running out of memory.
    -Xss = set java thread stack size

Command to find out heap size
    $ java -XX:+PrintFlagsFinal -version | grep -iE 'HeapSize|PermSize|ThreadStackSize'

I/O Classes and Objects in Java and Read a Line

System.out is a PrintStream object that outputs to the screen
System.in is an InputStream object that reads from the keyboard

But System.in doesn't have methods to read a line directly.  There is a method
called readLine that does, but it is defined on BufferedReader objects.

- How do we construct a BufferedReader?  One way is with an InputStreamReader.
- How do we construct an InputStreamReader?  We need an InputStream.
- How do we construct an InputStream?  System.in is one.
(You can figure all of this out by looking at the constructors in the online
Java libraries API--specifically, in the java.io library.)

InputStream objects (e.g. System.in) read raw data from some source (like Keyboard), but don't format the data.
InputStreamReader objects compose the raw data into characters (2 bytes long in Java).
BufferedReader objects compose the characters into entire lines of text.

Java program that reads a line from the keyboard and prints it on the screen.
 import java.io.*;

class SimpleIO {
     public static void main(String[] args) throws Exception {
          BufferedReader keybd = 
               new BufferedReader(new InputStreamReader(System.in));
          System.out.println(keybd.readLine());
     }
}

How to read a line of text: With readLine on BufferedReader
How to create a BufferedReader: With an InputStreamReader
How to create a InputStreamReader: With an InputStream
How to create InputStream: With a URL

public class BufferedReader extends Reader
BufferedReader is a class 

Code:
import java.net.*;
import java.io.*;
class WHWWW {
    public static void main(String[] arg) throws Exception {
        URL u = new URL("http://www.whitehouse.gov/");
        InputStream ins = u.openStream();
        InputStreamReader isr = new InputStreamReader(ins);
        BufferedReader whiteHouse = new BufferedReader(isr);
        System.out.println(whiteHouse.readLine());
    }
}

Thursday, August 27, 2015

常见数据结构操作和算法复杂度

Source: http://bigocheatsheet.com/

Legend

ExcellentGoodFairBadHorrible

Data Structure Operations

Data StructureTime ComplexitySpace Complexity
AverageWorstWorst
AccessSearchInsertionDeletionAccessSearchInsertionDeletion
ArrayO(1)O(n)O(n)O(n)O(1)O(n)O(n)O(n)O(n)
StackO(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)
Singly-Linked ListO(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)
Doubly-Linked ListO(n)O(n)O(1)O(1)O(n)O(n)O(1)O(1)O(n)
Skip ListO(log(n))O(log(n))O(log(n))O(log(n))O(n)O(n)O(n)O(n)O(n log(n))
Hash Table-O(1)O(1)O(1)-O(n)O(n)O(n)O(n)
Binary Search TreeO(log(n))O(log(n))O(log(n))O(log(n))O(n)O(n)O(n)O(n)O(n)
Cartesian Tree-O(log(n))O(log(n))O(log(n))-O(n)O(n)O(n)O(n)
B-TreeO(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
Red-Black TreeO(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)
Splay Tree-O(log(n))O(log(n))O(log(n))-O(log(n))O(log(n))O(log(n))O(n)
AVL TreeO(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(log(n))O(n)

Array Sorting Algorithms

AlgorithmTime ComplexitySpace Complexity
BestAverageWorstWorst
QuicksortO(n log(n))O(n log(n))O(n^2)O(log(n))
MergesortO(n log(n))O(n log(n))O(n log(n))O(n)
TimsortO(n)O(n log(n))O(n log(n))O(n)
HeapsortO(n log(n))O(n log(n))O(n log(n))O(1)
Bubble SortO(n)O(n^2)O(n^2)O(1)
Insertion SortO(n)O(n^2)O(n^2)O(1)
Selection SortO(n^2)O(n^2)O(n^2)O(1)
Shell SortO(n)O((nlog(n))^2)O((nlog(n))^2)O(1)
Bucket SortO(n+k)O(n+k)O(n^2)O(n)
Radix SortO(nk)O(nk)O(nk)O(n+k)

Graph Operations

Node / Edge ManagementStorageAdd VertexAdd EdgeRemove VertexRemove EdgeQuery
Adjacency listO(|V|+|E|)O(1)O(1)O(|V| + |E|)O(|E|)O(|V|)
Incidence listO(|V|+|E|)O(1)O(1)O(|E|)O(|E|)O(|E|)
Adjacency matrixO(|V|^2)O(|V|^2)O(1)O(|V|^2)O(1)O(1)
Incidence matrixO(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|V| ⋅ |E|)O(|E|)

Heap Operations

TypeTime Complexity
HeapifyFind MaxExtract MaxIncrease KeyInsertDeleteMerge
Linked List (sorted)-O(1)O(1)O(n)O(n)O(1)O(m+n)
Linked List (unsorted)-O(n)O(n)O(1)O(1)O(1)O(1)
Binary HeapO(n)O(1)O(log(n))O(log(n))O(log(n))O(log(n))O(m+n)
Binomial Heap-O(1)O(log(n))O(log(n))O(1)O(log(n))O(log(n))
Fibonacci Heap-O(1)O(log(n))O(1)O(1)O(log(n))O(1)

Big-O Complexity Chart

Big O Complexity Graph