Knight.Liao's Tale

God helps those who help themselves. 做有价值博客(2010.08.20).

[Top] 我要飞得更高

80 views 抢沙发

Fighting!

  • 就算难过也不痛,把伤心的碎片包一包带走,回家慢慢黏好再来过 — 《永不退缩》
  • 又怎会晓得执着的人 有隐形翅牓 — 《最初的梦想》
  • 我知道我要的那种幸福 就在那片更高的天空 — 《飞得更高》

寻找最大的K个数

4 views 抢沙发

这是编程之美书第2.5节的一道题目。

各种解法:

解法一,用nlgn复杂度的排序算法对数组进行从大到小排序,取前K个。但这方法做了两件不必要做的事:它对想得到的K个数进行了排序,对不想得到的n-K个数也进行了排序。方法不可取。

解法二,用选择排序或冒泡排序,复杂度O(NK)。但这方法也做了不必要做的一件事:对想得到的K个数进行了排序。方法不可取。

解法三,用顺序统计位(类快排)算法来计算(可参考算法导论)。算法导论上说这种方法从平均性能上来讲是线性的,但编程之美上却说复杂度是O(N*lgK)。对于这点,我对编程之美持怀疑态度。我认为,对于一个无序的数组,用顺序统计位算法,可以在近似O(n)的时间复杂度内得到第K大的元素。当这个过程执行完毕时,数组中位于该元素之前的元素就是前K大的元素。

解法三,先查找出数组中的Vmax和Vmin,组成新的数组[Vmin,Vmax],二分查找该数组,并在原数组中查找。具体请参见编程之美。复杂度为O(nlgn),方法不可取。

解法四,维护一个K大小的数组A,遍历原数组中的每个数,与A每个元素进行比较,如果大于A数组中的最小元素,则交换,否则继续。复杂度为O(NK),方法不可取。

解法五,维护一个最小堆,大小为K。一开始先从原数组中随便取K个元素建最小堆,复杂度为O(K)。然后遍历原数组中剩余的n-K个元素,每个元素先与堆顶比较,如果大于堆顶则交换,并维护最小堆性质。总复杂度为K+(n-K)lgK = nlgK。该方法只需要遍历一次数组,且无须在内存中存储所有数组数据,而只需维护K大小的数据。是一种适用于 大数据,小内存的好方法。如果K还是太大,则分次来求,通过先用K’(K’<K)来求……具体请参见编程之美。[1]

继续阅读

中午看《编程之美》的第2.5节中有这么一小段程序:

float array[100 000 000];

这个1亿个float变量,这样就有8亿个字节,转化为二进制单位G,就是小于等于1G。这样大小的数组量只能用堆(动态申请内存变量)或者静态存储区(全局变量)来申请。

好了,转入今天要讲的正题。到底栈、堆、静态存储区能申请的最大分配大小是多少呢?

栈(stack)

栈大小与编译器有关。

默认情况下,visual studio 2010 的栈大小为1M。但在平时应用程序中,由于函数会使用栈结果,所以只能用略小于1M大小的栈。
对于64位和32位程序,结果都是一样的,因为VS2010已经设定好了默认的栈大小了。

	const int nStackSize = 249036; // 这是0.95M
	int b[nStackSize];

	for(int i=0;i< nStackSize;++i)
		b[i] =0;

	std::cout << b[nStackSize-1];

静态存储区(全局变量)

继续阅读

532.5圈,213,000米

11 views 抢沙发

从2010年1月04日记起至今天,我总共绕操场532.5圈,共计213,000米。这个还是比较保守的估计,因为我总喜欢跑第三道,实际上一圈比400略多一点,大约有410米左右。

很高兴,看到这个统计成绩。

浙大的操场上洒满了我的汗水,每一滴都代表着我不屈的意志和永不退缩的勇气。

是孤独让我选择在长跑中享受自我。也是他让我实现自身的价值,Yes, I can!

最近压力比较大,时常有种想放弃但又不甘心的复杂念头。家里的父母很相信我,全权把未来都让我自己来掌控,他们对我说,成功了我为你骄傲,失败了就回来,家永远为你敞开。每每想到这,就感到很欣慰,也变得更有劲头。

很喜欢任贤齐的《永不退缩》这首歌,贴出来共勉:)

继续阅读

有意思的数列: Catalan数*

22 views 抢板凳

今天晚上小妹问我一个问题,

有一个随意的数组,一个栈,一个队列。现将数组内的元素随机进栈或进队列,等数组中所有元素均在栈中与队列中时,开始出栈和出队列。问题是:这样形成的序列总数有多少种?

对于这个问题,我现在还没有很确切的解答。要解决这个问题,需先了解如果单独只有栈时,序列有多少种的解决方法。因此,我也花了些时间在“出栈序列”种类问题上,从而发现了非常有趣了“Catalan数”。

【对于小妹的问题,我已经在8月31号做出了解答,用程序模拟出来了。可以发现得出来的序列并不是全排列,是介于栈与全排列之间的序列】

在中文维基上[1],它是这么来定义的:

卡塔兰数是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。

卡塔兰数的一般项公式为 C_n = \frac{1}{n+1}{2n \choose n} = \frac{(2n)!}{(n+1)!n!}

前几项为 (OEIS中的数列A000108): 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, …

继续阅读

Math

14 views 抢沙发

Catalan数

Bruce Eckel(Thinking in Java/C++作者) 在他的 5%的神话 (Mythical 5%) 中提到:

5%的程序员开发效率是其他95%程序员的20倍

(5% of programmers are 20x more productive than the other 95%)

按照80-20法则,80%的程序员几乎不看书,不读Blog,不参加技术会议,不持续学习。这些人也可能会进入大公司,他们日复一日的做着重复的 工作。另外20%则在专业方面比较主动,他们喜欢阅读,喜欢学习,喜欢参加技术活动。这20%当中又会有80%的人可能不会特别成功,他们仍然走在通往成 功的路上奋斗。剩下20%,也就是总数的5%的开发人员具备20倍的开发效率。

那如何成为这5%中的一员呢

Bruce Eckel 的观点:阅读,分析,总结,实践

这5%的人会习惯经常阅读新技术,并喜欢参与各种有潜在价值的新概念的实践,他们会有非常有选择性的参与会议,大部分时间都花在有效率的事情上,将事情做成。

要想比别人效率高出20%,则需要在各个方面达到平衡,而不单只是能将事情搞定那么简单,因此你要使用最好的工具,最优秀的技术,并尽最大的努力。 平衡点并 不是从明显的事物上 继续阅读

Somthing about “++i”

43 views 抢沙发

“++i” return a reference of the “i” object, it’s a left-hand value.
It’s more effective than “i++”.

int i = 0;
++i  =4;
std::cout << i << std::enld; // 4

Reference:

http://knightkid.blog.35.cn/2009/11/14/zhuanguanyuiheizaiczhongdexiaolvwenti/

[zz]Google的核心技术

46 views 抢沙发

本篇将主要介绍Google的十个核心技术,而且可以分为四大类:

    1. 分布式基础设施:GFS,Chubby和Protocol Buffer。
    2. 分布式大规模数据处理:MapReduce和Sawzall。
    3. 分布式数据库技术:BigTable和数据库Sharding。
    4. 数据中心优化技术:数据中心高温化,12V电池和服务器整合。

分布式基础设施

GFS

由 于搜索引擎需要处理海量的数据,所以Google的两位创始人Larry Page和Sergey Brin在创业初期设计一套名为“BigFiles”的文件系统,而GFS(全称为“Google File System”)这套分 继续阅读

In this example, I show some simple random generator examples using C++.

It simulates the generator of INT and FLOAT. The generator format is [a,b] or [a,b).

//////////////////////////////////////////////////////////////////////////
//
// Test the random generator of INT and float
//

#include <iostream>
#include <time.h>

void main()
{
	TestRandomIntFloatACM();
}

static void TestRandomIntClose(int ,int );
static void TestRandomFloatClose(float ,float);
static void TestRandomInt(int ,int );
static void TestRandomFloat(float ,float);

继续阅读

Powered by WordPress Web Design by SRS Solutions © 2010 Knight.Liao's Tale Design by SRS Solutions