Как получить корректно работающий indexOf после удаления префикса из Data?

Question

[redcircle]

Простой пример в Swift 4:

var data = Data([0, 1, 2, 3, 4, 5])
data.removeFirst(5)
let index5 = data.index(of: 5) // = 5 !!!
let count = data.count // = 1

Почему-то index5 равняется 5, хотя в data остаётся только 1 элемент.

Также, если сделать так:
var subdata = data.suffix(1)
let index5s = subdata.index(of: 5) // = 5
let countS = subdata.count // = 1
то результат такой же.

Как получить корректный индекс элемента при вызове indexOf?

Answer 1

[doublench21]

В описании метода index(of: )

Discussion
Attempting to remove more elements than exist in the collection triggers a runtime error.

Calling this method may invalidate all saved indices of this collection. Do not rely on a previously stored index value after altering a collection with any operation that can change its length.

А как этого избежать? Используя эти методы, никак. Используйте скажем filter:

import Foundation

var data = Data([0, 1, 2, 3, 4, 5])
var newData = data.filter{$0 < 5}
print(newData.index(of: 5) ?? "Ooops") // Ooops

Вообще избегайте всех метод, которые уменьшают длину массива в Data.

Comments

[redcircle]

У меня простая задача, поступают данные из URLSessionDataTask, я их добавляю к объекту Data методом append.
Если в Data находится символ перевода строки, я всё что до этого символа скармливаю дальше, и обрезаю этот объект Data спереди по этот символ. (То есть обычное построковое чтение).

Data.filter может и справится с задачей, но у него сложность O(n), а у removeFirst O(1).

[doublench21]

redcircle,

var linesOfData = [Data]()
repeat {
    let tmp: Data = getNewData()
    let index = tmp.index(of: ...)
    linesOfData.append(tmp.prefix(upTo: index))
// ...
} while(...)

func prefix(upTo end: Int) -> Data
Complexity: O(1)

[redcircle]

Это точно не будет работать. Как минимум ошибка в том, что в linesOfData добавляется только одна строка из данных полученных getNewData(); а их может быть потенциально и 1000.
Вторая ошибка в том, что теряется хвост после элемента index, который должен был бы приделан спереди к следующей порции данных.

[doublench21]

redcircle, я Вас не могу понять. Вы хотели сложность O(1) вы ёё получили. Там ничего не обрезается и индексы сохраняются, я для чего поставил ... . Делайте дальше что Вам нужно.

что в linesOfData добавляется только одна строка из данных полученных getNewData();

что за бред? Это был просто пример. Добвляйте в массив ровно так как вам надо.

[doublench21]

Суть в том что метод prefix(upTo: index) работает за O(1) и при этом ничего не режет и не трогает индексы. После вставки префикса, можете дальше работать с данными. Что не так та?

[doublench21]

Ну честно не вижу ничего сложного?
Для первой части ищите индекс tmp.index(of: ...) и находите первое вхождение "\n". Быстро за O(1) использую префикс prefix(upTo end: Int) сохраняем строку.
Дальше мы снова зная индекс юзаем suffix(from start: Int) от изначальной строки, которая тоже работает за O(1). и так далее

[redcircle]

Не так то, что данный метод не работает сразу по нескольким причинам, я показал почему.

В работающем коде точно необходимо склеивать куски данных.

Ещё раз, как это происходит: getNewData() предоставляет кусок данных, где в произвольном порядке присутствуют несколько разделителей (байт с кодом 10).
На выходе linesOfData должны содержать куски, которые находятся между разделителями (причём такие куски могут быть от разных вызовов getNewData() )

[doublench21]

redcircle, я ведь вам только что показал как это делается. Вы куда смотрите???
index(of: ...) для поиска 1го вхождения "\n"
prefix(upTo: ...) за 0(1) --> сохранили в массив строк 1ую строку
далее ищем index(of: ...) уже в suffix(from: ...) по тому же индексу что юзали для prefix(upTo: ...) и снова за 0(1) мы ищем уже новое вхождение и добавляем 2ую строку и так далее. Идея ясна? Ничего тут не теряется...

[doublench21]

redcircle,

var linesOfData = [Data]()
let tmp: Data = getNewData()

let index1 = tmp.index(of: ...)
linesOfData.append(tmp.prefix(upTo: index1)) /// 1

let index2 = tmp.suffix(from: index).index(of: ...)
linesOfData.append(tmp.suffix(from: index).prefix(upTo: index2)) /// 2

и так далее
можно всё это красиво обернуть в функцию

тут такой гемор только из-за того факта что вы хотите O(1)

ЭТО ЛИШЬ ПРИМЕР и эту идею можно красиво обернуть в функцию которая так пробежится по всей строке которую выплюнула функцию getNewData()

[redcircle]

Этот метод работает, хотя используется контринтуитивный let index2 = tmp.suffix(from: index).index(of: ...) , который возвращает позицию относительно начала tmp, а не tmp.suffix().

(Собственно про эту конструкцию и был вопрос топика)

Но это компенсируется тем, что prefix(upTo: index2) также работает от начала tmp, а не аргумента-подстроки.

В общем, всё это работает, но мозг надо перестраивать.

[doublench21]

redcircle, welcome. отблагодарите волшебной кнопкой.

[doublench21]

redcircle, тот код был чисто в голове как называется. И небольшие неполадки были связаны с тем, что я забыл +1 к индексу добавлять. Но в целом код верный. Вот полностью исправленный:

import Foundation

var linesOfData = [Data]()
let tmp: Data = Data([1, 2, 3, 5, 3, 2, 1, 5])

let index1 = tmp.index(of: 5) 
linesOfData.append(tmp.prefix(upTo: index1!)) 

let index2 = tmp.suffix(from: index1! + 1).index(of: 5)
linesOfData.append(tmp.suffix(from: index1! + 1).prefix(upTo: index2!)) 

print(linesOfData) // [3 bytes, 3 bytes]

[redcircle]

Вот в результате мой рабочий код:

private var buffer = Data()

func urlSession(_ session: URLSession, dataTask: URLSessionDataTask, didReceive data: Data) {
    buffer.append(data)
    
    var lines = buffer.split(separator: 10, maxSplits: Int.max, omittingEmptySubsequences: false)
    
    guard lines.count > 0 else {
        return
    }
    
    buffer = lines.popLast()!
    
    for line in lines {
        proceedLine(line)
    }
}

[doublench21]

redcircle, просили за O(1) ... ничего не понимаю.

[redcircle]

Это метод решения задачи описанной в первом моём комментарии:
"У меня простая задача, поступают данные из URLSessionDataTask, я их добавляю к объекту Data методом append.
Если в Data находится символ перевода строки, я всё что до этого символа скармливаю дальше, и обрезаю этот объект Data спереди по этот символ. (То есть обычное построковое чтение)."

Покажите, что это можно сделать быстрее.

(хотя тут конечно возможна мелкая оптимизация, не buffer.append(data) вызывать, а делать конкатенацию buffer и lines[0] и класть это в lines[0])

Разумеется, 0(1) имелось в виду это при сравнении быстродействия removeFirst (O(1)) и filter (O(n))
При решении же этой задачи целиком вы никогда не добьётесь O(1), так как у вас в любом случае будет цикл.

В общем, если напишите значительно более быстрый код — будет интересно.

[redcircle]

Вот лёгкая оптимизация (хотя я не знаю, как быстро работает Data.append, может там Apple написали так, что сами данные в действительности не копируются, тогда оптимизация не нужна)

private var buffer = Data()

func urlSession(_ session: URLSession, dataTask: URLSessionDataTask, didReceive data: Data) {

    var lines = data.split(separator: 10, maxSplits: Int.max, omittingEmptySubsequences: false)
    
    guard lines.count > 0 else {
        return
    }
    
    if !buffer.isEmpty {
         buffer.append(lines[0])
         lines[0] = buffer
    }

    buffer = lines.popLast()!
    
    for line in lines {
        proceedLine(line)
    }
}