Существует ли структура данных Java, которая является эффективно ArrayList с двойным indicies и встроенной интерполяцией?
Я ищу предварительно созданную структуру данных Java со следующими характеристиками:
Это должно посмотреть что-то как ArrayList, но должно позволить индексировать через двойную точность, а не целые числа. Обратите внимание, что это означает, что вероятно, что Вы будете видеть indicies, которые приводят в порядок не строку с исходными точками данных (т.е. просьба о значении, которое соответствует ключу "1.5").Править: Для ясности, на основе комментариев, я не надеюсь изменять реализацию ArrayList. Я ищу подобный интерфейс и опыт разработчика.
Как следствие возвращенное значение будет, вероятно, интерполировано. Например, если ключ 1.5, возвращенное значение могло бы быть средним числом значения в ключевых 1.0 и значения в ключевых 2.0.
Ключи будут отсортированы, но значения не обеспечены, чтобы монотонно увеличиться. На самом деле нет никакого обеспечения, что первая производная значений будет непрерывна (создание его бедные, в форме для определенных типов шлицов).
Код в свободном доступе только.
Для ясности я знаю, как записать такую вещь. На самом деле у нас уже есть реализация этого и некоторых связанных структур данных в унаследованном коде, который я хочу заменить из-за некоторой производительности и кодирующих проблем.
То, чего я стараюсь избегать, проводит много времени, прокручивая мое собственное решение, когда могла бы уже быть такая вещь в JDK, Apache палата общин или другая стандартная библиотека. Откровенно говоря, это - точно подход, который получил этот унаследованный код в ситуацию, что это находится в прямо сейчас....
Есть ли такая вещь там в библиотеке в свободном доступе?
3 ответа
Это огромное изменение по сравнению с ArrayList.
То же, что и ответ Иоахима выше, но я, вероятно, реализовал бы это как двоичное дерево, и когда я не нашел то, что искал, усредните значение следующего наименьшего и наибольшего значений, которое должно быть быстро перейти к.
Ваше описание того, что он должен быть «как ArrayList», вводит в заблуждение, поскольку то, что вы описали, является одномерным интерполятором и по сути не имеет ничего общего с список ArrayList. Вот почему вы получаете предложения для других структур данных, которые IMO отправляет вам по неправильному пути.
Я не знаю ни одного доступного в Java (и не мог найти ни одного в Google), но думаю, вам стоит взглянуть на GSL - Научную библиотеку GNU , которая включает ] сплайн-интерполятор . Это может быть немного тяжеловато для того, что вы ищете, поскольку это двухмерный интерполятор, но похоже, что вам следует искать что-то подобное, а не что-то вроде ArrayList.
Если вы хотите, чтобы он «выглядел как ArrayList», вы всегда можете заключить его в класс Java, у которого есть методы доступа, аналогичные интерфейсу List. Однако вы не сможете реализовать интерфейс, поскольку объявлены методы, принимающие целочисленные индексы.
Разрешение двойных значений в качестве индексов - это довольно большое изменение по сравнению с тем, что делает ArrayList .
Причина в том, что массив или список с double в качестве индексов почти по определению будет разреженным массивом , что означает, что он не имеет значения (или в зависимости от вашего определения : фиксированное известное значение) почти для всех возможных индексов, и только конечное число индексов имеет явное значение.
В Java SE нет готового класса, который бы все это поддерживал.
Лично я бы реализовал такую структуру данных как skip-list (или аналогичную структуру данных с быстрым поиском) кортежей (индекс, значение) с соответствующей интерполяцией.
Редактировать: На самом деле есть довольно хорошее соответствие для внутреннего хранилища (то есть все, кроме интерполяции): просто используйте NavigableMap , например TreeMap , чтобы сохранить отображение от индекса к значению.
При этом вы можете легко использовать потолокEntry () и (при необходимости) upperEntry () , чтобы получить ближайшее значение (я) к нужному индексу, а затем выполнить интерполяцию из них. .