码农SW-CSDN博客

转载 Add Sibling to Binary Tree

Question:Given a binary treestruct Node {Node* leftChild;Node* rightChild;Node* nextRight;}Populate the nextRight pointers in each node.The first idea come out should be the BFS tr

2014-09-16 17:59:37 1252 1

转载 Load Balancing Web Applications

This article offers an overview of several approaches to load balancing on Web application server clusters. A cluster is a group of servers running a Web application simultaneously, appearing to the w

2014-08-28 22:14:15 1124

转载 C++结构类型在GDB中的强制类型转换(带namespace的强制转型要加单引号的)

今天在调试程序的过程中遇到的一个小问题，在这里记录一下，希望能对遇到同样问题的朋友有所帮助。以下面的程序为例程进行说明：12345678910111213141516171819202122232425262728293031323334353637383940414243444

2014-08-27 14:27:15 4012

原创 LRU cache的一个简单实现

用一个结构表示Key 和 Value：class LRUCacheNode{friend LRUCache;int mKey, mVal;LRUCacheNode* next;LRUCacheNode* pre;LRUCacheNode(int iK, int iV):mKey(iK), mVal(iV), next(NULL), pre(NULL){};};

2014-06-16 15:58:22 1120

转载使用gdb调试异常

有时程序中有未捕获的异常会导致程序异常的行为甚至导致程序的直接退出。这对服务器程序来说是不可接受的。可以使用gdb的catch命令来帮助我们调试异常。使用gdb捕获异常的扔出点（相当于在扔出异常的地方添加断点）：catch throw使用gdb捕获线程退出（相当于在线程退出的时候添加断点）：catch pthread_exit这样，如果相应的事件发生，

2014-04-23 13:42:19 8724

转载 python 线程，GIL 和 ctypes

GIL 是什么东西？它对我们的 python 程序会产生什么样的影响？我们先来看一个问题。运行下面这段 python 程序，CPU 占用率是多少？# 请勿在工作中模仿，危险:)def dead_loop(): while True: passdead_loop()答案是什么呢，占用 100％ CPU？那是单核！还得是没有超线程的古董 CPU。在我

2014-04-15 20:06:11 1174

转载理解Python的With语句

With语句是什么？Python’s with statement provides a very convenient way of dealing with the situation where you have to do a setup and teardown to make something happen. A very good example for this is the

2014-04-09 11:44:50 134797 11

转载找出有环链表中环的起点

给定一个有环的链表，写一个算法，找出环的起点。例如：输入：A->B->C->D->E->C[与前面的C是同一个节点]输出：C判断一个链表是否存在环有一个简单的方法，就是使用一个快指针、和一个慢指针，快指针每次走两步，慢指针每次走一步，则如果有环，它们最后必然会相遇的。本题的难点在于要找出环的起点。其实也不难，与判断是否有环类似，用两个步长分别为1和2的指

2014-03-19 22:27:27 1312

转载从"read"看系统调用的耗时

1、fread和read有何不同？先看两段代码：fread.cread.c两个文件的功能完全一样，打开同一个名为test.file的文件，并逐字节地读取整个文件。将它们编译后得到的可执行程序fread和read分别在同一台PC（linux系统）上执行，得到的如果如下：发现没有？fread与r

2014-03-17 14:54:14 3964

转载五种I/O 模式——阻塞(默认IO模式)，非阻塞(常用语管道)，I/O多路复用(IO多路复用的应用场景)，信号I/O，异步I/O

五种I/O 模式：【1】阻塞 I/O (Linux下的I/O操作默认是阻塞I/O，即open和socket创建的I/O都是阻塞I/O)【2】非阻塞 I/O (可以通过fcntl或者open时使用O_NONBLOCK参数，将fd设置为非阻塞的I/O)【3】 I/O 多路复用 (I/O多路复用，通常需要

2014-03-07 17:04:39 1908

原创 gdb调试-查看STL容器

在GDB进行调试的时候，查看STL容器是个比较痛苦的事情，比如查看vector, map 这些容器，根本看不到里面的数据是什么。现在介绍一个gdb 查看STL容器神器。文件：http://www.yolinux.com/TUTORIALS/src/dbinit_stl_views-1.03.txt下载上述文件，按照文件要求吧上述文件存成".gdbinit"文件放到你的根

2014-02-27 17:37:32 5869 2

转载 linux下so动态库一些不为人知的秘密

linux 下有动态库和静态库，动态库以.so为扩展名，静态库以.a为扩展名。二者都使用广泛。本文主要讲动态库方面知识。基本上每一个linux 程序都至少会有一个动态库，查看某个程序使用了那些动态库，使用ldd命令查看 # ldd /bin/lslinux-vdso.so.1 => (0x00007fff597ff000)libsel

2014-02-27 13:16:48 12810 1

转载一致性hash算法 - consistent hashing

一致性 hash 算法（ consistent hashing ）张亮consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出，目前在 cache 系统中应用越来越广泛；1 基本场景比如你有 N 个 cache 服务器（后面简称 cache ），那么如何将一个对象 object 映射到 N

2014-02-18 14:36:28 1009

转载设计模式简单代码之Flyweight模式

出自： http://blog.csdn.net/dylgsy/article/details/1045678欢迎转载，请注明出处。[Flyweight模式] 官方描述：意图运用共享技术有效地支持大量细粒度的对象。适用性 1、一个应用程序使用了大量的对象。 2、完全由于使用大量的对象，造成很大的存储开销。 3、对象的大多数状态都

2014-01-27 14:57:12 731

转载 calloc(), malloc(), realloc(), free(),alloca()

内存区域可以分为栈、堆、静态存储区和常量存储区，局部变量，函数形参，临时变量都是在栈上获得内存的，它们获取的方式都是由编译器自动执行的。利用指针，我们可以像汇编语言一样处理内存地址，C 标准函数库提供了许多函数来实现对堆上内存管理，其中包括：malloc函数，free函数，calloc函数和realloc函数。使用这些函数需要包含头文件stdlib.h。四个函数之间的有区别

2014-01-27 11:05:52 774

转载用 Python ctypes 来调用 C/C++ 编写的第三方库

看到一篇简洁的文章--如何用Python ctypes调用C++(ctypes调用C没这么多麻烦事)，不敢独享...如果需要用 Python 调用 C/C++ 编写的第三方库（这些第三方库很可能就是你之前写出来的），只是需要一个脚本语言来粘合它们。这个时候，用 Python ctypes 可以很方便地实现调用。StackOverflow 上的 Calling C/C++ fro

2014-01-12 13:51:46 10525

转载 Unicode in Python 完全揭秘

挺不错的一个PPT, mark 一下http://farmdev.com/talks/unicode/

2013-12-30 14:41:40 749

转载程序分析工具gprof介绍

程序分析是以某种语言书写的程序为对象，对其内部的运作流程进行分析。程序分析的目的主要有三点：一是通过程序内部各个模块之间的调用关系，整体上把握程序的运行流程，从而更好地理解程序，从中汲取有价值的内容。二是以系统优化为目的，通过对程序中关键函数的跟踪或者运行时信息的统计，找到系统性能的瓶颈，从而采取进一步行动对程序进行优化。最后一点，程序分析也有可能用于系统测试和程序调试中。当系统跟踪起来比较复杂，

2013-12-30 10:54:15 980

转载 X-Y Problem

对于X-Y Problem的意思如下：1）有人想解决问题X2）他觉得Y可能是解决X问题的方法3）但是他不知道Y应该怎么做4）于是他去问别人Y应该怎么做？简而言之，没有去问怎么解决问题X，而是去问解决方案Y应该怎么去实现和操作。于是乎：1）热心的人们帮助并告诉这个人Y应该怎么搞，但是大家都觉得Y这个方案有点怪异。2）在经过大量地讨论和浪费了大量的时间后，热心的

2013-12-18 16:18:33 898

转载 PyMongo基本使用

引用PyMongo>>> import pymongo 创建连接Connection>>> import pymongo>>> conn = pymongo.Connection('localhost',27017)或import>>> conn = Connection('localhost',27017)

2013-12-18 13:18:45 15471

转载海量数据相似度计算之simhash和海明距离

通过采集系统我们采集了大量文本数据，但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复，如何选择和设计文本的去重算法？常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用，如果我们的爬虫每天采集的数据以千万计算，我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本

2013-12-16 16:40:03 3147

转载 Mahout的taste里的几种相似度计算方法

欧几里德相似度（Euclidean Distance）最初用于计算欧几里德空间中两个点的距离，以两个用户x和y为例子，看成是n维空间的两个向量x和y, xi表示用户x对itemi的喜好值，yi表示用户y对itemi的喜好值，他们之前的欧几里德距离是对应的欧几里德相似度，一般采用以下公式进行转换：距离越小，相似度越大在taste里，计算user之间

2013-12-16 16:27:26 6603

转载在python中使用SQLite

在python中使用SQLite--连接数据库导入库：from pysqlite2 import dbapi2 as sqlite建立数据库文件或打开数据库：connection = sqlite.connect('test.db')如数据库文件test.db文件不存在，则它将会创建；如存在，则会打开在内存中创建一个临时数据库：memoryConne

2013-11-25 13:25:51 2672

转载 Python Yield versus Return

As coders, we are familiar with how function calls work in Python or C. Whenever we call a function, the function gets a private namespace where its local variables are created.ReturnThe retu

2013-11-22 10:44:43 822

转载 std::string的Copy-on-Write：不如想象中美好

Copy-on-write（以下简称COW）是一种很重要的优化手段。它的核心思想是懒惰处理多个实体的资源请求，在多个实体之间共享某些资源，直到有实体需要对资源进行修改时，才真正为该实体分配私有的资源。COW技术的一个经典应用在于Linux内核在进程fork时对进程地址空间的处理。由于fork产生的子进程需要一份和父进程内容相同但完全独立的地址空间，一种做法是将父进程的地址空间完全复制一

2013-11-19 14:53:33 1016

转载 Centos 6.4 python 2.6 升级到 2.7

一开始有这个需求，是因为用 YaH3C 替代 iNode 进行校园网认证时，一直编译错误，提示找不到 Python 的某个模块，百度了一下，此模块是在 Python2.7 以上才有的，但是系统的自带的Python是2.6版本，难怪一直连不上网。于是，继续百度google，进行安装，后来又出现问题...在此开篇记录一下，权当备忘。查看python的版本

2013-11-16 18:27:24 999

转载 leetcode之 median of two sorted arrays

这是我做的第二个leetcode题目，一开始以为和第一个一样很简单，但是做的过程中才发现这个题目非常难，给人一种“刚上战场就踩上地雷挂掉了”的感觉。后来搜了一下leetcode的难度分布表（leetcode难度及面试频率）才发现，该问题是难度为5的问题，真是小看了它！网上搜了很多答案，但是鲜见简明正确的解答，唯有一种寻找第k小值的方法非常好，在此整理一下。首先对leetcod

2013-11-10 11:58:10 759

转载 git使用说明

1. 创建git项目使用git的第一步是创建一个git项目。这一步需要在github网站上完成，在网站中创建一个全新的repository。如果我们之前在本地完成一个项目，想要将该项目发布到github，则此时新建的repository不要有任何文件，即使是README这样的文件，然后我们可以按照如下流程完成创建： a) cd localpro

2013-11-10 11:52:58 614

转载青少年如何使用 Python 开始游戏开发

这是一篇由教程团队成员Julian Meyer发表的文章,一个12岁的python开发人员。你可以在Google+和Twitter上找到他。你可曾想过如何创建视频游戏吗？它不像你想象的那么复杂！在本教程中，您将创建一个简单的游戏叫做兔子和獾，在这里作为英雄的兔子要保卫城堡反击进攻的獾群。:O写这个游戏，你将使用Python。不，我指的并不是一条大蛇！:]Pyth

2013-10-31 13:49:42 2303 1

转载求和问题总结(leetcode 2Sum, 3Sum, 4Sum, K Sum)

前言:做过leetcode的人都知道, 里面有2sum, 3sum(closest), 4sum等问题, 这些也是面试里面经典的问题, 考察是否能够合理利用排序这个性质, 一步一步得到高效的算法. 经过总结, 本人觉得这些问题都可以使用一个通用的K sum求和问题加以概括消化, 这里我们先直接给出K Sum的问题描述和算法(递归解法), 然后将这个一般性的方法套用到具体的K, 比如leet

2013-10-18 18:13:10 1232

转载 STL算法之 next_permutation、prev_permutation 的原理和实现

两个函数类似，重点介绍next_permutation.template bool next_permutation (BidirectionalIterator first, BidirectionalIterator last ); template bool next_permutatio

2013-10-15 11:27:10 2079

原创 [leetCode]Search in Rotated Sorted Array

问题1：Suppose a sorted array is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).You are given a target value to search. If found in the arr

2013-10-10 16:37:41 787

转载 [LeetCode(Q41)] First Missing Positive (乱序数组中寻找第一个未出现的正整数)

Q:Given an unsorted integer array, find the first missing positive integer.For example,Given [1,2,0] return 3,and [3,4,-1,1] return 2.Your algorithm should run in O(n) time and uses co

2013-10-09 16:16:53 2707

转载 LeetCode-Valid Number - 有限状态机

判断合法数字，之前好像在哪里看到过这题，记得当时还写了好久，反正各种改，今天看到了大神的解法(https://github.com/fuwutu/LeetCode/blob/master/Valid%20Number.cpp),用有限状态机，非常简洁，不需要复杂的各种判断！先枚举一下各种合法的输入情况：1.空格+ 数字 +空格2.空格+ 点 + 数字

2013-09-27 14:50:47 7637 5

转载 LBS定位技术

LBS定位技术从方法上可分成三类：基于三角关系的定位技术、基于场景分析的定位技术、基于临近关系的定位技术（唐毅和杨博雄，2003）。本博文首先对基于三角关系的定位技术进行了介绍，并对其中的应用最广泛的代表GPS进行阐述。一、基于三角关系的定位方法该技术的基本原理很简单，可以抽象成如下问题：已知A、B、C三个点的坐标，以及该三点至D点的距离

2013-09-18 10:54:25 1271

转载 [珠玑之椟]随机数函数取样与概率

[珠玑之椟]随机数函数取样与概率　　本节主要受到《编程珠玑》第12章随机取样问题的启发，但不仅仅限于随机取样问题，进一步地，研究讨论了一些在笔试面试中常见的和随机函数以及概率相关的问题。　　阅读本文所需的知识：　　　　1.对C语言中或其他语言中等价的rand()、srand()有所了解。本文不讨论种子的设定和伪随机数的问题；　　　　2.中学或以上水平的概率基本概念。

2013-09-02 12:59:33 1329

转载最大滑动窗口

参考：http://blog.csdn.net/ssjhust123/article/details/7967489http://codercareer.blogspot.com/2012/02/no-33-maximums-in-sliding-windows.htmlhttp://leetcode.com/2011/01/sliding-window-maximum.html

2013-07-11 05:37:18 4657

原创硬币选择问题-动态规划

最少硬币问题假设有3种不同的硬币，币值分别是CoinValue[] = {1， 2， 5}，每一种硬币的数量是有限的，分别是CoinNum[] = {3, 3, 3}，给定一个数值target=18，找出一种硬币数最少的方法，输出最少的硬币数。思路：动态规划。问题定义： dp[n][m] 表示当目标值为n,有m种硬币可选的时候的最少硬币数，那么对于问题来说，dp[18][3

2013-07-11 03:17:54 8763 1

转载 geohash：用字符串实现附近地点搜索

上回说到了用经纬度范围实现附近地点搜索。一些小型应用中这样做没问题，但在大型应用中它有个显著的缺点：速度慢。慢的原因有两个，第一是范围比较的索引利用率并不高，第二是SQL语句极其不稳定(不同的当前位置会产生完全不同的SQL查询)，很难缓存。可以考虑使用geohash算法。geohash是一种地址编码，它能把二维的经纬度编码成一维的字符串。比如，北海公园的编码是wx4g0ec1。

2013-07-08 02:31:34 4714

转载求平方根sqrt()函数的底层算法效率问题

转： http://www.nowamagic.net/algorithm/algorithm_EfficacyOfFunctionSqrt.php我们平时经常会有一些数据运算的操作，需要调用sqrt，exp，abs等函数，那么时候你有没有想过：这个些函数系统是如何实现的？就拿最常用的sqrt函数来说吧，系统怎么来实现这个经常调用的函数呢？虽然有可能你平时没有想过这个问题，不过正所

2013-06-28 03:40:30 3502

空空如也

空空如也