小编ste*_*fan的帖子

我正在对排名算法进行一些研究,并且想要给出排序列表和该列表的一些排列,计算两个排列之间的一些距离.对于Levenshtein距离的情况,这对应于计算序列与该序列的分类副本之间的距离.例如,还有"反转距离",这里详细描述了线性时间算法,我正在努力实现.

有没有人知道反演距离的现有python实现,和/或Levenshtein距离的优化？我在大约50,000到200,000个元素的序列上计算它,因此O(n ^ 2)太慢,但O(n log(n))或更好应该足够.

还可以理解排列相似性的其他度量.

为未来的人们编辑:

基于Raymond Hettinger的回应 ; 它不是Levenshtein或反转距离,而是"格式塔模式匹配":P

from difflib import SequenceMatcher
import random
ratings = [random.gauss(1200, 200) for i in range(100000)]
SequenceMatcher(None, ratings, sorted(ratings)).ratio()

在可怕的桌面上运行约6秒钟.

编辑2:如果你可以将你的序列强制转换为[1 .. n]的排列,那么曼哈顿度量的变化非常快并且有一些有趣的结果.

manhattan = lambda l: sum(abs(a - i) for i, a in enumerate(l)) / (0.5 * len(l) ** 2)
rankings = list(range(100000))
random.shuffle(rankings)
manhattan(rankings) # ~ 0.6665, < 1 second

归一化因子在技术上是近似值; 它对于偶数大小的列表是正确的,但应该(0.5 * (len(l) ** 2 - 1))用于奇数大小的列表.

Edit3:还有其他几种算法可用于检查列表相似度!的肯德尔头排名系数和斯皮尔曼 …

我使用http://wiki.eclipse.org/CDT/User/FAQ#How_can_I_inspect_the_contents_of_STL_containers.3F配置了漂亮的打印机.它成功地适用于矢量和其他容器.但是我无法检查地图,如下例所示:

#include <map>
#include <iostream>

using namespace std;

int main ()
{
map <int, string> mapIntToString;
map <int, int> mapInt2;
 mapIntToString.insert (map <int, string>::value_type (3, "Three"));
 mapInt2.insert (map <int, int>::value_type (3, 4));
 return 0;
}

使用gdb打印时出现以下错误:

(gdb) p mapInt2
$1 = std::map with 1 elementsTraceback (most recent call last):
File "/home/myuser/opt/gdb_printers/python/libstdcxx/v6/printers.py", line 422, in    children
rep_type = find_type(self.val.type, '_Rep_type')
File "/home/myuser/opt/gdb_printers/python/libstdcxx/v6/printers.py", line 45, in    find_type
 raise ValueError, "Cannot find type %s::%s" % (str(orig), name)
ValueError: Cannot find type …

我正在尝试从tomcat servlet发送纯文本错误消息,以便应用程序可以将响应呈现给用户.

我的web.xml中有以下内容:

<error-page>
    <error-code>409</error-code>
    <location>/string_error.jsp</location>
</error-page>

string_error.jsp如下:

${requestScope['javax.servlet.error.message']}

这成功地为我提供了409响应的纯文本错误消息.但是,我想对400/500范围内的任何错误使用同一页面,而无需<error-page>为每个错误手动指定新块.我<error-code>*</error-code>本以为会做到这一点,但事实并非如此.Tomcat是否提供了执行此操作的机制？