带负权有向无环图的最短路径

Posted on Mon 15 May 2017 in Computer

最短路径

正权图

用广度优先,先到达的点一定是最短路径。因此不需要考虑后续更新问题

带负权

由于先到达的某条路可能被后面带负权的路所代替,需要考虑后续更新问题。为了防止某节点的最短路径更新导致的后续步骤重算,任何节点必须等待他的依赖做完,此时给出的路径才是真正的最短路径。这个过程需要使用拓扑排序(考虑依赖的任务排序)来实现。

每次某个事情做完的时候,计算假设走该路径它的后继到达所需要的时间。如果该时间更短的话,给它的后继节点更新时间并记录该路径。

拓扑排序

初始时有一系列任务待处理,构成一个任务树。这些任务有的不需要依赖(入度为零)即可以完成,称为树叶;另一些是出度为零的树根;其他的称为树干。每次剪除任意一个枝叶,此次剪除可能产生新的枝叶,加入枝叶队列。以此不断循环。

此方法应用于一个任意有向/无向图可以剪除所有树枝,剩余的皆是非平凡的,或者连接环路的


Continue reading

Blogging with Jupyter and Pelican

Posted on Thu 30 March 2017 in Computer

This articles tells how to build this blog site.

Installation and Setup

  • Jupyter, and an article telling what is jupyter notebook
  • Pelican, pythonic blog system supports markdown, rst, asciidoc, ipynb etc.
  • ipynb2pelican, a plugin enables ipynb support by metacell
  • ghp-import is needed for github page import. It can be installed …

Continue reading

ipynb2pelican Plugin released!

Posted on Mon 27 March 2017 in Computer

Yet another Pelican Plugin for blogging with Jupyter Notebooks using MetaCell to store metadata.

Thanks to super cow power of python, we can finally publish ipynb easily! Below is the README.md from the project at this time.

The ipynb2pelican plugin provides markup for Jupyter/IPython notebooks in pelican, so …


Continue reading

Javascript 学习小记

Posted on Sat 05 November 2016 in Computer

研究了一下Linux平台做笔记的软件,发现为知笔记半死不活,bug很多。其他的笔记程序尝试了leanote等各种软件都感觉难以使用,要么功能太弱,要么没有linux客户端。总计一下我想要的笔记软件的要求:

  • 支持Markdown
    • 支持嵌入代码块的语法高亮
    • 支持latex输入一些基本的数学公式
  • 电脑上使用起来方便
  • 方便用手机查看
  • 方便分享给其他人
  • 软件稳定,无明显BUG,体积小,依赖少

最终我发现了NBViewer+Jupyter Notebook+Github/Gist的组合。

注:现在更倾向于用Jupyter Notebook+Pelican的组合了,参见Blogging with Jupyter and Pelican

  • 存在的问题:刷新麻烦,需要手动加?flush=true
  • 解决方案:UserScript脚本Refresh NBViewer Button。具体请看描述。

为了写这个脚本,特意学习了一点js

基本知识

  • 获取元素的方法demo …

Continue reading

Jupyter Notebook的配置

Posted on Tue 01 November 2016 in Computer

默认目录

jupyter notebook --generate-config
vim /home/zpj/.jupyter/jupyter_notebook_config.py#查找dir设定notebook根目录

找到c.NotebookApp.notebook_dir条目,修改为启动jupyter后打开的目录,如/home/zpj/code

配置pylab, matplotlib默认载入

导入库,内联svg输出,需要运行:

In [2]:
%pylab
%matplotlib inline
%config InlineBackend.figure_format = 'svg'
Using matplotlib backend: agg
Populating the interactive namespace from numpy and matplotlib

配置ipython

创建配置文件,并且编辑 …


Continue reading

LaTeX环境搭建

Posted on Tue 17 May 2016 in Computer

安装

sudo zypper in texstudio texlive-ctex texlive-xecjk # texstudio -> kile is ok

NotoSans字体的配置

似乎过时了

\setCJKmainfont[BoldFont=Noto Sans CJK SC Medium,ItalicFont=KaiTi]{SimSun}
\setCJKsansfont[BoldFont=Noto Sans CJK SC Medium]{Noto Sans CJK SC Regular}
\setCJKmonofont{Noto Sans CJK SC Light}
\setCJKfamilyfont{zhkai}{KaiTi}
\setCJKfamilyfont{ltnoto}{Noto Sans CJK SC …

Continue reading

openSUSE的配置

Posted on Tue 17 May 2016 in Computer

更入门的图文教程可以参见我写的《openSUSE新手指南》的pdf文档。

配置

基本配置

  • .bashrc
  • .vimrc
  • .gitignore_global

软件源配置

可以用sudo zypper ar --repo添加文件.repo文件。sudo zypper mr -Ra禁用自动刷新可以极大的提高搜索的效率

软件源列表

安装软件

图形界面程序

  • Dolphin文件管理器预览插件
    • kffmpegthumbnailer 视频预览
    • kdegraphics-thumbnailers pdf, svg等文档图片预览
  • 画图
    • 矢量图 inkscape
    • 点阵图 gimp
    • 手绘等 krita
  • 影音播放 …

Continue reading

Use C++ Template Programming to find int of least byte width

Posted on Sun 01 May 2016 in Computer

Also see gist

#include <iostream>
#include <cstdint>
template<int N>
struct least {
    static_assert(N < 9 && N > 1, "Length beyond range 1<N<9!");
    using int_ = typename least <N+1>::int_;
};
template<> struct least<1> {using int_ = int8_t;};
template<> struct least<2> {using int_ = int16_t;};
template<> struct least<4> {using int_ …

Continue reading

QtCreator使用小结

Posted on Fri 01 April 2016 in Computer

Debug

首先要看使用的是什么构建系统:

  • qmake 不需要额外的设置
  • cmake Debug需要在生成配置的时候进行额外参数设置
  • qbs ???

QtC在左下角的Debug按钮一定要在Debug模式下运行才能有效。

进入Debug模式如果是qmake构建系统不需要额外配置。但是如果是cmake则每次都要重新生成配置。

参考Debug with cmake and qtcreator可知生成配置的时候应当添加参数-DCMAKE_BUILD_TYPE=Debug

C++11

  • CMake: set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
  • qmake: QMAKE_CXXFLAGS += -std=c++0x

Continue reading

Python plotting with infinite incontinuous point

Posted on Mon 01 February 2016 in Computer

In [1]:
%pylab
%matplotlib inline
%config InlineBackend.figure_format = 'svg'
Using matplotlib backend: agg
Populating the interactive namespace from numpy and matplotlib
In [2]:
def tannan(x, bound=6):
    t=tan(x)
    if abs(t)>bound:
        return nan
    else:
        return t
tann=vectorize(tannan …

Continue reading