我正在实现一个算法,它将在CSV文件中搜索具有用户输入的前缀的列的字符串.在找到第一搜索结果之后,用户可以输入不同的前缀来执行第二搜索.列号只指定一次,并且在后续搜索期间只允许更改前缀.这将一直持续到用户输入"End".

Example of search:

File Data:

1, "Adam", "Computer Science"
2, "Liza", "Condensed Matter Physics"
3, "Bob", "Electrochemistry"
4, "Eva", "Material Culture"

Search parameters:

column: 3, prefix: "Co"

Search result:

1, "Adam", "Computer Science"
2, "Liza", "Condensed Matter Physics"

My algorithm must meet specific conditions:

  • 每次搜索时未读取文件中的所有行
  • 不将所有文件数据存储在内存中(不管它是字节数组还是包含所有文件数据的任何其他 struct )
  • 不编辑文件,也不创建其他文件(也不使用db)

事实证明,对于每个搜索操作,我们必须处理整个文件,因为文件中的任何字符串都可以具有指定的前缀.如何才能在不违反上述条件的情况下实现这一点?也许你知道在这种情况下可以使用的算法?

根据我的猜测,无论如何我们都需要处理整个文件.这意味着要么在每次搜索时读取文件中的所有行,要么将其完全存储在内存中,以便排除对文件的访问并使用此 struct .这两个选项都违反了问题的条件.

推荐答案

您可以构造一个索引,将指定列中的每个值映射到文件中的行偏移量,然后使用RandomAccessFile跳转到该行.

public static void main(String[] args) throws IOException {
    Scanner in = new Scanner(System.in);

    System.out.print("File: ");
    String path = in.nextLine();

    System.out.print("Column: ");
    int col = in.nextInt();
    in.nextLine();

    Map<Long, String> index = index(path, col);

    while (true) {
        System.out.print("Prefix: ");
        String prefix = in.nextLine();
        if (prefix.equals("end")) {
            return;
        }

        try (RandomAccessFile file = new RandomAccessFile(path, "r")) {
            for (Map.Entry<Long, String> line : index.entrySet()) {
                if (line.getValue().startsWith(prefix)) {
                    file.seek(line.getKey());
                    System.out.println(file.readLine());
                }
            }
        }
    }
}

private static Map<Long, String> index(String file, int col) throws IOException {
    Map<Long, String> index = new LinkedHashMap<>();
    long offset = 0;
    for (String line : Files.readAllLines(Paths.get(file))) {
        String value = line.split(",")[col - 1]
                .replaceAll("^ *\"|\" *$", "");
        index.put(offset, value);
        offset += line.length() + System.lineSeparator().length();
    }
    return index;
}

为简单起见,我冒昧地假定行中不包含嵌套引号或逗号,并且我们使用的是系统行分隔符.但如果有必要,你可以随意调整.

还要注意的是,与其说这个映射实际上是一个映射,不如说它是一个条目列表.该列被存储为值,以防它包含重复项.Map不是为前缀搜索而设计的,但它应该不会有太大影响,除非您正在处理大型文件.如有必要,您可以使用trie进行优化,但我将把它作为练习留给读者.

Java相关问答推荐

收听RDX中用户数据的变化

使用包私有构造函数强制子类Java类

如何在返回bigint []值的子查询中使用any?

@org.springframework.beans.factory.annotation.Autowired(required=true)-注入点有以下注释:-SpringBoot

有没有一种方法使保持活动设置专用于java.net.http.HttpClient的一个实例

将关键字与正文中的_Allowed匹配,但带有__Signing可选后缀

无法初始化JPA实体管理器工厂:无法确定为Java类型<;类>;推荐的JdbcType

Kotlin内联互操作:强制装箱

将java.util.Date转换为OffsetDateTime

Jenv-相同的Java版本,但带有前缀

使用OAuth 2.0资源服务器JWT时的授权(授权)问题

解析方法";javax/imageio/metadata/IIOMetadata.getAsTree(Ljava/lang/String;)Lorg/w3c/dom/Node时加载约束冲突

舰队运行配置Maven版本

从映射列表中检索所有键

使用迭代器遍历HashMap不会因IF条件而停止

如何在SWT菜单项文本中保留@字符

Java KeyListener不工作或被添加

OpenJDK20:JEP434:Foreign Function&;内存API(第二次预览)

在JSON上获取反斜杠

Maven创建带有特定类的Spring Boot jar和普通jar