每条记录都有id，价格和数量。添加新记录时，如果id已经存在，新记录将替换旧记录，id在数据集中是唯一的。很多时候我需要获取排序数据(按价格)。就像数据集中的前 100 名或 25-50 名一样。好消息是，每次我需要排序数据都是从数据集开始的。(我尽可能使用Comparable CompareTo(Object o))。
我尝试将数据存储在：
-
当 id 相同时，数组列表替换元素或在末尾添加元素。在需要数据时对其进行排序。太慢了。
-
ArrayDeque 删除旧元素(如果存在)并添加新元素。在需要数据时对其进行排序。太慢了。
-
HashMap有助于唯一ID和替换现有id。排序时，我从HashMap中获取值并将它们排序为ArrayList。更快，但仍然不够。
-
树状图有助于处理唯一 ID，但无法按键对其进行排序。将值排序为数组列表。与HashMap相同。
-
SortedSet(TreeSet)删除旧元素(如果存在)并添加新元素。使用迭代器获取排序的元素。现在最快，但仍然不够。
我已经在这里和这里检查了 Java 集合 – 性能(时间复杂度)的操作。
如果有人有任何建议使用什么数据类型/排序或如何尽快做到这一点。
我为此需要一些时间，例如有 1 亿条记录更新(添加/替换)并根据要求排序。在 4Ghz 上的八核/四核(八线程 CPU)上不使用任何基准测试软件应该在 2,3 分钟左右。请记住，随着记录数量的增加，添加/替换和排序的时间会更长。
正如László van den Hoek所建议的那样，您应该考虑将数据实际存储在数据库中，该数据库可以处理大量数据，并且可以为数据编制索引以进行更快的排序查找。
但是，对于您自行开发的内存中数据"存储"，您应该维护一个用于按id查找的HashMap，以及一个用于排序访问的TreeSet。
您没有指定您使用的排序方式，因此下面我将假设您打算按price排序。
TreeSet要求元素是唯一的，因此要按price排序，您还需要按id进行二次排序，以使排序键唯一。额外的副作用：对具有相同price的记录进行一致的排序。
首先，我们完全定义您的Record类：
class Record implements Comparable<Record> {
private int id;
private double price;
private int quantity;
public Record(int id, double price, int quantity) {
this.id = id;
this.price = price;
this.quantity = quantity;
}
public Record(double price, int id) {
this.id = id;
this.price = price;
}
public int getId() {
return this.id;
}
public double getPrice() {
return this.price;
}
public int getQuantity() {
return this.quantity;
}
@Override
public int compareTo(Record that) {
int cmp = Double.compare(this.price, that.price);
if (cmp == 0)
cmp = Integer.compare(this.id, that.id);
return cmp;
}
@Override
public boolean equals(Object obj) {
if (! (obj instanceof Record))
return false;
Record that = (Record) obj;
return (this.id == that.id);
}
@Override
public int hashCode() {
return this.id;
}
}
备用构造函数是下面DataStore的方便帮助程序。
DataStore逻辑不需要equals和hashCode方法，但如果相等性定义明确，则实现它们始终是一个好主意。
现在我们实现DataStore类，它封装了同时具有HashMap和TreeSet的逻辑：
class DataStore {
private Map<Integer, Record> recordsById = new HashMap<>();
private TreeSet<Record> recordsByPrice = new TreeSet<>();
public Optional<Record> addOrReplace(Record newRecord) {
Record oldRecord = this.recordsById.put(newRecord.getId(), newRecord);
if (oldRecord != null)
this.recordsByPrice.remove(oldRecord);
this.recordsByPrice.add(newRecord);
return Optional.ofNullable(oldRecord);
}
public Optional<Record> remove(int id) {
Record oldRecord = this.recordsById.remove(id);
if (oldRecord != null)
this.recordsByPrice.remove(oldRecord);
return Optional.ofNullable(oldRecord);
}
public Optional<Record> getById(int id) {
return Optional.ofNullable(this.recordsById.get(id));
}
public NavigableSet<Record> getByPrice(double price) {
return this.recordsByPrice.subSet(new Record(price, Integer.MIN_VALUE), true,
new Record(price, Integer.MAX_VALUE), true);
}
public NavigableSet<Record> getByPriceRange(double fromPriceInclusive, double toPriceExclusive) {
return this.recordsByPrice.subSet(new Record(fromPriceInclusive, Integer.MIN_VALUE), true,
new Record(toPriceExclusive, Integer.MIN_VALUE), false);
}
}