列表的有效交集与舍入 [英] efficient intersection of lists with rounding
问题描述
我必须列出我需要找到的公共号码（第二个四舍五入到
最近的积分）我想知道是否有这是一种更有效的方式来实现它。
a = [（123 ，1.3），（123,2.4），（123,7.8），（123,10.2）]
b = [（123,0.9），（123,1.9），（123,8.0）] [（i，round（j））for i，j in a for l，m in b if if（i，round（j））==
（l，round（m））]
[（123,1.0），（123,2.0），（123,8.0）]
这有效，但a和b可以大约30K长。
其他一些信息。
- a和b从最小到最大排序（可以将模块分成两部分）用过？）
- 将来我会想要绕第二个最接近的0.25
而不是整数。
集合模块会更有效吗？
我正在使用python 2.3。
感谢任何想法。
问候，
戈登威廉姆斯
>其他一些信息。- a和b从最小到最大排序（可以使用二等分模块吗？）
- 将来我想要绕第二个数字最接近0.25
而不是整数。
集合模块会更有效吗？
我正在使用python 2.3。
我会选择使用列表的圆形版本然后
迭代第一个列表并让第二个cach up。对不起，我要懒得
来更好地描述它，所以这里是代码：
a = [（123,1.3），（123， 2.4），（123,7.8），（123,10.2）]
b = [（123,0.9），（123,1.9），（123,8.0）]
a = [（i，round（j））for i，j in a]
b = [（i，round（j））for i，j in b]
res = []
pos_b = 0
试试：
for i，支持：
而b [pos_b] [1]< pivot：
pos_b + = 1
而b [pos_b] [1] == pivot：
res.append（b [pos_b] ）
pos_b + = 1
除了IndexError：
＃如果b在某处耗尽
传递
打印res
虽然它看起来更复杂，但肯定更快，因为它的复杂性
是O（max（len（a） ），len（b）））你的代码是O（len（a）* len（b）） - 所以
通常或多或少是二次的。
速度增益当然来自元素的顺序。你可以
因为循环_into_循环，但那更难看。
-
问候，
Diez B. Roggisch
Gordon Williams写道：我必须列出我需要找到的公共号码（第2号）四舍五入到最近的积分）我想知道是否有更有效的方法来做它。
a = [（123,1.3），（123,2.4），（123,7.8），（123,10.2）]
b = [（123,0.9），（123,1.9），（123,8.0）]
[（i，round（j））for i，j in a for l，m in b if if（i，round（j））==
（l，round（m））] < br [> [123,1.0），（123,2.0），（123,8.0）]
[snip]集合模块会更有效吗？
嗯，在Python 2.3中，我相信集合是用Python实现的，而
它们是用Python 2.4中的C实现的。所以可能不会，除非你升级为
。带有集合的2.4解决方案：
a = [（123,1.3），（123,2.4），（123,7.8），（123,10.2）]
b = [（123,0.9），（123,1.9），（123,8.0）]
def roundedj（pairs_iterable）：
....返回（（i，round（j））for i ，j in pairs_iterable）
.... set（roundedj（a））。intersection（set（roundedj（b）））
set（[（123,8.0），（123,2.0），（123,1.0）]）
Steve
>其他一些信息。- a和b从最小到最大排序（可以使用二等分模块吗？）
- 将来我想要绕第二个数字最接近0.25
而不是整数。
集合模块会更有效吗？
我正在使用python 2.3。
我会选择使用列表的圆形版本然后
迭代第一个列表并让第二个cach up。对不起，我要懒得
来更好地描述它，所以这里是代码：
a = [（123,1.3），（123， 2.4），（123,7.8），（123,10.2）]
b = [（123,0.9），（123,1.9），（123,8.0）]
a = [（i，round（j））for i，j in a]
b = [（i，round（j））for i，j in b]
res = []
pos_b = 0
试试：
for i，支持：
而b [pos_b] [1]< pivot：
pos_b + = 1
而b [pos_b] [1] == pivot：
res.append（b [pos_b] ）
pos_b + = 1
除了IndexError：
＃如果b在某处耗尽
传递
打印res
虽然它看起来更复杂，但肯定更快，因为它的复杂性
是O（max（len（a） ），len（b）））你的代码是O（len（a）* len（b）） - 所以
通常或多或少是二次的。
速度增益当然来自元素的顺序。你可以
因为循环_into_循环，但那更难看。
-
问候，
Diez B. Roggisch
Hi,
I have to lists that I need to find the common numbers (2nd rounded to
nearest integral) and I am wondering if there is a more efficient way of
doing it.
a= [(123,1.3),(123,2.4),(123,7.8),(123,10.2)]
b= [(123, 0.9), (123, 1.9), (123, 8.0)]
[ (i,round(j)) for i,j in a for l,m in b if (i,round(j)) == (l,round(m))]
[(123, 1.0), (123, 2.0), (123, 8.0)]
This works but a and b can be in the order of 30K long.
A couple of other bits of info.
- a and b are ordered smallest to largest (could bisect module be used?)
- in the future I will want to round the second number of closest 0.25
rather than whole number.
Would the sets module be more efficient?
I''m using python 2.3.
Thanks for any ideas.
Regards,
Gordon Williams
> A couple of other bits of info.- a and b are ordered smallest to largest (could bisect module be used?)
- in the future I will want to round the second number of closest 0.25
rather than whole number.
Would the sets module be more efficient?
I''m using python 2.3.
I''d go for something that uses the rounded versions of the lists and then
iterates the first list and lets the second "cach up". Sorry, I''m to lazy
to desribe it better, so here is the code:
a= [(123,1.3),(123,2.4),(123,7.8),(123,10.2)]
b= [(123, 0.9), (123, 1.9), (123, 8.0)]
a = [ (i,round(j)) for i,j in a]
b = [ (i,round(j)) for i,j in b]
res = []
pos_b = 0
try:
for i, pivot in a:
while b[pos_b][1] < pivot:
pos_b += 1
while b[pos_b][1] == pivot:
res.append(b[pos_b])
pos_b += 1
except IndexError:
# If b gets exhausted somewhere
pass
print res
While it looks more complicated, it certainly is faster, as its complexity
is in O(max(len(a), len(b))) where your code was O(len(a) * len(b)) - so
usually more or less quadratic.
The speed gain comes of course from the order of the elements. And you could
factor the rounding _into_ the loops, but thats more ugly.
--
Regards,
Diez B. Roggisch
Gordon Williams wrote:I have to lists that I need to find the common numbers (2nd rounded to
nearest integral) and I am wondering if there is a more efficient way of
doing it.a= [(123,1.3),(123,2.4),(123,7.8),(123,10.2)]
b= [(123, 0.9), (123, 1.9), (123, 8.0)]
[ (i,round(j)) for i,j in a for l,m in b if (i,round(j)) ==
(l,round(m))]
[(123, 1.0), (123, 2.0), (123, 8.0)]
[snip] Would the sets module be more efficient?
Well, in Python 2.3, I believe sets are implemented in Python while
they''re implemented in C in Python 2.4. So probably not, unless you
upgrade. A 2.4 solution with sets:
a = [(123,1.3),(123,2.4),(123,7.8),(123,10.2)]
b = [(123, 0.9), (123, 1.9), (123, 8.0)]
def roundedj(pairs_iterable): .... return ((i, round(j)) for i, j in pairs_iterable)
.... set(roundedj(a)).intersection(set(roundedj(b)))
set([(123, 8.0), (123, 2.0), (123, 1.0)])
Steve
> A couple of other bits of info.- a and b are ordered smallest to largest (could bisect module be used?)
- in the future I will want to round the second number of closest 0.25
rather than whole number.
Would the sets module be more efficient?
I''m using python 2.3.
I''d go for something that uses the rounded versions of the lists and then
iterates the first list and lets the second "cach up". Sorry, I''m to lazy
to desribe it better, so here is the code:
a= [(123,1.3),(123,2.4),(123,7.8),(123,10.2)]
b= [(123, 0.9), (123, 1.9), (123, 8.0)]
a = [ (i,round(j)) for i,j in a]
b = [ (i,round(j)) for i,j in b]
res = []
pos_b = 0
try:
for i, pivot in a:
while b[pos_b][1] < pivot:
pos_b += 1
while b[pos_b][1] == pivot:
res.append(b[pos_b])
pos_b += 1
except IndexError:
# If b gets exhausted somewhere
pass
print res
While it looks more complicated, it certainly is faster, as its complexity
is in O(max(len(a), len(b))) where your code was O(len(a) * len(b)) - so
usually more or less quadratic.
The speed gain comes of course from the order of the elements. And you could
factor the rounding _into_ the loops, but thats more ugly.
--
Regards,
Diez B. Roggisch
这篇关于列表的有效交集与舍入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
