Dart - 对List对象列表属性值的快速搜索及模糊搜索
代码借鉴了简书作者南山伐木# 对List对象列表属性值的快速搜索 该文章是对Java代码编写的，但是由于我在flutter开发中也有类似需求，就将其代码改写为dart版本
引言
在处理不同数据结构的时候，我们往往需要一个统一、高效的搜索工具。在这篇文章中，我们将探讨如何使用Dart编写一个适应各种数据类型的搜索工具。
考虑这样一个场景：一个班的所有学生都已经加载到List<Student>列表中，现在我们需要根据学生的姓名和住址进行模糊搜索。因为数据已经在内存中，再回到数据库或网络上进行搜索显得不太理想。通常的做法是在查找关键字时，遍历整个列表进行逐个匹配，但如果在手机等设备上实时搜索，这样会产生大量的循环操作，效率不高。
传统做法
List<Student> students = [
Student("001", "小王", "天府大道一街"),
Student("002", "张大彪", "天府大道一街"),
Student("003", "张晓", "天府大道一街"),
Student("004", "老王", "天府大道一街")
];
List<Student> searchTraditional(String keyword) {
List<Student> result = [];
for (Student student in students) {
if (student.name.contains(keyword)) {
result.add(student);
}
}
return result;
}
print(searchTraditional("张"));
优点：
- 直观易懂。
缺点：
- 每次搜索都会遍历整个列表，导致效率较低。
- 不易扩展，若要加入其他搜索条件或字段，需要修改代码。
2. 使用FSearchTool的搜索方法：
List<Student> students = [
Student("001", "小王", "天府大道一街"),
Student("002", "张大彪", "天府大道一街"),
Student("003", "张晓", "天府大道一街"),
Student("004", "老王", "天府大道一街")
];
FSearchTool tool = FSearchTool(students, ['name']);
print(tool.searchTasks("张"));
优点：
- 不需要遍历整个列表，只需要检索一次生成的长字符串。
- 更加灵活，容易扩展到其他字段和数据结构。
- 代码更简洁，更容易维护。
缺点：
- 需要初次设置时做一些预处理。
虽然传统方法对于小数据集来说可能效果还不错，但当数据量增加时，FSearchTool的优越性就显现出来了。它提供了一种高效、灵活并且可扩展的搜索方式，特别适合在内存中的大量数据搜索。
为此，今天我想分享一种对于Dart中List列表更高效的搜索方法。
思路
- 数据源与搜索字段：首先，我们需要传入数据源
List，并指定要进行搜索的字段。接着，将这些字段的值拼接成一个长的字符串，并记下每个对象值的起始和结束位置。 - 正则表达式搜索：当进行搜索时，我们首先使用正则表达式在已保存的搜索字符串中查找关键字的位置。找到后，我们利用这些位置在索引数据数组中迅速定位到对应的对象索引。
- 以Dart为例，我们设计了
FSearchTool工具类，它可以处理不同的数据结构，包括原始数据类型、映射和对象。通过适配器模式，我们将各种数据统一为一个可搜索的接口，并构建一个大的搜索字符串和一个范围列表。当进行搜索时，我们可以利用正则表达式迅速定位到关键字，再通过范围列表找到对应的对象。
结合MapAdapter、PrimitiveAdapter和Range等辅助类，这个工具为Dart中的列表搜索提供了一种新的、高效的解决方案。
具体实现
// 定义一个可搜索的接口
abstract class Searchable {
dynamic getField(String fieldName);
}
// 为Map提供适配器实现
class MapAdapter implements Searchable {
final Map<String, dynamic> map;
MapAdapter(this.map);
@override
dynamic getField(String fieldName) {
return map[fieldName];
}
Map<String, dynamic> get value => map;
@override
String toString() {
return map.toString();
}
}
// 为基础数据类型提供适配器实现
class PrimitiveAdapter<T> implements Searchable {
final T value;
PrimitiveAdapter(this.value);
@override
dynamic getField(String fieldName) {
if (fieldName == 'value') {
return value.toString();
}
throw Exception('Invalid field name: $fieldName');
}
@override
String toString() {
return value.toString();
}
}
// 搜索工具类
class FSearchTool<T, S extends Searchable> {
final List<S> mSearchObjs;
final StringBuffer mKeyWordString = StringBuffer();
final List<Range> mRanges = [];
FSearchTool(List<S> objects, List<String> fields) : mSearchObjs = List.from(objects) {
init(fields);
}
// 初始化搜索对象并创建索引
void init(List<String> fields) {
mKeyWordString.clear();
for (var obj in mSearchObjs) {
final start = mKeyWordString.length;
mKeyWordString.write(getSearchKey(obj, fields));
final end = mKeyWordString.length;
mRanges.add(Range(start, end));
}
}
// 从Searchable对象中获取用于搜索的关键字
String getSearchKey(Searchable obj, List<String> fields) {
final searchKeys = StringBuffer();
for (String field in fields) {
final val = obj.getField(field);
searchKeys.write('$val ');
}
return searchKeys.toString().trim();
}
// 为Map列表提供特定搜索工具
static FSearchTool<Map<String, dynamic>, MapAdapter> forMapList(List<Map<String, dynamic>> list, List<String> fields) {
return FSearchTool(list.map((map) => MapAdapter(map)).toList(), fields);
}
// 为基础数据类型列表提供特定搜索工具
static FSearchTool<T, PrimitiveAdapter<T>> forPrimitiveList<T>(List<T> list) {
return FSearchTool(list.map((value) => PrimitiveAdapter(value)).toList(), ['value']);
}
// 执行搜索并返回匹配的结果
List<T> searchTasks(String keyWords) {
final searchedTasks = <T>{};
final searchIndexes = getSearchIndex(keyWords);
for (var index in searchIndexes) {
if (index != -1 && index < mRanges.length) {
final obj = mSearchObjs[index];
searchedTasks.add((obj as dynamic).value);
}
}
return searchedTasks.toList();
}
// 获取匹配关键字的索引位置
List<int> getSearchIndex(String keyWords) {
final pattern = RegExp(keyWords, caseSensitive: false);
final matches = pattern.allMatches(mKeyWordString.toString());
return matches.map((match) => _findRangeIndex(match.start)).toList();
}
// 找到字符位置所在的范围
int _findRangeIndex(int charAt) {
for (int i = 0; i < mRanges.length; i++) {
if (mRanges[i].contains(charAt)) return i;
}
return -1;
}
}
// 表示字符范围的类
class Range {
final int start;
final int end;
Range(this.start, this.end);
bool contains(int value) => start <= value && value < end;
}
// 学生类，实现Searchable接口
class Student implements Searchable {
final String id;
final String name;
final String address;
Student(this.id, this.name, this.address);
Student get value => this;
@override
dynamic getField(String fieldName) {
switch (fieldName) {
case 'id':
return id;
case 'name':
return name;
case 'address':
return address;
default:
throw Exception('Invalid field name: $fieldName');
}
}
@override
String toString() => 'Student(id: $id, name: $name, address: $address)';
}
// 测试示例
void main() {
List<Student> students = [];
students.add(Student("001", "小王", "天府大道一街"));
students.add(Student("002", "小王", "天府大道二街"));
students.add(Student("003", "小红", "天府大道三街"));
students.add(Student("004", "小明", "天府大道四街"));
students.add(Student("005", "小王", "天府大道五街"));
students.add(Student("006", "小王", "软件园南门"));
students.add(Student("007", "小张", "吉泰路"));
FSearchTool<Student, Student> tool = FSearchTool<Student, Student>(students, ['name', 'address']);
for (var student in tool.searchTasks("明")) {
print(student);
}
List<Map<String, dynamic>> objects = [
{'name': 'Alice', 'age': '25', 'city': 'Shanghai'},
{'name': 'Bob', 'age': '30', 'city': 'Beijing'},
{'name': 'Charlie', 'age': '35', 'city': 'Shenzhen'},
];
var tool1 = FSearchTool.forMapList(objects, ['name', 'age', 'city']);
print(tool1.searchTasks("Ali"));
List<String> objects1 = ['Shanghai','Beijing','Shenzhen'];
var tool2 = FSearchTool.forPrimitiveList(objects1);
print(tool2.searchTasks("Shang"));
List<int> numbers = [1, 2, 3, 4, 5];
var tool3 = FSearchTool.forPrimitiveList(numbers);
print(tool3.searchTasks("3"));
List<double> floats = [1.5, 2.5,2.3, 3.5, 4.5];
var tool4 = FSearchTool.forPrimitiveList(floats);
print(tool4.searchTasks("2"));
}
运行效果
[Student(id: 004, name: 小明, address: 天府大道四街)]
[{name: Alice, age: 25, city: Shanghai}]
[Shanghai]
[3]
[2.5, 2.3]