任意一个类型与字符串相加自动转化成字符串

I was doing code review, someone wrote something as the following.

It can totally build and it's the first time I know this.

 

int i = 1;

string s = i+""; //任意一个类型与字符串相加自动转化成字符串。没有直接调用C#类库，隐含间接调用的。

powershell script to replace strings in a file

ReplaceStringInFile.bat

----------------

echo off

powershell.exe -command "Get-Content %1 | ForEach-Object {$_ -replace \"%3\", \"%4\"} | Set-Content %2"

timeout 5

----------------

托管与非托管的区别

 

1.托管代码 (managed code)

由公共语言运行库环境（而不是直接由操作系统）执行的代码。托管代码应用程序可以获得公共语言运行库服务，例如自动垃圾回收、运行库类型检查和安全支持等。这些服务帮助提供独立于平台和语言的、统一的托管代码应用程序行为。

托管代码是可以使用20多种支持Microsoft .NET Framework的高级语言编写的代码，它们包括：C#, J#, Microsoft Visual Basic .NET, Microsoft JScript .NET, 以及C++。所有的语言共享统一的类库集合，并能被编码成为中间语言(IL)。运行库编译器（runtime-aware ompiler）在托管执行环境下编译中间语言（IL）使之成为本地可执行的代码，并使用数组边界和索引检查，异常处理，垃圾回收等手段确保类型的安全。
 
在托管执行环境中使用托管代码及其编译，可以避免许多典型的导致安全黑洞和不稳定程序的编程错误。同样，许多不可靠的设计也自动的被增强了安全性，例如 类型安全检查，内存管理和释放无效对象。程序员可以花更多的精力关注程序的应用逻辑设计并可以减少代码的编写量。这就意味着更短的开发时间和更健壮的程序。

 

2.非托管代码 (unmanaged code)

在公共语言运行库环境的外部，由操作系统直接执行的代码。非托管代码必须提供自己的垃圾回收、类型检查、安全支持等服务；它与托管代码不同，后者从公共语言运行库中获得这些服务。

 

3.托管代码和非托管代码的区别
 
非托管代码：一般是直接与OS打交道.
托管代码： 一般是委托中介（如.net framework 等）
 

所谓托管代码:

是指.Net下面编译为msil的一种字节码, 而非传统的编译语言编译入C,C++之流, 直接编译成二进制的可执行机器码.
就是说, 需要一个额外的解释器, 才能执行这种假的奇迹码. 在.net里面, 就是一个jit的编译器, 在执行的时候, 才编译成可执行的目标机器码, 才能真正执行起来.

 

这个概念类似于, java里面的那些.class文件, 需要jdk虚拟机才能执行起来是一个意思.

同样, 这个特性, 造成了一个很好的效果, 就是平台无关的特性.

Difference between Heap and Stack

堆(heap)和栈(stack)有什么区别??

简单的可以理解为：  
heap：是由malloc之类函数分配的空间所在地。地址是由低向高增长的。  
stack：是自动分配变量，以及函数调用的时候所使用的一些空间。地址是由高向低减少的。

预备知识—程序的内存分配

一个由c/C++编译的程序占用的内存分为以下几个部分
1、栈区（stack）—   由编译器自动分配释放   ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap）   —   一般由程序员分配释放，   若程序员不释放，程序结束时可能由OS回收   。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表，呵呵。
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，   未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。   -   程序结束后有系统释放
4、文字常量区   —常量字符串就是放在这里的。   程序结束后由系统释放
5、程序代码区—存放函数体的二进制代码。

二、例子程序
这是一个前辈写的，非常详细
//main.cpp
int   a   =   0;   全局初始化区
char   *p1;   全局未初始化区
main()
{
int   b;   栈
char   s[]   =   "abc ";   栈
char   *p2;   栈
char   *p3   =   "123456 ";   123456在常量区，p3在栈上。
static   int   c   =0；   全局（静态）初始化区
p1   =   (char   *)malloc(10);
p2   =   (char   *)malloc(20);
分配得来得10和20字节的区域就在堆区。
strcpy(p1,   "123456 ");   123456放在常量区，编译器可能会将它与p3所指向的 "123456 "优化成一个地方。
}  
二、栈的理论知识
2.1申请方式
stack:
由系统自动分配。   例如，声明在函数中一个局部变量   int   b;   系统自动在栈中为b开辟空间
heap:
需要程序员自己申请，并指明大小，在c中malloc函数
如p1   =   (char   *)malloc(10);
在C++中用new运算符
如p2   =   (char   *)malloc(10);
但是注意p1、p2本身是在栈中的。
2.2
申请后系统的响应
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，
会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。
2.3申请大小的限制
栈：在Windows下,栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在   WINDOWS下，栈的大小是2M（也有的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
2.4申请效率的比较：
栈由系统自动分配，速度较快。但程序员是无法控制的。
堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.
另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度

也最灵活
2.5堆和栈中的存储内容
栈：   在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。
当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。
堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。
2.6存取效率的比较

char   s1[]   =   "aaaaaaaaaaaaaaa ";
char   *s2   =   "bbbbbbbbbbbbbbbbb ";
aaaaaaaaaaa是在运行时刻赋值的；
而bbbbbbbbbbb是在编译时就确定的；
但是，在以后的存取中，在栈上的数组比指针所指向的字符串(例如堆)快。
比如：
#include  
void   main()
{
char   a   =   1;
char   c[]   =   "1234567890 ";
char   *p   = "1234567890 ";
a   =   c[1];
a   =   p[1];
return;
}
对应的汇编代码
10:   a   =   c[1];
00401067   8A   4D   F1   mov   cl,byte   ptr   [ebp-0Fh]
0040106A   88   4D   FC   mov   byte   ptr   [ebp-4],cl
11:   a   =   p[1];
0040106D   8B   55   EC   mov   edx,dword   ptr   [ebp-14h]
00401070   8A   42   01   mov   al,byte   ptr   [edx+1]
00401073   88   45   FC   mov   byte   ptr   [ebp-4],al
第一种在读取时直接就把字符串中的元素读到寄存器cl中，而第二种则要先把指针值读

edx中，在根据edx读取字符，显然慢了。

 

2.7小结：
堆和栈的区别可以用如下的比喻来看出：
使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。
使用堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大。

堆和栈的区别主要分：
操作系统方面的堆和栈，如上面说的那些，不多说了。
还有就是数据结构方面的堆和栈，这些都是不同的概念。这里的堆实际上指的就是（满足堆性质的）优先队列的一种数据结构，第1个元素有最高的优先权；栈实际上就是满足先进后出的性质的数学或数据结构。
虽然堆栈，堆栈的说法是连起来叫，但是他们还是有很大区别的，连着叫只是由于历史的原因。

双程计

 从google reader上看到的，挺逗的一篇

http://jacquesmattheij.com/A+tale+of+two+programmers

A tale of two programmers

Submitted by administrator on Wed, 03/09/2011 - 17:21.

When MSX and Atari ST were still 'hot', I contracted for a short while for a game company in the Netherlands, called Aackosoft, in Leiderdorp, a small town near The Hague. The reason it was only short was because the company failed spectacularly (the financial director came in one night and started shredding documents, I just packed my bag and left). Other than the management, the people working there were great.

We wrote interesting programs, the pay was OK (assuming you got paid), and the amount of knowledge floating around there was amazing. The designers were as good as I've ever seen, given the limited display capabilities of the various platforms available. For me, two people stood out: Steve and Chris, both from the UK. Because most of us had a very long commute, we slept 'on campus', one section of the building was something that is best described as a college dorm. After work we'd get together, order pizza or Thai food, talk shop and play games, sometimes our own games (Indy500, FlightDeck), sometimes those by competitors (does anybody even remember Gauntlet?).

Steve and Chris were as unalike as I've ever seen. Steve would toss out reams of code, sometimes creating the skeleton of a game in a few manic nights of coding and then he'd run out of steam to become slow as molasses. At roughly this point in time, Chris would enter the picture. He'd take the pile of work that Steve had done, and bit by bit, he'd clean it up and make it reliable and efficient. They knew each other so well that they didn't actually discuss the code much, it just got passed back and forth in this fashion until the job was done, usually in record time.

Their secret was obviously their complimentary characters and the fact that they'd grown up together, and had gotten to rely on the other guy 'having your back', as opposed to spending endless hours on transferring the knowledge Chris had been through this so many times that he knew quite well what to expect.

Today we'd probably call this 'pair programming', but it was pair programming in a way that was far more than the sum of its parts. Chris wouldn't be able to come up with an original work if his life depended on it. Steve would not be able to finish a job if you threatened to fire him. But as a team, they worked out splendid. They typically had their releases based on the same storyboards ready before we'd had the skeleton fleshed out.

Over the years, Steve had collected a whole encyclopedia of useful chunks of assembly code and he would beat these in shape just long enough for Chris to find his way.

Co-dependency amongst programmers. I've never seen it afterwards, and I don't really expect to see it ever again, it was one of those small things that remain as unique on the day that I first came across it as it is today.

But what I have seen is 'halves'. I've seen Steve's (I'm fairly strongly in his 'camp' when it comes to personality, when the engine works, I usually find it very hard to motivate myself to continue, that was the interesting bit for me), and I've seen Chris's.

Typically they wander around big companies looking for their soulmate, but they never ever run into them in a way that they recognize each other, or manage to hit it off on a personal level. But it makes me wonder if there isn't a use for a 'programmer dating service', where the Steve's and the Chris's of this world can meet up and achieve miracles that they alone would not be able to realize.

中文原文地址

http://www.aqee.net/2011/03/22/a-tale-of-two-programmers/

当MSX和Atari ST还很‘火’的时候，我在荷兰的一家叫做Aackosoft的游戏公司里短暂的就职过一段时间，这个公司位于Leiderdorp —— 离海牙不远的一个小镇。之所以短暂，原因是这个公司神奇的倒闭了(一天晚上财务主管一进来就开始粉碎各种文件，我只好拿起公文包离开了)。除了管理方面的问题外，这里工作的人都很不错。

要开发的程序非常有趣，这里的薪水还行(假如你是拿薪水过日子的)，开发过程伴随着大量的知识学问，让我惊叹不已。这里的设计人员都非常的优秀，他们让这不通用的显示效果能够在各种平台上使用。对于我，有两个人格外的吸引我：Steve 和 Chris，他们都是英国人。我们大部分人下班后都会一起坐一段很长的路程，我们住在“校园宿舍”里 —— 因为对这栋建筑的这个部分最好的描述就是校园宿舍。下班后我们就待在一起，我们叫了匹萨或泰国食品，聊天、玩游戏，有时是我们自己的游戏(Indy500, FlightDeck)，有时是竞争对手的(是否还有人记得Gauntlet？)。

Steve 和 Chris 这两个人极不相似。Steve 讨厌大量的编码工作，他有时会疯狂的花上几个昼夜的时间把一个游戏的框架搭建起来，之后他就会像泄漏气的脾气，行动慢慢腾腾，像个蜗牛。而大概就在这个节骨眼上，Chris入场了。他捡起Steve已经完成的那一大堆代码，一个字节一个字节的，规整清理，使之可靠、高效。他们之间是如此了解，根本不需要讨论哪段代码是干什么、为什么这样写，只是用这种方式来回交替的进行，直到任务完成，通常都是迅速顺利的搞定。

这其中的奥秘显然是得益于他们值得称赞的性格，长期共处培养出来的融洽，以及形成的一种依赖于对方的习惯，而不是相反的用大量的时间来相互传授自己的知识和用意。Chris 已经无数次的这样配合Steve，已经十分清楚的知道Steve想干什么。

如今我们也许可以称这为“结对编程”，而这种结对的方式产生的效果远超了他们两个作为单独个体的总和。Chris 如果一直依赖于这种工作方式，那他将不会有自己的原创作品。而Steve一旦失去了Chris，将不能完整的完成任何一个工作。可作为一个团队，他们做出了出色的东西。就像是他们在搭起骨架，填充内容之前，脑海中有了共同的图纸，这是他们能成功完成任务的基础。

数年里，Steve已经积攒了犹如大百科全书那样丰富的有用的程序代码，这些足够Chris用来发现他的思维轨迹。

这是程序员中的合作依赖。之后我再也没有遇到这种情况，我也并不是真的想盼望看到这样的组合出现，这只是那些日子里能让我感到独特、至今回忆的一件小事，就像发生在昨天。

我所看到的是一种‘热情’。我看到了Steve的 (从个性上来讲，我更喜欢他，但当我发现有趣的事情时，我却不能像他那样富有激情的工作)。我看到了Chris的。

他们曾徘徊在各大公司里寻找他们的精神伙伴，但从来没有遇到这样能够相知、能超出工作范畴、从个人角度上相互接受的人。这让我产生奇想，也许应该有个“程序员约会服务系统”，像Steve和Chris这样的人能够遇到一起，一起合作创造出他们各自独自根本无法想到的奇迹来。

 

求最大公约数（欧几里德算法）

求最大公约数的欧几里德算法，也称作辗转相除法，如下：

int GetGCD(int m, int n)
{
if (n = 0)
{
return m;
}
return GetGCD(n, m % n);
}
(GCD = Greatest Common Divisor)

比如
GetGCD(18, 24)
-> GetGCD(24, 18)
-> GetGCD(18, 6);
-> GetGCD(6, 0);
-> return 6;

----------------------------------------

另外，最小公倍数 = 两数之积 / 最大公约数
所以 GetLCM(m, n) = m * n / GetGCD(m, n)
(LCM = Least Common Multiple)

比如
GetLCM(18, 24) = 18 * 24 / 6 = 72

The two egg problem solution (copy-pasted from http://classic-puzzles.blogspot.com)

Google Interview Puzzle : 2 Egg Problem

My intention here is not to trouble Google interviewers. I was just collecting some classic puzzles and found this one and a small Google search showed me that this is a Google interview puzzle to my pleasant surprise. But many of the answers I found were either wrong or totally twisted. I am making no surety of the answer I give and I am open to your remarks or suggestion or corrections.

The Standard Problem in simple writing goes like this:

* You are given 2 eggs.
* You have access to a 100-storey building.
* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.
* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process



If you are one of the people who likes to solve a puzzle before seeing the answer you must quit the blog now and come back later for checking the answer.


Now that this is a Google interview question I am taking the normal "Interview-Style" of solving a problem. Simply saying thinking aloud through the solution from worst to the best correcting the flows optimizing the solution or taking the 5-minute hard thinking acting pause to a problem, which you know already and just want to make your interviewer think that you are a challenge lover.

Solution

Drop the first egg from 50.If it breaks you can try the same approach for a 50-storey building (1 to 49) and try it from 25th floor. If it did not break try at 75th floor. And use linear search with the remaining portion of storey we need to test. For example if the first egg breaks at 50 we need to try all possibilities from 1 to 49.

Now this looks a feasible solution. In computer student's jargon do a binary search with first egg and linear search with the second one. Best case is log (100) and worst is 50.


Now the optimal solution for the problem is that you figure out that you will eventually end up with a linear search because you have no way of deciding the highest floor with only one egg (If you broke one egg and you have to find the answer among 10 all you can do is start from the lowest to the highest and the worst is the total number of floors). So the whole question grinds up to how to make use of the first egg to reduce the linear testing of the egg.


(For strict computer science students, well this problem can be solved using binary search on the number of drops needed to find the highest floor.)

Now let x be the answer we want, the number of drops required.

So if the first egg breaks maximum we can have x-1 drops and so we must always put the first egg from height x. So we have determined that for a given x we must drop the first ball from x height. And now if the first drop of the first egg doesn't breaks we can have x-2 drops for the second egg if the first egg breaks in the second drop.

Taking an example, lets say 16 is my answer. That I need 16 drops to find out the answer. Lets see whether we can find out the height in 16 drops. First we drop from height 16,and if it breaks we try all floors from 1 to 15.If the egg don't break then we have left 15 drops, so we will drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd floor we can try all the floors from 17 to 31 in 14 drops (total of 16 drops). Now if it did not break then we have left 13 drops. and we can figure out whether we can find out whether we can figure out the floor in 16 drops.

Lets take the case with 16 as the answer

1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45 .....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task


Now finding out the optimal one we can see that we could have done it in either 15 or 14 drops only but how can we find the optimal one. From the above table we can see that the optimal one will be needing 0 linear trials in the last step.

So we could write it as

(1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.

Let 1+p=q which is the answer we are looking for

q (q+1)/2 >=100

Solving for 100 you get q=14.
So the answer is: 14
Drop first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).

Please feel free to correct or post any comment on the solution or the answer.

0/1 KnapSack problem in C#

The following program find a best solution in 0/1 KnapSack problem, but it does not pick all the best solutions.

        public static int CalculateBagProblem(int BagVolumn, List<int> items, out List<int> chosenItems)

        {

            chosenItems = new List<int>();

            if (items.Count == 0)

            {  

                return 0;

            }

            else if (items.Count == 1)

            {

                if (items[0] <= BagVolumn)

                {

                    chosenItems.Add(items[0]);

                    return items[0];

                }

                else

                {

                    return 0;

                }

            }

            else

            {

                // without the first item

                List<int> remainItems = items.GetRange(1, items.Count - 1);

                List<int> chosenItemsInRemainItems = new List<int>();

                int withoutFirstItemResult = CalculateBagProblem(BagVolumn, remainItems, out chosenItemsInRemainItems);

                

                // with all the items

                int withFirstItemResult = 0;

                List<int> chosenItemsInItems = new List<int>();

                if (BagVolumn >= items[0])

                {

                    withFirstItemResult = CalculateBagProblem(BagVolumn - items[0], remainItems, out chosenItemsInItems) + items[0];

                    chosenItemsInItems.Add(items[0]);

                }

 

                // select max from the two results               

                if (withoutFirstItemResult >= withFirstItemResult)

                {

                    chosenItems = chosenItemsInRemainItems;

                    return withoutFirstItemResult;

                }

                else

                {

                    chosenItems = chosenItemsInItems;

                    return withFirstItemResult;

                }

            }

        }