Bowen's Tech Blog

Some common Python library.

Notes of book Introduction ot Robotics Mechanics and Control.

There is a lot of development frameworks for Java. This post talks about Guice (for Dependency Injection design pattern implementation), Spring (Java integration environment), JUnit and Mockito (for unit test).

Keywords and features

Common Use

• new
  • Create instance for value type and reference type
    • For int, is used to configure the value to 0
    • Will automatically call the constructor
  • In derived class, hide the inherited method from base class
  • Cannot be override
• base
  • Access Keywords
  • Call the public or protected methods in base class.
  • If the base class has this method, call that method; If not, recursively call the base class of the base class
• this
  • Access Keywords
  • Refer to current instance of object
• using
  • Import namespace (library)
  • Rename the importing namespace
  • Force to release the non-managed resource (Generate a try-finally block, and put the Dispose method in finally block) for a single object
• About Null
  • null: Means a reference type points to nothing
  • Nullable<T>
    • Is the same with T?
    • Allow value type to support the NullException
  • null object
    • Is a sub class of original class but defined the property IsNull
    • Can implement INullable interface
  • ??
    • (A ?? B): return the non-null object. Check A firstly
• Data type convert
  • Must be static
  • Will be transferred to a method in IL
  • Explicit
    • Explicit convert a data type
    • public static explicit operator XX(para)
  • Implicit
    • Implicit convert a data type
    • public static implicit operator XX(para)
• Precompile keywords
  • #if, #else, #elif, #endif
    • Use to determine whether compile a block of code
    • Use ConditionalAttribute could also achieve the conditional compile. Like [Conditional("Debug")]
  • #define, #undef
    • Work with other precompile keywords together, e.g. #define Debug for the conditional compile
  • #warning, #error
    • Add reminders which shows when compiling the code
  • #region, #endregion
  • #pragma

Less Use

• checked, unchecked
  • Turn on/off the overflow check during the operation and type converting
• yield
  • Can only appear in a enumerator block
  • yield return is used to return a value in the enumerator. The return type of the method belongs to System.Collections.Generic.IEnumerator<T>, System.Collections.IEnumerable or etc.
  • yield break is used to end the enumerating.
• lock
  • Use lock(xx) to add a lock for the xx object, so that if other threads want to call this object, they need to wait current thread to finish the process on this object.
  • the object to lock should be a reference type, it’s better to be private
• unsafe
  • To allow to use *, &, sizeof to avoid the CLR and operate the memory
• sealed
  • For sealed class, it cannot be inherited by other class
  • For sealed method, it appear with override keyword together
• Name: is the property of Type
  • Name: type name
  • Property Name: type name containing the namespace
  • AssemblyQualifiedName: type name containing the namespace and assembly

Constant

• Once const or readonly values are assigned a value, the value couldn’t be changed.
• const
  • Only support the value type and string, and not support new keyword
  • It should be assigned value when it declares.
  • It should be determined during the compile instead of in CLR (operating the memory).
  • When compile to IL code, it will turn to private static member. Can be get only through the class
• readonly or static readonly
  • Support any type
  • It could be assigned value in the constructor or when it is declares. Constructor is prior to declares
  • It is compiled to private member and the value is determined in CLR. Can be get through the object

Class and Struct

• Class
  • Reference type, instance is stored in the managed heap
  • Used to show actions
  • Contains field, property, method, constructor, indexer, operator
• Struct
  • Value type, instance is stored in the stack
  • Used to store data
  • Contains field, property, method, constructor, indexer, operator
    • Not support constructor without parameters
    • All members should be public
    • Don’t required to use new to instantiate
  • Only support inherit from interface, can override virtual method

Attribute and Property

Actually they have no relationship to each other.

Attribute

• Is a class, inherit from System.Attribute
  • Support customized, can include new method
• Initialize during the compile, Stored in metadata, provide support relevant info or show info for the targeted element in CLR
  • Targeted element include: assembly, module, type, property, event, field, method, param, return
  • Use [], support multi attribute
• The info of attribute can be get through reflector
• Used for compile command and some actions
• Example
  • [AttributeUsage()]: Control how to apply customized attributes to targeted element
  • [Flags]: Regard the value of enum as bit flag rather than value
  • [DllImport()]: Call the un-managed code. e.g. Win32 API method
  • [Serializable]: Indicate the element could be serialized
  • [Conditional()]: Support the conditional compile

Property

• Encapsulation for private field in class

Interface and abstract class

See here for more info.

Class can implement interfaces and inherit another class.

Interface doesn’t inherit from System.Object. Methods in an interface are abstract methods, so interface cannot be instantiated but only be implemented by other classes. Classes implement one interface need to implement all the abstract methods or properties in the interface. It supports the polymorphisn.

For abstract class, it also contains the abstract methods and the abstract class cannot be instantiated but only be inherited. Classes which inherits a abstract class need to implement all the abstract methods. Apart from the abstract methods, the abstract class can also include some public and virtual methods which contains the body. So the subclass can use those methods directly. It supports the polymorphisn.

Some use cases are as follow.

is and as

Subclass converting to base class can be achieved implicitly, while base class converting to subclass needs to be achieved explicitly.

• is: Is used to determine whether this type can be converted to another type. Return false is object is null.
• as: Convert the type. Return null if object is null.

Override and Overload

Deep copy and Shallow copy

Use = for value type is deep copy; Use = for reference type is mainly shallow copy. (String is deep copy)

Inherit interface ICloneable to customize the Object Clone() method. e.g. return a new object

Static and non-static

Use static field to define a Singleton class.

Dynamic

Dynamic is the keyword and a class. It can be used for field, property, method, indexer, parameters, return value, local variable. The specific type of the element declared dynamic will be determined during the CLR/DLR.

Dynamic solve the dynamic bind for objects. It combines C# with other dynamic language like IronPython, IronRuby.

1
2
3

ScriptRuntime py = Python.CreateRuntime();
dynamic mypy = py.UseFile("XX.py");
Console.WriteLine(mypy.Method());

Dynamic can also dynamically add a filed or property to a class.

Special Object Types and Methods

System.Object

Object is the top base class for any other classes in .NET C#. The base methods of System.Object contains:

• GetType
  • the type could use GetMembers and GetMethods to get the instance of this type
• ToString: get the full name of the type
  • Can be override by subclass
• Equals, ReferenceEquals, ==: check whether equals
• MemberwiseClone: Shadow copy
• GetHashCode
• Finalize

Equals

• public virtual bool Equals(object obj)
  • Default it checks whether points to the same instance
  • Will be override by subclass
    • Check null
    • Check ReferenceEquals
    • Check whether the same type
    • Customized compare 2 fields
  • Need to override the GetHashCode the same time
    • A equals B => A.HashCode = B.HashCode
• public static bool Equals(object objA, object objB)
  • Check whether 2 objs are points to same instance
  • Check whether 2 objs are both null
  • Use objA’s virtual equals method
• public static bool ReferenceEquals(object objA, object objB): compare whether 2 objects are points to the same instance
  • Can only compare two reference type
  • When compare two value type, will lead to the boxing, then the result is False
• ==
  • For value type, it compare whether the two values are the same
  • For reference type, it compare whether the two objects point to the same instance

Note: String is a very special type.

Constructor

There are two kinds of constructors. Their IL forms are as follow.

• .ctor: object constructor
  • Called when new an object
• .cctor: type constructor (static constructor)
  • Called when need to assign value to static members
  • Customized code in static constructor will be called after assigning values to static members.
  • Accurate time to call
    • precise
      • If the static constructor is implemented
      • The constructor needs to be executed before the first time use the type
    • beforefieldinit
      • If the static constructor is not implemented
      • The constructor can be executed any time

.NET also provide a flexible constructor to allow to set the properties in the constructors.

1

User user = new User {Name = "aa", Age = "bb"};

String

String is a sealed class. It is a reference type but shows value type features when using.

Immutability. Once a string is created in the memory, it cannot change. Any actions including Insert, Substring, ToUpper will create a new string.

String interning. When the CLR loads, it will create a resident pool. This pool won’t be controlled by GC or Every unique string value in code will store in this resident pool. CLR will also create a hash map, the key is the string stored in resident pool and the value is the address. When creating a string value by assigning a unique value, it will store that value in resident pool and assign the address to this string. When assigning a value appeared before, CLR will assign the address checking from hash map to this string.

Note. If a string is assigned dynamically e.g. assigned by other string, the result value of this string won’t be stored in the resident pool. Use System.Intern(xx) can add it to resident pool.

For convert. Some value types already override the ToString method for converting itself to a string. To convert a string to other value types. e.g. Double.Parse(str), Double.TryParse(str, out num), num = Convert.ToDouble(str)

StringBuilder can help to append several strings and convert to a string together.

Enum

System.Enum inherits from System.ValueType. Default, the first element equals to int 0. The value of the element can also equals to bit number 0x00 if the attribute [Flags] is added to the enum. At this time, a enum variable supports the | operation.

Common methods contain

• GetNames(typeof(X)): Get all names of the enum
• GetValues(typeof(X)): Get all value of the enum
• IsDefined(typeof(), XX): Check whether the name of value in the enum

Collections

Collection is a container to control a bunch of objects. The collection can be treated as a whole object and every object can also be get separately.

Collection is a class in .NET. The common methods for most collections types include:

For a collection, it should implement the IEnumerator interface, which support MoveNext and Reset methods, and Current property. Then in C#, users can use foreach to get the value from the enumerator.

For a collection, it should implement the Synchronized method, which support for the safe action on the object in the multi-thread code.

The category of collections include:

• Ordered Collection: only implement ICollection
  • Stack
    • Stack<T>
  • Queue
    • Queue<T>
• Index Collection: implement IList
  • Array
    • Fixed length
    • Only support the same type
    • Several dimension
    • Cannot insert or remove values
  • ArrayList
    • Dynamic length
    • Support different type
    • 1 dimension
    • Can insert or remove values
    • List<T>
• Key Collection: implement IDictionary
  • Hashtable
    • The key-value pairs have no order
    • Dictionary<TKey, TValue>
  • SortedDictionary
    • The key-value pairs have order.
  • SortedList
    • Support both index and key-value pair
    • SortedList<T>

For customized collection, users can inherit the CollectionBase abstract class or implement interfaces like ICollection, IList.

Delegate, Anonymous Method, Lambda Expression

Delegate is a class which implements a safe type callback method. Delegate is like the method pointer in C++. It defines the return type and parameters list. A delegate type needs to be instantiated and then added other methods. By calling this delegate directly or use its Invoke method, it could callback other methods added to this delegate.

For multi-methods added to the delegate, it is called multicast. Methods could use += or -= to bind or unbind to the delegate. The order of callback those methods is the same with the order to bind to the delegate.

There is some pre-defined delegate in C#, which include

• EventHandler: void EventHandler(object sender, EventArgs.Empty)
• Func<T, TResult>: TResult Func(T t)

Event model is also based on delegate. It is a encapsulation for delegate. See here for more examples about delegate and event.

Anonymous method is a method without name but have the expression body.

Delegate keyword can be used to declare an anonymous method. The anonymous method can be assigned to a delegate variable.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

delegate void MyDelegateType(int x, int y);
MyDelegateType myDelegateInstance = delegate(int x, int y)
{
    Console.WriteLine(x - y);
}
myDelegateInstance += delegate(int x, int y)
{
    Console.WriteLine(x + y);
    Console.WriteLine(x * y);
}

Func<float, float> myFunc = delegate(int x)
{
    return x + 10;
}

Thread.Start(delegate()
{
    // Do some tasks
});

Lambda Expression can also be used to declare an anonymous method. The form is Argument => expression or (Arguments) => {expression}. Compared with using delegate to declare anonymous method, it don’t required to declare the type of the arguments because the compiler will set the type automatically.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

MyDelegateType myDelegateInstance = 

delegate void MyDelegateType(int x, int y);
MyDelegateType myDelegateInstance = (x, y) => Console.WriteLine(x - y);
myDelegateInstance += (x, y) => 
{
    Console.WriteLine(x + y);
    Console.WriteLine(x * y);
};

Func<float, float> myFunc = x => x + 10;

Thread.Start(() =>
{
    // Do some tasks
});

Generic

1
2

public class test<T> {}
public class MyDict<TKey, TValue> {}

• Advantages
  • Flexible for any data types
  • Handle one kind of data type at one time, avoid problem in type converting
  • Avoid boxing and unboxing process
• The class cannot be instantiated if the type T isn’t assigned a specific type
• In CLR
  • The instance of generic happens in the JIT compile
  • When T is value type, JIT will generate different naive code by replace the T with different value types
  • When T is reference type, there will only be one copy of naive code
• Some basic generic type in FCL
  • in System.Collections.Generic
  • List<T>
  • SortedList<TKey, TValue>
  • Queue<T>
  • Stack<T>
  • Collection<T>
  • Dictionary<TKey, TValue>

Instantiation

When instantiate a parameterized type field, the default keyword can be used, which will return 0 for value type and null for reference type.

1
2
3
4
5

public class test<T>
{
    T data = default(T);
}

Constraints

The generic can use where keyword to add constraints for the parameterized type.

1

public class test<T> where T: constraint1, constraint2, ...

Generic Method, interface and delegate

Generic method can exist in a generic class or a non-generic class.

1
2
3
4
5
6
7

class MyClass{
    public void ShowInfo<T>(T t) {}
}

// Call above method
MyClass a = new MyClass();
a.ShowInfo<int>(3);

Interface can also have generic features. Some generic collections class implements those generic interfaces. e.g. IList<T>, IComparable<T>

1
2
3

class MyArray<T>: IComparable<T> {}

class MyArray<T>: IComparable<int>, IComparable<String> {}

Delegate can also have generic features. e.g. delegate string MyMethod<T>(T t).

Generic delegate can also use for event. Like EventHandler<TEventArgs>. It is defined as delegate void EventHandler<TEventArgs>(object sender, TEventArgs e)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

using System;

class MyEventArgs: EventArgs
{
    public int Num {get; set;}
    public bool flag {get; set;}
}

class MyClass {
    public event EventHandler<bool> Event1;
    public event EventHandler<MyEventArgs> Event2;
}

MyClass a = new MyClass();
a.Event1 += (sender, e) => // Do some action ;
a.Event2 += delegate(object sender, MyEventArgs e)
{
    // Do some action
};

Using tricks

• Use generic collections to improve efficiency
• Set constraints for generic
• Use EventHandler<TEventArgs> for event definition
• Use Nullable<T> for handling null condition
• Implement IEnumerable<T> for achieving enumerator
• Consider using generic when using System.Object or System.Type
• NOT use generic in Web service

Exception

• try
  • Must use with catch or finally
• catch
  • Can have several catch blocks
  • Catch content category
    • System.Exception
      • DivideByZeroException
      • StackOverflowException
      • FileNotFoundException
      • …
  • Each catch block contains codes to recover from the exception
  • Can use throw to throw the exception
• finally
  • Execute in the end no matter whether exception happens

System.Exception is a class, which contains

• Message: string message
• InnerException: the collections who through the exception
• StackTrack: the stack of calling the method, where the exception begins

Safety

Safety models structure of .NET

• Role-Based Security
  • Role-based security is based on the Principle data. Principal is created by Identity.
  • Principle
    • Implement IPrincipal
    • Contains IsInRole and Identity
    • Instance class includes GenericPrincipal for generic users and WindowsPrincipal for Windows users.
  • Identity
    • Implement IIdentity
    • Contains AuthenticationType, IsAuthenticated, and Name
    • Instance class includes GenericIdentity, WindowsIdentity, FormsIdentity for ASP.NET application and PassportIdentity which requires Passport SDK.
  • Use PrincipalPermissionAttribute or PrincipalPermission class to declarative or explicitly check the access
• Code-Access Security
  • CLR will check the evidence of the application, then determine the permissions of the code according to the security policy. The group of evidence and its permissions forms the code group.
  • Evidence
    • Code’s publisher
    • StrongName
    • Site
    • Application Directory
  • Permissions of code
    • FileIOPermission
    • EnvironmentPermission
    • EventLogPermission
    • …
  • Security Policy
    • Enterprise
    • Machine
    • User
    • AppDomain
  • Use Demand, LinkDeman, Assert to declarative or explicitly check the access
• Windows-User Security

Namespace

FCL Structure

.NET Framework includes CLR (Memory Management, Thread Management and Remote Process) and FCL, which is a object-oriented collection of reusable types. FCL needs to provide API for program and it provides a tree type structure. FCL assemblies is stored as .dll files in disks.

The node of the FCL structure is called namespace, which contains class, struct, enum, delegate, interface. The namespace is only the logic structure of the FCL structure rather than the physical structure of the assembly. The same namespace could stored in different assemblies. Common namespace are as follows.

System Namespace

System namespace contains many basic data type. It includes

• Object
• ValueType
  • Int16, Int32, Char, Boolean, Double
• String
• Array
• Delegate
• Attribute
• Type
• Nullable

It also includes many basic services

• Exception
• GC
• AppDomain: provide a virtual boundary for a program
• Console: control the standard I/O stream
• Environment: get current OS, machine, folder info
• Convert: data type convert
• Math
• Random
• TimeZone

System.IO

It contains handle for the file, folder and memory stream.

• File, FileInfo: create, open, copy, move, delete action for files
• Dictionary, DictionaryInfo: create, open, copy, move, delete action for folders
• Path: provide method to handle the string of the folder path
• Stream: base class of all the stream class
  • Read, Write, Seek, Flush, Close
  • FileStream: specific for file
  • StreamReader, StreamWriter: read and write string to file
  • StringReader, StringWriter: read and write string to memory

System.Runtime.Serialization, System.Xml.Serialization

It is related to the serialization (convert object to a saveable or transmittable format) and deserialization (recover the object from physical material or stream).

• System.Runtime.Serialization
  • Deep Serialization: serialize all properties and filed
  • BinaryFormatter
  • SoapFormatter
• System.Xml.Serialization
  • Shadow Serialization: serialize public properties and filed
  • XmlSerializer

System.Diagnostics

Handle the system process, event log and help to debug.

• Process: control the start and stop of outside program
• Debug, Trace: trace the running status of program

Reference

1. 《你必须知道的.NET（第二版）》，第3部分、第4部分，王涛著

Metadata and IL Language

Metadata and IL Language are the fundamentals of CLR. Metadata describes the static structure and IL Language
describes the dynamic execution.

Metadata

Metadata is fundamental data that is used to describe other complex data.

For the .NET metadata, it is used to describe: class, type, property, method, filed, parameters, attribute. The main category of .NET metadata are:

Below is the metadata to describe the Main function of class Program

![Metadata for the Main function of class program](Metadata.png %}

IL Language

• IL (Intermediate Language) is the language appearing after compile and before compile in CLR. It links the programming language which follows the CLS standard and the machine code.
• It is independent from the CPU command. It is converted to machine code through JIT compile
• It is still object-oriented, and it still owns class, object, inheritance, polymorphisn.

![IL code without reference](ILCodewithoutReference.png %}

IL Grammar

1
2
3

ldc.i4.2    // Load integer 2 to evaluation stack
stloc.0     // Assign the value in evaluation stack to variable 0
brtrue.s IL_XX  // If brtrue is true,  jump to XX line to run

![IL Command](ILCommand.png %}

Metadata, IL works together

IL language uses Metadata Token to refer a metadata, which is a 4 bytes address. Below is the IL code with the reference to metadata.

![IL Code](ILCodewithReferencetoMetadata.png %}

Pipeline for JIT to load metadata and IL program and compile to naive code and call methods.

• JIT uses class loader to load the class structure from metadata to CORINFO_CLASS_STRUCT structure in CLR.
• After loading the class structure to CORINFO_CLASS_STRUCT, all methods are saved in MethodsDesc. Contents for each method are a pointer that points to the method’s IL code. There is also a pointer to trigger the compile of JIt, called PreJitStub.
• When call a method in the class. If it is the first time, JIT will compile the IL code to naive code (machine code), and replace that method’s MethodsDesc with a jmp command which points to the naive code’s line.
• When the method is called again, since the naive code has been generated, the jmp command will be executed automatically.

Initialization in CLR

CLR supports value type and reference type. For a line of code.

1

Person person = new Person();

• Person person: Reference type
  • initobj
  • Initialize the type of the class
  • Set value type of class to 0, and reference type of class to null
• new Person(): Value type
  • newobj
  • Create a space in the heap, initialize pointer and other members used by CLR
  • Call the ctor constructor method
  • Return the pointer of this address

Initialization of some special type

• ldstr: initialize string
• newarr: initialize array
  • only handles the 1-dimension array
  • more than 1-dimension array still requires newobj

Call the method in CLR

IL has two keywords to describe the method type.

• For static method
  • use static keyword to declare
  • Initialize during the compile
  • use call keyword to execute
• For instance method
  • use instance keyword to declare
  • Initialize during the runtime
  • use callvirt to execute

Direct Calling

• call: call the method according to the static type of the reference, mainly used for non-virtual method.
  • Special cases for virtual method
    • Call the virtual method of System.Object Equals, ToString
    • Value type (closed type) call the virtual method
• callvirt: call the method according to the dynamic type (real object) of the reference, mainly used for virtual method.
  • Special cases for non-virtual method
    • In the reference type, it is more safe because it could throw the exception

Indirect Calling

• calli: call the method through a method pointer
  • Use Idftn or Idvirtftn command get the method pointer
  • Based on reflection, MethodInfo.Invoke() and Dynamic Method Delegate

Some Useful Info and Tools

• mscorlib.dll: Microsoft Standard Common Objected Runtime Library
  • Contains base class System.Object
• constructor, see more here
  • .ctor method: class constructor method
  • .cctor method: class type constructor method
• Compile and Decompile Tools (run in .NET SDK Powershell)
  • .cs to .exe
    • csc: can build cs file to metadata or .dll or .exe
  • .cs to .il
    • reflector.exe (need to download)
  • .il and .exe
    • ILASM.exe: IL Assembler, compile .il to .exe
    • ILDASM.exe: IL Disassembler, decompile .exe to .il
      • In the ILDASM, use ctrl + m could view the metadata in that code.

Data types in memory

Common Type System

CTS defines the types and rules for different programming language based on .NET. It defines the relationship between each language with their IL program.

Like in C#, the type of int, char, string corresponds to System.Int32, System.Char, System.String.

.NET Structure

.NET Specification

• Common Type System (CTS): defines the basic types of different .NET languages.
• Common Language Specification (CLS): subset of CTS. The minimum set that .NET language should support.
• Common Intermediate Language (CIL): MSIL. The intermediate language between the .NET language and the naive code. Based on Heap and Stack. Can be compiled to naive code with JIT compiler.
• Common Language Infrastructure (CLI): includes the above elements

The type in the content of CTS includes the following chart.

.NET Implement

• Common Language Runtime (CLR): Control the code to execute.
• Framework Class Library (FCL): Standard types for some fundamental work. Organized in a tree shape with the namespace and the root is System
• .NET Framework: implementation of above 2 elements in Windows platform.

Primitive type in C# and FCL

Value Type and Reference Type

Value Type

• int, char, long, bool, float, double, byte, enum, struct.
• Is allocated in the stack of thread
  • The value type itself contains the data
  • When assign one value type variable to another, it assign the data
• Inherit from System.ValueType (which inherits from System.Object)
  • Override the Equals method, could compare the value of two data instead of the addresses of two data
• Scenarios to use
  • Simple structure and no polymorphism requirement
  • Only store data and no action required
  • No inheritance requirement
  • Parameters passing and return

Reference type

• It includes: class, interface, delegate, object, string and int[] etc.
• Is allocated in the stack of thread, but its instance is allocated in the managed heap
  • The reference type contains the address of its instance in the managed heap
    • When assign one reference type variable to another, it assign the address
  • Instance in managed heap is managed by GC (Garbage Collection)
    • Reference type is less efficient than value type because it requires GC to manage
• Inherit from System.Object
  • Could compare whether two address are the same
  • String is very special. The equals of string will compare the value instead of the address. Every action on the string will generate a new string data in the managed heap.
• Scenarios to use
  • Required inheritance, polymorphism, and actions
  • Several parameters returning (ref, out)

Relationship of 2 types

• When the value type is inside a reference type (a variable in the class), the data will be allocated in the managed heap together with the whole class
• Use static public implicit operator XX(YY y) to write a method can customize the convert between different type

For the convert between value type and reference type, we need to use boxing (from value to reference) and unboxing (from reference to value) to achieve it.

Note. unboxing must happen in the reference type which is generated from boxing process.

The boxing and unboxing will influence the efficiency. Use generic could avoid influencing the efficiency.

Examples of boxing and unboxing

• ArrayList
• Hashtable
• enum

Parameters Passing

For reference passing, must use ref or out

• ref: must be initialized before passing
• out: must be initialized inside method

Memory Management

.NET CLR has 3 part of memory.

• Stack of thread.
  • Store the instance of value type
  • Managed by OS
  • Release when the method of value type ends, thus high efficiency
• Garbage Collection Heap
• Large Object Heap

Memory allocation

When call an instance method. The next command will be pushed to stack of thread, then other local value type will be pushed to the stack. When finish, those value type will be pop until get the pointer to the next command.

GC Heap stores the instance of reference type. Manged by GC. The instance will contains a TypeHandler which points to its method table in the Loader Heap.

Loader Heap stores the metadata (type). Every type in the loader heap is a method table. Managed by AppDomain. The method table has a part called Method Slot Table, which is a linked list containing the methods. When call a method in a reference type (class), CLR will follow the TypeHandler in the GC heap to find the metadata which contains this type’s definition in Loader Heap. Then CLR will check the Method Slot Table in this method table, and use JIT to compile the method’s IL code to naive code. The naive code will be stored in a dynamic memory.

![Memory in Heap](MemoryInHeap.png %}

Garbage Collection

If an object is not used by other objects in heap or not referred by data in stack, it will be regarded as garbage.

When the memory is full, the CLR will automatically work to recycle garbage and release the memory.

After releasing the memory, the CLR will use GC to move existed data to a continuous space to make the heap looks dense. The generation of the left data will increase by 1. Next time, the data with generation 0 will be checked firstly.

In C#, you can call GC.Collect to force the GC recycle the memory. You can also use Finalize method or Dispose method to customize the behavior when the class was recycled.

Methods to improve GC efficiency

• Use Dispose instead of Finalize
• Use using keyword to achieve automatically dispose calling
• Choose the right type of GC. Workstation GC or Server GC
• Use WeakReference class to achieve the weak reference
• Use generic for value type data to avoid boxing and unboxing process
• Set a configured size for collections
• Rewrite ToString in subclass
• Use String.Compare instead of ==; str.Length instead of == ''
• Use foreach instead of for
• Use struct if class is not necessary
• Use is to check the type, use as to convert the type
• Use static readonly instead of const
• Use 1-d array
• Use Multi-thread for system
• Avoid throw lots of exceptions. For catch block, catch the specific exception firstly
• Use FxCop software to check the efficiency of code

Reference

1. 《你必须知道的.NET（第二版）》，第2部分，王涛著

From workshop

From bruce force, to a perfect solution.

From local optimum to a whole optinum. According to experience.

Steps

1. Determine wether can use Greedy
2. Choose the strategy of Greddy
3. Calculate

Some samples

1. Arrange the activitices
   • Minuim end time of meeting
2. Minunm sum of weight of tree from graph
   • Prim
   • Krusal
3. Huffman coding
   prefix-tree binary code; choose the two min weighted elements to be the leaves of tree(from down to up)

There are several classic questions that include data structure and algorithm.

Overview

There are several similar data structure.

• HashTable / Dictionary
  • Key/value
  • dic = {} in Python
  • dic[key] = value
• HashSet
  • No repeated values
  • se = set() in Python
  • se.add(item) se.remove(item)

The time complexity of search in HashTable’s key or HashSet is O(1)

Useful functions

• collections.Counter(list) can count the element in the list and generate a dictionary
• for key, value in dic.items() can iterate the key and value at the same time
• sorted(dic.keys()) is sorting the keys
• dic.get(key, value) return the dic[key] if the key in dic, otherwise return value you give

Samples

Used for quick search

No.1 Two Sum

1
2
3
4
5
6

dic = {} 
for i, item in enumerate(nums):
    if target - item in dic:
        return [i, dic[target-item]]
    else:
        dic[item] = i

No.138 Copy List with Random Pointer

No.202 Happy Number

No.136 Single Number

1
2
3
4
5
6
7

se = set()
for num in nums:
    if num in se:
        se.remove(num)
    else:
        se.add(num)
return se.pop()

No.217 Contains Duplicate

Used for record the index

No.3 Longest Substring Without Repearting Characters

Used for record the count

No.49 Group Anagrams

1
2
3
4
5
6
7
8
9
10
11
12

dic = {}
for str_ in strs:
    form = dict(collections.Counter(str_))
    form_t = [0 for _ in range(26)]
    for (key, value) in form.items():
        form_t[ord(key) - 97] = value
    form_t = str(form_t)
    if form_t in dic:
        dic[form_t].append(str_)
    else:
        dic[form_t] = [str_]
return dic.values()

No.347 Top K Frequent Elements
Swap the key and values

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

form = dict(collections.Counter(nums))
form_r = {}
for key, value in form.items():
    if value in form_r:
        form_r[value].append(key)
    else:
        form_r[value] = [key]

sort_fre = sorted(form_r)[::-1]
ans = []
count = 0
index = 0
while count < k:
    ans.extend(form_r[sort_fre[index]])
    count += len(form_r[sort_fre[index]])
    index += 1
    
return ans

No.387 First Unique Character in a String

No.242 Valid Anagram

No.350 Intersection of Two Arrays II

No.36 Valid Sudoku

No.454 4Sum II

Overview

Queue and stack are just like a store. You just want to put and pick the items one by one. The time complexity of put and pick is O(1)

Python makes queue and stack easier because we can use list to finish the functions of queue and stack.

1
2
3
4
5
6
7
8
9

my_queue = []
my_queue.append(4)
my_queue.append(5)
print(my_queue.pop(0))    # we get 4

my_stack = []
my_stack.append(4)
my_stack.append(5)
print(my_stack.pop())    # we get 5

Samples

Travel the tree

No.94 - Binary Tree Inorder Traversal

No.103 - Binary Tree Zigzag Level Order Traversal

Pair Match

No.20 - Valid Parentheses

Store the data in order[Some special questions]

No.42 - Trapping Rain Water

To be continued…

Overview

There are 7 main sorting algorithm, which are also connected with other conceptions. Will be finished in the future.

Insert sort

$O(n^2)$

• Insert the value into a sorted list - swap with element of bottom one by one

Hill sort

$O(nlog(n))$

Select sort

$O(n^2)$

• Choose the smallest/largest element and put into the sorted array

Heap sort

$O(nlog(n))$

• Put items into heap, and pop one by one out
• Use heap can find the top K values easily. Create a heap with length of K, put items into it one by one

Bubble sort

$O(n^2)$

• Choose a value, if it is larger than the next one, replace them, until this value arrive the boundary of end
• Update the boundary of end, do the previous choosing and moving steps again

Quick sort (binary sort)

$O(nlog(n))$

• Choose a pivot, put all values smaller than pivot into left, all values larger than pivot into right
• Do quick sort for left and right
• Connect left, pivot and right

Merge sort

$O(nlog(n))$

• Divide a list into left and right
• Do the merge sort for left and right
• Put the sorted left and right together

Some functions in Python

• sorted(a, key=lambda x:x[0])

Some samples

• Find the 0-Kth largeset elements
  • Heap O(klong(n))
• Find the Kth largeset element
  • Move the smaller elements to left, larger elemetns to right, until the right part only have K elements

Reference

[1] https://www.cnblogs.com/ktao/p/7800485.html