我找到了一种在quicksort中更有效地处理重复元素的方法,并且想知道是否有人之前已经看过这个.
这种方法大大减少了检查重复元素所涉及的开销,这有助于在有和没有重复元素的情况下提高性能.通常,重复的元素以几种不同的方式处理,我将首先列举.
首先,有荷兰国旗方法对数组进行排序[ < pivot | == pivot | unsorted | > pivot].
其次,有一种方法是在排序过程中将相等的元素放在最左边,然后将它们移动到排序中心[ == pivot | < pivot | unsorted | > pivot],然后在排序后将==元素移动到中心.
第三,Bentley-McIlroy分区将==元素放在两边,以便排序[ == pivot | < pivot | unsorted | > pivot | == pivot],然后==元素移动到中间.
最后两种方法是为了减少开销.
现在,让我解释一下我的方法如何通过减少比较次数来改进快速排序.我一起使用两个quicksort函数而不是一个.
我将调用的第一个函数q1,它将数组排序为[ < pivot | unsorted | >= pivot].
我将调用的第二个函数q2,它将数组排序为[ <= pivot | unsorted | > pivot].
现在让我们一起看看它们的用法,以便改进重复元素的处理.
首先,我们调用 …
我发现了一种方法可以改进(就我已经测试过的)快速排序算法,超出了已经完成的范围.我正在测试它,然后我想了解它.但是,我会感谢一些帮助.所以这是我的问题.顺便说一句,我的所有代码都是用C++编写的.
我一直在与我的快速排序进行比较的一种方法是来自C++标准库的std :: sort.但是,它似乎非常缓慢.我只是排序整数和长期数组,但它似乎比我的快速排序和Bentley和McIlroy(也许是Sedgewick)的标准快速排序慢了大约8-10倍.有没有人有任何想法,为什么它这么慢？我用于排序的代码只是std :: sort(a,a + numelem); 其中a是long或int的数组,numelem是数组中元素的数量.数字是非常随机的,我尝试了不同的大小以及不同数量的重复元素.我也尝试过qsort,但是我的预期更糟糕了.编辑:忽略第一个问题 - 它已经解决了.
我想找到更好的quicksort实现来与我的quicksort进行比较.到目前为止,我有一个Bentley-McIlroy,我还与Vladimir Yaroslavskiy的双枢轴快速排序的第一个版本进行了比较.另外,我计划移植timsort(我认为这是合并类型)和来自jdk 7源的优化双枢轴快速排序.你知道其他什么样的快速实施方案？如果他们不是C或C++,那可能没事,因为我非常擅长移植,但如果你知道它们我会更喜欢C或C++.
你会如何推荐关于我对quicksort的补充？到目前为止,我的quicksort似乎比我测试过的所有其他quicksort快得多.它速度的主要来源是它比我发现的其他方法更有效地处理重复元素.它几乎完全消除了最坏情况的行为,而没有在检查重复元素上花费太多时间.我在Java论坛上发布了它,但没有得到回复.我还试着写信给Jon Bentley,因为他正在与弗拉基米尔合作进行他的双枢轴快速反应并没有得到任何回应(尽管我对此并不感到非常惊讶).我应该写一篇关于它的论文并把它放在arxiv上.ORG？我应该在一些论坛上发帖吗？我应该发布一些邮件列表吗？我已经在这方面工作了一段时间,我的方法是合法的.我确实有一些出版研究的经验,因为我是计算物理学的博士候选人.我应该尝试接触我大学计算机科学系的某个人吗？顺便说一句,我还开发了一个不同的双枢轴快速排序,但它并不比我的单枢轴快速排序更好(尽管它比弗拉基米尔的双枢轴快速排序更好,有一些数据集).
我非常感谢你的帮助.我只想将我能为计算机世界添加的内容.我对这种或任何荒谬的事情申请专利并不感兴趣.
我在python中有问题。我正在使用 scipy，我使用 scipy.io 加载 .mat 文件。.mat 文件是使用 MATLAB 创建的。
listOfFiles = os.listdir(loadpathTrain)
for f in listOfFiles:
fullPath = loadpathTrain + '/' + f
mat_contents = sio.loadmat(fullPath)
print fullPath
这是错误：
Traceback (most recent call last):
File "tryRankNet.py", line 1112, in <module>
demo()
File "tryRankNet.py", line 645, in demo
mat_contents = sio.loadmat(fullPath)
File "/usr/lib/python2.6/dist-packages/scipy/io/matlab/mio.py", line 111, in loadmat
matfile_dict = MR.get_variables()
File "/usr/lib/python2.6/dist-packages/scipy/io/matlab/miobase.py", line 356, in get_variables
getter = self.matrix_getter_factory()
File "/usr/lib/python2.6/dist-packages/scipy/io/matlab/mio5.py", line 602, in matrix_getter_factory
return self._array_reader.matrix_getter_factory()
File "/usr/lib/python2.6/dist-packages/scipy/io/matlab/mio5.py", line 274, …我为Python编译了一个简单的hello world C模块,它在我尝试过但IDLE的所有内容中都能正常工作.这是我输入的测试方法:
>>> import hello
>>> hello.say_hello('Justin')
我在命令提示符(我正在使用Windows),Eclipse的PyDev和PieDream中使用Python尝试了这一点,它们都打印出来Hello Justin!.但是,在IDLE中它不会打印任何东西 - 它只是给我提示.
setup.py我正在使用的模块来自此页面.我认为问题出在编译器上.我正在使用MinGW,我将其设置为.cfg文件中distutils的编译器.我从命令提示符构建模块:
python setup.py build
得到
running build
running build_ext
building 'hello' extension
creating build
creating build\temp.win32-2.6
creating build\temp.win32-2.6\Release
C:\MinGW\bin\gcc.exe -mno-cygwin -mdll -O -Wall -IC:\Python26\include -IC:\Python26\PC -c hellomodule.c -o build\temp.win32-2.6\Release\hellomodule.o
writing build\temp.win32-2.6\Release\hello.def
creating build\lib.win32-2.6
C:\MinGW\bin\gcc.exe -mno-cygwin -shared -s build\temp.win32-2.6\Release\hellomodule.o build\temp.win32-2.6\Release\hello.def -LC:\Python26\libs -LC:Python26\PCbuild -lpython26 -lmsvcr90 -o build\lib.win32-2.6\hello.pyd
我在想它可能与那里的-mno-cygwin部分有关,但我不确定.
关于为什么这个模块不能在IDLE中工作的任何想法或建议？我应该使用不同的编译器吗？
为了迫使不被内联这是耗时运行时的46%的功能,我用__attribute__((noinline))的它,并编译的代码gcc -Wall -Winline -O2(这些加-g有什么使用的Makefile文件-我也看到了大致相同的效果使用时,-g如好吧)使用gcc 4.5.2.我发现具有非内联功能的程序比原始程序快20%以上.有谁知道为什么会这样？
让我提供一些更多细节.发生这种情况的程序是Linux 的压缩实用程序bzip2的最新版本.程序中的关键功能(在compress.c中找到generateMTFValues)是执行Move To Front变换的功能.该功能仅由程序中的一个功能调用.
有没有人知道为什么程序在这种情况下运行得更快,因为强制编译器不要内联这个函数？该函数只接受一个参数 - 一个指向包含所有块和压缩信息的结构的指针.此外,它只调用另一个不会消耗任何实质处理时间的功能.