Giá trị N đầu tiên của một Bản đồ <K, V> được sắp xếp theo giá trị

Question

Tôi có một danh sách các Chuỗi. Tôi muốn đánh giá từng chuỗi dựa trên hàm trả về gấp đôi. Sau đó, tôi muốn 5 chuỗi đầu tiên, dựa trên giá trị được tính toán của chúng. Nếu có ít hơn 5, tôi muốn tất cả chúng (theo thứ tự). Giả sử các chuỗi là các hợp chất hóa học và hàm tính toán khối lượng. Hàm này tốn kém về mặt tính toán; Tôi cần phải đánh giá nó một lần cho mỗi chuỗi. (Tuy nhiên, tôi chỉ đang tạo nên dữ liệu ở đây.)

H2O => 18.5 
C12H11O22 => 109.1 
HeNe => 32.0 
H2SO4 => 54.37 
HCl => 19.11 
4FeO3 => 82.39 
Xe6 => 281.9 

Chương trình phải trả lại năm chuỗi đầu tiên được sắp xếp theo thứ tự theo giá trị tương ứng. Đối với dữ liệu mẫu này: H20, HCl, HeNe, H2SO4, 4FeO3. Trên thực tế, tôi không thực sự quan tâm đến thứ tự; Tôi chỉ cần năm cái thấp nhất theo thứ tự bất kỳ.

Tôi đã nghĩ về cách tôi làm điều này trong Perl. Đó chỉ là một vài dòng:

foreach $s (@str) { 
    $strmap{$s} = f($s); 
} 
@sorted = sort { $strmap{$a} <=> $strmap{$b} } keys %strmap; 
return @sorted[0, 4] 

Nhưng tôi cần làm điều đó trong Java. Và điều đó khiến tôi phát điên.

Trước tiên, tôi đã thử điền một số HashMap<String, Double>, sau đó sử dụng Collections.sort với trình so sánh tùy chỉnh, giống như phiên bản Perl. Nhưng phạm vi trên Comparator ngăn không cho nó đề cập đến HashMap để tra cứu các giá trị.

Sau đó, tôi đã thử một TreeMap<String, Double>, nhưng nó chỉ sắp xếp theo khóa và không có số tiền co giật có thể làm cho nó để đặt hàng các mục theo giá trị.

Vì vậy, tôi đã thử một TreeMap<Double, String>. Nó sẽ loại bỏ các mục với cùng một đôi. Tuy nhiên, khả năng có các chuỗi ánh xạ tới cùng một Đôi là thấp, vì vậy tôi đã nhấn tiếp. Việc thêm các mục vào TreeMap là không có vấn đề gì, nhưng tôi đã gặp phải các vấn đề cố gắng trích xuất các giá trị từ nó.

Bản đồ cây cung cấp phương thức được gọi là subMap, nhưng thông số của nó là các khóa phân định tập hợp con. Tôi không biết chúng là gì; Tôi chỉ muốn năm người đầu tiên trong số họ. Vì vậy, tôi đã thử sử dụng phương thức values để lấy tất cả các giá trị trong TreeMap, hy vọng chúng sẽ theo thứ tự. Sau đó, tôi chỉ có thể nhận được mười đầu tiên.

ArrayList<String> strs = (ArrayList<String>)(treemap.values()); 
return new ArrayList<String>(strs.subList(0, 5)); 

Không. Lỗi thời gian chạy: không thể truyền TreeMap $ Values ​​vào ArrayList.

List<String> strs = (List<String>)(treemap.values()); 
return new ArrayList<String>(strs.subList(0, 5)); 

Tương tự. Lỗi thời gian chạy cố gắng thực hiện dàn diễn viên. OK, hãy chỉ gán cho Bộ sưu tập ...

Collection<String> strs = treemap.values(); 
return new ArrayList<String>(strs.subList(0, 5)); 

Xin lỗi, subList không phải là một phương pháp thu thập.

Collection<String> strs = treemap.values(); 
ArrayList<String> a = new ArrayList<String>(strs); 
return new ArrayList<String>(a.subList(0, 5)); 

Cuối cùng, thứ gì đó hoạt động! Nhưng hai cấu trúc dữ liệu bổ sung chỉ để có được năm yếu tố đầu tiên? Và tôi không quá hoang dại về việc sử dụng Double làm chìa khóa cho TreeMap.

Có giải pháp nào tốt hơn không?

Answer 1

Tôi không nghĩ bạn sẽ nhỏ gọn hơn ba dòng ở trên, không phải trong Java. Ngoài ra, tôi có ấn tượng rằng Map là cấu trúc dữ liệu là lựa chọn sai ở nơi đầu tiên, vì bạn dường như không cần tra cứu chuỗi (UNLESS bạn muốn theo cách nào đó đối phó với nhiều lần xuất hiện của chuỗi, nhưng bạn đã không nói như vậy). Một phương pháp khác sẽ được tuyên bố có thể so sánh riêng lớp ghi dữ liệu của bạn:

private static class Record implements Comparable<Record> { 
    // public final fields ok for this small example 
    public final String string; 
    public final double value; 

    public Record(String string, double value) { 
     this.string = string; 
     this.value = value; 
    } 

    @Override 
    public int compareTo(Record other) { 
     // define sorting according to double fields 
     return Double.compare(value, other.value); 
    } 
} 

// provide size to avoid reallocations 
List<Record> records = new ArrayList<Record>(stringList.size()); 
for(String s : stringList) 
    records.add(new Record(s, calculateFitness(s)); 
Collections.sort(records); // sort according to compareTo method 
int max = Math.min(10, records.size()); // maximum index 
List<String> result = new ArrayList<String>(max); 
for(int i = 0; i < max; i++) 
    result.add(records.get(i).string); 
return result; 

này bây giờ là nhiều hơn nữa tiết hơn so với ba dòng trên (đây là Java, sau khi tất cả), mà còn bao gồm các mã mà sẽ được yêu cầu để chèn các cặp khóa/giá trị vào bản đồ.

Answer 2

Có gì đó giống như công việc sau cho bạn?

Lưu ý rằng tôi đã giả định rằng bạn không yêu cầu giá trị kép ngoài việc sắp xếp dữ liệu.

public static void main(String[] args) throws Exception { 
    List<String> data = new ArrayList<>(Arrays.asList("t", "h", "i", "s", "i", "s", "t", "e", "s", "t", "d", "a", "t", "a")); 

    Collections.sort(data, new Comparator<String>() { 
    @Override 
    public int compare(String o1, String o2) { 
     double o1Value = evaluate(o1); 
     double o2Value = evaluate(o2); 
     return Double.compare(o1Value, o2Value); 
    } 
    }); 

    List<String> result = data.subList(0, 10); // Note the end point is exclusive 

    for (String s : result) { 
    System.out.println(s); 
    } 
} 

private static double evaluate(String s) { 
    return s.codePointAt(0); // Nonsense, I know 
} 

Ví dụ này in:

a 
a 
d 
e 
h 
i 
i 
s 
s 
s 

Answer 3

Tại sao bạn không chỉ tạo ra một lớp kết hợp String, Double và chức năng mà không tính toán - một cái gì đó như:

public Thing implements Comparable<Thing> 
{ 
    private String s; 
    private Double d; 

    public Thing(String s) 
    { 
    this.s = s; 
    this.d = calculateDouble(s); 
    } 

    public String getString() 
    { 
    return this.s; 
    } 

    public Double getDouble() 
    { 
    return this.d; 
    } 

    public int compareTo(Thing other) 
    { 
    return getDouble().compareTo(other.getDouble()); 
    } 

    public Double calculateDouble(String s) 
    { 
    ... 
    } 
} 

Sau đó, tất cả những gì bạn cần là List<Thing>, Collections.sort và List.subList.