是否可以在线性时间内检查边界列表是否包含重复项? [英] Can I check whether a bounded list contains duplicates, in linear time?

问题描述

假设我有一个 Int 列表，其中已知元素是有界的，并且已知该列表不超过其范围，因此完全有可能不包含重复项.我如何最快地测试是否是这种情况?

我知道 nubOrd .它是非常快.我们可以通过列表，看看它是否变短了.但是 nubOrd 的效率仍然不是线性的.

我的想法是我们可以交换空间以节省时间.势必要，我们将分配一个与我们的范围一样宽的位字段，然后遍历列表，标记与列表元素的值相对应的条目.一旦我们尝试翻转已经为1的位，我们将返回False.它只需要(读+比较+写)*列表的长度.没有二进制搜索树，什么也没有.

在Haskell中尝试类似的构造是否合理?

解决方案

歧视包有一个线性时间 nub 可以使用.或线性时间 group 不需要将等效的元素相邻即可对其进行分组，因此您可以查看是否有任何一组的尺寸都不是1.

整个程序包基于使用基于区分"的算法而不是基于比较的算法，绕开了基于比较的排序(和联接等)上众所周知的界限.据我了解，该技术有点像基数排序，但可以推广到ADT./p>

Suppose I have an Int list where elements are known to be bounded and the list is known to be no longer than their range, so that it is entirely possible for it not to contain duplicates. How can I test most quickly whether it is the case?

I know of nubOrd. It is quite fast. We can pass our list through and see if it becomes shorter. But the efficiency of nubOrd is still not linear.

My idea is that we can trade space for time efficiency. Imperatively, we would allocate a bit field as wide as our range, and then traverse the list, marking the entries corresponding to the list elements' values. As soon as we try to flip a bit that is already 1, we return False. It only takes (read + compare + write) * length of the list. No binary search trees, no nothing.

Is it reasonable to attempt a similar construction in Haskell?

解决方案

The discrimination package has a linear time nub you can use. Or a linear time group that doesn't require the equivalent elements to be adjacent in order to group them, so you could see if any of the groups are not size 1.

The whole package is based on sidestepping the well known bounds on comparison-based sorts (and joins, and etc) by using algorithms based on "discrimination" rather than ones based on comparisons. As I understand it, the technique is somewhat like a radix sort, but generalised to ADTs.

这篇关于是否可以在线性时间内检查边界列表是否包含重复项?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！