Двоичный поиск ArrayBuffer - PullRequest
Новая
       28

Двоичный поиск ArrayBuffer

0 голосов
/ 21 марта 2019

Итак, у меня есть ArrayBuffer [Signal], в котором каждый сигнал имеет временную метку (массив сортируется по этой временной метке).Я хочу выполнить бинарный поиск и вернуть Seq [Сигнал] сигналов, которые находятся в определенном диапазоне.Теперь это делается с помощью линейного поиска, в основном потому, что я из 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
}

Ответы [ 3 ]

0 голосов
/ 21 марта 2019

Вы можете использовать dropWhile & takeWhile.
Таким образом, вы можете сохранить все изменяемость и итерации.

Примечание: Это все еще линейно, но более функционально и более распространено в Scala . 

private def getSignalsFromCache(mapId: String, mac: String, startTime: Long, endTime: Long): Seq[Signal] =
  getCache(VehicleWithMap(mapId, mac)
    .dropWhile(_.timestamp < startTime)
    .takeWhile(_.timestamp <= endTime)
}

(сначала проверьте его, вам может понадобитьсянемного поиграть с условиями) .

0 голосов
/ 22 марта 2019

Я не знаю 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, поэтому, возможно, вы захотите подумать об изменении этого.

0 голосов
/ 21 марта 2019

Вы можете использовать Поиск, чтобы выполнить бинарный поиск.

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)
...