Hpw使列表易于排序。 [英] Hpw make lists that are easy to sort.
问题描述
Python'的排序算法利用
序列中预先存在的顺序：
＃sort_test.py
随机导入
导入时间
def测试（）：
n = 1000
k = 2 * * 28
L = random.sample（xrange（-k，k），n）
R = random.sample（xrange（-k，k） ），n）
t = time.time（）
LR = [（i + j）for i in L in j in R]
打印time.time（） - t
LR.sort（）
打印time.time（） - t
打印
t = time.time（）
＃L.sort（）
R.sort（）
presorted_LR = [（i + j）for i in L for j in R]
print time.time（） - t
presorted_LR .sort（）
print time.time（） - t
如果__name __ ==''__ main__''：
测试（）
在这个 - 非常慢的计算机上打印：
> d：\ python25 \ pythonw -u" sort_test.py"
1.10000014305
8.96000003815
1.10000014305
5.49000000954
>退出代码：0
预先输出第二个序列会使我们超过三秒钟。我想知道是否有办法以这种方式生成合并项目
排序它们的速度更快？还有一些其他排序算法
可以专门利用这种方式 - 或另一种方式 -
生成这个列表吗？
最后的序列是len（L）* len（R）long，但它只是从
len（L）+ len（R）不同的项目生成，是否有可能利用这一事实？我也会对一个更通用的解决方案感兴趣，这个解决方案对于
这两种列表中的项目总和是这样的。
A.
3月28日下午12:12，Anton Vredegoor< anton.vredeg ... @ gmail .com>
写道：
Python的排序算法利用了预先存在的订单
顺序：
＃sort_test.py
随机导入
导入时间
def test（）：
n = 1000
k = 2 ** 28
L = random.sample（xrange（-k） ，k），n）
R = random.sample（xrange（-k，k），n）
t = time.time（）
LR = [（i + j）for i in L for j in R]
print time.time（） - t
LR.sort （）
打印time.time（） - t
打印
t = time.time（）
#Ls ort（）
R.sort（）
presorted_LR = [（i + j）for i in L in j in R]
打印time.time（） - t
presorted_LR.sort（）
print time.time（） - t
if __name__ ==''__ main__''：
test（）
在这个非常慢的计算机上打印：
> d：\ python25 \ pythonw -u" sort_test.py"
1.10000014305
8.96000003815
1.10000014305
5.49000000954
>退出代码：0
预先输出第二个序列会使我们超过三秒钟。我想知道是否有办法以这种方式生成合并项目
排序它们的速度更快？还有一些其他排序算法
可以专门利用这种方式 - 或另一种方式 -
生成这个列表吗？
最后的序列是len（L）* len（R）long，但它只是从
len（L）+ len（R）不同的项目生成，是否有可能利用这一事实？我也会对一个更通用的解决方案感兴趣，这个解决方案对于
这两种列表中的项目总和是这样的。
A.
我找到了一个网站，希望能指向你的方向
方向：
http://wiki.python.org/moin/HowTo/排序
这个有一个有趣的各种排序方法的配置文件
Python：
<一个rel =nofollowhref =http://www.biais.org/blog/index.php/2007/01/28/23-python-sorting-efficiencytarget =_ blank> http：//www.biais .org / blog / index.php / ... ing-efficiency
享受，
Mike
Anton Vredegoor< an ************* @ gmail.comwrites：
预先判断第二个序列会使我们超过三秒钟。我想知道是否有办法以这种方式生成合并项目
排序它们的速度更快？是否还有一些其他的排序
算法可以特别利用这种方式 - 或另一种
方式生成此列表？
嗯，有各种各样的黑客可以想到，但你有没有真正的
应用程序？
< blockquote class =post_quotes>
最后的序列是len（L）* len（R）long，但它仅由
len（L）+ len（R）不同的项目产生是否有可能利用这一事实？
我也会对一个更通用的解决方案感兴趣，这个解决方案适用于
总结两个以上列表中的项目这条路。
如果你真的想要几个概率分解的总和（在这个案例中，这是几个制服副本的总和）分配），
它是汇总的分布的卷积。你可以用快速傅立叶变换来比
更有效地研究笛卡尔积。
但是我不知道那是不是你想要做的事情。
Paul Rubin写道：
嗯，有各种各样的黑客可以想到，但是你有一个实际的
应用程序吗？
假设两个输入列表都已排序。然后产品清单仍然没有分类，但它也没有完全未分类。我怎样才能对
产品进行排序？我想知道是否有必要先计算完整的
产品清单以便对其进行排序。是否可以仅使用一小堆生成按排序顺序生成
项目？
此外，由于排序，我有一个缓慢的sumfour脚本。如果分类的价格比b
快十倍，那么它将成为散列解决方案的竞争对手。如果项目可以直接生成，那么<br />
脚本也只有非常小的内存占用。
如果你真的想要几个概率分解的总和（在这个案例中，它是统一分布的几个副本的总和），
它是分布的卷积求和。你可以用快速傅立叶变换来比
更有效地研究笛卡尔积。
但我不知道那是不是你想要做的事情。
我想要这个产品，但是在更短的时间内排序。如果傅立叶变换可以给b
帮助，我想要它们:-)
A.
Python''s sorting algorithm takes advantage of preexisting order in a
sequence:
#sort_test.py
import random
import time
def test():
n = 1000
k = 2**28
L = random.sample(xrange(-k,k),n)
R = random.sample(xrange(-k,k),n)
t = time.time()
LR = [(i+j) for i in L for j in R]
print time.time()-t
LR.sort()
print time.time()-t
print
t = time.time()
#L.sort()
R.sort()
presorted_LR = [(i+j) for i in L for j in R]
print time.time()-t
presorted_LR.sort()
print time.time()-t
if __name__==''__main__'':
test()
On this -very slow- computer this prints:
>d:\python25\pythonw -u "sort_test.py"
1.10000014305
8.96000003815
1.10000014305
5.49000000954
>Exit code: 0
Presorting the second sequence gains us more than three seconds. I
wonder if there is a way to generate the combined items in such a way
that sorting them is even faster? Is there some other sorting algorithm
that can specifically take advantage of this way -or another way- of
generating this list?
The final sequence is len(L)*len(R) long but it is produced from only
len(L)+len(R) different items, is it possible to exploit this fact? I''d
also be interested in a more general solution that would work for
summing the items of more than two lists in this way.
A.
On Mar 28, 12:12 pm, Anton Vredegoor <anton.vredeg...@gmail.com>
wrote:Python''s sorting algorithm takes advantage of preexisting order in a
sequence:
#sort_test.py
import random
import time
def test():
n = 1000
k = 2**28
L = random.sample(xrange(-k,k),n)
R = random.sample(xrange(-k,k),n)
t = time.time()
LR = [(i+j) for i in L for j in R]
print time.time()-t
LR.sort()
print time.time()-t
t = time.time()
#L.sort()
R.sort()
presorted_LR = [(i+j) for i in L for j in R]
print time.time()-t
presorted_LR.sort()
print time.time()-t
if __name__==''__main__'':
test()
On this -very slow- computer this prints:
>d:\python25\pythonw -u "sort_test.py"1.10000014305
8.96000003815
1.10000014305
5.49000000954>Exit code: 0
Presorting the second sequence gains us more than three seconds. I
wonder if there is a way to generate the combined items in such a way
that sorting them is even faster? Is there some other sorting algorithm
that can specifically take advantage of this way -or another way- of
generating this list?
The final sequence is len(L)*len(R) long but it is produced from only
len(L)+len(R) different items, is it possible to exploit this fact? I''d
also be interested in a more general solution that would work for
summing the items of more than two lists in this way.
A.I found a website that hopefully will point you in the right
direction:
http://wiki.python.org/moin/HowTo/Sorting
And this one has an interesting profile of various sort methods with
Python:
http://www.biais.org/blog/index.php/...ing-efficiency
Enjoy,
Mike
Anton Vredegoor <an*************@gmail.comwrites:Presorting the second sequence gains us more than three seconds. I
wonder if there is a way to generate the combined items in such a way
that sorting them is even faster? Is there some other sorting
algorithm that can specifically take advantage of this way -or another
way- of generating this list?Well there are various hacks one can think of, but is there an actual
application you have in mind?
The final sequence is len(L)*len(R) long but it is produced from only
len(L)+len(R) different items, is it possible to exploit this fact?
I''d also be interested in a more general solution that would work for
summing the items of more than two lists in this way.If you really want the sum of several probability distriutions (in
this case it''s the sum of several copies of the uniform distribution),
it''s the convolution of the distributions being summed. You can do
that with the fast fourier transform much more efficiently than
grinding out that cartesian product. But I don''t know if that''s
anything like what you''re trying to do.
Paul Rubin wrote:
Well there are various hacks one can think of, but is there an actual
application you have in mind?Suppose both input lists are sorted. Then the product list is still not
sorted but it''s also not completely unsorted. How can I sort the
product? I want to know if it is necessary to compute the complete
product list first in order to sort it. Is it possible to generate the
items in sorted order using only a small stack?
Also, I have a sumfour script that is slow because of sorting. It would
become competitive to the hashing solution if the sorting would be about
ten times faster. If the items could be generated directly in order the
script would also have only a very small memory footprint.
If you really want the sum of several probability distriutions (in
this case it''s the sum of several copies of the uniform distribution),
it''s the convolution of the distributions being summed. You can do
that with the fast fourier transform much more efficiently than
grinding out that cartesian product. But I don''t know if that''s
anything like what you''re trying to do.I want the product, but sorted in less time. If Fourier transforms can
help, I want them :-)
A.
这篇关于Hpw使列表易于排序。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
