Swift: быстрый способ увеличить часть целочисленного массива
У меня есть массив возрастающих целых чисел, например: [0, 5, 23, …]. Массив большой (>500Т). Мне нужно найти все элементы, превышающие входное значение x, и добавить к каждому из них 1.
Я делаю следующее:
extension Array where Element == Int {
func incrementElements(largerThan x: Int) -> [Int] {
return self.map { $0 > x ? $0 + 1 : $0 }
}
}
Все идет нормально. Проблема в том, что эта операция должна быть очень быстрой, а моя — слишком медленной. Есть ли более быстрый способ сделать это?
Вы хотите увеличить/изменить массив на месте? Вы знаете, что .map также создает поверхностную копию входного массива?
Ответы 2
Во-первых, неправильное имя функции. Это имя, которое вы бы использовали для функции, изменяющей массив на месте. Вы возвращаете новый массив, поэтому вы должны написать, скажем,
пусть newarray = oldarray.byIncrementingElementsGreaterThan(200)
Во-вторых, невозможно за любые деньги купить компьютер, который будет работать с двумя массивами по 500 терабайт.
В-третьих, вы должны опубликовать, какую проблему вы хотите решить. Не так, как вы думаете, вы бы решили эту проблему.
«Во-вторых, невозможно купить за любые деньги компьютер, который будет работать с двумя массивами по 500 терабайт». - Файлы, отображаемые в памяти, в огромную сеть SAN...
Вы тестируете каждый элемент массива («Этот элемент больше, чем x? Хорошо, этот элемент больше, чем x? Хорошо, а как насчет этого элемента...?»). Это глупо. Если массив изначально отсортирован («массив возрастающих целых чисел»), вы уже знаете, что вам нужно увеличивать элементы только после последнего элемента «меньше или равного x».
Таким образом, необходимо пройти по массиву не более одного раза, и необходимо только выполнять любое тестирование достаточно долго, чтобы найти первый элемент, который больше x.
Мы можем наиболее эффективно перемещаться по массиву, указывая непосредственно на его смежное буферное хранилище. Итак, наш обход может выглядеть так:
// initial conditions
var array = [1, 2, 3, 4, 5, 6, 7] // or whatever
let k = 3 // or whatever; this is your `x`
// okay, here we go
array.withUnsafeMutableBufferPointer { buffer in
var index: Int?
for i in (buffer.startIndex..<buffer.endIndex) {
if buffer[i] > k {
index = i
break
}
}
if let index {
for i in (index..<buffer.endIndex) {
buffer[i] += 1
}
}
}
Мы могли бы сделать это еще быстрее, исключив первую часть обхода; вместо этого мы могли бы использовать двоичный поиск, чтобы найти первый элемент, который больше x. Но это оставлено в качестве упражнения для читателя.
Вы можете реализовать эту «обходную» часть с помощью zip(array.indices, array).first { index, element in element > k }?.index. В Swift-algorithms есть PartitioningIndex(where:) для двоичного поиска, так что вы можете вставить его вместо first(where:)
Не могли бы вы рассказать о преимуществах использования базового буфера в этом случае? Это для того, чтобы предотвратить копирование CoW или что-то в этом роде?
…500 триллионов элементов?