BooleanArray大小大于2147483647。

Question

我想在 Kotlin 中实现 Atkin 筛法。我希望它能处理高达 2^32-1 的数字，因此筛子必须是一个以 UInt 为索引的数组。
我尝试像这样初始化筛子：

var sieve = BooleanArray(limit + 1u)

接着，我遇到了错误：

error: type mismatch: inferred type is UInt but Int was expected

那么，有没有办法使一个BooleanArray（或等效的）存储至少4294967295个值？

- some random nerd

---

这个回答解决了你的问题吗？如何使用Java创建非常大的布尔数组？ - Martin Zeitler

@shreyashshah 这是荒谬的，因为 Int 消耗的空间比 Boolean 多，而且通过 Int 进行寻址才是实际的问题。这应该类似于：BitArrayBin，它通过 Long 进行寻址。在 Kotlin 中进行自定义实现甚至可以通过 UInt 或 ULong 进行寻址。 - Martin Zeitler

使用二进制数组（更轻）代替整数数组。 - Nandostyle

只是一个想法，（顺便说一句，对于问题的背景我没有很多上下文），怎么样使用整数数组代替布尔值呢？其中每个元素定义了由布尔序列构成的十进制数。例如：如果您将布尔数组存储为：[1, 0, 1, 0]，则在整数数组中它等同于[10]。现在这样做的好处是，假设您的布尔数组是uint限制大小的5倍，使用整数数组，您将拥有包含5个整数的数组，其中每个元素都是表示'x'个布尔值（其中x是uint limit的大小）的十进制表示。 - ImShrey

@Nandostyle，你读了问题或我的评论吗？它的含义是 size: Int，这正是同样的问题，因此不会有任何区别，只会浪费 RAM。 - Martin Zeitler

Answer 1

最简单的方法可能是使用UInt作为大小，然后在内部映射2个常用的BooleanArray，它们使用Int进行寻址，尽管永远不会有负索引值（这似乎是设计缺陷-或者至少是优化不足）。这意味着，也可以使用带符号的Int来寻址所有内容。我的意思是，将负值在一个BooleanArray中映射到另一个正值的BooleanArray中。实际问题似乎是传递了一个带符号的Int，但只能使用正范围（50％）来寻址数据。可以使用absoluteValue，因为数组填充的方向并不重要。

- Martin Zeitler

---

我成功地修复了我的问题，只需使用更少的内存。我使用了一种算法，可以执行以下操作：var sieve = BooleanArray((limit / 2u).toInt())。但这将来可能会有用。谢谢！ - some random nerd