Java. Сложность поиска O(1)

Question

Недавно пробовал устроиться на работу, дали тестовое задание, сделал все кроме сложности поиска за O(1). HR сказала, что решение основывается на построении индекса в памяти. Можете обьяснить, что это значит желательно с примером. Заранее спасибо!) Ссылка на гит с проектом:(https://github.com/venoman9867/testTask)

Answer 1

Никакой индекс не дает сложность O(1). Все же ваше решение не соответствует требованиям. Вы читаете весь файл целиком, хотя это прямо запрещено заданием, вам надо ознакомиться с принципами функционирования баз данных и тем, как в них устроены индексы. Но в любом случае, не думаю, что вы много потеряли: работодатели с "домашними заданиями" на собеседовании как правило так себе.

Чуть подробнее все же опишу, в какую сторону двигаться. Посмотрите, FileChannel.map() - это способ работать с memory-mapped файлами. Общая схема такая - предварително нужно построить таблицу в памяти, где для строк в файла CSV будут записаны смещения в файле по которым они расположены. Поиск в таблице занимает O(log(N)) и не требует операций чтения с диска. После этого достаточно прочитать запись из mmap по смещению.

Answer 2

Этот ответ не решает задачу поставленную на собеседовании. В частности он не решает проблемы:

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

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

Идея в том, чтобы в памяти хранить сразу HashMap, в которой ключи это поисковые строки, а значения ссылки на строки из таблицы. Так как вас строка представлена как String[], то это выглядело бы так (если бы можно было создать Set массивов):

Map<String, Set<String[]>> index = new HashMap<>();

Но так как Set<String[]> не будет работать, то нужно строку по другому хранить, например преобразовать массив в List<String>. Или альтернативный вариант, хранить просто номер строки по порядку в файле. В этом случае индекс будет выглядеть:

Map<String, Set<Integer>> index = new HashMap<>();

Вам нужно хранить такой индекс для каждого столбца, т.е. нужен List из таких структур.

При считывании строки из файла, нужно ее индексировать, т.е. добавлять для каждой колонки ссылку на такую строку в Set:

String[] stroka;
List<Map<String, Set<Integer>>> indices = new List<>();
List<List<String>> allLines = new ArrayList<>();
int lineNumber = 0;
while ((stroka = reader2.readNext()) != null) {
   List<String> line = Arrays.asList(stroka);
   if (indices.empty()) { // создаем пустые индексы
      for(int i = 0; i < line.size(); ++i) {
          indices.add(new HashMap<>()); 
      }      
   }
   // индексируем строку
   indexLine(lineNumber, line, indices);
   lineNumber++;
   
}

void indexLine(int lineNumber, List<String> line, List<Map<String, Set<Integer>>> indices) {
   for(int i = 0; i < line.size(); +i) {
       Set<Integer> lines = indices.get(i).getOrDefault(line.get(i), new HashSet<>());
       lines.add(lineNumber); 
   }
}

После этой процедуры можно искать полные совпадения: indices.get(columnNumber).get("строка поиска") вернет индексы всех строк в allLines, в которых в колонке columnNumber значение "строка поиска". Такой поиск использует поиск по индексу в ArrayList и поиск в HashMap - все это за O(1).

Чтоб искать по префиксу, нужно изменить indexLine, а именно добавлять в индекс значение не только для line.get(i), т.е. значение в колонке, а и для всех префиксов:

void indexLine(int lineNumber, List<String> line, List<Map<String, Set<Integer>>> indices) {
   for(int i = 0; i < line.size(); +i) {
       String value = line.get(i);
       for (int j = 1; j < value.getLength(); ++j) {
           String prefix = value.substring(0, j);
           Set<Integer> lines = indices.get(i).getOrDefault(prefix, new HashSet<>());
           lines.add(lineNumber); 
       }
   }
}

Для решения проблем с загрузкой данных в память, нужно изменить структуру индекса. Вместо номера строки в массиве в памяти, нужно хранить смещение строки относительно начала файла.

Что касается размеров индекса, то вполне возможно, что он будет слишком большим, и нужно использовать другую структуру данных, которая будет оптимизирована по размеру, но будет давать время поиска не O(1), а O(log(n)).

БЛОГ НА HUSL

Java. Сложность поиска O(1)

Ответы (2 шт):