Ruby: Tại sao Array.sort lại làm chậm đối tượng lớn?

Question

Một đồng nghiệp cần sắp xếp một mảng các đối tượng ActiveRecord trong ứng dụng Rails. Ông đã cố gắng rõ ràng Array.sort! nhưng nó dường như đáng ngạc nhiên chậm, lấy 32s cho một mảng của 3700 đối tượng. Vì vậy, trong trường hợp nó là những vật thể béo lớn làm chậm mọi thứ, anh ta reimplemented sắp xếp bằng cách sắp xếp một mảng các đối tượng nhỏ, sau đó sắp xếp lại mảng ban đầu của các đối tượng ActiveRecord để khớp - như được hiển thị trong mã bên dưới. Tada! Các loại bây giờ mất 700ms.

Điều đó thực sự làm tôi ngạc nhiên. Phương pháp sắp xếp của Ruby có kết thúc sao chép các đối tượng về địa điểm thay vì chỉ tham chiếu không? Anh ấy đang sử dụng Ruby 1.8.6/7.

def self.sort_events(events) 
    event_sorters = Array.new(events.length) {|i| EventSorter.new(i, events[i])} 
    event_sorters.sort! 
    event_sorters.collect {|es| events[es.index]} 
end 

private 

# Class used by sort_events 
class EventSorter 
    attr_reader :sqn 
    attr_reader :time 
    attr_reader :index 

    def initialize(index, event) 
    @index = index 
    @sqn = event.sqn 
    @time = event.time 
    end 

    def <=>(b) 
    @time != b.time ? @time <=> b.time : @sqn <=> b.sqn 
    end 
end 

Answer 1

sort chắc chắn không sao chép các đối tượng. Một sự khác biệt mà tôi có thể tưởng tượng giữa mã sử dụng EventSorter và mã mà không có nó (mà bạn không cung cấp, vì vậy tôi phải đoán) là EventSorter gọi event.sqn và event.time chính xác một lần và lưu trữ kết quả trong biến. Trong quá trình phân loại chỉ các biến cần phải được truy cập. Phiên bản gốc có lẽ được gọi là sqn và time mỗi lần chặn phân loại được gọi.

Nếu trường hợp này xảy ra, nó có thể được sửa bằng cách sử dụng sort_by thay vì sắp xếp. sort_by chỉ gọi khối một lần cho mỗi đối tượng và sau đó sử dụng kết quả được lưu trong bộ nhớ cache của khối để so sánh thêm.

Answer 2

Không có câu hỏi nào về câu trả lời như thế này tốt hơn mã nguồn ngôn ngữ thực tế. Mảng # sắp xếp! sử dụng sort_internal() được định nghĩa trong array.c:

sort_internal()

(Vâng, tôi biết đó là nguồn cho 1.8.4 nhưng tôi không thể tìm thấy những cái đúng 1.8.6 trực tuyến và khá chắc chắn này đã không thay đổi.)

Answer 3

Cũng giống như giải thích về những gì có thể xảy ra và làm thế nào để đối phó với nó ...

Sorting có xu hướng nhìn vào một yếu tố nhiều lần vì vậy một tra cứu tốn kém vào đối tượng hoặc cấu trúc sẽ trở nên rất tốn kém rất nhanh chóng .

Biến đổi Schwartzian thường được sử dụng khi sắp xếp mảng các đối tượng hoặc cấu trúc phức tạp. Ý tưởng cơ bản là tính toán trước một giá trị đơn giản phản ánh chính xác cấu trúc hoặc đối tượng lớn, sau đó sắp xếp các giá trị, sau đó sử dụng mảng được sắp xếp kết quả để tham chiếu đến thứ mà chúng xuất phát.

http://en.wikipedia.org/wiki/Schwartzian_transform