Shellsort 是我不久前遇到的一种有趣的排序算法。最神奇的是，不同的空位序列可以显着提高算法的速度。我读了一些书(没有广泛阅读)，似乎 Tokuda 的序列被推荐用于实际应用。
另一个有趣的地方是比率2.20~2.25的序列往往效率更高。所以我做了一个小的搜索，考虑从 2.20 到 2.50 的比率序列，并尝试搜索哪个比率可以平均表现良好。我遇到了这个比率:2.48，在许多不同的试验中似乎平均表现良好。
然后，我想出了序列生成器:2.48k-1(我们称它为 248 序列)并尝试将其与 Tokuda 的序列进行比较。事实证明，它们的速度平均相等。 248序列倾向于使用稍微多一些的比较。
我知道我可能是错的，这就是为什么我来这里寻求更有经验的程序员的更多意见。如果您不明白问题，这里是我的简短问题:
248 Sequence: ROUNDUP ( 2.48(k-1) ) eg: 1, 3, 7, 16, 38, 94, 233, 577, 1431, 3549, 8801, 21826, ... Tokuda's Sequence ROUNDUP ( (9k - 4k) / (5 * 4k - 1) ) eg: 1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, 5985, 13467, ...
As @woolstar suggested me to also test with edge cases such as reversed and sorted. As expectedly, 248 sequence is faster in edge cases because 248 sequence gap is larger so it moves the inverse faster.
Shellsort Implementation
public static int compare = 0;
public static int swap = 0;
public static bool greaterthan(int a, int b) {
compare++;
return a > b;
}
public static int shellsort(int[] a, int[] gaps) {
// For keeping track of number of swap and comparison
compare = 0;
swap = 0;
int temp, gap, i, j;
// Finding a gap that is smaller than the length of the array
int gap_index = gaps.Length - 1;
while (gaps[gap_index] > a.Length) gap_index--;
while (gap_index >= 0) {
// h-sorting
gap = gaps[gap_index];
for (i = gap; i < a.Length; i++) {
temp = a[i];
for(j = i; (j >= gap) && (greaterthan(a[j - gap], temp)); j -= gap) {
a[j] = a[j - gap];
}
// swapping
a[j] = temp;
swap++;
}
gap_index--;
}
return compare;
}
最佳答案
根据 this reserach : (Ciura，Marcin(2001 年)“Shellsort 平均案例的最佳增量”。在 Freiwalds，Rusins。第 13 届国际计算理论基础研讨会论文集。伦敦:Springer-Verlag。第 106-117 页) 对于大小小于 108 的数组，shell 排序中的主要操作应该是比较操作，而不是交换操作:
Knuth’s discussion assumes that the running time can be approximated as 9×number of moves, while Figures 3 and 4 show that for each sequence the number of key comparisons is a better measure of the running time than the number of moves. The asymptotic ratio of 9 cycles per move is not too precise for N ≤ 108, and, if some hypothetical sequence makes Θ(NlogN) moves, it is never attained. Analogous plots for other computer architectures would lead to the same conclusion.
Treating moves as the dominant operation leads to mistaken conclusions about the optimal sequences.
在这种情况下，您的问题的答案是否定的:248 序列更糟糕，因为它使用了更多的比较。您还可以考虑将您的序列与本文中介绍的 Ciura 序列进行比较，因为这项研究似乎证明它比 Tokuda 的序列更好。
关于c# - Shellsort，2.48^(k-1) vs Tokuda 的序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21508595/
如何在ruby中调用C#dll？ 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL
我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha
给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最
C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.
假设我必须(小型到中型)阵列:tokens=["aaa","ccc","xxx","bbb","ccc","yyy","zzz"]template=["aaa","bbb","ccc"]如何确定tokens是否以相同的顺序包含template的所有条目？(请注意，在上面的示例中，应忽略第一个“ccc”，从而由于最后一个“ccc”而导致匹配。) 最佳答案 这适用于您的示例数据。tokens=["aaa","ccc","xxx","bbb","ccc","yyy","zzz"]template=["aaa","bbb","ccc"]po
首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟
我如何做Ruby方法"Flatten"RubyMethod在C#中。此方法将锯齿状数组展平为一维数组。例如:s=[1,2,3]#=>[1,2,3]t=[4,5,6,[7,8]]#=>[4,5,6,[7,8]]a=[s,t,9,10]#=>[[1,2,3],[4,5,6,[7,8]],9,10]a.flatten#=>[1,2,3,4,5,6,7,8,9,10 最佳答案 递归解决方案:IEnumerableFlatten(IEnumerablearray){foreach(variteminarray){if(itemisIEnume
我最近从C#转向了Ruby，我发现自己无法制作可折叠的标记代码区域。我只是想到做这种事情应该没问题:classExamplebegin#agroupofmethodsdefmethod1..enddefmethod2..endenddefmethod3..endend...但是这样做真的可以吗？method1和method2最终与method3是同一种东西吗？还是有一些我还没有见过的用于执行此操作的Ruby惯用语？ 最佳答案 正如其他人所说，这不会改变方法定义。但是，如果要标记方法组，为什么不使用Ruby语义来标记它们呢？您可以使用
什么是Linq聚合方法的ruby等价物。它的工作原理是这样的varfactorial=new[]{1,2,3,4,5}.Aggregate((acc,i)=>acc*i);每次将数组序列中的值传递给lambda时，变量acc都会累积。 最佳答案 这在数学以及几乎所有编程语言中通常称为折叠。它是更普遍的变形概念的一个实例。Ruby从Smalltalk中继承了这个特性的名称，它被称为inject:into:(像aCollectioninject:aStartValueinto:aBlock一样使用。)所以，在Ruby中，它称为inj
文章目录1、自相关函数ACF2、偏自相关函数PACF3、ARIMA(p,d,q)的阶数判断4、代码实现1、引入所需依赖2、数据读取与处理3、一阶差分与绘图4、ACF5、PACF1、自相关函数ACF自相关函数反映了同一序列在不同时序的取值之间的相关性。公式：ACF(k)=ρk=Cov(yt,yt−k)Var(yt)ACF(k)=\rho_{k}=\frac{Cov(y_{t},y_{t-k})}{Var(y_{t})}ACF(k)=ρk=Var(yt)Cov(yt,yt−k)其中分子用于求协方差矩阵，分母用于计算样本方差。求出的ACF值为[-1,1]。但对于一个平稳的AR模型，求出其滞