как увеличить предел размера изменяемого списка в kotlin? - PullRequest
Новая
       108

как увеличить предел размера изменяемого списка в kotlin?

0 голосов
/ 14 июля 2020

Я пытался решить вопрос о мультимножестве (https://codeforces.com/contest/1354/problem/D) на codeforces, используя структуру данных дерева Фенвика. Я прошел образцы тестовых случаев, но после отправки получил ошибку ограничения памяти, тестовый пример упомянут ниже. (В основном тестовый пример:

1000000 1000000

1 ............. 1 // 10 ^ 6 раз

-1. ..........- 1 // 10 ^ 6 раз).

Я пробовал аналогичный тестовый пример в своей среде IDE и получил указанную ниже ошибку. (Как и в предыдущем случае, я предоставил следующий тестовый пример:

1000000 1

1 ............. 1 // 10 ^ 6 раз

-1

)

Исключение в потоке «main» java .lang.IndexOutOfBoundsException: индекс 524289 выходит за пределы длины 524289 в java .base / jdk .internal.util.Preconditions.outOfBounds (Предварительные условия. java: 64) в java .base / jdk.internal.util.Preconditions.outOfBoundsCheckIndex (Предварительные условия. java: 70) в java .base / jdk .internal.util.Preconditions.checkIndex (Предварительные условия. java: 248) в java .base / java .util.Objects.checkIndex (Objects. java: 373) в java .base / java .util.ArrayList.get (ArrayList. java: 426) в MultisetKt.main (multiset.kt: 47) в MultisetKt.main (multiset.kt)

Вот мой код : 

private fun readInt() = readLine()!!.split(" ").map { it.toInt() }

fun main() {
    var (n, q) = readInt()
    var list = readInt() //modify the list to store it from index 1
    var finalList = listOf(0) + list
    val query = readInt()
    var bit  = MutableList(n+1){0}

    fun update(i:Int, value:Int) {
        var index = i
        while(index < n){
            bit.set (index , bit[index] + value)
            index += (index and -index)
        }
    }
    fun rangefunc(i:Int): Int {
        var su = 0
        var index = i
        while(index > 0){
            su += bit[index]
            index -= (index and -index)
        }
        return su
    }
    fun find(x:Int):Int {
        var l = 1
        var r = n
        var ans = n
        var mid = 0
        while (l <= r) {
            mid = (l + r) / 2
            if (rangefunc(mid) >= x) {
                ans = mid
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        return ans
    }
    for (i in 1..n) {
        update(finalList[i], 1)
    }
    for (j in 0..q - 1) {
        if (query[j] > 0) {
            update(query[j], 1)
        } else {
            update(find(-query[j]), -1)
        }
    }
    if(rangefunc(n) == 0){
        println(0)
    }else{
        println(find(1))
    }
}

Я считаю, что это потому, что BITlist не может хранить 10 ^ 6 элементов, но не уверен. Пожалуйста, дайте мне знать, какие изменения мне следует внести в свой код, а также какие-либо дополнительные советы о том, как поступать в таких случаях в будущем.

Заранее спасибо :)

1 Ответ

2 голосов
/ 14 июля 2020

ArrayList может хранить более 2 миллиардов элементов (2 * 10 ^ 9). Это не твоя проблема. ArrayIndexOutOfBoundsException предназначен для попытки доступа к индексу ArrayList, который меньше нуля или больше или равен его размеру. Другими словами, индекс, которого он еще не содержит.

Там больше кода, чем у меня есть время на отладку. Но я бы начал со строки, на которую указывает трассировка стека, и посмотрел, как вы можете попытаться вызвать bit[index] с индексом, равным размеру ArrayList.

Чтобы ответить на ваш буквальный вопрос, вы можете явно использовать LinkedList в качестве своего типа MutableList, чтобы избежать ограничения размера, но он тяжелее и медленнее при доступе к элементам по индексу.

...