В swift есть две функции для определения range в string.
myString.range(of: myString2)
myString.range(of: myString2, range: myRange)
Есть ли что-нибудь взамен что работает быстрее этих двух стандартных функций?
Вопрос о функциях .range(of:) и .range(of:, range:)
VYT
#3
Если это вообще возможно то нужно меньшее абсолютное время. Поясню почему возник вопрос. Может Вы предложите другое решение.
Есть массив of string и некоторые из этих strings имеют общие участки и их можно объединить. Задача состоит в том чтобы провести такое объединение и получить новый массив. Решение в лоб - это проверить каждый элемент этого массива с каждым другим элементом. И при такой проверке используем range(of: ). Соотвественно время будет пропорционально квадрату размера массива.
VYT
#5
Например есть массив
let array1 = ["TGGTCTGAATCTTCAGCGTTTGAATTCATGTATTTTTTTACGCTTCTAGTTTTACATTTAGTGGATGTGTTTGGAC",
"CAGTGATTTATGTCTATGTATGCTCGGTGAGCTGTCCAGAATCGACGATTTGAAATCCTAGGCTGGTTTACTGTTC",
"TCTACATCTTAATGGCCTGAAGTTGAGTAAATAAACAGTGTATTTTCATTTCCAGGTGACCCGTCTCTTGAAGACG",
"CGGATTTATCTCGGTTGTCTTTTGTTTAATTTCCACACCAACCTCCCACAAAATGGATCTTGCAAGTGATGATCAG",
"TTCATTCTCTACAAAAACGCAGATTGTAAACAAAACACGTGGGCTCACAAAGAAGGAGAAAGAGAAAAGGAGTATG",
"CTCGGGCTCTCTGAAGGAGCTCAAGAGCCTGCAGCAGATCGGAGACAAGAAGGCCAAACTCATCATGGGATGGAGA",
"CTGCTTTCCGTTGGAGGACTGAACGCTTATGATTTACTCACACTAAAGGATTGCGTGTGAAGACGTGCACACTTCT"]
Допустим в нем есть две string которые содержат идентичные substrings на их концах и их соотвественно можно объединить создав одну string. Задача состоит в том чтобы найти такие string которые можно объединить и записать объединенные в новый массив.
Это задача возникает при чтении генома. Сначала экспериментально “прочитывают” короткие участки, порядка 50-500 букв, и получают массив strings. Затем их объединяют, и в итоге получается одна или несколько очень больших strings.
Да и, размер исходного массива порядка миллиона элементов
VYT
#7
Замечательно (я на верном пути), именно так я и работает мой алгоритм на данный момент, чтобы уйти от решение в лоб. Хотя этот трик работает в 7 раз быстрее чем решение в лоб, тем не менее, для массива из 10 000 строк, это 80 секунд, а для 50 000 строк около 35 минут. Относительное время здесь все равно пропорционально квадрату от размера массива. Поскольку, для 50 000 в сравнении с 10 000 строк массив вырос в пять раз и объединенная строка строка тоже выросла в 5 раз, то и время на поиск с использованием range(of: ) выросло в 25 раз. На мой взгляд я уже все что можно сделал для этого подхода, поэтому и спросил насчет возможной замены range(of: ). Поскольку, только если уменьшить время на поиск range то можно уменьшить общее время. Сейчас если взять массив 500 000 строк то время вырастает до неприемлемого.
Есть вроде подход с использованием графов, если кто имел с ними дело может кто даст какой совет.
VYT
#10
Я использую несколько потоков. Ниже один из них для поиска тех строк которые могут быть объедены. Именно в этом блоке уходит основное время на поиск объединяемых строк. В итоге имею индексы строк и далее объединяю.
Функция searchForSubstringOfReadsInReadsString находит все range в строке, в ней соотвественно используется range(of: ).
let blockOperationSelect1 = BlockOperation
{
childAssemblingProgress0.totalUnitCount = Int64(subArray1Pre.count)
for each in subArray1Pre
{
if !(self.assembledReadsSelectionBlockOperation1 != nil) || self.assembledReadsSelectionBlockOperation1!.isCancelled
{
break
}
childAssemblingProgress0.completedUnitCount += 1
let leftMinimalPart = each[..<each.index(each.startIndex, offsetBy: minimalIdentity)]
let arrayOfIndexesLeft = leftMinimalPart.searchForSubstringOfReadsInReadsString(readsString: stringOfNumberedReads, substringOfRead: leftMinimalPart, length: minimalIdentity, endIndexOfReadsString: endIndexOfReadsString)
var setOfIndexes = Set<Int>()
if arrayOfIndexesLeft.count >= 2
{
for each2 in arrayOfIndexesLeft
{
if stringOfNumberedReads.index((each2?.lowerBound)!, offsetBy: 100, limitedBy: stringOfNumberedReads.endIndex) == nil
{
setOfIndexes.insert(numberOfReadsForPre - 1)
}
else
{
let part = stringOfNumberedReads[(each2?.lowerBound)!..<stringOfNumberedReads.index((each2?.lowerBound)!, offsetBy: 100)]
let arrayOfNumbers = part.components(separatedBy: CharacterSet.decimalDigits.inverted).filter {$0 != ""}
setOfIndexes.insert(Int(arrayOfNumbers[0])!)
}
}
}
let rightMinimalPart = each[each.index(each.endIndex, offsetBy: -minimalIdentity)..<each.endIndex]
let arrayOfIndexesRight = rightMinimalPart.searchForSubstringOfReadsInReadsString(readsString: stringOfNumberedReads, substringOfRead: rightMinimalPart, length: minimalIdentity, endIndexOfReadsString: endIndexOfReadsString)
if arrayOfIndexesRight.count >= 2
{
for each2 in arrayOfIndexesRight
{
if stringOfNumberedReads.index((each2?.lowerBound)!, offsetBy: 100, limitedBy: stringOfNumberedReads.endIndex) == nil
{
setOfIndexes.insert(numberOfReadsForPre - 1)
}
else
{
let part = stringOfNumberedReads[(each2?.lowerBound)!..<stringOfNumberedReads.index((each2?.lowerBound)!, offsetBy: 100)]
let arrayOfNumbers = part.components(separatedBy: CharacterSet.decimalDigits.inverted).filter {$0 != ""}
setOfIndexes.insert(Int(arrayOfNumbers[0])!)
}
}
}
if setOfIndexes.isEmpty != true
{
arrayOfCombinableReadsNumbers1.append(setOfIndexes)
}
}
}
queueSelection1.addOperation(blockOperationSelect1)
assembledReadsSelectionBlockOperation1 = blockOperationSelect1
VYT
#11
Насчет графов. Есть такое как De Bruijn Graphs. Читал что именно он используется для данной задачи. По ссылкам есть видео с пояснением о том что это такое, но пока не разобрался как это все прикрутить в swift к моей задаче.
paketik
#12
На это сообщение поступили жалобы от участников сообщества, поэтому оно временно скрыто.
VYT
#13
Из массива input мы должны получить одну строку в массиве output если две строки в input имеют общую подстроку (для примера сделал в них общую подстроку)
Например
let input = ["TGGTCTGAATCTTCAGCGTTTGAATTCATGTATTTTTTTACGCTTCTAGTTTTACATTTAGTGGATGTGTTTGGAC, TTTTTTTACGCTTCTAGTTTTACATTTAGTGGATGTGTTTGGACCGACGATTTGAAATCCTAGGCTGGTTTACTGTTC"]
var output = ["TGGTCTGAATCTTCAGCGTTTGAATTCATGTATTTTTTTACGCTTCTAGTTTTACATTTAGTGGATGTGTTTGGACCGACGATTTGAAATCCTAGGCTGGTTTACTGTTC"]
В моем случае я использую проверку наличия общих подстрок по концам.
В случае графов разбивают строки на короткие k-mers и затем строят граф что позже позволяет объединить k-mers и исходные строки. Но как и почему этот подход работает быстрее пока не понял.