卡瓦邦噶！ | 无法自制的人得不到自由。

Java优先队列(PriorityQueue)介绍

Posted on 2016年10月8日 by laixintao Leave a comment

队列(Queue)这种数据结构，是”先来先服务”(FIFO)的。但是有的时候，我们需要对“优先级”高的对象先处理。或者说，我们想在队列中按照我们喜欢的样子排序。

Java 1.5，开始引入了优先队列（PriorityQueue）。

继承自 AbstractQueue
泛型要实现Java Comparable或使用Comparator比较
大小不固定
非线程安全的(线程安全的是PriorityBlockingQueue)

简单来说，要使用这个队列，那么放入队列的对象要实现Comparable接口。之后，队列在添加元素的时候，就会根据这个方法，放入合适的位置。取出的时候，会弹出排在最前面的元素。

下面，我们通过一个例子体会一下优先队列的作用和用法。

这个练习题来自HackkerRank：Java Priority Queue

题目要求

学生有token，成绩，名字。每次输入一个命令，如果是“ENTER”，就添加新的学生进来，按照成绩排序放入。如果成绩相同，按照名字字母序放入。如果名字也相同，就按照token放。如果命令是“SERVED”，就弹出最前面的同学。最后，打印剩下的队列，如果为空，打印“EMPTY”。

输入示例

12
ENTER John 3.75 50
ENTER Mark 3.8 24
ENTER Shafaet 3.7 35
SERVED
SERVED
ENTER Samiha 3.85 36
SERVED
ENTER Ashley 3.9 42
ENTER Maria 3.6 46
ENTER Anik 3.95 49
ENTER Dan 3.95 50
SERVED

ENTER John 3.75 50

ENTER Mark 3.8 24

ENTER Shafaet 3.7 35

SERVED

ENTER Samiha 3.85 36

SERVED

ENTER Ashley 3.9 42

ENTER Maria 3.6 46

ENTER Anik 3.95 49

ENTER Dan 3.95 50

SERVED

输出示例

Dan
Ashley
Shafaet
Maria

Dan

Ashley

Shafaet

Maria

我的代码：

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class Student implements Comparable<Student>{
    private int token;
    private String fname;
    private double cgpa;
    public Student(int id, String fname, double cgpa) {
        super();
        this.token = id;
        this.fname = fname;
        this.cgpa = cgpa;
    }
    public int getToken() {
        return token;
    }
    public String getFname() {
        return fname;
    }
    public double getCgpa() {
        return cgpa;
    }

    @Override
    public String toString() {
        return this.fname;
    }

    @Override
    public int compareTo(Student student) {
        int result;
        if(this.cgpa!=student.getCgpa()){
            result = this.cgpa < student.getCgpa() ? 1:-1;
        }else if(!this.fname.equals(student.getFname())){
            result = this.fname.compareTo(student.getFname());
        }else{
            result = -(this.token - student.getToken());
        }
        return result;
    }
}

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int totalEvents = Integer.parseInt(in.nextLine());
        Queue<Student> queue = new PriorityQueue<Student>();

        while(totalEvents>0){
            String cmd = in.next();
            if(cmd.equals("ENTER")){
                String name = in.next();
                double cgpa = in.nextDouble();
                int id = in.nextInt();
                queue.add(new Student(id,name,cgpa));
            }else if(cmd.equals("SERVED")){
                queue.poll();
            }
            totalEvents--;
        }
        if(queue.isEmpty()){
            System.out.println("EMPTY");
        }else{
            while (!queue.isEmpty()){
                System.out.println(queue.poll());
            }
        }
    }
}

import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

class Student implements Comparable<Student>{

private int token;

private String fname;

private double cgpa;

public Student(int id, String fname, double cgpa) {

super();

this.token = id;

this.fname = fname;

this.cgpa = cgpa;

}

public int getToken() {

return token;

}

public String getFname() {

return fname;

}

public double getCgpa() {

return cgpa;

}

@Override

public String toString() {

return this.fname;

}

@Override

public int compareTo(Student student) {

int result;

if(this.cgpa!=student.getCgpa()){

result = this.cgpa < student.getCgpa() ? 1:-1;

}else if(!this.fname.equals(student.getFname())){

result = this.fname.compareTo(student.getFname());

}else{

result = -(this.token - student.getToken());

}

return result;

}

public class Solution {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int totalEvents = Integer.parseInt(in.nextLine());

Queue<Student> queue = new PriorityQueue<Student>();

while(totalEvents>0){

String cmd = in.next();

if(cmd.equals("ENTER")){

String name = in.next();

double cgpa = in.nextDouble();

int id = in.nextInt();

queue.add(new Student(id,name,cgpa));

}else if(cmd.equals("SERVED")){

queue.poll();

}

totalEvents--;

}

if(queue.isEmpty()){

System.out.println("EMPTY");

}else{

while (!queue.isEmpty()){

System.out.println(queue.poll());

}

通过这个例子，可以很好地理解优先队列了。

参考资料

Java优先队列（PriorityQueue）示例

详解 Python 的 “==” 和 “is”

Posted on 2016年10月6日 by laixintao Leave a comment

Python中比较两个对象是否相等，一共有两种方法，简单来说，它们的区别如下：

is是比较两个引用是否指向了同一个对象（引用比较）。
==是比较两个对象是否相等。

>>> a = [1, 2, 3]
>>> b = a
>>> b is a # a的引用复制给b，他们在内存中其实是指向了用一个对象
True 
>>> b == a # 当然，他们的值也是相等的
True
>>> b = a[:] # b通过a切片获得a的部分，这里的切片操作重新分配了对象，
>>> b is a # 所以指向的不是同一个对象了
False
>>> b == a # 但他们的值还是相等的
True

>>> a = [1, 2, 3]

>>> b = a

>>> b is a # a的引用复制给b，他们在内存中其实是指向了用一个对象

True

>>> b == a # 当然，他们的值也是相等的

True

>>> b = a[:] # b通过a切片获得a的部分，这里的切片操作重新分配了对象，

>>> b is a # 所以指向的不是同一个对象了

False

>>> b == a # 但他们的值还是相等的

True

实现原理

is比较的是两者是否是同一个对象，所以比较的是内存地址（id是否相同）。

Python文档3.1 对象、值和类型中是这样说的：

每个变量都有标识、类型和值。对象一旦创建，它的标识绝不会变；你可以把标识理解为对象在内存中的地址。is运算符比较两个对象的标识；id()返回对象标识的证书标识。

对象ID真正的意义在不同的实现中也不同，在CPython中，id()返回的对象的内存地址，在其他解释器中可能是别的意义。但重要的是，它一定能表示唯一的对象并且在对象的生命周期内不变，不同对象的标识一定是不一样的。

==是值比较。不可变对象，例如int，str，它会直接进行值比较。对于Python已知的对象，会调用他们的__eq__函数来比较。（其实已知的对象应该也是通过内置的__eq__函数来比较的）。对于自定义的对象，如果实现了__eq__函数，就会使用它比较，如果没有实现，效果和==是一样的。

对象缓存机制

Python会对比较小的对象缓存，下次用到比较小的对象时，会去缓存区查找，如果找到，不会再开辟新的内存，而是继续把小对象的地址赋给新的值。例子：

>>> c = 1
>>> d = 1
>>> print(c is d) 
True

>>> 1000 is 10**3
False
>>> 1000 == 10**3
True

>>> c = 1

>>> d = 1

>>> print(c is d)

True

>>> 1000 is 10**3

False

>>> 1000 == 10**3

True

通过计算得到的赋值，不会使用缓存区。从第一个代码示例中可以看出。

对于字符串，你可以通过使用intern函数强制使用缓存区。

总结

这一段总结引用自《Fluent Python》，我觉得写的非常好：

is运算符比==快，因为它不能被重载，所以Python不必寻找并调用特殊方法，而是直接比较两个证书id。而a == b 则是一个语法糖，等同于a.__eq__(b)。继承自object的__eq__方法比较两个对象的id，结果与is一样。但是多数内置类型使用更有意义的方法覆盖了__eq__方法，会考虑对象属性的值。相等性测试可能涉及大量处理工作，例如，比较大型集合或嵌套层级深的结构时。

参考

Is there a difference between `==` and `is` in Python?
python源码学习（八）——string对象的intern机制
比较python类的两个instance(对象) 是否相等
《Fluent Python》8.2 标志、相等性和别名

Apache2 AH00558 警告解决办法

Posted on 2016年8月18日 by laixintao Leave a comment

Apache2 在Ubuntu下有下面的警告：

AH00558: apache2: Could not reliably determine the server's fully qualified domain name, using 127.0.0.1. Set the 'ServerName' directive globally to suppress this message

1	AH00558: apache2: Could not reliably determine the server's fully qualified domain name, using 127.0.0.1. Set the 'ServerName' directive globally to suppress this message

如果是在服务器端，那么127.0.0.1就是你的服务器内网IP。

查了一下资料，在/etc/apache2/httpd.conf文件中添加一行ServerName localhost就可以解决，但是我在Ubuntu下并没有找到httpd.conf配置文件。

解决方法：在Ubuntu下，相应的文件应该是apache2配置目录（默认是/etc/apache2/）下面的apache2.conf。所以搞定这个警告的具体步骤如下：

~ echo "ServerName localhost" > /etc/apache2/apache2.conf
~ service apache2 restart

1 2	~ echo "ServerName localhost" > /etc/apache2/apache2.conf ~ service apache2 restart

参考：https://aslamnajeebdeen.com/how-to-fix-apache-could-not-reliably-determine-the-servers-fully-qualified-domain-name-using-127011-for-servername-error-on-ubuntu

Mac pyenv安装失败的解决办法

Posted on 2016年8月15日 by laixintao 3 Comments

写了很久的Python2，今天被Python3 *等特性吸引了，忍不住想试一下。

在MAC OS X上Python的多版本共存，我们可以使用pyenv来解决，配合virtualenv，可以轻松搭建多个虚拟环境。

但是安装的时候，遇到了两个问题。

~ pyenv install 3.5-dev
Cloning https://hg.python.org/cpython...

BUILD FAILED (OS X 10.11.6 using python-build 20150818)

~ pyenv install 3.5-dev

Cloning https://hg.python.org/cpython...

BUILD FAILED (OS X 10.11.6 using python-build 20150818)

在官网的issues#429发现，用下面的方式解决。

~ brew link --force openssl
Linking /usr/local/Cellar/openssl/1.0.2d_1... 1548 symlinks created

1 2	~ brew link --force openssl Linking /usr/local/Cellar/openssl/1.0.2d_1... 1548 symlinks created

然后又遇到了下面的问题：

~ pyenv install 3.5-dev
Cloning https://hg.python.org/cpython...
Installing Python-3.5-dev...

BUILD FAILED (OS X 10.11.6 using python-build 20150818)

Inspect or clean up the working tree at /var/folders/23/4kbs9t712jv1mvmw6cpjwr2m0000gn/T/python-build.20160815000934.22185
Results logged to /var/folders/23/4kbs9t712jv1mvmw6cpjwr2m0000gn/T/python-build.20160815000934.22185.log

Last 10 log lines:
  File "/private/var/folders/23/4kbs9t712jv1mvmw6cpjwr2m0000gn/T/python-build.20160815000934.22185/Python-3.5-dev/Lib/ensurepip/__main__.py", line 4, in <module>
    ensurepip._main()
  File "/private/var/folders/23/4kbs9t712jv1mvmw6cpjwr2m0000gn/T/python-build.20160815000934.22185/Python-3.5-dev/Lib/ensurepip/__init__.py", line 209, in _main
    default_pip=args.default_pip,
  File "/private/var/folders/23/4kbs9t712jv1mvmw6cpjwr2m0000gn/T/python-build.20160815000934.22185/Python-3.5-dev/Lib/ensurepip/__init__.py", line 116, in bootstrap
    _run_pip(args + [p[0] for p in _PROJECTS], additional_paths)
  File "/private/var/folders/23/4kbs9t712jv1mvmw6cpjwr2m0000gn/T/python-build.20160815000934.22185/Python-3.5-dev/Lib/ensurepip/__init__.py", line 40, in _run_pip
    import pip
zipimport.ZipImportError: can't decompress data; zlib not available
make: *** [install] Error 1

~ pyenv install 3.5-dev

Cloning https://hg.python.org/cpython...

Installing Python-3.5-dev...

BUILD FAILED (OS X 10.11.6 using python-build 20150818)

Inspect or clean up the working tree at /var/folders/23/4kbs9t712jv1mvmw6cpjwr2m0000gn/T/python-build.20160815000934.22185

Results logged to /var/folders/23/4kbs9t712jv1mvmw6cpjwr2m0000gn/T/python-build.20160815000934.22185.log

Last 10 log lines:

File "/private/var/folders/23/4kbs9t712jv1mvmw6cpjwr2m0000gn/T/python-build.20160815000934.22185/Python-3.5-dev/Lib/ensurepip/__main__.py", line 4, in <module>

ensurepip._main()

File "/private/var/folders/23/4kbs9t712jv1mvmw6cpjwr2m0000gn/T/python-build.20160815000934.22185/Python-3.5-dev/Lib/ensurepip/__init__.py", line 209, in _main

default_pip=args.default_pip,

File "/private/var/folders/23/4kbs9t712jv1mvmw6cpjwr2m0000gn/T/python-build.20160815000934.22185/Python-3.5-dev/Lib/ensurepip/__init__.py", line 116, in bootstrap

_run_pip(args + [p[0] for p in _PROJECTS], additional_paths)

File "/private/var/folders/23/4kbs9t712jv1mvmw6cpjwr2m0000gn/T/python-build.20160815000934.22185/Python-3.5-dev/Lib/ensurepip/__init__.py", line 40, in _run_pip

import pip

zipimport.ZipImportError: can't decompress data; zlib not available

make: *** [install] Error 1

然后又查到了issue#451，应该使用下面的命令来安装。

~ CFLAGS="-I$(brew --prefix openssl)/include -I$(xcrun --show-sdk-path)/usr/include" \
  LDFLAGS="-L$(brew --prefix openssl)/lib" \
  pyenv install -v 3.5-dev

~ CFLAGS="-I$(brew --prefix openssl)/include -I$(xcrun --show-sdk-path)/usr/include" \

LDFLAGS="-L$(brew --prefix openssl)/lib" \

pyenv install -v 3.5-dev

然后，就安装成功了。

~ pyenv versions
* system (set by /Users/laixintao/.pyenv/version)
  3.5-dev

~ pyenv versions

* system (set by /Users/laixintao/.pyenv/version)

3.5-dev

如果需要使用虚拟环境，可以使用下面的命令安装pyenv-virtualenv插件，然后新建虚拟环境。

~ git clone https://github.com/yyuu/pyenv-virtualenv.git ~/.pyenv/plugins/pyenv-virtualenv
Cloning into '/Users/laixintao/.pyenv/plugins/pyenv-virtualenv'...
remote: Counting objects: 1849, done.
remote: Total 1849 (delta 0), reused 0 (delta 0), pack-reused 1849
Receiving objects: 100% (1849/1849), 527.44 KiB | 699.00 KiB/s, done.
Resolving deltas: 100% (1267/1267), done.
Checking connectivity... done.
~ echo 'eval "$(pyenv virtualenv-init -)"' >> ~/.bash_profile
~ source ~/.bash_profile
~ pyenv virtualenv 3.5-dev hackerrank
Ignoring indexes: https://pypi.python.org/simple
Requirement already satisfied (use --upgrade to upgrade): setuptools in /Users/laixintao/.pyenv/versions/3.5-dev/envs/hackerrank/lib/python3.5/site-packages
Requirement already satisfied (use --upgrade to upgrade): pip in /Users/laixintao/.pyenv/versions/3.5-dev/envs/hackerrank/lib/python3.5/site-packages

~ git clone https://github.com/yyuu/pyenv-virtualenv.git ~/.pyenv/plugins/pyenv-virtualenv

Cloning into '/Users/laixintao/.pyenv/plugins/pyenv-virtualenv'...

remote: Counting objects: 1849, done.

remote: Total 1849 (delta 0), reused 0 (delta 0), pack-reused 1849

Receiving objects: 100% (1849/1849), 527.44 KiB | 699.00 KiB/s, done.

Resolving deltas: 100% (1267/1267), done.

Checking connectivity... done.

~ echo 'eval "$(pyenv virtualenv-init -)"' >> ~/.bash_profile

~ source ~/.bash_profile

~ pyenv virtualenv 3.5-dev hackerrank

Ignoring indexes: https://pypi.python.org/simple

Requirement already satisfied (use --upgrade to upgrade): setuptools in /Users/laixintao/.pyenv/versions/3.5-dev/envs/hackerrank/lib/python3.5/site-packages

Requirement already satisfied (use --upgrade to upgrade): pip in /Users/laixintao/.pyenv/versions/3.5-dev/envs/hackerrank/lib/python3.5/site-packages

以这样的方式新建的虚拟环境，位置在~/.pyenv/versions如果使用pycharm的话，可以从这个路径导入。

Python对Json的解析

Posted on 2016年8月13日 by laixintao Leave a comment

什么是Json

Json是一种常用的数据交换结构，由于轻量、易于阅读和编写等特点，在网络方面应用很广。

它的格式一般是这样的：

对象是一个无序的“‘名称/值’对”集合。一个对象以“{”（左括号）开始，“}”（右括号）结束。每个“名称”后跟一个“:”（冒号）；“‘名称/值’ 对”之间使用“,”（逗号）分隔。

例如下面这样：

{"b": "Hello", "c": null, "a": true}

1	{"b": "Hello", "c": null, "a": true}

它的值可以是双引号括起来的字符串（string）、数值(number)、true、false、 null、对象（object）或者数组（array）。这些结构可以嵌套。

使用Python编码和解析Json

Python内置了json包来帮助我们完成对json的操作。

将Python的字典结构导出到json使用json.dumps()，将json读成Python的字典结构，使用json.loads()。

如果不是针对string操作而是对文件操作，分别使用json.load()函数和json.dump()函数。

import json

data = {
    'name' : 'ACME',
    'shares' : 100,
    'price' : 542.23
}

json_str = json.dumps(data)
data = json.loads(json_str)

# Writing JSON data to file
with open('data.json', 'w') as f:
    json.dump(data, f)

# Reading data back
with open('data.json', 'r') as f:
    data = json.load(f)

import json

data = {

'name' : 'ACME',

'shares' : 100,

'price' : 542.23

}

json_str = json.dumps(data)

data = json.loads(json_str)

# Writing JSON data to file

with open('data.json', 'w') as f:

json.dump(data, f)

# Reading data back

with open('data.json', 'r') as f:

data = json.load(f)

默认的类型对应如下：

JSON	Python
object	dict
array	list
string	unicode
number (int)	int, long
number (real)	float
true	True
false	False
null	None

其他数据类型与Json之间的编码和解码

一般来说，Python对json的解析是list或dict之间的操作，如果需要其他类型与json之间转换，就需要object_hook参数。先定义一个类，将类的字典初始化成json的key-value键值对。这样，json的参数就变成了类的属性。

>>> class JSONObject:
...     def __init__(self, d):
...         self.__dict__ = d
...
>>>
>>> data = json.loads(s, object_hook=JSONObject)
>>> data.name
'ACME'
>>> data.shares
50
>>> data.price
490.1

>>> class JSONObject:

... def __init__(self, d):

... self.__dict__ = d

...

>>>

>>> data = json.loads(s, object_hook=JSONObject)

>>> data.name

'ACME'

>>> data.shares

>>> data.price

490.1

还可以通过指定“函数”来进行转换。

用函数来指定序列化的方法，即将对象的“属性-值”对变成字典对，函数返回一个字典，然后json.dumps会格式化这个字典。

如果是通过函数将json变成对象，首先获得类名，然后通过__new__来创建一个对象（不调用初始化函数），然后将json字典的各个属性赋给对象。

def serialize_instance(obj):
    d = { '__classname__' : type(obj).__name__ }
    d.update(vars(obj))
    return d

# Dictionary mapping names to known classes
classes = {
    'Point' : Point
}

def unserialize_object(d):
    clsname = d.pop('__classname__', None)
    if clsname:
        cls = classes[clsname]
        obj = cls.__new__(cls) # Make instance without calling __init__
        for key, value in d.items():
            setattr(obj, key, value)
        return obj
    else:
        return d

def serialize_instance(obj):

d = { '__classname__' : type(obj).__name__ }

d.update(vars(obj))

return d

# Dictionary mapping names to known classes

classes = {

'Point' : Point

}

def unserialize_object(d):

clsname = d.pop('__classname__', None)

if clsname:

cls = classes[clsname]

obj = cls.__new__(cls) # Make instance without calling __init__

for key, value in d.items():

setattr(obj, key, value)

return obj

else:

return d

使用方法如下：

>>> p = Point(2,3)
>>> s = json.dumps(p, default=serialize_instance)
>>> s
'{"__classname__": "Point", "y": 3, "x": 2}'
>>> a = json.loads(s, object_hook=unserialize_object)
>>> a
<__main__.Point object at 0x1017577d0>
>>> a.x
2
>>> a.y
3

>>> p = Point(2,3)

>>> s = json.dumps(p, default=serialize_instance)

>>> s

'{"__classname__": "Point", "y": 3, "x": 2}'

>>> a = json.loads(s, object_hook=unserialize_object)

>>> a

<__main__.Point object at 0x1017577d0>

>>> a.x

>>> a.y

参考

介绍Json
python3-cookbook>第六章：数据编码和处理 >6.2 读写JSON数据
https://docs.python.org/2.7/library/json.html

2025 年 4 月
一	二	三	四	五	六	日
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30