Skip to content
Ider

沉淀我所学习,累积我所见闻,分享我所体验

Primary Navigation Menu
Menu
  • Home
  • About Ider
    • Who Ider?
    • Why Ider?
    • How Ider?
    • Where Ider?
    • What Ider?

C/C++

2016-07-31
31 July
On July 31, 2016
In Article Collection(聚宝收藏), Knowledge Base(心得笔库), Language Tips(语言初试)

编程术语鉴别-函数篇

常说“隔行如隔山”,每个行业都只有该业内人士才懂的术语。软件行业里也有很多别人听不懂的话,比如有个笑话就说:所有讲不清楚的过程都叫做“算法(Algorithm)”。但其实即使身处在软件行业里,也任然有好多模棱两可的的概念,常常被混淆使用。就让本文来梳理一下这些概念的细微区别。

function vs. method

函数(function)和方法(method)在编程中的概念就很相近,经常被互换着称呼,但它们的区别主要是在定义的位置上。

function是一段通过名字调用的代码,它可以接受数据进行操作,并可能会有返回值。
method是一段通过关联在对象上的名字调用的代码。

从这段解释上看函数和方法基本一致,只是方法是属于对象的一部分,所以在面向对象语言中才有概念。如果是C语句,就只有函数的说法。

方法是附属于对象的,相对于函数可以接受传入参数,对象本身也会作为隐性参数可以在方法中被调用。在返回值方面,方法不仅可以选择返回数据,还可以将数据赋予其所属的对象。

(在我看来,计算机函数的概念应该与数学的“函数”概念是相通的,只是数学上的函数必须要输入和输出。如果考虑到计算机函数的参数的类型,以及异常(Exception)的情况,则感觉与数学的“映射”更接近了。)

References:

  • Difference between a method and a function – Stack Overflow
  • Subroutine – Wikipedia, the free encyclopedia
  • programming practices – Method vs Function vs Procedure – Programmers Stack Exchange

parameter vs. argument

parameter和argument都被翻译成“参数”,它们也经常被混淆。其实很好更精准的翻译应该是“形参(formal parameter)”和“实参(actual argument)”。

parameters是定义函数时定义的那些变量,它们是函数类型识别(type signature)的一部分;
arguments是调用函数时传入到函数中的那些变量,它们是函数的输入值。

这称为也是相对的,比如说下边的例子:
[codesyntax lang=”java” lines=”normal”]

void foo(int x, int y) {
    bar(x, y);
}

[/codesyntax]
x和y对于foo函数来说是形参(parameter),而对于bar来说是实参(argument)。因此也可以说argument是parameter的实例。

References:

  • Parameter (computer programming) – Wikipedia, the free encyclopedia
  • function – “Parameter” vs “Argument” – Stack Overflow
  • language agnostic – Difference between parameter and argument – Stack Overflow

declaration vs. definition

申明(declaration)和定义(definition)这两个概念应该缘起于C/C++,因为写C/C++程序会分头文件(header files)和实现文件(implementation files)。方法和变量的申明部分一般放在头文件,定义部分则在实现文件里。

所以很容易理解

declaration是描述变量、方法、类的类型标识,它没有具体的实现;编译器看到申明部分不会分配内存,而是从其它地方找到其实现的定义。
definition是真正实例化变量,实现方法和类。编译器看到定义部分时就知道如何分配内存,在运行时分配相应大小内存去存放内容。

比如下边这些代码都属于申明:

[codesyntax lang=”cpp” lines=”normal”]

extern int bar;
extern int g(int, int);
double f(int, double); // extern can be omitted for function declarations
class foo; // no extern allowed for type declarations

[/codesyntax]

而下边的代码是对上述“申明”的具体“定义”:

[codesyntax lang=”cpp” lines=”normal”]

int bar;
int g(int lhs, int rhs) {return lhs*rhs;}
double f(int i, double d) {return i+d;}
class foo {};

[/codesyntax]

不严格的说“定义”也包含了“申明”的部分,应该单看定义中变量,方法和类的名字部分,那些可以算是“申明”。

 

在Java中并没有“申明”的概念,所有内容都是“申明”即“定义”。如果实在要说细分“申明”,不严格的讲可以把接口(interface)和抽象方法(abstract method)看做“申明”。但实际中我们还是会说“定义接口”,“定义抽象函数”。

References:

  • c++ – What is the difference between a definition and a declaration? – Stack Overflow
  • What’s the difference between declaring and defining in C and C++ – Cprogramming.com
  • What is the difference between declaration and definition in Java? – Stack Overflow
2015-01-30
30 January
On January 30, 2015
In Algorithm Analysis(算法分析), Data Structures(数据结构), Design Patterns(设计模式), Knowledge Base(心得笔库)

树结构遍历的实现汇总

在计算机数据结构中,树(Tree)结构是基础的结构之一,对于其定义、实现以及相关算法在一般的算法与数据结构书中都有详细介绍和分析。不过本文还是想要罗列一下树结构基本的遍历算法,同时简单随机介绍各种遍历算法的使用情境。

本文中将会实现树遍历主要两种方式:深度优先和广度优先。对于深度优先也会包括其三种不同方式:前序遍历、中序遍历、后续遍历。同时对于深度优先的三种方式还会包括最简单直观的递归实现,和相对复杂的迭代实现。

为方便起见文中的算法将基于二叉树(Binary Tree)结构,其树节点的结构也简单定义如下:

[codesyntax lang=”cpp” lines=”normal”]

using namespace std;
class Node {
public:
    Node *left;
    Node *right;
    int value;
};

[/codesyntax]

深度优先遍历

深度优先遍历隐藏着回溯法(Backtracking)应用,因此利用递归自动创建堆栈(stack)的性质,就可以非常好的实现这些遍历算法。虽然递归可以通过创建自定义的栈对象来变成迭代,但对于进栈出栈的控制,三种遍历方式有着不同的条件,因而实现反而变得复杂。

递归实现

对于节点的访问操作,定义了如下的方法,其实只是简单的输出节点的值再以空格分隔。对于空节点也将预留输出特别的符号来指示。

[codesyntax lang=”cpp” lines=”normal”]

#define NULL_NODE "#"

void operate(Node *node) {
    if (node == NULL) {
//        cout << (NULL_NODE" ");
    } else {
        cout << node->value << " ";
    }
}

[/codesyntax]

三种深度优先遍历的算法实现如下

[codesyntax lang=”cpp” lines=”normal”]

void preorder(Node *node) {
    if (node == NULL) {
        operate(NULL);
        return;
    }
    
    // operate node before any children
    operate(node);
    preorder(node->left);
    preorder(node->right);
}

void inorder(Node *node) {
    if (node == NULL) {
        operate(NULL);
        return;
    }
    
    inorder(node->left);
    // operate node in the middle of children
    operate(node);
    inorder(node->right);
}

void postorder(Node *node) {
    if (node == NULL) {
        operate(NULL);
        return;
    }
    
    postorder(node->left);
    postorder(node->right);
    // operate node after all child
    operate(node);
}

[/codesyntax]
Read More →

2014-04-28
28 April
On April 28, 2014
In Data Structures(数据结构), Design Patterns(设计模式), Language Tips(语言初试)

各种面向对象程序语言的toString方法实现

字符串(String)类型在程序语言中都有非常广泛的使用,因此字符串(String)也同整型、浮点型等一样被作为基本数据类型提供给开发者直接使用。在面向对象程序语言中,String作为对象的类,被赋予了各种方法来方便对String的操作和变换。而其他类,常常也会有默认的方法能让该类的实体对象转变成字符串(String)对象。比如最常见的就是Java和C#的toString()方法了。

将对象转换成字符串有几个好处:可以打印记录方便debug;可以存储为JSON或CSV等类型的文档又具有可读性。另一方面程序语言提供方法会在一些情况被隐式的调用来转换成字符串,比如对象和字符串拼接、String类型强制转换等等。开发者也可以重定义这些方法以得到希望的格式出现在上述情况中。

本文就来总结归纳一下当前流行的面向对象程序语言对“toString()”方法的实现方式。
Read More →

2014-03-31
31 March
On March 31, 2014
In Data Structures(数据结构), English Posts(英文写作), Language Tips(语言初试), Mobile Development(移动开发)

Introduction to Loc (Lua Objective-C)

Recently we were starting to use Lua in our game. Lua is a very popular scripting language in the game industry. It’s written in pure C and is very lightweight. We can simply add Lua source code to our project, and it is very easy to compile and run.

However, in practice we encountered issues with type conversion between Lua and Objective-C. In the beginning, we followed instructions to create C functions, and inside the functions we called Objective-C methods, then registered those functions into Lua State as library. When requirements went more complicated, we have to create a bunch of C functions, which are redundancy in a lot of places. This is really not an ideal to bridge between Lua and Objective-C.

After reading the Lua instructions for two days, and with knowledge about iOS7 JavaScript Framework, I decided to create a similar framework to handle type conversion between these two languages. The good thing is Objective-C is a superclass of C, and Lua is naturally compiled from C, this makes it very easy to construct a bridge and make them communicating with each other. With reflection from Objective-C, it’s also very convenient to call Objective-C methods from Lua.

Loc (Lua Objective-C) is the framework I created to convert type between Lua and Objective-C for our project. It’s as simple as Lua, with only 6 packages. It reduces a lot of time to create functions mapping Lua call, and it works pretty well so far.

With the permission from my company, I shared the slides that I presented to my colleagues about the design and syntax about Loc. I am trying to persuade my managers to make it open source, so more developers could use it to prove the usability and make the framework more mature.

2013-07-18
18 July
On July 18, 2013
In Algorithm Analysis(算法分析), Data Structures(数据结构), Knowledge Base(心得笔库)

从优化到再优化,最长公共子串

最长公共子串(Longest Common Substring)是一个非常经典的面试题目,在实际的程序中也有很高的实用价值,所以把该问题的解法总结在本文重。不过不单单只是写出该问题的基本解决代码而已,关键还是享受把学习算法一步步的优化,让时间和空间复杂度一步步的减少的惊喜。

概览

最长公共子串问题的基本表述为:

给定两个字符串,求出它们之间最长的相同子字符串的长度。

最直接的解法自然是找出两个字符串的所有子字符串进行比较看他们是否相同,然后取得相同最长的那个。对于一个长度为n的字符串,它有n(n+1)/2 个非空子串。所以假如两个字符串的长度同为n,通过比较各个子串其算法复杂度大致为O(n4)。这还没有考虑字符串比较所需的时间。简单想想其实并不需要取出所有的子串,而只要考虑每个子串的开始位置就可以,这样可以把复杂度减到O(n3)。

但这个问题最好的解决办法是动态规划法,在后边会更加详细介绍这个问题使用动态规划法的契机:有重叠的子问题。进而可以通过空间换时间,让复杂度优化到O(n2),代价是空间复杂度从O(1)一下子提到了O(n2)。

从时间复杂度的角度讲,对于最长公共子串问题,O(n2)已经是目前我所知最优的了,也是面试时所期望达到的。但是对于空间复杂度O(n2)并不算什么,毕竟算法上时间比空间更重要,但是如果可以省下一些空间那这个算法就会变得更加美好。所以进一步的可以把空间复杂度减少到O(n),这是相当美好了。但有一天无意间让我发现了一个算法可以让该问题的空间复杂度减少回原来的O(1),而时间上如果幸运还可以等于O(n)。
Read More →

2013-06-06
06 June
On June 6, 2013
In Article Collection(聚宝收藏), Knowledge Base(心得笔库), Language Tips(语言初试)

小心程序运算符的陷阱

每一门程序语言都会提供各种运算符(Operator),每个运算符都会有特定的含义和规则,去完成指定操作最后给出相应的结果。有些运算符会普遍出现在各种语言中,比如加减乘除这些算数运算符;有些运算符则为某些语言特有,比如取地址运算符和反引用运算符只在C/C++中用到而Java,C#这类不能直接访问地址的程序语言就不具有;有些运算符因为特定的需要,还会改变其一般的含义,比如加法运算符在很多语言都被作为字符串拼接的操作符。学习一门程序语句,除了学习其语法以外还要了解其所拥有的运算符,但是因为各个语言运算符的相似性,常常让人简单略过对它们的了解。

运算符最主要有两个特性:优先级(Precedence)和结合律(Associativity)。在很早以前我的《两年半大学总结》讲到过自己对运算符, 特别是优先级的问题上的一些理解。在之后的学习和编写程序的过程中,我常常发现原来运算符的这两个特性会给代码带来隐形的意想不到的陷阱。所以我将实际中碰到的一些关于运算符的问题罗列于此,希望能对这些问题提高警惕以免跌入陷阱。
Read More →

2013-04-23
23 April
On April 23, 2013
In Algorithm Analysis(算法分析), Data Structures(数据结构), Mathematical Theory(数学理论), Special Tricks(奇技妙招)

寻找比特位

人类有十个手指,所以我们的算数都是10 进制的,而计算机的世界里,所有事物都只由0和1呈现出来,所以数字也只能用2进制表示。因为2进制的表示方式,在计算机里对于数字的运算,除了现实中常用的“加减乘除”,更多了“与非或”这些位运算。

在进行数学运算的过程中,我们经常会总结出一些技巧方法,而这些方法其实跟进制有很大的关系。比如小学老师就告诉我们:检查一个整数能否被3整除,只要派定各个数位上的数字加起来是否能被3;判定一个整数是否能被5整除,只要看最后一位是不是0或5。而这些规律却不能适用到2进制表示的数字上。

不过利用2进制的特殊性,我们也能从位运算上找到很多的技巧。比如一个常见的面试问题:

有一组数包含了1到100的整数,且每个整数只出现一次且随机出现于数组中,现在有一个数被从中删除,请找出被删除的数。

Read More →

2012-09-08
08 September
On September 8, 2012
In Algorithm Analysis(算法分析), Knowledge Base(心得笔库)

二分查找法的实现和应用(进阶篇)

在《二分查找法的实现和应用汇总》中,我介绍了二分查找法的基本应用,不过在面试的准备过程中,我还碰到了更多对于二分查找法的更进一步的使用。其实在《二分查找法的实现和应用汇总》的最后,我已经介绍了一个非常规的使用,也就是基于“轮转后的有序数组(Rotated Sorted Array)”检查某一个数是否存在。

在此篇文章中,我将进一步介绍更多我碰到的一些二分查找法的应用。
Read More →

2012-05-03
03 May
On May 3, 2012
In Algorithm Analysis(算法分析), Data Structures(数据结构), Knowledge Base(心得笔库), Language Tips(语言初试)

画虎画皮难画骨,编程编码难编译

古语“画虎画皮难画骨”,是说画老虎时要画它的外表很容易,可要将老虎的气势画出来却很难。

对于现在的程序员来说,似乎也是这样子,可以写出整洁的代码,设计出优异的程序,但却不一定需要知道代码在编译之后的是如何运行的。

但是有时候,能了解表面背后的故事,知道一些程序编译过程,其实对写出一个正确的正确的程序会有很大的帮助,这起源自一段很简单的问题实现:两整数交换。
Read More →

2012-04-10
10 April
On April 10, 2012
In Data Structures(数据结构), Language Tips(语言初试)

C++仿制静态构造函数

在《C++的头文件和实现文件分别写什么》文章中,我对于的C++的数据成员,逐个分析了可以作用在它们上边的限定符都有哪些,以及它们所对应的进行初始化的位置。可以看出这些修饰符其实就是const和static的两种的组合,但是却有不同的效用。

本文,我想讲关于static的问题,《C++的头文件和实现文件分别写什么》已经指出如果数据成员被声明为static,那么它在编译时就必须被初始化。仅含static的则放在类之外,实现文件之中;同时含有的const的则放在类之内,直接跟在数据的定义之后。

在我实际代码编写中碰到的问题是:static成员的初始化比较的复杂,步骤较多,需要调用另一个函数来完成。此时,简单使用赋值语句就不太能完成那些目的了。
Read More →

Posts pagination

1 2 Next
Facebook
Twitter
LinkedIn
RSS
ZhiHu

Recent Posts

  • 三年居家工作感受
  • Pixel Watch智能手表和Pixel 5, 6 Pro 及 7 Pro手机
  • 我拥有过的无线耳机
  • 毕业工作一个月,我差点被开除
  • 我拥有过的移动硬盘
  • ProtoBuf 2.0 method count optimization for android development
  • 面过100场行为面试后

Categories

  • Algorithm Analysis(算法分析)
  • Article Collection(聚宝收藏)
  • Data Structures(数据结构)
  • Design Patterns(设计模式)
  • English Posts(英文写作)
  • Front Interface(界面构想)
  • IT Products(数码产品)
  • Knowledge Base(心得笔库)
  • Language Tips(语言初试)
  • Mathematical Theory(数学理论)
  • Mobile Development(移动开发)
  • Programming Life(程序人生)
  • Reading Notes(阅而后知)
  • Software Engineering(软件工程)
  • Special Tricks(奇技妙招)
  • Tangential Speech(漫话杂谈)

Tags

Aero Android API Bash Binary Search Bitwise Operation Book C/C++ Career Chrome Conference CSS Debug Device DOM Extension Framework Game Gradle Hearthstone HTML Initialization Intellij Interview iOS Java JavaScript jQuery Keyword Language Issues Mac Microsoft Mobile Modifier Objective-C PHP Principle Reference Regular Expression Static String Tools Tutorial UI XML

Blogroll

  • Ahmed's Blog
  • Gert Lombard's Blog
  • Gordon Luk
  • Jack & Allison
  • 开发部落

Archives

Designed using Chromatic. Powered by WordPress.