计算机科学领域的任何人都知道HeapSort O(n log n)在理论上是O(n^2)最糟糕的,而QuickSort是最糟糕的情况.但是,实际上,一个实现良好的QuickSort(具有良好的启发式)将在每个数据集上优于HeapSort.一方面,我们几乎没有观察到最坏的情况,另一方面,例如CPU缓存线,预取等在许多简单的任务中产生巨大的差异.虽然例如QuickSort可以处理预分类数据(具有良好的启发式)O(n),但HeapSort将始终重新组织数据O(n log n),因为它不利用现有结构.
对于我的玩具项目卡尺分析,我最近一直在研究从基准测试结果中估算算法的实际平均复杂度的方法.特别是,我尝试过Lawson和Hanson的NNLS拟合不同的多项式.
但是,它还不能很好地工作.有时候我会得到有用的结果,有时我却没有.我认为只做更大的基准测试可能有所帮助,特别是尝试更多参数.
以下结果用于以具有10%随机性的SAW模式对Double对象进行排序.对于此次运行,n最多只能达到500,因此对于实际使用来说它并不具有代表性...数字是估计的运行时对大小的依赖性.输出是手工编辑和手动排序的,因此它不能反映当前工具提供的内容!
BubbleSortTextbook LINEAR: 67.59 NLOG2N: 1.89 QUADRATIC: 2.51
BubbleSort LINEAR: 54.84 QUADRATIC: 1.68
BidirectionalBubbleSort LINEAR: 52.20 QUADRATIC: 1.36
InsertionSort LINEAR: 17.13 NLOG2N: 2.97 QUADRATIC: 0.86
QuickSortTextbook NLOG2N: 18.15
QuickSortBo3 LINEAR: 59.74 QUADRATIC: 0.12
Java LINEAR: 6.81 NLOG2N: 12.33
DualPivotQuickSortBo5 NLOG2N: 11.28
QuickSortBo5 LINEAR: 3.35 NLOG2N: 9.67
你可以看出,虽然在这个特定的设置中(通常它完全没有令人满意)但结果在很大程度上与已知的行为一致:冒泡排序真的很昂贵,而且QuickSort上的一个好的启发式方法要好得多.但是,例如,具有三个中值启发式的QuickSort最终会进行O(n + n^2)估算,而其他QuickSort估计为O(n + n log n)
那么现在我的实际问题: …
我有一堆处理文档聚类的代码.一步涉及计算每个文档与给定语料库中的每个其他文档的相似性(对于"类似"的一些不重要的定义),并存储相似性以供以后使用.相似之处是不同的,我不关心具体的相似性是什么,我的分析的目的,只是它在什么桶.例如,如果文件15378和3278是52%相似,有序对(3278,15378)得到存储在[0.5,0.6]桶中.在初始分析之后,文档有时会在语料库中添加或删除,因此根据需要将相应的对添加到桶中或从桶中删除.
我正在研究存储这些ID对列表的策略.我们发现一个SQL数据库(这个项目的大多数其他数据都存在)对于我们的目的来说太慢而且磁盘空间太大,所以目前我们将每个存储桶存储为磁盘上的整数压缩列表(最初zlib压缩,但现在使用lz4代替速度).我喜欢这件事:
有点糟糕的事情:
那么:我应该关注哪种数据结构？我怀疑正确的答案是某种奇特的简洁数据结构,但这不是我所熟知的空间.此外,如果重要:所有文档ID都是无符号的32位整数,处理这些数据的当前代码是用C语言编写的,作为Python扩展,所以这可能是我们坚持的通用技术系列.
我的项目可以从源代码自动生成一些额外的帮助文件。
我如何让 maven 将这些文件安装到生成的 JavaDoc 包中？
我不知道如何拥有 Maven：
运行一些类来生成附加文档，例如编译和启动src/main/java/mypackage/ListOptions.javaakamypackage.ListOptions以生成所有可用选项/模块/示例/等的列表。.
安装输出文件（我只能让 Maven 将文件安装src/main/javadoc/resources到site/apidocs/resources子文件夹中；但我希望此文档位于顶级site/apidocs文件夹中；更准确地说，我根本不关心该site部分，而是拥有完整的文档in mypackage-0.1.0-SNAPSHOT-javadoc.jar; 包括从 javadoc 链接的非 Javadoc 生成的辅助信息）。
最小示例 - maven 的插件配置：
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-javadoc-plugin</artifactId>
<version>2.9.1</version>
<executions>
<execution>
<id>attach-javadocs</id>
<goals>
<goal>jar</goal>
</goals>
</execution>
</executions>
<configuration>
<docfilessubdirs>true</docfilessubdirs>
</configuration>
</plugin>
目录布局：
./pom.xml
./src/main/java/foobar/GenerateNonstatic.java
./src/main/javadoc/staticfile.js
./src/main/javadoc/resources/insubfolder.png
mvn package产生：javadoc in./target/apidocs和./target/foobar-0.0.1-SNAPSHOT-javadoc.jar. 该文件target/apidocs/resources/insubfolder.png最终位于文件夹target/apidocs/resources（和.jar）中，但未staticfile.js安装。
我不清楚如何运行GenerateNonstatic.java以将输出包含在 javadoc.jar中。我没有看到一个钩子让 exec:exec …
对于ELKI,我需要(并且拥有)比标准Java JDK和Collections API提供的更灵活的排序实现.(排序不是我的最终目标.我使用部分排序来批量加载索引结构,例如kd-tree和R*-tree,我希望对这些结构进行相当通用的实现,比目前在ELKI中更通用 - 但不管怎样,优化排序意味着优化索引构建时间.
但是,排序算法根据您的数据大小而有很大差异.对于小型数组,已知的事实是插入排序可以很好地执行(事实上,大多数快速排序实现将回退到低于某个阈值的插入排序); 不是理论上的,而是通过排序理论不考虑的CPU流水线和代码大小效应.
所以我现在正在对许多排序实现进行基准测试,以找到满足我特定需求的最佳组合; 我希望我的更灵活的实现与JDK默认实现(已经很好地调整,但可能用于不同的JDK版本)相当.
从长远来看,我需要这些东西易于重现和重新运行.在某些时候,我们将看到JDK8.在Dalvik VM上,结果也可能与Java 7不同.哎呀,他们甚至可能在AMD,Core i7和Atom CPU上也有所不同.因此,Cervidae可能会包含不同的排序策略,并在课程加载时选择最合适的排序策略.
我目前的努力是在GitHub上:https://github.com/kno10/cervidae
所以现在对实际的问题.最新的caliper commit为macrobenchmarks添加了一些实验代码.不过,我面对我需要的问题都.当运行时间小于定时器分辨率的0.1%时,Caliper宏基准测试失败; 有10000个对象,一些算法达到了这个阈值.与此同时,microbenchmarks抱怨说,当你的运行时间过长时,你应该做一个宏基准测试......
因此,对于不同排序大小的基准测试,我实际上需要一种根据运行时动态从微基准标记切换到宏基准标记的方法.实际上,我甚至更喜欢如果caliper会自动地意识到运行时足够大以进行宏基准测试,然后只进行一次迭代.
现在,我试图通过使用以下方式来模拟这个:
@Macrobenchmark
public int macroBenchmark() { ... }
public int timeMicroBenchmark(int reps) {
int ret = 0;
for (int i = 0; i < reps; i++) {
ret += macroBenchmark();
}
}
在两种方案中共享基准测试代码.另一个代码是使用
@Macrobenchmark
public int macroBenchmark() {
return timeMicroBenchmark(1);
}
public int timeMicroBenchmark(int reps) { ... }
两个"适配器"中哪一个更受欢迎？任何其他提示从微观一直到宏一致的基准测试？
鉴于卡尺WebUI当前不起作用,您使用什么来分析结果？我目前正在使用一个小的python脚本来处理JSON结果并报告加权方法.事实上,我喜欢旧文本报告比Web UI更好.
哦,有没有办法让Caliper在基准测试循环中发生Hotspot编译时重新运行基准测试？现在它记录了一个错误,但也许它可以重新启动那部分基准测试？
我有 100,000 个点，我想使用 ELKI 中的 OPTICS 算法进行聚类。对于这个点集，我有一个大约 50 亿个条目的上三角距离矩阵。在ELKI想要矩阵的格式中，大约需要100GB的内存。我想知道 ELKI 是否处理这种数据加载？任何人都可以确认您之前是否做过这项工作？
我必须使用Kotlin在Android上将字符串转换为double.
以下应该在Kotlin中有效,但不是(没有这样的方法):
var dbl = "1.0".toDouble()
以下Javaish方式也不起作用:
var dbl = Double.parseDouble("1.0")
显然,Android上的String类既没有Kotlin API,Double也没有通常的Java API？
是否有任何优雅的方式适用于Android与Kotlin？
现在,我正在使用它(这是有效的,但它很难看):
var dbl = java.lang.Double.parseDouble("1.0")
该项目是使用Android Studio新创建的,使用以下版本:
ext.kotlin_version = '1.1.51'
minSdkVersion 23
targetSdkVersion 26
我认为这是Android API和Kotlin API之间的一些不匹配.