Tôi tò mò về thuật toán mặc định của Lua là sử dụng table.sort mặc định, chỉ vì nó chậm hơn so với một số thuật toán sắp xếp khác mà tôi đã gặp. Tôi cũng tò mò nếu Lua của table.sort được viết trong Engine trong C, hoặc nếu nó trong một thư viện trong Lua.Thuật toán nào sử dụng table.sort?
Thuật toán nào sử dụng table.sort?
Các comment in tablib.c (di chuyển lên một chút) khẳng định
/*
** {======================================================
** Quicksort
** (based on `Algorithms in MODULA-3', Robert Sedgewick;
** Addison-Wesley, 1993.)
** =======================================================
*/
Bạn có thể đọc mã nguồn tại liên kết tôi cung cấp.
Tôi cũng tò mò nếu Table.sort của Lua được viết trong Engine in C hoặc nếu nó nằm trong thư viện ở Lua.
Tại thời điểm này, tất cả các thư viện mà đến trực tiếp với Lua (io, table, math ...) được viết bằng C.
Bên trong, table.sort sử dụng quicksort, và nó được viết bằng C. Lưu ý quicksort không ổn định. Và một chút ngạc nhiên với tôi, Lua không sử dụng trực tiếp số qsort() của C.
Về hiệu suất, thật khó để biết vì có nhiều yếu tố khác nhau, ví dụ, ngôn ngữ và thuật toán nào bạn so sánh và loại dữ liệu nào đang được kiểm tra.
Sử dụng Lua, có một vài thuật toán tôi thấy nhanh hơn một chút so với mặc định. Nếu kích thước có liên quan nhỏ, loại cocktail và loại bong bóng thực sự nhanh hơn mặc định. Nếu kích thước lớn, thì LSD Radix sắp xếp, cùng với hai cái kia tôi nói, sẽ nhanh hơn. Tôi đang thử nghiệm nó với các loại dữ liệu khác nhau, chẳng hạn như các mảng đảo ngược, mảng ngẫu nhiên và thậm chí các mảng được sắp xếp chủ yếu, nhưng đối với mỗi thử nghiệm, sắp xếp mặc định vẫn chậm hơn một chút. – jocopa3
@ jocopa3 Theo tôi thấy, đây không phải là vấn đề của Lua, thay vì của quicksort. ví dụ: quicksort hoạt động kém trên các mảng được sắp xếp và các mảng được đảo ngược. Nếu bạn cần phải phân loại các vấn đề cụ thể, và sắp xếp mặc định của Lua không hoạt động đủ tốt, thì có thể viết một thuật toán sắp xếp cụ thể trong C chính bạn là một ý tưởng hay. –
@YuHao Từ khi nhìn vào nguồn được liên kết, qsort của Lua đang chọn giữa là trục xoay mọi lúc. Điều đó nên gần với trường hợp lý tưởng của qsort và nó không nên hoạt động kém. Tôi nghi ngờ tất cả những cuộc gọi API lua có thể là những gì làm chậm những thứ xuống nhưng không thể chắc chắn trừ khi nó được lược tả. – greatwolf
Lưu ý rằng LuaJIT đang xem xét chuyển sang [smoothsort] (http://en.wikipedia.org/wiki/Smoothsort) và một số chức năng thư viện của nó hiện được triển khai trong Lua bytecode (thực sự có lợi vì nó có thể JIT được biên dịch tốt hơn) –