Skip to content
Ider

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

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

Binary Search

2020-03-12
12 March
On March 12, 2020
In Data Structures(数据结构), Knowledge Base(心得笔库), Language Tips(语言初试), Mobile Development(移动开发)

基础数据类型的包装类的内存大小

谈到 Java 的基础数据类型(Primitive Data Types),可以找到很多关于其种类以及内存大小的文章。基础数据类型对应的包装类(Wrapper Classes)也会介绍自动装箱(Autoboxing)和拆箱(Unboxing),以及带来的效率上的影响。但可能是因为Java一般所使用的环境都有比较充足的内存,似乎从来没有人讨论过每种包装类所占的内存大小以及对内存溢出可能造成的影响。

到了 Android 应用程序开发领域,由于设备硬件本身以及系统对各个程序在资源使用上的约束,就会出现很多特别的使用习惯,比如推荐使用Typedef来替代枚举类型(enum)来减少内存使用和方法数。因此关于基础数据类型的包装类所占内存大小就值得写篇博客来研究一下。

包装类所占内存大小

网上我找了很多计算类内存大小的方法,但是既然我是 Android 工程师,我就用 Android Studio 提供的 Memory Profiler 来查看内存使用情况

下边就是我用来做内存检查的类,它包含了所有基础数据类型和对于的包类型

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

public class Primitives {
  boolean pBoolean;
  byte pByte;
  char pChar;
  double pDouble;
  float pFloat;
  int pInt;
  long pLong;
  short pShort;

  Boolean cBoolean;
  Byte cByte;
  Character cChar;
  Double cDouble;
  Float cFloat;
  Integer cInt;
  Long cLong;
  Short cShort;

  public Primitives() {}

  public Primitives(Void v) {
    cBoolean = false;
    cByte = 0;
    cChar = '\0';
    cDouble = 0.0;
    cFloat = 0.0f;
    cInt = 0;
    cLong = 0L;
    cShort = 0;
  }
}

[/codesyntax]

接着在 MainActivity 中创建两个 Primitives 类的字段:一个没有初始化对象类型,一个将所有对象类型初始化成默认值。然后运行程序,在 Android Studio 中打开 Profiler 查看内存时”Dump Java heap” 就可以看到这两个 Primitives 对象内存使用情况

从图中的结果可以看出如果对象的值是 null,那他们是不占用空间。在这一点上看,如果字段大部分时间都存的是空值或者以空值指代默认值,那相对比总是会被赋予默认值的基础数据类型在内存使用方面要好一些。

对于包装类,它们都比其对应基础数据类型要占用更多的内存空。仔细对比不难计算出他们的差别都是 8 bytes,正好是一个普通 Object 实例的大小。这也证明的包装类只是对基础数据类型的简单包装。

基础数据类型 包装类型
类型 大小 类型 大小
boolean 1 byte Boolean 9 bytes
byte 1 byte Byte 9 bytes
char 2 bytes Character 10 bytes
double 8 bytes Double 16 bytes
float 4 bytes Float 12 bytes
int 4 bytes Integer 12 bytes
long 8 bytes Long 16 bytes
short 2 bytes Short 10 bytes

所以,使用包装类不仅会有自动装箱和拆箱产生的效率上的影响,对内存的使用也有很大的影响。而 Android 的内存又是稀缺资源,所以 Android 库里多了特殊的数据类型来优化内存的使用,比如 SparseArray 替换以 int 为主键的 HashMap。
Read More →

2018-09-24
24 September
On September 24, 2018
In Programming Life(程序人生), Tangential Speech(漫话杂谈)

我的四次Facebook面试经历

在 FB 已经工作了已经快三年了,在这段日子里我学到了很多也成长得很快,一切似乎都有序地推进着,可回过头看加入 FB 的过程却有些一波三折。翻看邮件记录,我总共面了 FB 四次:头两次面完后我被拒了,第三次拿到了Offer但换成我拒了他们,直到第四次才达成一致加入进来。

 

第一次面试是在研究生刚毕业的时候,那会儿社交网络正火,对于 FB 和 Twitter 这些比较热门的公司都会收到很多简历,所以对于New Grad来说申请的门槛却要高很多,我也尝试网上申请但都石沉大海。

后来是通过 Interviewstreet (网站现在已经更名为 HackerRank 了)这个在线程序测试平台才拿到了面试机会。当时 Interviewstreet 上的题库很小但难度很高,只要做完8道题就可以解锁网站上公司申请功能。我当时只是觉得在上边做题很有趣,就一直不停地钻研着,也要感谢一位学长在题目解法上给了我很多的指点让我更快地领悟了各种算法的真谛。在艰难地完成了8道题后,我就随便点了网站上包括 FB 在内的几个知名公司提交了申请,我也没有觉得会有下文只是继续在上边做题来努力提高排位。

在我去 Seattle 面试 Amazon 的路上,我收到了 Interviewstreet 给 FB recruiter的引荐邮件。这让我感到非常惊喜,立刻表达了我强烈的兴趣,然后顺利安排了电话面试。电面一共面了两题,第一题很快就解决了,但是第二道关于二分查找的变体我却卡在了条件检查上了,最后是通过电子邮件把最后的答案发了过去。在邮件里我还把我写二分法的博客链接贴了上去来表达我是懂这个算法,好在面试官给了我 onsite 的机会。

因为那时候在忙着毕业的事情,还要带家人在美国游玩,所以把面试安排到了一个月以后。也因为如此,我并没有能够充分地去准备面试。


Read More →

2015-12-28
28 December
On December 28, 2015
In Algorithm Analysis(算法分析), Knowledge Base(心得笔库), Programming Life(程序人生)

聊聊刷题

在之前的《谈谈面试》中我讲述了我在面试上的经历和看法,而对于软件行业的面试很多都要求被面试者解决一些编程上的问题。这类面试有很多名字:算法题(Algorithm Question)、编程题(Programming Problem)、考代码(Coding Interview)等等,但基本形式都是:给出一道问题的描述和目的,要求写出程序能够接受相应的参数然后完成目标需求最终得到结果。

大部分常见的这类面试问题都被大家总结在了网上,可以直接搜索找到,或者在一些论坛的特定板块(比如未名空间的待字闺中,一亩三分地的面经)里见到讨论,甚至形成了在线测试网站(比如LeetCode、LintCode)直接验证程序的正确性。

由于面试题目的公开性,造就了软件行业特殊的面试准备过程:刷题。很多朋友也会问我:“出去面试还刷题吗?”准确地讲,我刷过算法题目,也经常后悔没有早在还在学校里时就开始刷题,那样就能更早地进入心仪的公司。但现在出去面试前基本都还是忙着正常的工作,不会专门去练习题目。

刷题的目是理解算法和数据结构

好比读书的时候每次老师教授了新的知识后都会布置习题,完成那些作业可能会让我们在考试中碰到原题而拿到高分,但正真的作用是帮助我们理解和消化所学的知识。从简单的理解:“程序=算法+数据结构”,要写好程序就必须去熟悉算法和数据结构,刷题就应该是完成这样的作用。如果题目做不出来,就说明连最基本写程序的能力都没有,自然很难得到公司的青睐。

我常常幻想如果我高考没有失常,能进入更好的学校学习计算机知识,甚至参加ACM小组,得到老师在算法上更好的点拨指导,也因为要参加计算机竞赛,我也会练习更多的题目,现在就不需要刷题了。但现实是在我就读的大学里,算法只是一门选修课,我也没有参加过任何计算机竞赛。但联想高中数学竞赛的培训过程,老师肯定会分类进行知识传授和练习。所以刷题也一样要分类进行强化训练。

LeetCode虽然是最火的题库,但是在我刷题的时候它只是简单的罗列一百多道题目(可参看我的不完全题解列表),所以当时我更倾向去做UVa上的题目。那上边有上千道题目,肯定是不可能做完的,但是有比较好的分类专区,可以专门的加强某一特定算法和数据结构的基础知识。

一开始我连最简单的二分查找(Binary Search)算法都写不好,但是在反复练习之后,我也能总结出二分法的实现,并汇总一些变形题目到博客里。刚毕业那会找工作,好多次面试都挂在了二叉树(Binary Tree)上,后来做遍各类遍历算法,总结了不同的实现方式,就不再担心关于树的操作。动态规划(Dynamic Programming)在我看来是面试时会碰到最难的问题,后来我发现这类问题的关键在于找到类似于数学中的“递归公式”,这样就可以找到递归的实现,之后利用空间来存放中间值来减少时间复杂度。
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-04-01
01 April
On April 1, 2012
In Algorithm Analysis(算法分析), Knowledge Base(心得笔库)

二分查找法的实现和应用汇总

在学习算法的过程中,我们除了要了解某个算法的基本原理、实现方式,更重要的一个环节是利用big-O理论来分析算法的复杂度。在时间复杂度和空间复杂度之间,我们又会更注重时间复杂度。

时间复杂度按优劣排差不多集中在:

O(1), O(log n), O(n), O(n log n), O(n2), O(nk), O(2n)

到目前位置,似乎我学到的算法中,时间复杂度是O(log n),好像就数二分查找法,其他的诸如排序算法都是 O(n log n)或者O(n2)。但是也正是因为有二分的 O(log n), 才让很多 O(n2)缩减到只要O(n log n)。
Read More →

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.