我有一个相当大的字符串集(比如100),它有许多以其相似性为特征的子组.我试图找到/设计一个算法,可以合理有效地找到这些组.
举个例子,假设输入列表位于左下方,输出组位于右侧.
Input Output
----------------- -----------------
Jane Doe Mr Philip Roberts
Mr Philip Roberts Phil Roberts
Foo McBar Philip Roberts
David Jones
Phil Roberts Foo McBar
Davey Jones =>
John Smith David Jones
Philip Roberts Dave Jones
Dave Jones Davey Jones
Jonny Smith
Jane Doe
John Smith
Jonny Smith
有没有人知道如何合理有效地解决这个问题？
寻找类似字符串的标准方法似乎是Levenshtein距离,但我无法看到如何在这里充分利用它,而不必将每个字符串与列表中的每个其他字符串进行比较,然后以某种方式决定差异判断两个字符串是否在同一组中的阈值.
另一种方法是将字符串分解为整数的算法,其中类似的字符串散列为在数字行上靠近的整数.我不知道会是什么算法,如果有的话甚至存在
有没有人有任何想法/指示？
更新:@Will A:也许名字并不像我最初想的那么好.作为一个起点,我认为我可以假设在我将使用的数据中,字符串中的一个小变化不会使它从一个组跳到另一个组.
在角度,我有一个对象将通过服务暴露在我的应用程序中.
该对象上的某些字段是动态的,并且将通过使用该服务的控制器中的绑定正常更新.但是一些字段是计算属性,取决于其他字段,需要动态更新.
这里有一个简单的例子(这是工作在jsbin 这里).我的服务模型公开领域a,b并c在那里c通过以下公式计算a + B在calcC().请注意,在我的实际应用程序中,计算要复杂得多,但实质内容就在这里.
我能想到让它工作的唯一方法是将我的服务模型绑定到$rootScope,然后$rootScope.$watch用来监视任何控制器更改a或b何时更改,重新计算c.但这看起来很难看.有没有更好的方法呢？
第二个问题是表现.在我的整个应用程序a和b是对象的大名单,其中获得合计下来c.这意味着$rootScope.$watch函数将进行大量深度数组检查,这听起来会损害性能.
我在BackBone中采用了一种平衡的方法,尽可能地减少了重新计算,但角度似乎并不适合采用一种方法.对此的任何想法都会很棒.
这是示例应用程序.
var myModule = angular.module('myModule', []);
//A service providing a model available to multiple controllers
myModule.factory('aModel', function($rootScope) {
var myModel = {
a: 10,
b: 10,
c: null
};
//compute c from a and b
calcC = function() …我有很长的氨基酸字符串,我想根据列表中的起止值进行拆分.一个例子可能是最明确的解释方式:
str = "MSEPAGDVRQNPCGSKAC"
split_points = [[1,3], [7,10], [12,13]]
output >> ['M', '(SEP)', 'AGD', '(VRQN)', 'P', '(CG)', 'SKAC']
额外的括号是显示从split_points列表中选择的元素.我不认为开始 - 停止点会重叠.
我有一堆可行的想法,但看起来非常低效(代码长度明智),似乎必须有一个很好的pythonic方式来做到这一点.
是否可以在VIM中重用ex命令的范围？
例如,我可以使用以下命令将当前文件中的第4行(第10行)写入(复制)到新文件:
:4,10w foo/bar.txt
但我真正想做的是将线移到一个新文件.我可以这样做:
:4,10w foo/bar.txt
:4,10d
但是两次输入4,10都有点烦人.
所以我有两个问题:
我在javascript中有一个base64编码的jpg,我想发布到期望multipart/form-data的服务器.
具体来说,对于关键跟踪器API,它有一个示例curl调用,如下所示:
curl -H "X-TrackerToken: TOKEN" -X POST -F Filedata=@/path/to/file \
http://www.pivotaltracker.com/services/v3/projects/PROJECT_ID/stories/STORY_ID/attachments
我有基本的XML调用他们的API工作正常,使用.ajax像这样:
$.ajax({
url: 'http://www.pivotaltracker.com/services/v3/projects/158325/stories',
type: 'POST',
contentType: 'application/xml',
dataType: 'xml',
beforeSend: function(xhr) {
xhr.setRequestHeader("X-TrackerToken", "<KEY>")
},
data: '<story><story_type>feature</story_type><name>Fire torpedoes</name></story>',
success: function() { alert('PUT completed'); }
});
但我很难理解如何使用我的base64编码的jpg并发送它,好像我已经在表单中上传了一个文件.
有任何想法吗？
我很高兴在Rails模型上使用虚拟属性,如果它们是字符串,但我也想使用其他类型的属性,如日期或布尔值,以便我可以使用像date_select这样的帮助器来设置虚拟属性.
有这么好的方法吗？
就目前而言,在虚拟属性上使用date_select助手会引发:
1 error(s) on assignment of multiparameter attributes
如果我想要一个布尔属性,我最终会得到@v_attribute = "true",而不是@v_attr = true.
我找到了一个似乎有用的例子:
class MyModel
#virtual attribute
attr_accessor :v_date_field
attr_accessible :v_date_field
columns_hash["virtual_date_field"] = ActiveRecord::ConnectionAdapters::Column.new("vi_date_field", nil, "date")
end
但我真的不知道它为什么会起作用,它是否有任何副作用,而且看起来像是一个黑客.
最近几天我在 postgres 中遇到了全文搜索，在跨多列搜索时我对索引有点困惑。
postgres文档讨论了ts_vector在连接列上创建索引，如下所示：
CREATE INDEX pgweb_idx ON pgweb
USING gin(to_tsvector('english', title || ' ' || body));
我可以这样搜索：
... WHERE
(to_tsvector('english', title||' '||body) @@ to_tsquery('english', 'foo'))
但是，如果我想有时只搜索标题，有时只搜索正文，有时两者都搜索，我将需要 3 个单独的索引。如果我添加了第三列，那可能是 6 个索引，依此类推。
我在文档中没有看到的另一种方法是单独索引两列，然后只使用普通WHERE...AND查询：
... WHERE
(to_tsvector('english', title) @@ to_tsquery('english','foo'))
AND
(to_tsvector('english', body) @@ to_tsquery('english','foo'))
在大约 100 万行上对两者进行基准测试似乎在性能上基本上没有差异。
所以我的问题是：
为什么我要像这样连接索引，而不是单独索引列？两者的优点/缺点是什么？
我最好的猜测是，如果我事先知道我只想搜索两列（一次从不搜索），我将只需要通过连接使用较少内存的一个索引。
编辑
移至：https : //dba.stackexchange.com/questions/15412/postgres-full-text-search-with-multiple-columns-why-concat-in-index-and-not-at
我很欣赏LIKE查询很慢,因为它们无法编入索引.但是,我很好奇在这种情况下的性能影响:
说我有一个像这样的表:
user_id | message
-------------------
1 | foo bar baz
1 | bar buz qux
. . .
. . .
2 | bux bar foo
2 | bar
我说100万行,但有10,000个用户,所以每个用户有大约100条消息.
显然搜索如下:
SELECT * FROM table WHERE message like '%ar%';
会很慢.但是在我的应用程序中,我只会搜索用户的消息:
SELECT * FROM table WHERE message like '%ar%' AND user_id = 2;
其中user_id列将被索引.
我是否正确地认为在这样的场景中,Postgres只会在使用索引的user_id列而不是完整的表后对用户~100行执行慢LIKE查询 - 从而限制了我的性能损失？
而且只要任何一个用户只有大约100条消息,这样的查询对于10或1亿用户来说不会明显变慢？