Flask下载动态生成文件加一个简单的进度条

前一段码代码的时候碰见了这么一个情况,用户需要点击一个button然后下载一个比较大的动态生成的文件。flask里有一个send_file方法,可以把一个文件返回给客户端。可以先把动态生成的内容写到文件中,然后再用发送静态文件的方法,用send_file方法把这个文件返回,然后再把这个文件删除。不过这样的话就多了磁盘IO这一段时间,感觉很多此一举。

然后看了看send_file方法的代码,实际上是调用了一个FileWrapper的类,返回一个iterator,然后迭代返回块(默认的大小是4KB),和普通的Streaming的方法也没什么不一样的,只是包装了一下。所以直接用生成器构造Response即可。代码如下,关键的地方就只有添加一个Content-Length头,客户端每隔一段时间就可以计算一下当前的下载进度。

from flask import Flask
from flask import Response
from flask import render_template
from flask import make_response
from gevent.pywsgi import WSGIServer
app = Flask(__name__)
app.template_folder = "."

@app.route("/generate-on-fly")
def gen_on_fly():
def gen():
for i in xrange(200000):
yield "l"+"o"*100+"g\n"
resp = Response(gen())
resp.headers["Content-Length"] = resp.calculate_content_length()
return resp

@app.route("/")
def root():
resp = make_response(render_template("./root.html"))
resp.headers["Cache-Control"] = "no-store"
return resp

if __name__ == "__main__":
server = WSGIServer(('', 5000), app)
server.serve_forever()

根目录会返回一个html页面,页面上只有一个进度条和一个按钮。点击按钮会向/generate-on-fly发送请求,然后进度条开始滚动。root.html的内容如下。

<!DOCTYPE html>
<html>
<head>
<script src="https://code.jquery.com/jquery-1.12.4.js"></script>
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/css/bootstrap.min.css">
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.2.0/js/bootstrap.min.js"></script>
<script>
function updateProgress(evt)
{
var percentComplete = (evt.loaded / evt.total)*100;
$('#progressbar').attr("aria-valuenow", percentComplete);
$('#progressbar').attr("style", "width: "+percentComplete+"%;");
}
function sendreq(evt)
{
var req = new XMLHttpRequest();
req.onprogress = updateProgress;
req.open('GET', 'http://localhost:5000/generate-on-fly', true);
req.send();
}
</script>
</head>
<body>
<div class="row" style="margin: 30px">
<div class="col-lg-6">
<div class="progress">
<div id="progressbar" class="progress-bar" role="progressbar" aria-valuenow="0" aria-valuemin="0"
aria-valuemax="100"
style="width: 0%;">
</div>
</div>
</div>
<button type="button" class="btn" onclick="sendreq()">Download</button>
</div>
</body>
</html>

过程大致就是每隔一段时间,就会进入req的onprogress绑定的回调,回调里面计算一下当前下载的百分比,然后更新一下进度条的状态,也不是很复杂。

算法学习笔记(5):Dijkstra

在刷Hackerrank的时候碰到了这道题,其本身倒是十分普通的一道题,照本宣科的把Dijkstra实现一遍就可以做出来了。在讨论区和别人讨论发现的时间复杂度也是会被Accept的。

如果使用数组储存所有unvisited点的距离,在找当前最近点的时候,会需要遍历整个数组,而这是的时间复杂度。如果使用一个最小优先级队列,那么只需要将队首的元素取出,然后min-heapify一下,保持最小堆的性质,而这是的时间复杂度。能够显著减少时间消耗。

但是如果使用最小堆的话,降低堆中元素的优先级的操作就很麻烦了。首先如果想要找到堆中的某个元素就需要的时间复杂度,而修改了这个元素的优先级之后,想要维持最小堆的性质又要的时间复杂度。所以整体而言就变得和没有使用最小堆一样了。

为了解决这个问题有一个弥补的方法。就是在一个散列表中存储优先级队列中对应点的元素的handle。

如果想要降低某个点的优先级,那么可以通过查询散列表,获得最小堆中对应元素的handle,然后直接标志该点已经被删除(但是不实际从堆中删除),然后在储存堆的数组的最后新添加一个储存新优先级和该点的元素。标志删除的操作因为没有破坏最小堆的性质,只是 的时间复杂度,而最小堆中插入一个元素是 的时间复杂度。最后就实现了 的降低优先级的操作。

如果使用python实现的话,python的官方文档中简单介绍了使用heapq实现最小优先级队列的方法。

不过残念的是,add_task()方法的第一行就出现了个遍历dict,而这是的,所以推荐额外再使用一个set来维护entry_finder.keys(),这样查找和删除操作就都是 了。

另外一个有意思的事情是,heappush()原地的,所以pq会在原地修改。而pq中保存的是[distance, vertex]的list,而list是mutable的。所以在remove_vertex()把entry[-1]也就是vertex标志城REMOVED了之后,pq中的对应entry会自动修改。

最后挂上自己的代码。

# Enter your code here. Read input from STDIN. Print output to STDOUT
from heapq import *
 
def add_vertex(vertex, distance=0):
    if vertex in entry_set:
        remove_vertex(vertex)
    entry = [distance, vertex]
    entry_finder[vertex] = entry
    entry_set.add(vertex)
    heappush(pq, entry)
 
def remove_vertex(vertex):
    entry = entry_finder.pop(vertex)
    entry[-1] = REMOVED
    entry_set.remove(vertex)
 
def pop_vertex():
    while pq:
        priority, vertex = heappop(pq)
        if vertex is not REMOVED:
            del entry_finder[vertex]
            return priority, vertex
 
T = int(raw_input())
for T_ in range(T):
    pq = []
    entry_finder = {}
    REMOVED = "REMOVED"
 
    N, M = [int(i) for i in raw_input().split(" ")]
    connection = [[] for conn_ in range(N)]
    for M_ in range(M):
        x, y, r = [int(i)-1 for i in raw_input().split(" ")]
        connection[x].append([y, r+1])
        connection[y].append([x, r+1])
    S = int(raw_input())-1
     
    entry_set = set()
    unvisited = set()
    distance = {}
 
    for node in range(M):
        unvisited.add(node)
        if node!=S:
            distance[node] = float("Inf")
            add_vertex(vertex = node, distance = float("Inf"))
        else:
            distance[node] = 0
            add_vertex(vertex = node, distance = 0)
 
    while len(unvisited)!=0:
        current_distance, current_node = pop_vertex()
        if current_distance==float("Inf"):
            break
        for node, edge in connection[current_node]:
            if node in unvisited:
                new_distance = current_distance + edge
                if new_distance < distance[node]:
                    distance[node] = new_distance
                    add_vertex(node, new_distance)
                distance[node] = new_distance if new_distance < distance[node] else distance[node]
        unvisited.remove(current_node)
 
    for node in range(N):
        if node!=S:
            if distance[node]==float("Inf"):
                print -1,
            else:
                print distance[node],
    print

How to Install Pyeemd on Windows in 3 Steps

1. Prepare Compiling Environment

Download MSYS2 of your windows version from here.

Follow the instructions on the homepage to update the system. Run commands listed below.

$ update-core
$ pacman -Suy

If you have trouble connecting to the official repository of MSYS2, modify the configuration files of pacman, which are located at /etc/pacman.d/.

For those living in China, I recommend a MSYS2 mirror hosted by LUG@USTC. Just follow the instructions on their wiki.

We need to install the mingw64 toolchain (suppose we use 64-bit windows) and some tools like tar and make. The mingw64 toolchain contains compiler and other compiling-related tools. Just run the command below.

$ pacman -S mingw-w64-x86_64-toolchain tar make

After the installation, close the MSYS2 window and run mingw64_shell.bat located at MSYS2 root directory. You may notice the word in purple before tilde changes from MSYS to
MINGW64. According the introduction of MSYS2, the MINGW64 shell is more natively oriented. Meanwhile, and the MSYS2 shell provides some linux features.

The mingw subsystems provide native Windows programs and are the main focus of the project. These programs are built to co-operate well with other Windows programs, independently of the other subsystems.

The msys2 subsystem provides an emulated mostly-POSIX-compliant environment for building software, package management, and shell scripting. These programs live in a virtual single-root filesystem (the root is the MSYS2 installation directory). Some effort is made to have the programs work well with native Windows programs, but it's not seamless.

2. Compile GSL and Libeemd

Libeemd depends on GNU Scientific Library (GSL). Run following command in MINGW64 shell to download GSL source code.

$ curl -o gsl-latest.tar.gz http://mirror.clarkson.edu/gnu/gsl/gsl-latest.tar.gz
$ tar zxvf gsl-latest.tar.gz

Change directory to the GSL directory and compile it. (Suppose we have GSL 2.1 here.)

$ cd gsl-2.1
$ ./configure
$ make
$ make install

GSL is installed to /usr/local/ without assigning --prefix flag. So we need to modify PKG_CONFIG_PATH variable before compiling libeemd so compiler may find GSL libraries.

$ export PKG_CONFIG_PATH=$PKG_CONFIG_PATH:/usr/local/lib/pkgconfig

Then we clone libeemd source code from bitbucket and compile it. A makefile is included so we don't need to run a configure script.

$ git clone https://bitbucket.org/luukko/libeemd.git
$ cd libeemd
$ make

After compiling, you may use file command to check out file type of libeemd.so. It's a dll file! It sounds weird but I will continue with this convention. Otherwise you may modify Makefile and remake by yourself.

$ file libeemd.so
libeemd.so: PE32+ executable (DLL) (console) x86-64, for MS Windows

3. Install pyeemd module to Anaconda2

Anaconda is a great platform based on python for data analytic. It contains lots of modules and make it much simpler to do calculation.

But there're no EMD related modules included in Anaconda by default. And I can't find any one in pypi or by conda search command. (There's one named emd in pypi actually. But there's no document and I don't think it reliable.) That's why I write this blog.

If you tried googling about libeemd and windows before reading this blog, you may have found this issue. Owner of libeemd stated that using libeemd on windows may be unpleasant.

Please also note that installing libeemd on Windows is currently quite unsupported – I haven't tested it, and I have no way to test it.

This unpleasantness may be caused by compiling, which we have already fixed, and dll loading. Library searching is different in linux and windows. I know little about os. So it may be appropriate to quote from tldp.org, rather than gibberishing by myself.

The interface used by Linux is essentially the same as that used in Solaris, which I'll call the ''dlopen()'' API. However, this same interface is not supported by all platforms; HP-UX uses the different shl_load() mechanism, and Windows platforms use DLLs with a completely different interface.

It means, instead of appointing library search work to os, that we need to load dll files libeemd.so depending on on our own. Luckily finding dll dependency and loading them in python is not hard.

You may use objdump to find dll dependency as shown below.

$ objdump -p libeemd.so | grep "\.dll"
        DLL Name: KERNEL32.dll
        DLL Name: msvcrt.dll
        DLL Name: libgomp-1.dll
        DLL Name: libgsl-19.dll

There's a handy tool named dependencywalker to find dll dependency as well. After opening the dll file, namely libeemd.so here, dependencies will be shown in the top-left column.

dll

We have known that libeemd.so depends on kernel32.dll, msvcrt.dll, libgomp-1.dll and libgsl-19.dll. Kernel32.dll and msvcrt.dll are located in C:/windows/system32 and we don't need to worry about them. We have to worry about libgomp-1.dll's and libgsl-19.dll's dependencies. (pretty messy, right?)

Do basically same to them as to libeemd.so. And we get this dependency tree. (You don't get it directly. I draw this manually.)

libeemd.so
|-KERNEL32.dll
|-msvcrt.dll
|-libgomp-1.dll
  |-KERNEL32.dll
  |-msvcrt.dll
  |-libwinpthread-1.dll
    |-KERNEL32.dll
    |-msvcrt.dll
  |-user32.dll
  |-libgcc_s_seh-1.dll
    |-KERNEL32.dll
    |-msvcrt.dll
    |-libwinpthread-1.dll
|-libgsl-19.dll
  |-KERNEL32.dll
  |-msvcrt.dll
  |-user32.dll
  |-libgslcblas-0.dll
    |-KERNEL32.dll
    |-msvcrt.dll

This tree ends in kernel32.dll, msvcrt.dll and user32.dll. They are all located in C:/windows/system32, which is in system searching path. Other dlls are located in MSYS2 directory. You can find them in MINGW64 shell by find / -name command.

After all these dlls being found, we may begin installing pyeemd to Anaconda.

Change directory to libeemd/pyeemd directory and install pyeemd module to Anaconda2/Lib/site-packages directory.

Make sure you're using Anaconda2's python when running the setup.py script. You can use absolute path in MINGW64 shell like /c/Users/juiceyang/Anaconda/python . (You should replace with your own username here.)

$ /c/Users/juiceyang/Anaconda2/python setup.py install

Change directory to Anaconda2/Lib/site-packages/pyeemd, you may find they are already there. But once you try to run pyeemd.py, a windows error 126 prompt out. That's because python can't find dlls libeemd.so depending on. We may fix this by insert some lines into pyeemd.py. It looks like this after inserting.

# Load libeemd.so
# ---------new lines start from here
ctypes.WinDLL("kernel32.dll")
ctypes.WinDLL("msvcrt.dll")
ctypes.WinDLL("user32.dll")
ctypes.WinDLL("C:\\msys64\\mingw64\\bin\\libwinpthread-1.dll")
ctypes.WinDLL("C:\\msys64\\mingw64\\bin\\libgcc_s_seh-1.dll")
ctypes.WinDLL("C:\\msys64\\mingw64\\bin\\libgomp-1.dll")
ctypes.WinDLL("C:\\msys64\\home\\YOUR_USERNAME\\gsl-2.1\\cblas\\.libs\\libgslcblas-0.dll")
ctypes.WinDLL("C:\\msys64\\home\\YOUR_USERNAME\\gsl-2.1\\.libs\\libgsl-19.dll")
# ctypes.WinDLL("C:\\msys64\\home\\YOUR_USERNAME\\libeemd\\libeemd.so") --> This line is commented out. Load libeemd.so in next 3 lines.
# ---------new lines end
_LIBDIR = os.path.dirname(os.path.realpath(__file__))
_LIBFILE = os.path.join(_LIBDIR, "libeemd.so")
_libeemd = ctypes.CDLL(_LIBFILE)

ctypes.WinDLL() function loads dlls. First three dlls are in system32 folder so we need no absolute path. Other dlls is located by absolute path.

Then run following snippet in Jupyter notebook to check out whether it's working!

%matplotlib inline
from pyeemd import ceemdan
from pyeemd.utils import plot_imfs
import matplotlib.pyplot as plt
import numpy as np

y = np.sin(2*np.pi*np.linspace(0,1,1000))+np.sin(20*np.pi*np.linspace(0,1,1000))
plt.plot(y)
plt.show()
imfs = ceemdan(y, S_number=4, num_siftings=50)
plot_imfs(imfs)
plt.show()

Here's my output. Have fun using pyeemd!

notebook

MongoDB上手笔记4——在很多数据中进行查询

上一次把简单的Restful API搭建起来了,接下来让我们往数据库里面填充一些数据。

俗话说的好,一天一个苹果,考不上博士。假设小明每天吃一个苹果,为了记录截止到某一天小明一共吃了多少个苹果,我在db logs的collection applesIAte中,记录了截止到某一天小明一共吃了多少苹果。

假设小明命中注定不会读博,所以小明骨骼惊奇的生下来就不吃奶,而是出生第一天就吃苹果,每天以苹果为生(好像一个并吃不饱的样子,请不要在意这些细节)。然后每天为了建设祖国而奋斗,一直活到了100岁,最后在100岁生日的当晚因为看到了祖国的建设成果过于兴奋(以及吃了太多的苹果)而含笑九泉。

按照这以上假设,我写了个脚本,记录了无私而强韧的小明的不平凡的一生中吃了的苹果数量。这段脚本中用了个insert_many()的方法,在一次性写入很多条document的时候比较快。

from flask_pymongo import MongoClient
mongo = MongoClient(host="localhost", port=27999)
db = mongo.logs
auth_res = db.authenticate("readwriter", "123456")
apples = [{
    "day": day,
    "apple": day
} for day in range(1, 100*365+1)]
db.applesIAte.insert_many(apples)

然后我们看一看小明这光辉的一生。

> db.applesIAte.stats()
{
        "ns" : "logs.applesIAte",
        "count" : 36500,
        "size" : 1752064,
        "avgObjSize" : 48,
        "numExtents" : 5,
        "storageSize" : 2793472,
        "lastExtentSize" : 2097152,
        "paddingFactor" : 1,
        "paddingFactorNote" : "paddingFactor is unused and unmaintained in 3.0. It remains hard coded to 1.0 for compatibility only.",
        "userFlags" : 1,
        "capped" : false,
        "nindexes" : 1,
        "totalIndexSize" : 1193696,
        "indexSizes" : {
                "_id_" : 1193696
        },
        "ok" : 1
}

恩,小明活了36500天(原谅我忘了闰年这事),真是了不起!

在回顾小明这光辉的一生(中吃了多少苹果)之前,让我们先做一些小手脚。这样我们才能看看我们能以多快的速度回顾(查询)了小明的一生(丫可是活了100年口阿!)

> db.setProfilingLevel(2)
{ "was" : 0, "slowms" : 100, "ok" : 1 }

上面这句话的意思是,我们所有的回顾小明一生的行为(查询)的相关信息都会被记录下来。

接下来我们看看小明在10000天的时候一共吃了多少苹果。(此处也可以用findOne({day: 10000}),不过并不影响结论)

> db.applesIAte.find({day: 10000})
{ "_id" : ObjectId("56a9c39cabf8322aa0828dec"), "day" : 10000, "apple" : 10000 }

显然他吃了10000个,awesome!那让我们看看我们花了多长时间发现他吃了这么多苹果。

> db.system.profile.find()
{
    "op":"query",
    "ns":"logs.applesIAte",
    "query":{
        "day":10000
    },
    "ntoreturn":0,
    "ntoskip":0,
    "nscanned":0,
    "nscannedObjects":36500,
    "keyUpdates":0,
    "writeConflicts":0,
    "numYield":285,
    "locks":{
        "Global":{
            "acquireCount":{
                "r":NumberLong(572)
            }
        },
        "MMAPV1Journal":{
            "acquireCount":{
                "r":NumberLong(286)
            }
        },
        "Database":{
            "acquireCount":{
                "r":NumberLong(286)
            }
        },
        "Collection":{
            "acquireCount":{
                "R":NumberLong(286)
            }
        }
    },
    "nreturned":1,
    "responseLength":62,
    "millis":20,
    "execStats":{
        "stage":"COLLSCAN",
        "filter":{
            "day":{
                "$eq":10000
            }
        },
        "nReturned":1,
        "executionTimeMillisEstimate":10,
        "works":36502,
        "advanced":1,
        "needTime":36500,
        "needFetch":0,
        "saveState":285,
        "restoreState":285,
        "isEOF":1,
        "invalidates":0,
        "direction":"forward",
        "docsExamined":36500
    },
    "ts":    ISODate("2016-01-28T07:53:57.857    Z"),
    "client":"127.0.0.1",
    "allUsers":[
        {
            "user":"boss",
            "db":"admin"
        },
        {
            "user":"readwriter",
            "db":"logs"
        }
    ],
    "user":"readwriter@logs"
}

上面这一大段基本上都没啥用,我们只需要两条——"millis":20,"docsExamined":36500。也就是查询一共花了20ms,查看了36500条document才找到了这条记录。(好慢!)

如果小明不是一个普通的人,是一个脱离了低级趣味的神仙,他活了一万年,甚至十万年前他就和猛犸象谈笑风生了(可他依旧不想读博)。那么我们的记录会越来越多,查询速度会越来越慢。

而我们为days加上索引可以有效的解决这个问题。因为day是单调增长的,所以参数是{day: 1}。

> db.applesIAte.createIndex({day: 1})
{
        "createdCollectionAutomatically" : false,
        "numIndexesBefore" : 1,
        "numIndexesAfter" : 2,
        "ok" : 1
}
> db.applesIAte.stats()
{
        "ns" : "logs.applesIAte",
        "count" : 36500,
        "size" : 1752064,
        "avgObjSize" : 48,
        "numExtents" : 5,
        "storageSize" : 2793472,
        "lastExtentSize" : 2097152,
        "paddingFactor" : 1,
        "paddingFactorNote" : "paddingFactor is unused and unmaintained in 3.0. It remains hard coded to 1.0 for compatibility only.",
        "userFlags" : 1,
        "capped" : false,
        "nindexes" : 2,
        "totalIndexSize" : 2117584,
        "indexSizes" : {
                "_id_" : 1193696,
                "day_1" : 923888
        },
        "ok" : 1
}

从stats()返回的结果来看,day的索引确实是加上了。那么结果如何呢?

{
    "op":"query",
    "ns":"logs.applesIAte",
    "query":{
        "day":20000
    },
    "ntoreturn":0,
    "ntoskip":0,
    "nscanned":1,
    "nscannedObjects":1,
    "keyUpdates":0,
    "writeConflicts":0,
    "numYield":0,
    "locks":{
        "Global":{
            "acquireCount":{
                "r":NumberLong(2)
            }
        },
        "MMAPV1Journal":{
            "acquireCount":{
                "r":NumberLong(1)
            }
        },
        "Database":{
            "acquireCount":{
                "r":NumberLong(1)
            }
        },
        "Collection":{
            "acquireCount":{
                "R":NumberLong(1)
            }
        }
    },
    "nreturned":1,
    "responseLength":62,
    "millis":0,
    "execStats":{
        "stage":"FETCH",
        "nReturned":1,
        "executionTimeMillisEstimate":0,
        "works":2,
        "advanced":1,
        "needTime":0,
        "needFetch":0,
        "saveState":0,
        "restoreState":0,
        "isEOF":1,
        "invalidates":0,
        "docsExamined":1,
        "alreadyHasObj":0,
        "inputStage":{
            "stage":"IXSCAN",
            "nReturned":1,
            "executionTimeMillisEstimate":0,
            "works":2,
            "advanced":1,
            "needTime":0,
            "needFetch":0,
            "saveState":0,
            "restoreState":0,
            "isEOF":1,
            "invalidates":0,
            "keyPattern":{
                "day":1
            },
            "indexName":"day_1",
            "isMultiKey":false,
            "direction":"forward",
            "indexBounds":{
                "day":[
                    "[20000.0, 20000.0]"
                ]
            },
            "keysExamined":1,
            "dupsTested":0,
            "dupsDropped":0,
            "seenInvalidated":0,
            "matchTested":0
        }
    },
    "ts":    ISODate("2016-01-28T08:05:46.904    Z"),
    "client":"127.0.0.1",
    "allUsers":[
        {
            "user":"boss",
            "db":"admin"
        },
        {
            "user":"readwriter",
            "db":"logs"
        }
    ],
    "user":"readwriter@logs"
}

结果发现"docsExamined":1,"millis":0。我们只查询了一条数据就直接找到了到20000天的时候小明吃了多少苹果,花的时间更是小到近似于0了!所以说当小明成仙之后,我们必须对day加上索引才能知道他为了不读博吃了多少苹果XD。

后记:最近看了一本书,作者比鸟哥还谐,整本书写的很像《春物》这种轻小说的风格。于是尝试着『学习』了一下这种风格,试过之后感觉有些浮夸啊XD

MongoDB上手笔记3——写个简单的Restful API读写数据库

上一篇中设置好了db logs的两个用户,并尝试往collection gen1中写入了一条简单的document。使用上一篇中的同样的方法,又写入了新的两条document,现在gen1中有了三条document。

> db
logs
> db.gen1.find()
{ "_id" : ObjectId("56a0daabcf03a917cb662aef"), "time" : 1, "value" : 1 }
{ "_id" : ObjectId("56a0dab3cf03a917cb662af0"), "time" : 2, "value" : 2 }
{ "_id" : ObjectId("56a0dabacf03a917cb662af1"), "time" : 3, "value" : 3 }

在命令行中写js语句来操作mongoDB自然是可行的,可是有很多情况需要使用别的语言来读取数据库。js可能缺少某些别人造好的轮子,比如我想用python来做科学计算,数据存在mongoDB里面,我就需要用python的驱动来操作数据库。

提供这个功能的轮子已经有很多了,mongoEngine和pymongo之类的。但是代码变多之后,感觉维护变得比较麻烦。代码中往往操作数据库和进行计算的部分混合在一起,看着条理不是很清晰。

所以想是不是可以将两部分分开来做,中间用个什么东西连接起来。后来知道了很Fancy(大概?)的Restful API,于是想着可以把各个部分分开,中间用http连接起来。

于是用flask和做了个十分简单的Restful API,功能就只有读取db logs的collection gen1中的最新一条数据以及向其中写数据。

api的验证部分使用了最简单的basic http authentication。request header中的auth部分就只是使用了base64加密而已(都不能算得上加密吧),十分简陋,完全没有安全性。每次请求都会创建一个MongoClient,简单测试了一下,目前没看出来有什么性能影响。

# 创建MongoClient
mongo = MongoClient(host="localhost", port=27999)
# 使用创建的对象验证身份
mongo["logs"].authenticate(request.authorization.username, request.authorization.password)

以下就是所有的代码了,一共只有50行。

simple_restful.py

from flask import request
from flask_restful import Resource
from bson.json_util import loads, dumps
from flask_pymongo import MongoClient
from pymongo.errors import OperationFailure
from flask import Flask
from flask_restful import Api


class Data(Resource):
    def get(self):
        mongo = MongoClient(host="localhost", port=27999)
        try:
            mongo["logs"].authenticate(request.authorization.username, request.authorization.password)
            last_log = mongo["logs"]["gen1"].find().sort("_id", -1)[0]
            return {
                       "err": "False",
                       "message": "Successfully get data",
                       "result": {"data": dumps(last_log)}
            }
        except OperationFailure, err:
            return {
                "err": "True",
                "message": "Failed getting data",
                "result": err.details
            }

    def post(self):
        mongo = MongoClient(host="localhost", port=27999)
        try:
            mongo["logs"].authenticate(request.authorization.username, request.authorization.password)
            data = request.data
            l = loads(data)
            result = mongo["logs"]["gen1"].insert_one(l["data"])
            return {
                "err": "False",
                "message": "Successfully post data",
                "result": {"data": dumps(l["data"]), "ack": str(result.acknowledged)}
            }
        except OperationFailure, err:
            return {
                "err": "True",
                "message": "Failed post data",
                "result": err.details
            }

app = Flask(__name__)
api = Api(app)
api.add_resource(Data, '/data')
app.run(debug=True)

使用curl简单测试一下吧。

>curl -v -H "Content-Type: application/json" --user readwriter:123456 http://localhost:5000/data
* Adding handle: conn: 0x140cf10
* Adding handle: send: 0
* Adding handle: recv: 0
* Curl_addHandleToPipeline: length: 1
* - Conn 0 (0x140cf10) send_pipe: 1, recv_pipe: 0
* About to connect() to localhost port 5000 (#0)
*   Trying 127.0.0.1...
* Connected to localhost (127.0.0.1) port 5000 (#0)
* Server auth using Basic with user 'readwriter'
> GET /data HTTP/1.1
> Authorization: Basic cmVhZHdyaXRlcjoxMjM0NTY=
> User-Agent: curl/7.33.0
> Host: localhost:5000
> Accept: */*
> Content-Type: application/json
>
* HTTP 1.0, assume close after body
< HTTP/1.0 200 OK
< Content-Type: application/json
< Content-Length: 189
< Server: Werkzeug/0.11.3 Python/2.7.10
< Date: Thu, 21 Jan 2016 13:59:24 GMT
<
{
    "err": "False",
    "message": "Successfully get data",
    "result": {
        "data": "{\"_id\": {\"$oid\": \"56a0dabacf03a917cb662af1\"}, \"value\":
3.0, \"time\": 3.0}"
    }
}
* Closing connection 0

确实读出来了最新的一条document。再写入一条document试试。

C:\Users\Juiceyang\Desktop>curl -v -H "Content-Type: application/json" --user re
adwriter:123456 http://localhost:5000/data -X POST -d "{\"data\":{\"time\":4,\"v
alue\":4}}"
* Adding handle: conn: 0x85cf10
* Adding handle: send: 0
* Adding handle: recv: 0
* Curl_addHandleToPipeline: length: 1
* - Conn 0 (0x85cf10) send_pipe: 1, recv_pipe: 0
* About to connect() to localhost port 5000 (#0)
*   Trying 127.0.0.1...
* Connected to localhost (127.0.0.1) port 5000 (#0)
* Server auth using Basic with user 'readwriter'
> POST /data HTTP/1.1
> Authorization: Basic cmVhZHdyaXRlcjoxMjM0NTY=
> User-Agent: curl/7.33.0
> Host: localhost:5000
> Accept: */*
> Content-Type: application/json
> Content-Length: 29
>
* upload completely sent off: 29 out of 29 bytes
* HTTP 1.0, assume close after body
< HTTP/1.0 200 OK
< Content-Type: application/json
< Content-Length: 210
< Server: Werkzeug/0.11.3 Python/2.7.10
< Date: Thu, 21 Jan 2016 14:02:58 GMT
<
{
    "err": "False",
    "message": "Successfully post data",
    "result": {
        "ack": "True",
        "data": "{\"_id\": {\"$oid\": \"56a0e512612bf10dcce366d7\"}, \"value\":
4, \"time\": 4}"
    }
}
* Closing connection 0

结果来看也确实写入成功了。

算法学习笔记(4):计数排序

在宿舍呆着无聊接着在hackerrank上刷水题。这道题由于排序的依据是一定范围内的整数,所以用计数排序效率应当不错。

说到计数排序,实际上思路也很常见。最常见的一个例子就是比赛或者是考试的时候要进行排名。

比如某班有3名同学考了100分,2名同学考了99分,5名同学考了98分。那么很明显,比99分高的同学一共有3名,所以考99分的同学只能是第4名了。

计数排序大概就是做了个数数每个元素前面有多少元素这个事情。先统计最高分多少分,然后依次统计各个分数的学生个数,然后以此叠加就可以统计出前面有多少个学生了。

而且由于不同分数段的学生是按照原顺序放置到新数组中的,所以在原数组中的顺序并不会被打乱,即这个算法是稳定的。这也是为什么这道题可以用计数排序解,因为并不会打乱文本的顺序。

顺便一提,这道题中的最大值max()的复杂度应该是,所以总运行时间应该是。因为计数排序并不涉及到不同元素之间的比较,即不是比较排序,所以的下界并不适用于计数排序。

最后附上这道题的一个无脑解。

# Enter your code here. Read input from STDIN. Print output to STDOUT
n = int(raw_input())
ar = []
idx = []
out = [None]*n
for _ in range(n):
    ar.append(raw_input().split())
    ar[-1][0] = int(ar[-1][0])
    idx.append(ar[-1][0])
    if _<n/2:
        ar[-1][1] = "-"
countlist = [0]*(max(idx)+1)
for item in ar:
    countlist[item[0]]+=1
for i in range(len(countlist)-1):
    countlist[i+1]+=countlist[i]
for item in reversed(ar):
    out[countlist[item[0]]-1]=item
    countlist[item[0]]-=1
for item in out:
    print item[1],

算法学习笔记(3):插入排序、归并排序与逆序数

前些天在挨个做hackerrank上的题目的时候,碰到了这么一道题

题目的完成率并不高,只有百分之三十六点多,我估计了下难度,自己应该是做不出来的,最后果然没做出来。不过在Discussion下面还是看到了些有用的帮助,有人说用mergesort能做出来。于是又仔细的想了想,还是花了些力气做出来了...

题目的内容是计算插入排序一个序列的移动元素的总次数。实际上是计算的序列的逆序数

逆序数的定义上面那个wiki的链接里说的挺清楚的了,数的就是反序排列的数字对数。

比如[1,3,2]的逆序数是1,在插入排序的时候,2会向左移动一次,整个序列变成了[1,2,3]。

[2,3,1]的逆序数是2,在插入排序的时候,1会向左移动两次,整个序列变成[1,2,3]。

hackerrank在排序这一章前面也有一道题是计算插入排序移动次数的,当时按照题目的提示,使用的直接在插入排序的时候,移动一次,加一次,最后依次数出来移动的次数。当然这个的时间复杂度就是,在序列比较长的情况下很容易超时。这种比较『暴力』的方法,显然不适合本题。

mergesort是一种比较简单的方法。可以很容易的想象出,在merge过程中,如果『小序列』非空,每当『大序列』的最小元素被选出来,就意味着逆序数需要自增目前『小序列』中元素个数那么多,因为这个时候『小序列』中的所有元素都比位于他们之后的『大序列』中挑出的最小元素大。

而且mergesort的时间复杂度是,已经是比较排序的最优了,所以也理应在本题中不会超时。

知道这个关键点,代码实现就很容易了,就是增添个自增的语句而已,代码如下所示。

def merge(a,b):
    global answer
    a_flag = 0
    b_flag = 0
    result = []
    while a_flag<len(a) and b_flag<len(b):
        if a[a_flag]>b[b_flag]:
            result.append(b[b_flag])
            answer+=(len(a)-a_flag)
            b_flag+=1
        else:
            result.append(a[a_flag])
            a_flag+=1
    if a_flag==len(a):
        result.extend(b[b_flag:])
    else:
        result.extend(a[a_flag:])
    return result

def mergesort(l):
    if len(l)>1:
        mid = len(l)/2
        a = l[:mid]
        b = l[mid:]
        a = mergesort(a)
        b = mergesort(b)
        return merge(a,b)
    else:
        return l

n = input()
for iterate in range( n ):
    x = input()
    a = [ int( i ) for i in raw_input().strip().split() ]
    answer = 0
    mergesort(a)
    print answer

reportLab渲染pdf

继续之前的工作。因为kindle支持的格式有限,所以剩下的只有mobi,pdf两个选择了。找了半天没找到合适的制作mobi文件的模块,所以选用了一个不错的制作pdf的模块——reportlab。

昨天折腾了半天,发现reportlab-userguide的第二章中最简单的helloworld例程输出的pdf文件在电脑中看还正常,在kindle的竖屏模式中看就没有字了,不过横屏模式倒是可以看到字。

我以一个什么都不知道的普通用户的心态猜测了下,可能是kindle为了尽可能将pdf表现的和txt文件差不多,采用了比较奇葩的解析方式,这样竖屏看的时候字比较大。

于是又把后面几张大概看了看,最后还是成功的输出了可以在kindle上阅读的pdf文件。

# 首先import需要用到的模块
from reportlab.platypus import SimpleDocTemplate, Paragraph, Spacer
from reportlab.lib.styles import getSampleStyleSheet
from reportlab.pdfbase import pdfmetrics
from reportlab.pdfbase.ttfonts import TTFont

其中后两条是为了使用自定义的字体。因为不太清楚kindle支持的中文字体有哪些,所以使用了华文宋体。

# 准备要用到的一些东西
STSong = r"/home/juiceyang/jianshuDownloader/STSong.TTF"
# 将华文中宋字体的注册名为"STSong"的字体,当然也可以取别的名字
pdfmetrics.registerFont(TTFont("STSong", STSong))
# 要生成的pdf的尺寸,对应的是kpw2的6寸屏,单位是postpoints
kpw2_size = (331.2, 476.2)
# 使用华文中宋的style模板,style的属性之类的可以看reportlab-userguide的5.6一节
styles = getSampleStyleSheet()
style = styles["Normal"]
style.fontName = "STSong"

STSong.TTF是从网上下载的字体文件,也许应该换成开源字体,不过为了做样例,就不再细改了。

# 新建一个文档
doc = SimpleDocTemplate("你好世界.pdf", pagesize=kpw2_size)
# 开头先插一个大空白
Story = [Spacer(1, 20)]
# 插入简体中文
chs = "我能吞下玻璃而不伤身体。"
p = Paragraph(chs, style)
Story.append(p)
Story.append(Spacer(1, 10))
# 插入繁体中文
cht = "我克藝吃玻璃,我不毀受傷。"
p = Paragraph(cht, style)
Story.append(p)
Story.append(Spacer(1, 10))
# 插入日文
jap = "私は硝子を食べられます。私を傷付けません。"
p = Paragraph(jap, style)
Story.append(p)
# 韩文不太常见就不测试了,输出文档
doc.build(Story)

最后输出的pdf的效果和在kindle上看得效果分别如下:

pdf

可以看出,kindle中竖屏模式浏览的效果和电脑上看的效果还是有些差别的,明显字大了很多。

简书下载器——使用BeautifulSoup4解析网页

虽然名字是下载器,不过实际上就是用python写的一个网络爬虫,通过某种规则将网页爬完,然后进行解析,获得自己想要获得信息。

而简书上的文章的集合方式大概有3种:

  • 文集(notebook),url为http://www.jianshu.com/notebooks/文集id/latest
  • 专题(collection),url为http://www.jianshu.com/collection/专题id
  • 用户(users),url为http://www.jianshu.com/users/用户id/latest_articles

下载器主要也就是批量下载这三种集合中的文章。

下面用一篇文章来解释下大概的工作原理。

这篇文章的url是http://www.jianshu.com/p/8862a4250944,可以看出来并没有像某些网页一样,带有.html/.php/.asp之类的后缀,是因为服务器有某些机制可以知道在访问这种没有后缀的url的时候,究竟是想访问哪些文件。

以chrome为例,如果按下F12打开Developer Tools,然后再刷新上面那篇文章,那么可以在Network下看到http://www.jianshu.com/p/8862a4250944.html这个文件的GET请求。如果将这个html文件下载下来,看代码的话,会发现我们想要的文章的内容都在这个html文件中有所体现。

就像wikipedia中说的一样,html只是一种组织信息的一种方法,我们所需要的文章中的信息(包括图片、引用等等)都在html文件中有所体现。我们所需要做的,就是通过html tag的类型,将信息分门别类,并下载到本地。最终再通过某种方式,按其性质制作回pdf文件当中去。

所以工作流程大概就是:获得html文件内容,解析html文件,重新排列内容,并制作成pdf文件。

获得html文件的内容可以使用python内置模块urllib/urllib2,我使用了urllib2(其实对于这么小的问题两个用起来差不多)。

import urllib2
html = urllib2.urlopen("http://www.jianshu.com/p/8862a4250944").read()
print html

这面那段代码可以将那片文章的html文件打开,并读出内容。如果便于理解的话,类似于open()和readlines(),只不过readlines()会返回一个list,这个会返回一个str。看输出的话就会发现str对象html的__str__()方法会返回html文件的内容,第一步完成。

解析html文件使用了BeautifulSoup4,安装方法在这片短文中已经简要介绍了。这个工具的功能就像一个筛子,通过html tag的不同,筛出使用者想要的内容。

from bs4 import BeautifulSoup
import urllib2
html = urllib2.urlopen("http://www.jianshu.com/p/8862a4250944").read()
soup = BeautifulSoup(html)
print soup.title

运行上面一段代码,就会发现输出内容为html文件的title标签的内容:

<title>简书干货内容推荐 - 简书</title>

所谓的筛子的功能,大概就是这样,所需要做的就是先预先找好要筛出来的tag的范围,然后用bs4筛出来。通过观察html的结构,可以看出文章的内容集中在<div class="show-content"></div>中,所以我们所需要做的也就只是找到class是show-content的标签,然后将其从html里面提取出来而已。这样第二步也就完成了。

之后也可以再一次通过标签的内容(比如<strong>、<a>、<blockquote>)再次筛选内容。即完成第三步。不过由于目前制作pdf的方法还在学习当中,输出的文件格式还是txt,也就没有必要进行第三步第四步了。所以现在是通过正则表达式直接删除了所有的html标签,丢掉了格式信息。在学习完了pdf制作方法后应该会再次进行第三步和第四步。

写了个批量下载简书文章的工具

前言:这个脚本目前只能用来下载文本,也就是说下载下来的都是txt文件。以后可能会写输出pdf文件的脚本,以后的事以后再说啦┐(´_`)┌

前几天zhihu上有人问怎么批量下简书上的文章到kindle上看,恰好上个学期用了beautifulsoup,趁着手热,写了个简书的批量下载工具。以下是简单的使用方法,linux平台下使用很简单,就不细说了,主要记录下windows的使用过程。

1.首先从这里下载python2,安装就是各种下一步,没什么好说的。

2.从这里右键另存为下载get-pip.py,安装方法就按照网页上的安装。

get-pip

比如下载到了桌面上,就先进入桌面的路径,然后python get-pip.py即可。

3.安装BeautifulSoup,这东西大概理解可以理解为一个筛子,把网页中需要的东西筛选出来。安装方法是在cmd中运行安装命令:

pip install beautifulsoup4

bs4

至此脚本的运行环境已经安装完毕了。

4.从这里下载脚本,下载完解压出来。比如解压到了一个名叫jianshuDownloader-master的文件夹下。在jianshuDownloader-master中新建两个空文件——userlist.txt和notebooklist.txt。

userlist.txt中存放批量下载的用户名。比如我们想批量下载该用户的文章,url为http://www.jianshu.com/users/5104d005424d/latest_articles,我们需要的就是users/和/latest_articles中间的那串字符。简单来说可以把它看成用户的『身份证号』,能唯一识别出是哪个用户。

userlist.txt中可以存放多个用户的『身份证号』,比如我们想下载5104d005424d、7041c064cbd2、2659558557cc三位用户的所有文章,就把他们的『身份证号』每行存一个就行了。

userlist

userlist.txt中存放用户的『身份证号』

 

同理,notebooklist.txt中用来存放文集的编号。比如我们想下载这个这个这个三个文集中的所有文章。就把这三个文集的编号存到notebooklist.txt中,存的方法和userlist.txt的一样,也是一行一个。

notebook

notebooklist.txt里面存文集的编号

 

5.最后一步就是双击main.py,按照提示选择是按用户下载还是按文集下载了。

输入1按用户下载,输入2按文集下载。

由于现在是用正则直接把html里面的标签去掉,所以比较慢,不过既然是为了省鼠标,运行起来别管就好了...以后可能会抛弃这种做法,不过以后的事以后再说啦┐(´_`)┌

另外我也不知道为啥linux下和windows下速度差那么多...

还有windows的cmd里面一涉及到中文就烦得不行,直接用英文了...

下载完成之后会自动退出,然后下载好的txt就放在jianshuDownloader-master\data文件夹下了,在然后拷进kindle里看就好了。

IMG_20150212_052232

随便拷进去一篇文章,大概效果就是这样了

 

后记:这玩意儿纯属一个代码爱好者的练手作,请各位老爷要求不要太高。如果有问题我尽量修改