====================
== Hi, I'm Vimiix ==
====================
Practice makes perfect (ง •̀_•́)ง

《算法图解》读书笔记5-散列函数及扩展

algorithms Linux

散列函数

散列函数就是一种映射,是从关键字到存储地址的映射。通常,包含散列函数的算法的算法复杂度都为 O(1),对应到 Python 中的数据结构就是字典,给一个 key 可以得到一个固定的 value 值。散列函数必须满足一些要求:

  • 它必须是一直的。例如,假设输入 apple 时得到的是 4,那么每次输入 apple 时,都必须是 4,不然这个散列函数就是无意义的;
  • 散列函数应该将不同的输入值,对应到不同的值上。(虽然不同的 key 对应相同的 value 是允许的,但最理想的情况是不同的 key,对应不同的 value,这种称之为完美散列
Read more...

《算法图解》读书笔记4-分治思想和快排

algorithms Linux

分而治之(Divide and Conquer)

所谓分而治之,分为分解问题,但我们目的是解决大问题,所有还有将分解后得到的结果贡献回大问题,最终使得我们解决大问题。

分而治之的思想是采用了递归的思想,将原问题分成几个规模较小但是类似于原问题的子问题, 通过递归的方式来求解这些小问题,最后将子问题的解合并来得到原问题的解。分治思想的本质是我们中学时候学的数学归纳法。

书上提到,使用分治思想解决问题的过程包括两个步骤,其实应该是三个步骤:

  1. 找出基线条件,这种条件必须尽可能简单。
  2. 不断将问题分解为子问题(或者说缩小规模),直达符合基线条件。
  3. 合并子问题的结果,得到最终问题的解(利用系统栈的特性实现过程状态的记录)
Read more...

《算法图解》读书笔记2-数组链表和选择排序

algorithms linux sort

理解数组和链表

链表和数组是两种基本的数据结构,他们的区别在于数据在内存中的存储方式不同。

数组

数组在内存中是用一块连续的内存来存储数据的,数组中的每个数据地址是连续的。数组中的每个元素所占用的内存是相同的,所以,我们可以通过下标索引在常数数量级的时间内,迅速访问数组中的任何一个元素。但是要在数组中任意位置添加一个元素,就需要移动大量的元素,使得内存中空出一个位置来存放新插入的元素。同理,当删除一个元素的时候,也需要移动大量的元素,来使得删除元素以后的数组数据在内存中仍旧是连续的。

由此可见:当对于一组数据,读取操作频繁,写操作少的情况,应该使用数组数据结构。

Read more...

《算法图解》读书笔记3-递归

algorithms Linux

如果使用循环 ,程序的性能可能更高;如果使用递归,程序可能更容易理解。如何选择要看什么对你来说更重要。

递归函数

在一个函数中,可以调用另一个函数,如果调用的另一个函数是函数本身,这样的函数就是递归函数。如下示例:

def foo(x):
    if x == 0:
        return 'end'
    else:
        # 在函数中继续调用自己
        return foo(x-1)
Read more...

《算法图解》读书笔记1-二分和大O

algorithms Linux

算法是一组完成任务的指令

为什么要学习算法

这次是我第二次读《算法图解》,当我第一次看这本书的时候,我更兴奋于书中有什么内容,迫不及待的去过内容,学习那些算法概念。但当我第二次准备开始读这本书的时候,我脑海中出现的了一个问题:“为什么要学习算法?”,这个问题也许会有人和我一样,之前根本没有好好的去思考,只是知道,作为一个程序员我应该学习算法。当然,能够有这个觉悟,说明我们还算是个合格的程序员。

但是,不妨认真思考一下,为什么要学习算法?算法应该怎么学?

Read more...

TLPI笔记—深入文件I/O模型

tlpi Linux note I/O

原子操作和竞争操作

所有的系统调用都是以原子操作方式执行的。之所以这么说,是指内核保证了某系统调用中的所有步骤会作为地理操作而一次性加以执行,期间不会被其他进程或线程中断。原子性规避了竞争状态(race condition),竞争状态指:操作共享资源的两个进程(或线程)其结果取决于一个无法预期的顺序,即这些进程或线程获得 CPU 使用权的先后相对顺序。

Read more...

TLPI笔记—通用文件I/O模型

tlpi Linux note I/O

文件描述符

所有执行 I/O 操作的系统调用都是以文件描述符,一个非负整数来指代打开的文件。文件描述符用以表示所有类型的已打开的文件,包括管道(pipe)、FIFO、socket、终端、设备和普通文件。每个进程都各自独立维护着一张文件描述符表。

标准文件描述符

文件描述符用途POSIX 名称stdio 流
0标准输入STDIN_FILENOstdin
1标准输出STDOUT_FILENOstdout
2标准错误STDERR_FILENOstderr
Read more...

TPLI笔记—linux/unix标准和历史

tlpi Linux note POSIX

前言

最近开始阅读《Linux/Unix 系统编程手册》 这本书,重新系统的学习一下 linux 系统编程方面的知识。

在阅读完第一章《历史和标准》以后,对于很多标准名词都见过,但是对于他们之间的发展历程很是模糊,通读这部分内容后豁然开朗,尤其本章最后总结部分,对于前面的概况的既简练还没有遗漏。不禁在书上用笔写下:“牛 B 总结,一气呵成”

方便以后不去翻书回顾,特花点时间摘录至此。

Read more...

[python]记录关于websocket的原理和使用

Python websocket note django

什么是 websocket

WebSocket 是一种在单个 TCP 连接上进行全双工通讯的协议。WebSocket 使得客户端和服务器之间的数据交换变得更加简单,允许服务端主动向客户端推送数据。在 WebSocket API 中,浏览器和服务器只需要完成一次握手,两者之间就直接可以创建持久性的连接,并进行双向数据传输。

Websocket 是一个持久化的协议,相对于 HTTP 这种非持久的协议来说的。

举个例子:

HTTP 的生命周期通过 Request 来界定,也就是发送一次 Request,收到一次 Response ,那么在 HTTP1.0 中,这次 HTTP 请求就结束了

在 HTTP1.1 中进行了改进,使得有一个 keep-alive,也就是说,在一个 HTTP 连接中,可以发送多个 Request,接收多个 Response。但是请记住 Request = Response , 在 HTTP 中永远是这样,也就是说一个 request 只能有一个 response。而且这个 response 也是被动的,不能主动发起。

而对于 websocket 来说,在 HTTP 的握手基础上建立起链接,服务器端可以主动的向客户端发送数据。

Read more...

[笔记]git push卡主不动问题记录:Git push hangs on POST git-receive-pack

git note solution

问题

昨天完成了《一个完整的 Django 入门指南》 - 第 6 部分的翻译工作,本地在翻译的过程中,存储了十几张原文中的 png 格式的插图。

git push 提交 github 仓库的时候,终端显示写成功 100%, 但是一直卡在了下面这里没有推送成功:

Counting objects: 21, done.
Delta compression using up to 8 threads.
Compressing objects: 100% (21/21), done.
Writing objects: 100% (21/21), 1018.52 KiB | 17.87 MiB/s, done.
Total 21 (delta 7), reused 0 (delta 0)
# 卡在这里
Read more...
上一页 4 of 9 下一页