Java 7下高效筛选Movie对象的优化方案及迭代器实现问询

定义的Movie类 #

class Movie{

    private String genre;
    private String title;
    private Date releaseDate;

    Movie(String genre, String title, Date releaseDate){
        this.genre = genre;
        this.title = title;
        this.releaseDate = releaseDate;
    }

    void setGenre(String genre){
        this.genre = genre;
    }
    void setTitle(String title){
        this.title = title;
    }
    void setReleaseDate(Date releaseDate){
        this.releaseDate = releaseDate;
    }
    String getGenre(){
        return genre; // 修正原代码拼写错误：retuen → return
    }
    String getTitle(){
        return title;
    }
    Date getReleaseDate(){
        return releaseDate;
    }
}

需求 #

• 创建目录存储所有Movie对象（时间复杂度无限制）
• 实现方法返回目录中指定类型且在指定时间段内的所有电影（该方法会被调用数千次，需尽可能优化）

现有实现 #

方法1：填充目录 #

void populateCatalog(List<Movie> catalog, String genre, String title, Date date){
        catalog.add(new Movie(genre, title, date));
    }

方法2：查询电影 #

boolean isWithinRange(Date date, Date beforeDate, Date afterDate){
        return !date.before(beforeDate) && !date.after(afterDate);
    }
    
    // timePeriod = "11/1/2020-11/2/2022"
    List<Movie> findGenreTimePeriod(List<Movie> catalog, String genre, String timePeriod){
        List<Movie> result = new ArrayList<>();

        int catalogSize = catalog.size();
        String dates[] = timePeriod.split("-");
        Date beforeDate = new Date(dates[0]);
        Date afterDate = new Date(dates[1]);

        for(int i=0; i<catalogSize; i++){
            Movie movie = catalog.get(i);
            String movieGenre = movie.getGenre();
            Date date = movie.getReleaseDate(); // 修正原代码错误：getDate() → getReleaseDate()
            if(movieGenre.equals(genre) && isWithinRange(date, beforeDate, afterDate)) // 去掉原代码末尾多余分号
                result.add(movie);
        }
        
        return result;
    }

当前实现需遍历整个目录，时间复杂度为O(N)。请问是否有更优时间复杂度的实现方案（例如修改方法1）？另外，能否返回迭代器类按需获取结果？

一、优化存储结构，降低查询时间复杂度 #

现有List存储方案每次查询都要全量遍历，效率低下。可以通过按类型分组+日期排序的方式，将查询时间复杂度降至O(logM + K)（M为该类型下的电影总数，K为符合条件的电影数量）：

1. 修改存储结构 #

将原来的List<Movie>替换为Map<String, SortedSet<Movie>>：

• Key为电影类型（genre）
• Value为对应类型下的电影集合，按releaseDate排序（用TreeSet实现）

两种排序实现方式

• 方式1：让Movie实现Comparable接口

class Movie implements Comparable<Movie>{
    // 原有属性、构造方法、get/set方法不变

    @Override
    public int compareTo(Movie other) {
        return this.releaseDate.compareTo(other.releaseDate);
    }
}

• 方式2：使用自定义比较器初始化TreeSet
  如果不想修改Movie类，填充目录时给TreeSet传入比较器：

Map<String, SortedSet<Movie>> genreMovieMap = new HashMap<>();
// 首次添加某类型电影时，初始化按日期排序的TreeSet
genreMovieMap.computeIfAbsent(genre, k -> new TreeSet<>(Comparator.comparing(Movie::getReleaseDate)));

2. 修改填充目录的方法 #

private Map<String, SortedSet<Movie>> genreMovieMap = new HashMap<>();

void populateCatalog(String genre, String title, Date date){
    Movie movie = new Movie(genre, title, date);
    // 按类型分组，不存在则创建新的SortedSet并添加电影
    genreMovieMap.computeIfAbsent(genre, k -> new TreeSet<>(Comparator.comparing(Movie::getReleaseDate)))
                .add(movie);
}

3. 优化查询方法 #

利用TreeSet的subSet方法快速获取日期范围内的电影：

List<Movie> findGenreTimePeriod(String genre, String timePeriod){
    List<Movie> result = new ArrayList<>();
    SortedSet<Movie> genreMovies = genreMovieMap.get(genre);
    if(genreMovies == null || genreMovies.isEmpty()){
        return result;
    }

    // 解析时间范围
    String dates[] = timePeriod.split("-");
    Date startDate = new Date(dates[0]);
    Date endDate = new Date(dates[1]);

    // 创建用于范围查询的"虚拟"Movie对象
    Movie startMarker = new Movie(genre, "", startDate);
    Movie endMarker = new Movie(genre, "", endDate);

    // 获取指定日期范围内的子集（包含边界值）
    SortedSet<Movie> filteredMovies = genreMovies.subSet(startMarker, true, endMarker, true);
    result.addAll(filteredMovies);
    return result;
}

二、返回迭代器按需获取结果 #

可以直接返回SortedSet的迭代器，或自定义迭代器封装过滤逻辑，避免一次性加载所有结果到内存：

1. 返回原生迭代器 #

Iterator<Movie> findGenreTimePeriodIterator(String genre, String timePeriod){
    SortedSet<Movie> genreMovies = genreMovieMap.get(genre);
    if(genreMovies == null || genreMovies.isEmpty()){
        return Collections.emptyIterator();
    }

    String dates[] = timePeriod.split("-");
    Date startDate = new Date(dates[0]);
    Date endDate = new Date(dates[1]);

    Movie startMarker = new Movie(genre, "", startDate);
    Movie endMarker = new Movie(genre, "", endDate);

    SortedSet<Movie> filteredMovies = genreMovies.subSet(startMarker, true, endMarker, true);
    return filteredMovies.iterator();
}

2. 自定义迭代器（适配无法修改存储结构的场景） #

如果不能改动原有存储结构，可以自定义迭代器实现按需过滤：

class MovieFilterIterator implements Iterator<Movie> {
    private final Iterator<Movie> iterator;
    private final String targetGenre;
    private final Date startDate;
    private final Date endDate;
    private Movie nextValidMovie;

    public MovieFilterIterator(Iterator<Movie> iterator, String targetGenre, Date startDate, Date endDate) {
        this.iterator = iterator;
        this.targetGenre = targetGenre;
        this.startDate = startDate;
        this.endDate = endDate;
        findNextValid();
    }

    private void findNextValid() {
        nextValidMovie = null;
        while (iterator.hasNext()) {
            Movie movie = iterator.next();
            if (targetGenre.equals(movie.getGenre()) 
                && !movie.getReleaseDate().before(startDate) 
                && !movie.getReleaseDate().after(endDate)) {
                nextValidMovie = movie;
                break;
            }
        }
    }

    @Override
    public boolean hasNext() {
        return nextValidMovie != null;
    }

    @Override
    public Movie next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        Movie current = nextValidMovie;
        findNextValid();
        return current;
    }
}

使用示例：

// catalog为原有List<Movie>对象
String dates[] = timePeriod.split("-");
Date startDate = new Date(dates[0]);
Date endDate = new Date(dates[1]);
Iterator<Movie> iterator = new MovieFilterIterator(catalog.iterator(), genre, startDate, endDate);

额外注意事项 #

1. 原代码中存在两处错误：getDate()应为getReleaseDate()、if语句末尾多余分号，已在示例中修正；
2. Java 8及以上建议使用LocalDate/LocalDateTime替代Date，线程更安全且API更友好；
3. 若需支持类型模糊匹配（如忽略大小写），可将Map的Key统一转成小写/大写，或使用Apache Commons Collections的CaseInsensitiveMap。

内容的提问来源于stack exchange，提问作者dark lion