Как реализовать кеш с двоичным массивом в качестве ключа и двоичными массивами в качестве значений в Java

Question

У меня есть требование создать кеш Java, который будет содержать все города и аэропорты. Итак, если я запрашиваю кеш для определения местоположения, скажем, города, он должен вернуть все аэропорты в этом городе, и если я запрашиваю местоположение, которое является аэропортом, я должен вернуть этот аэропорт. Кроме того, каждое местоположение должно храниться в виде байтового массива в кеше (поскольку открытый интерфейс для запроса к кешу имеет byte [] в качестве параметра для местоположения) Другие соображения:

1. Поиск должен быть очень быстрым, максимально быстрым
2. Кеш загружается только один раз при запуске системы. Не меняется после получения загружен.
3. Поскольку он загружен только один раз, мы можем сохранить его в сортировке, если это ускоряет поиск.

Что у меня так далеко:

Подход 1

Создайте тонкий контейнер над байтом [], скажем, ByteWrapper. Поместите каждое местоположение (и аэропорты, и города) в качестве ключа на карте (TreeMap?). Используйте списки ByteWrapper (содержащие аэропорты, где это возможно) в качестве значений.

Подход 2

Создание многомерного массива byte [], который сортируется по местоположению. По сути, это карта. Затем используйте бинарный поиск, чтобы найти ключ и вернуть результаты.

Какой подход вы бы предложили? Пожалуйста, дайте мне знать, если у вас есть лучшие идеи Спасибо

Answer 1

Тот факт, что предоставляемый API основан на байтах [], не должен обязательно определять внутренние детали вашего кэша.

Второе наблюдение заключается в том, что это не проблема обобщенной структуры данных. И пространство всех аэропортов, и пространство всех городов конечны и хорошо известны. (Вы даже знаете размер).

Хеш-карты, деревья и т. Д. - это все алгоритмы, которые гарантируют определенные характеристики производительности в установленных пределах для общего использования .

Поскольку целостность данных не является проблемой («данные не меняются») и если соображения относительно пространства не являются критическими («как можно быстрее»), то почему бы и нет:

[Редактировать: этот бит каким-то образом теряется в вырезке и вставке: Вы индексируете (нумеруете) свои города и аэропорты, учитывая, что вы знаете эти наборы и они фактически статичны.]

// these need to get initialized on startup
// this initialization can be optimized.

Map<byte[], Long> airportIndexes = new HashMap<byte[], Long>(NUMBER_OF_AIRPORTS);
Map<byte[], Long> citiesIndexes = new HashMap<byte[], Long>(NUMBER_OF_CITIES);

Map<Long, byte[]> airports = new HashMap<Long, byte[]>(NUMBER_OF_AIRPORTS);
Map<Long, byte[]> cities = new HashMap<Long, byte[]>(NUMBER_OF_CITIES);

long[][] airportToCitiesMappings = new byte[NUMBER_OF_AIRPORTS][];
long[][] citiesToAirportMappings = new byte[NUMBER_OF_CITIES][];


public List<byte[]> getCitiesNearAirport(byte[] airportName) {
   Long[] cityIndexes = getCitiesByIdxNearAirport(airportName);
   List<byte[]> cities = new ArrayList<byte[]>(cityIndexes.length);
   for(Long cityIdx : cityIndexes) {
       cities.add(cities.get(cityIdx));
   }
   return cities;
}
public long[] getCitiesByIdxNearAirport(Long airportIdx) {
   return airportToCitiesMappings[airportIdx];
}
public long[] getCitiesNearAirport(byte[] airportName) {
   return getCitiesNearAirport(airportIndexes.get(airportName));
}
public long[] getCitiesNearAirport(Long airportIdx) {
   return airportToCitiesMappings[airportIdx];
}
// .. repeat above pattern for airports.

Это должно дать вам O (1) временные характеристики производительности. Существует значительная избыточность с точки зрения пространства.

Answer 2

ТАК, вот что я сделал до сих пор:

private static byte[][][] cache = null; // this is the actual cache
// this map has ByteArrayWrapper(a wrapper over byte[]) as key which
//  can be an airport or city and index of corresponding 
// airport/airports in byte[][][]cache as value
Map<ByteArrayWrapper, Integer> byteLocationIndexes = null;
/**
* This is how cache is queried. You can pass an airport or city as a location parameter
* It will fetch the corresponding airport/airports
*/
private byte[][] getAllAirportsForLocation(ByteArrayWrapper location) {
    byte[][] airports = null;
    airports = byteLocationIndexes.get(location)== null ? null : cache[byteLocationIndexes.get(location).intValue()];
    return airports;
}

Я измерял производительность, используя String в качестве ключа в indexMap (и используя String [] [] кеш) и ByteArrayWrapper в качестве ключа (и byte [] в качестве кеша). Улучшение на 15-20%, если я использую ByteArrayWrapper и byte [] [] [] кеш.

Что еще можно сделать, чтобы улучшить производительность? Поможет ли мне использовать другую реализацию Map? Поскольку кэш загружается только один раз и никогда не изменяется, его можно отсортировать. Большая часть времени уходит на поиск ключей в byteLocationIndexes, и это бутылочное горлышко. Я уже вычисляю hashCode во время создания объекта и сохраняю его как локальную переменную в ByteArrayWrapper.

Есть предложения?

Answer 3

Попробуйте приблизиться к 1, так как byte [] - это тип объекта, который вы можете использовать примерно так:

Map<byte[], List<byte[]>> cache = ... 

Вероятно, это самый простой подход, вам просто нужно выбрать реализацию для вашей карты. Вероятно, вы должны пойти с HashMap, потому что это самый простой ...

Как сказал Густав, использование HashMap не будет работать, поэтому вы можете вместо этого использовать TreeMap с данным компаратором:

Map<byte[], List<byte[]>> m = new TreeMap<byte[], List<byte[]>>(new Comparator<byte[]>() {
    public int compare(byte[] o1, byte[] o2) {
        int result = (o1.length < o2.length ? -1 : (o1.length == o2.length ? 0 : 1));
        int index = 0;
        while (result == 0 && index < o1.length) {
            result = (o1[index] < o2[index] ? -1 : (o1[index] == o2[index] ? 0 : 1));
            index++;
        }
        return result;
    }
});

Answer 4

Вам не нужны байтовые массивы, строки будут в порядке.

Как часто вы добавляете элементы в этот кеш? Я предполагаю, что это полностью статично, так как они не делают новые города или аэропорты каждый день.

Итак, вы можете использовать две MultiHashMaps, одну для города и другую для аэропортов. Оформить заказ Google Multimap http://google -collections.googlecode.com / svn / trunk / javadoc / com / google / common / collect / Multimap.html

Если вы случайно используете mySQL, вы можете использовать таблицу, основанную на Memory Storage Engine.

Многие базы данных могут закрепить таблицу в памяти, определенно Oracle, так что это еще один способ.