Бинарный поиск ArrayBuffer
Итак, у меня есть ArrayBuffer[Signal], в котором каждый сигнал имеет временную метку (массив сортируется по этой временной метке). Я хочу выполнить бинарный поиск и вернуть Seq[Signal] сигналов, которые находятся внутри определенного диапазона. Теперь это делается с помощью линейного поиска, в основном потому, что я пришел из Java и новичок в Scala. Как лучше всего это сделать?
Вот код:
private def getSignalsFromCache(mapId: String, mac: String, startTime: Long, endTime: Long): Seq[Signal] = {
val signals = getCache(VehicleWithMap(mapId, mac))
val result: ArrayBuffer[Signal] = new ArrayBuffer[Signal]()
if (signals.isEmpty) {
return signals
}
var startIndex: Int = 0
if (startTime > signals.head.timestamp) {
while (startIndex < signals.size && signals(startIndex).timestamp < startTime) {
startIndex += 1
}
}
var finished: Boolean = false
var currentIndex = startIndex
while (!finished && currentIndex < signals.size) {
val timestamp = signals(currentIndex).timestamp
if (timestamp > endTime) {
finished = true
}
else {
result += signals(currentIndex)
}
currentIndex += 1
}
result
}
@LuisMiguelMejíaSuárez да, это так
Это кажется простым. Замените startIndex+=1 на startIndex+=half_the_unchecked_length_in_the_correct_direction(). Это просто вопрос бухгалтерии.
Ответы 3
Вы можете использовать Searching для выполнения бинарного поиска.
import scala.collection.Searching._
val signalWithLowerBoundTimestamp = ???
val signalWithUpperBoundTimestamp = ???
val lower = signals.search(signalWithLowerBoundTimestamp)(
Ordering.by(_.timestamp)).insertionPoint
// If the upper bound is an exact match, add one
// to make sure it's included in the slice.
val upper = signals.search(signalWithUpperBoundTimestamp)(
Ordering.by(_.timestamp)) match {
case Found(i) => i + 1
case InsertionPoint(i) => i
}
val result = signals.slice(lower, upper)
Ordering.by(_.timestamp) не разрешен IDE
Если есть несколько сигналов с отметкой времени нижней границы, этот метод может пропустить некоторые из них, потому что Searching.search не гарантирует возврат первого совпадающего результата. Вы можете исправить это, поэкспериментировав с порядком, но на данный момент становится проще и чище просто написать бинарный поиск.
@Guillem, вы можете сказать мне, какая ошибка произошла? Может быть, вам нужно импортировать Ordering?
@Matt Да, вы можете следовать бинарному поиску с линейным поиском ребер, но это ухудшит время выполнения, если будет много дубликатов. Я согласен с тем, что реализация бинарного поиска лучше, если дубликаты вызывают беспокойство.
@BrianMcCutchon Дело в том, что я очень новичок в Scala. Сигнал - это класс case, поэтому, когда я делаю signal.search(startTime)(Ordering.by(_.timestamp)) IDE не может разрешить, потому что не определен специальный порядок. Мой класс case такой: класс case Signal(ap: AccessPoint, timestamp: Long, rssi: Double, mac: String = ""). Как мне определить порядок и как с его помощью вызвать поиск метода? Спасибо, Брайан, ты классный!
Вы можете использовать dropWhile и takeWhile.
Таким образом, вы можете сохранить все изменения и итерации.
Примечание: Это по-прежнему линейно, но более функционально и более распространено в Скала.
private def getSignalsFromCache(mapId: String, mac: String, startTime: Long, endTime: Long): Seq[Signal] =
getCache(VehicleWithMap(mapId, mac)
.dropWhile(_.timestamp < startTime)
.takeWhile(_.timestamp <= endTime)
}
(не забудьте сначала протестировать его, возможно, вам придется немного поиграть с условиями).
Я не знаю scala, но вот бинарный поиск, с которым вы можете сравнить более функциональные ответы. Я не думаю, что в этом есть что-то постыдное. Обратите внимание, что нет смысла выполнять бинарный поиск по конечному индексу, поскольку вам все равно придется копировать элементы:
private def getSignalsFromCache(mapId: String, mac: String, startTime: Long, endTime: Long): Seq[Signal] = {
val signals = getCache(VehicleWithMap(mapId, mac))
var startIndex: Int = 0
var endIndex: Int = signals.size
while(startIndex<endIndex) {
var testIndex: int = startIndex + (endIndex-startIndex)/2
if (signals(testIndex).timestamp < startTime) {
startIndex = testIndex + 1
} else {
endIndex = testIndex
}
}
while(endIndex < signals.size && signals(endIndex).timestamp <= endTime) {
endIndex = endIndex + 1
}
signals.slice(startIndex, endIndex)
}
Обратите внимание, что я включил сигналы в конце с помощью timestamp == endTime, потому что это то, что вы сделали... хотя это делает интерфейс немного странным. Обычно такой метод должен быть написан для возврата сигналов с помощью startTime <= timeStamp < endTime, поэтому, возможно, вы захотите подумать об этом.
Насколько я понимаю, ArrayBuffer сортируется по возрастанию, верно?