如何实现大型本地音乐库快速搜索？现有线性搜索性能不佳

1. 重复注册LiveData观察者：在afterTextChanged回调中每次调用observe，会导致多次注册观察者，引发重复UI更新和潜在内存泄漏。
2. MediaStore查询效率低下：每次搜索都直接查询MediaStore，且使用LIKE %query%的全表扫描逻辑，1万条数据量级下每次查询都会消耗大量IO资源。
3. 无任务防抖与取消：用户快速输入时会触发大量并行搜索任务，结果可能乱序返回，且无效任务会浪费CPU资源。
4. 内存消耗无控制：每次搜索都创建新列表并填充所有匹配项，无分页或懒加载逻辑，大结果集时内存占用过高。

一、先修正当前实现的基础错误 #

1. 调整LiveData观察逻辑 #

将观察者注册移到Activity初始化阶段，仅在输入变化时传递搜索关键词，避免重复注册：

// Activity初始化时注册一次观察者
searchViewModel.getResultList().observe(SearchHome.this, songsPOJOS -> {
    Log.i(TAG, "onChanged: searchViewModel->" + songsPOJOS.size());
    songAdapter.clearSongData(songsPOJOS);
});

layoutBinding.searchEdittextBox.addTextChangedListener(new TextWatcher() {
    @Override
    public void beforeTextChanged(CharSequence charSequence, int i, int i1, int i2) {}

    @Override
    public void onTextChanged(CharSequence charSequence, int i, int i1, int i2) {}

    @Override
    public void afterTextChanged(Editable editable) {
        // 仅传递关键词，不重复观察
        searchViewModel.updateSearchQuery(SearchHome.this, editable.toString());
    }
});

ViewModel对应调整：

private MutableLiveData<List<SongsPOJO>> setList = new MutableLiveData<>();
private String currentQuery = "";

// 对外暴露LiveData供Activity观察
public LiveData<List<SongsPOJO>> getResultList() {
    return setList;
}

// 更新搜索关键词并触发搜索
public void updateSearchQuery(Context context, String query) {
    if (query.equals(currentQuery)) return; // 避免重复搜索
    currentQuery = query;
    
    myapp = (App) context.getApplicationContext();
    service = myapp.getExecutorService();
    
    // 提交搜索任务（可扩展为取消旧任务）
    service.submit(() -> {
        List<SongsPOJO> filteredList = filteredData(context, query);
        setList.postValue(filteredList);
    });
}

2. 取消MediaStore重复查询 #

一次性预加载所有歌曲到内存，后续搜索直接操作内存数据：

// ViewModel中预加载全量歌曲
private List<SongsPOJO> allSongs = new ArrayList<>();

public void loadAllSongs(Context context) {
    service.submit(() -> {
        ContentResolver contentResolver = context.getContentResolver();
        String[] projection = {
                MediaStore.Audio.Media._ID,
                MediaStore.Audio.Media.TITLE
        };
        Cursor cursor = contentResolver.query(
                MediaStore.Audio.Media.EXTERNAL_CONTENT_URI,
                projection,
                null,
                null,
                MediaStore.Audio.Media.TITLE + " ASC"
        );
        if (cursor != null) {
            try {
                while (cursor.moveToNext()) {
                    SongsPOJO song = new SongsPOJO();
                    song.setSongName(cursor.getString(cursor.getColumnIndexOrThrow(MediaStore.Audio.Media.TITLE)));
                    song.setId(cursor.getLong(cursor.getColumnIndexOrThrow(MediaStore.Audio.Media._ID)));
                    allSongs.add(song);
                }
            } finally {
                cursor.close();
            }
        }
    });
}

二、高效搜索算法选型 #

1. 前缀搜索：Trie树（前缀树） #

适合实时输入场景，用户每输入一个字符都能快速返回前缀匹配结果，时间复杂度O(k)（k为关键词长度）：

• 预构建Trie树，将所有歌曲标题的前缀节点映射到对应歌曲
• 搜索时遍历Trie树，直接获取所有匹配前缀的歌曲

2. 任意子串搜索：倒排索引 #

构建子串到歌曲的映射，支持任意位置的关键词匹配，近似O(1)查询效率：

private Map<String, List<SongsPOJO>> invertedIndex = new HashMap<>();

// 构建倒排索引（可优化为仅保留长度>=2的子串减少内存）
private void buildInvertedIndex() {
    for (SongsPOJO song : allSongs) {
        String title = song.getSongName().toLowerCase();
        for (int i = 0; i < title.length(); i++) {
            for (int j = i+1; j <= title.length(); j++) {
                String sub = title.substring(i, j);
                invertedIndex.computeIfAbsent(sub, k -> new ArrayList<>()).add(song);
            }
        }
    }
}

// 搜索时直接查询索引
private List<SongsPOJO> searchFromIndex(String query) {
    if (query.isEmpty()) return allSongs;
    return invertedIndex.getOrDefault(query.toLowerCase(), new ArrayList<>());
}

3. 基础优化：二分查找（前缀匹配） #

如果仅需前缀匹配，可先对歌曲标题排序，用二分查找快速定位匹配起始位置，时间复杂度O(logn)：

// 假设allSongs已按标题排序
private List<SongsPOJO> searchWithBinary(String query) {
    if (query.isEmpty()) return allSongs;
    String lowerQuery = query.toLowerCase();
    List<SongsPOJO> results = new ArrayList<>();
    
    // 二分查找第一个前缀匹配的位置
    int left = 0, right = allSongs.size()-1;
    int startIndex = allSongs.size();
    while (left <= right) {
        int mid = (left + right)/2;
        String midTitle = allSongs.get(mid).getSongName().toLowerCase();
        if (midTitle.startsWith(lowerQuery)) {
            startIndex = mid;
            right = mid -1;
        } else if (midTitle.compareTo(lowerQuery) < 0) {
            left = mid +1;
        } else {
            right = mid -1;
        }
    }
    
    // 遍历后续所有匹配项
    for (int i = startIndex; i < allSongs.size(); i++) {
        String title = allSongs.get(i).getSongName().toLowerCase();
        if (title.startsWith(lowerQuery)) {
            results.add(allSongs.get(i));
        } else {
            break;
        }
    }
    return results;
}

三、其他体验优化 #

• 防抖处理：设置300ms延迟，等待用户输入完成后再触发搜索，减少无效请求：

private Handler searchHandler = new Handler(Looper.getMainLooper());
private Runnable searchRunnable;

@Override
public void afterTextChanged(Editable editable) {
    if (searchRunnable != null) {
        searchHandler.removeCallbacks(searchRunnable);
    }
    String query = editable.toString();
    searchRunnable = () -> searchViewModel.updateSearchQuery(SearchHome.this, query);
    searchHandler.postDelayed(searchRunnable, 300);
}

• 分页加载：使用Paging3库实现搜索结果分页，减少内存占用和UI渲染压力
• 结果缓存：对相同搜索关键词的结果进行缓存，重复搜索直接返回缓存数据

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