Как получить индекс элемента в SortedSet

Я реализую какую-то «матрицу записи», где индексы осей представляют собой (уникальные) ключи некоторого типа K (например, String). Эти ключи не нужно сортировать, но мне нужен порядок, поэтому я выбрал SortedSet.

Основная цель ключей (SortedSet) - найти фактический целочисленный индекс в базовом двумерном массиве данных (Seq[Seq[.]] или что-то еще). Но я не могу найти способы получить такую ​​функцию f(key: K): Int.

Вместо SortedSet[K] я мог бы использовать Map[K,Int], значения которого являются индексами, но я нахожу это излишним (и плохо типизированным).

Есть идеи?

Изменить

Метод Map что-то вроде, но в 2D:

val myKeys = // SortedSet("A", "B", "C")
val data   = // Array(13,42,117)
val keyIndices = myKeys.zipWithIndex.toMap

// get indices of "B", and lookup in data array
data(keyIndices("B"))

Я написал «неправильно типизированный» для решения карты, потому что тип не гарантирует, что индексы последовательны и начинаются с 0. В то время как позиция в упорядоченной последовательности есть.

Выбранное решение

Я выбрал ответ Неймана, потому что он лучше всего подходил для моей реальной проблемы. Но Cipcigan's и Verkerk'sответы больше подходят для названия.


scala sortedset
person Juh_    schedule 05.02.2016    source источник
comment
Почему карта избыточна и плохо типизирована? Если я понимаю ваш вопрос, вы говорите, что вам нужна функция K => Int.   -  person The Archetypal Paul    schedule 05.02.2016
comment
Не совсем понятно, что вы хотите сделать. Не могли бы вы предоставить код, как вы это используете? Как бы вы использовали ключ и как бы вы использовали индекс?   -  person thoredge    schedule 05.02.2016

Ответы (3)


arrow_upward
1
arrow_downward

Короткий ответ

ХранитьSet нельзя. Возможность получить элемент по индексу — это черта Seq.

scala> val data =scala.collection.SortedSet("a", "l", "m", "o", "n", "d")
data: scala.collection.SortedSet[String] = TreeSet(a, d, l, m, n, o)

scala> data(1)
<console>:12: error: type mismatch;
found   : Int(1)
required: String
   data(1)
        ^

scala> data("a")
res3: Boolean = true

В этом примере показано, что метод apply проверяет, содержится ли данный аргумент в наборе.

Я бы выбрал подход, который вы уже предложили, используя метод Map. Или преобразовать данные в Seq

scala> val indexedData = data.toVector
indexedData: Vector[String] = Vector(a, d, l, m, n, o)

scala> indexedData(2)
res9: String = l

scala> indexedData.indexOf("l")
res1: Int = 2
person Andreas Neumann    schedule 05.02.2016
comment
На самом деле мне нужно: key("l") => 3 чтобы я мог сделать value(rowKey("rowName"))(colKey("colName")), где значение - это базовый массив 2D-данных (вкратце) - person Juh_; 05.02.2016
comment
Добавлен пример использования indexOf. Это должно дать вам то, что вы хотите ;) - person Andreas Neumann; 05.02.2016
comment
indexOf - это то, что я ищу. Но почему он не определен для sortedSet!! :-( Думаю, indexOf равен O(n), а решение карты равно O(1), но это большой, неэффективный O(1) и плохо типизированный для моей проблемы. Думаю, я просто постараюсь не вызывать его тоже много - person Juh_; 05.02.2016
comment
и снова плохо напечатано, что вы имеете в виду здесь? С типами все в порядке, насколько я понимаю. У вас есть какое-то другое значение плохо напечатанного? - person The Archetypal Paul; 05.02.2016
comment
Я отредактировал вопрос, чтобы объяснить проблему с плохим типом. На самом деле это не имеет большого значения, потому что я использую их только в частном порядке. - person Juh_; 08.02.2016

arrow_upward
1
arrow_downward

Использование zipWithIndex должно сделать это:

def getIndex[T](xs: scala.collection.SortedSet[T], x:T): Option[Int] =
   xs.zipWithIndex.find(_._1 == x).map(_._2)

val a = scala.collection.SortedSet("a", "l", "m", "o", "n", "d")

getIndex(a, "a") // => Some(0)
getIndex(a, "m") // => Some(3)
getIndex(a, "x") // => None
person Flaviu Cipcigan    schedule 05.02.2016

arrow_upward
1
arrow_downward

Вы можете создать неявный класс, чтобы добавить функциональность в SortedSet.

implicit class SortedListFunctions[T](val s: SortedSet[T]){
    def getIndex(key: T): Int = {
        val notDropped = s.dropWhile(_ != key).size

        if(notDropped == 0) -1
        else s.size - notDropped
    }
}

С помощью неявного класса вы можете вызвать getIndex(..) a, если он существует в API.

 set.getIndex(key)

Обратите внимание, что это может быть не очень эффективным способом поиска чего-либо, что отсортировано. Если ваш SortedSet действительно большой, вы можете использовать бинарный поиск.

person Pim Verkerk    schedule 05.02.2016
comment
Хорошее решение, но (я знаю, что не должен так говорить в контексте scala) мне не нравится неявное: -/ - person Juh_; 05.02.2016
comment
Да, может быть, это слишком. - person Pim Verkerk; 05.02.2016