小编Anu*_*ush的帖子

我有一个大文件,我需要阅读并从中制作字典.我希望这个尽可能快.但是我在python中的代码太慢了.这是一个显示问题的最小示例.

首先制作一些假数据

paste <(seq 20000000) <(seq 2 20000001)  > largefile.txt

现在这里有一段最小的python代码来读取它并制作一本字典.

import sys
from collections import defaultdict
fin = open(sys.argv[1])

dict = defaultdict(list)

for line in fin:
    parts = line.split()
    dict[parts[0]].append(parts[1])

时序:

time ./read.py largefile.txt
real    0m55.746s

但是,可以更快地读取整个文件:

time cut -f1 largefile.txt > /dev/null    
real    0m1.702s

我的CPU有8个内核,是否有可能在python中并行化这个程序来加速它？

一种可能性是读入大块输入,然后在不同的非重叠子块上并行运行8个进程,使字典与内存中的数据并行,然后在另一个大块中读取.在某种程度上使用多处理的python中这是可能的吗？

更新.假数据不是很好,因为每个键只有一个值.更好的是

perl -E 'say int rand 1e7, $", int rand 1e4 for 1 .. 1e7' > largefile.txt

(与大文件中的读取和制作字典相关.)

假设你有两个长度为100,000的字符串,包含0和1.您可以在大约10 ^ 10次操作中计算其编辑距离.

如果每个字符串只有100个,其余的都是零,那么我可以用100个整数表示每个字符串,说明它们的位置.

使用这种稀疏表示是否有更快的算法来计算编辑距离？更好的是算法也使用100 ^ 2空间而不是10 ^ 10空间.

为了给测试一些东西,考虑这两个字符串,每个字符串10个.整数表示每个字符串中的位置.

[9959, 10271, 12571, 21699, 29220, 39972, 70600, 72783, 81449, 83262]

[9958, 10270, 12570, 29221, 34480, 37952, 39973, 83263, 88129, 94336]

在算法术语中,如果我们有两个长度为n每个由k整数表示的稀疏二进制字符串,那么是否存在O(k^2)时间编辑距离算法？

甲托普利兹矩阵"是一个矩阵,其中每个对角降序从左至右是恒定的." 给定二进制矩阵M,是否有一种有效的算法来确定是否存在使其成为Toeplitz的行的排列？

例如,设置

M= [0 1 1]
   [1 1 0]
   [1 0 1]

如果你交换了第一行和第二行

[1 1 0]
[0 1 1]
[1 0 1]

这是Toeplitz.

在python中,您可以创建一个随机二进制矩阵,如下所示.

n = 10
h = 10
M =  np.random.randint(2, size=(h,n))

我想将测试应用于M.

(注意矩阵M不需要是正方形.)

最大子数组和问题有一个非常简单的线性时间解决方案https://en.m.wikipedia.org/wiki/Maximum_subarray_problem。

相反，如果我们想最大化sum（subarray）/ sqrt（subarray length），是否存在次二次时间解？

输入数组的元素将是-infinity到+ infinity范围内的浮点值。

我正在尝试编写代码来为库中不同书籍的数量创建置信区间(以及生成信息图).

我的堂兄在小学,每周都会给老师讲一本书.然后他读取并及时返回,以便在下周获得另一个.过了一会儿,我们开始注意到他以前读过的书,随着时间的推移逐渐变得越来越普遍.

假设图书馆中真实的图书数量是N,老师会随机选择一个(有替换),每周给你.如果在第t周,您收到的图书已经读过的次数为x,那么我可以根据https://math.stackexchange.com/questions/生成图书馆图书数量的最大似然估计值.615464/how-many-books-are-a-a-library.

示例:考虑一个包含五本书A,B,C,D和E的图书馆.如果您连续七周收到书籍[A,B,A,C,B,B,D],那么x的值(在每个星期之后,重复的数量将是[0,0,1,1,2,3,3],这意味着在七周之后,您已经收到了三本已经阅读过的书.

为了可视化似然函数(假设我已经理解了什么是正确的)我写了下面的代码,我相信它绘制了似然函数.最大值约为135,这实际上是根据上述MSE链接的最大似然估计.

from __future__ import division
import random
import matplotlib.pyplot as plt
import numpy as np

#N is the true number of books. t is the number of weeks.unk is the true number of repeats found 
t = 30
unk = 3
def numberrepeats(N, t):
    return t - len(set([random.randint(0,N) for i in xrange(t)]))

iters = 1000
ydata = []
for N in xrange(10,500):
    sampledunk = [numberrepeats(N,t) for i in xrange(iters)].count(unk)
    ydata.append(sampledunk/iters)

print …

该Viterbi算法发现的隐马尔可夫模型隐藏状态的最有可能的序列。我目前正在使用hhquark的以下出色代码。

import numpy as np


def viterbi_path(prior, transmat, obslik, scaled=True, ret_loglik=False):
    '''Finds the most-probable (Viterbi) path through the HMM state trellis
    Notation:
        Z[t] := Observation at time t
        Q[t] := Hidden state at time t
    Inputs:
        prior: np.array(num_hid)
            prior[i] := Pr(Q[0] == i)
        transmat: np.ndarray((num_hid,num_hid))
            transmat[i,j] := Pr(Q[t+1] == j | Q[t] == i)
        obslik: np.ndarray((num_hid,num_obs))
            obslik[i,t] := Pr(Z[t] | Q[t] == i)
        scaled: bool
            whether or not to normalize the probability trellis along …

有没有办法在python中绘制方向字段？

我的尝试是修改http://www.compdigitec.com/labs/files/slopefields.py给出

#!/usr/bin/python

import math
from subprocess import CalledProcessError, call, check_call

def dy_dx(x, y):
    try:
        # declare your dy/dx here:
        return x**2-x-2
    except ZeroDivisionError:
        return 1000.0

# Adjust window parameters
XMIN = -5.0
XMAX = 5.0
YMIN = -10.0
YMAX = 10.0
XSCL = 0.5
YSCL = 0.5

DISTANCE = 0.1

def main():
    fileobj = open("data.txt", "w")
    for x1 in xrange(int(XMIN / XSCL), int(XMAX / XSCL)):
        for y1 in xrange(int(YMIN / YSCL), int(YMAX / YSCL)):
            x= float(x1 * …

scipy.special.binom和scipy.misc.comb有什么区别？

在ipython中,我可以看到它们返回不同的类型,并且具有不同的准确性.

scipy.special.binom(4,3)
4.0

scipy.misc.comb(4,3)
array(4.000000000000001)

然而他们到底做了什么不同？

看看https://github.com/scipy/scipy/blob/master/scipy/special/generate_ufuncs.py,scipy.special.binom说

binom -- binom: dd->d                                      -- orthogonal_eval.pxd

scipy.misc.comb调用scipy.special.gammaln,其行在generate_ufuncs.py中表示

gammaln -- lgam: d->d, clngamma_wrap: D->D                 -- cephes.h, specfun_wrappers.h

给定一个整数M的矩阵，峰值是一个数组的元素，且不小于其4个相邻元素（上，下，左，右）。有一种很好的线性时间算法（用于n×n矩阵的O（n））来找到一个峰值，例如在这些讲义中，或者在该代码中， O（n log n）时间解决方案稍微简单一些。

假设我想找到k个峰（如果有那么多）。有没有办法在O（n + k）或O（n log n + k）时间内做到这一点？

我有一个大文件,我需要阅读并从中制作字典.我希望这个尽可能快.但是我在python中的代码太慢了.这是一个显示问题的最小示例.

首先制作一些假数据

paste <(seq 20000000) <(seq 2 20000001)  > largefile.txt

现在这里有一段最小的python代码来读取它并制作一本字典.

import sys
from collections import defaultdict
fin = open(sys.argv[1])

dict = defaultdict(list)

for line in fin:
    parts = line.split()
    dict[parts[0]].append(parts[1])

时序:

time ./read.py largefile.txt
real    0m55.746s

但是它不是I/O绑定的:

time cut -f1 largefile.txt > /dev/null    
real    0m1.702s

如果我注释掉这dict条线需要9几秒钟.似乎几乎所有的时间都花在了dict[parts[0]].append(parts[1]).

有什么方法可以加快速度吗？我不介意使用cython甚至C,如果这会产生很大的不同.或者熊猫可以在这帮忙吗？

以下是大小为10000000行的文件的配置文件输出.

python -m cProfile read.py test.data         20000009 function calls in 42.494 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000 …