问题标签 [in-place]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
ruby-on-rails - Rails 中富文本编辑的最佳选择是什么?
我想在表单上使用富文本编辑,以便管理员更改说明。这样做的最佳选择是什么?
[更清楚一点-管理员不是技术人员,但可能希望在不使用标记或尽可能少的标记的情况下控制某些格式。我希望他们能够使用具有一些格式控制的 RTE 编辑所有 AJAXy 内联,然后提交并能够在不更改页面的情况下查看最终用户的说明。
关于插件,我想知道哪些 Rich Test Editing 插件最适合在 Rails 中使用。最容易实现、最清晰的 API、最容易内联使用等...]
c++ - 有没有一种简单的方法来对 char* 的数组进行排序?C++
我char*
在一个文件中有一个数组。我工作的公司将数据存储在平面文件中。有时数据是排序的,但有时不是。我想对文件中的数据进行排序。
现在我可以从头开始编写代码来做到这一点。有没有更简单的方法?
当然,就地排序将是最好的选择。我正在处理大文件并且内存很小。但我会考虑所有选项。
所有字符串的长度相同。
这是一些示例数据:
这将表示长度为 28 的三个记录。应用程序知道长度。每条记录都以 CRLF ( \r\n
) 结尾,尽管这对于这种排序无关紧要。
algorithm - 就地基数排序
这是一篇长文。请多多包涵。归结起来,问题是:是否有可行的就地基数排序算法?
初步的
我有大量固定长度的小字符串,它们只使用我想要排序的字母“A”、“C”、“G”和“T”(是的,你猜对了:DNA )。
目前,我使用which 在STL的所有常见实现中std::sort
使用introsort。这工作得很好。但是,我相信基数排序非常适合我的问题集,并且在实践中应该工作得更好。
细节
我已经用一个非常幼稚的实现测试了这个假设,并且对于相对较小的输入(大约 10,000 个)这是正确的(嗯,至少快两倍以上)。但是,当问题规模变大(N > 5,000,000)时,运行时间会大大降低。
原因很明显:基数排序需要复制整个数据(实际上在我的幼稚实现中不止一次)。这意味着我已将 ~ 4 GiB 放入我的主内存中,这显然会影响性能。即使没有,我也负担不起使用这么多内存,因为问题的大小实际上变得更大了。
用例
理想情况下,该算法应适用于 2 到 100 之间的任何字符串长度,适用于 DNA 和 DNA5(允许额外的通配符“N”),甚至是具有IUPAC 歧义码的 DNA (产生 16 个不同的值)。但是,我意识到无法涵盖所有这些情况,因此我对获得的任何速度改进感到满意。代码可以动态决定分派到哪个算法。
研究
不幸的是,关于基数排序的维基百科文章毫无用处。关于就地变体的部分完全是垃圾。NIST-DADS 关于基数排序的部分几乎不存在。有一篇听起来很有前途的论文叫做Efficient Adaptive In-Place Radix Sorting,它描述了算法“MSL”。不幸的是,这篇论文也令人失望。
特别是有以下几点。
首先,该算法包含几个错误并且有很多无法解释的地方。特别是,它没有详细说明递归调用(我只是假设它增加或减少了一些指针来计算当前的移位和掩码值)。此外,它使用函数dest_group
并且dest_address
没有给出定义。我看不到如何有效地实现这些(也就是说,在 O(1) 中;至少dest_address
不是微不足道的)。
最后但同样重要的是,该算法通过将数组索引与输入数组中的元素交换来实现就地性。这显然只适用于数值数组。我需要在字符串上使用它。当然,我可以只是搞砸强类型并继续假设内存将允许我存储不属于它的索引。但这只有在我可以将字符串压缩到 32 位内存(假设为 32 位整数)时才有效。那只有 16 个字符(让我们暂时忽略 16 > log(5,000,000))。
其中一位作者的另一篇论文根本没有给出准确的描述,但它给出了 MSL 的运行时间是亚线性的,这完全是错误的。
回顾一下:是否有希望找到一个有效的参考实现,或者至少是一个很好的伪代码/描述一个适用于 DNA 字符串的就地基数排序?
java - 更新 java 映射条目
我面临一个似乎没有直接解决方案的问题。
我正在使用java.util.Map
,并且我想更新键值对中的值。
现在,我正在这样做:
那么有没有什么方法可以让我获得所需的Entry
对象而不必遍历整个对象Map
?或者有什么方法可以更新条目的值吗?有什么方法Map
吗setValue(String key, int val)
?
jrh
java - 为什么就地合并排序不稳定?
下面的实现是稳定的,因为它使用<=
而不是<
在标记为 XXX 的行。这也使它更有效率。有没有理由使用<
而不是<=
在这条线上?
python - 对列表的一部分进行就地排序
假设我们有一个列表:
现在, a.sort() 将对列表进行适当的排序。如果我们只想对列表的一部分进行排序,仍然在原地怎么办?在 C++ 中,我们可以这样写:
Python中有类似的方法吗?
algorithm - 如何掌握原地数组修改算法?
我正在准备软件工作面试,但在就地数组修改时遇到了麻烦。
例如,在 out-shuffle 问题中,您将数组的两半交错,这样1 2 3 4 5 6 7 8
就会变成1 5 2 6 3 7 4 8
. 这个问题要求一个恒定的内存解决方案(和线性时间,虽然我不确定这是否可能)。
首先我认为线性算法是微不足道的,但后来我无法解决。然后我确实找到了一个简单的O(n^2)
算法,但花了我很长时间。而且我仍然没有找到更快的解决方案。
我记得在解决 Bentley 的 Programming Pearls 第 2 列中的类似问题时也遇到了麻烦:
将数组向左旋转
i
位置(例如abcde
旋转 2 变为cdeab
),及时O(n)
且仅保留几个字节的额外空间。
有没有人有提示可以帮助我解决这些问题?
arrays - 如何使用归并排序算法就地排序?
我知道这个问题不太具体。
我想要的只是有人告诉我如何将普通的合并排序转换为就地合并排序(或具有恒定额外空间开销的合并排序)。
我所能找到的(在网上)只有页面说“它太复杂了”或“超出了本文的范围”。
唯一已知的就地合并方法(没有任何额外空间)太复杂而无法简化为实际程序。(取自这里)
即使它太复杂,如何使归并排序就地的基本概念是什么?
jquery - Replace entire HTML document in-place
I'm trying to avoid using a data URI because I do not want the generated document to be stored in the browser's history. Is it possible to replace the entire HTML document in-place?
I tried jQuery("html").html("<html>....</html>")
, but the style
information does not survive.
algorithm - 数组中两类元素的稳定分离
考虑以下问题。
我们得到一个属于两个类的元素数组:红色或蓝色。我们必须重新排列数组的元素,以便所有蓝色元素排在第一位(所有红色元素紧随其后)。必须以稳定的方式进行重新排列,这意味着必须保留蓝色元素的相对顺序(红色元素也是如此)。
是否有一种聪明的算法可以就地执行上述重新排列?
当然,非就地解决方案很简单。
一个明显的就地解决方案是将任何稳定的排序算法应用于数组。然而,在数组上使用成熟的排序算法直觉上感觉有点过头了,特别是考虑到我们只处理两类元素的事实。
任何想法都非常感谢。