主页 / 问题 / 1411378
Accepted
Venoman9867
Asked:2022-07-19 01:58:43 +0800 CST2022-07-19 01:58:43 +0800 CST

爪哇。搜索复杂度 O(1)

  • 772

在此处输入图像描述最近我试图找到一份工作，我被分配了一个测试任务，除了搜索 O(1) 的复杂性之外，我什么都做了。HR 表示，该解决方案基于构建内存索引。你能用一个例子解释一下这意味着什么。在此先感谢！）链接到带有项目的git：（https://github.com/venoman9867/testTask）

java

2 个回答

  1. Best Answer

    没有索引给出复杂性O(1)。您的解决方案仍然不符合要求。您正在阅读整个文件，尽管工作明确禁止这样做，但您需要熟悉数据库的运行原理以及索引在其中的排列方式。但无论如何，我认为你并没有失去太多：接受“家庭作业”面试的雇主往往马马虎虎。

    然而，更详细一点，我将描述移动的方向。看，FileChannel.map()这是一种处理memory-mapped文件的方法。一般方案如下——首先你需要在内存中建立一个表，对于文件中的行，CSV将记录它们所在文件中的偏移量。表查找需要O(log(N)) 并且不需要磁盘读取。之后，通过偏移量从 mmap 读取条目就足够了。

    • 4

  2. 这个答案并不能解决面试中提出的问题。特别是，它不能解决问题：

    1. 不需要将所有文件数据加载到内存中
    2. 不优化索引，从某种意义上说，这种幼稚执行中的索引可能不适合内存，需要创建更优化的结构。

    答案回答了作者提出的问题，并描述了创建此类索引的原理，并在上面列出的几点上进行了修改，可以使用。我认为这将是有用的。

    想法是立即在内存中存储一​​个HashMap，其中键是搜索字符串，值是表中行的链接。由于您的字符串表示为String[]，它看起来像这样（如果可以创建一组数组）：

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

    但由于 Set<String[]> 不起作用，您需要以不同的方式存储字符串，例如将数组转换为List<String>. 或者，仅在文件中按顺序存储行号。在这种情况下，索引将如下所示：

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

    您需要为每一列存储这样一个索引，即 需要此类结构的列表。

    从文件中读取一行时，您需要对其进行索引，即 为每一列添加一个指向集合中这样一行的链接：

    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("строка поиска")的所有行的索引。这样的查找使用索引查找和查找- 都在 O(1) 中。allLinescolumnNumberArrayListHashMap

    要按前缀搜索，您需要更改indexLine，即在索引中添加一个值，而不仅仅是 for 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))。

    • 0

相关问题